Find the number of ways to build a wall with 3x1 and 4.5x1 sized bricks.

brickwalls.py

# -*- coding: utf-8 -*-

"""Find the number of ways to build a wall with different sized bricks.

Command line usage:
    python brickwalls.py <width> <height>

Examples:
    python brickwalls.py 12 3
    python brickwalls.py 27 5

"""

import argparse
import copy
import sys


def is_staggered(sequence_1, sequence_2):
    """Check if two sequences are staggered.

    Note:
        Two sequences are staggered if none of their numbers line up,
        apart from their last numbers. The numbers represent the ends
        of bricks, so the idea is that two sequenecs of bricks are
        staggered if none of their inner bricks end in the same place.

        For instance, [3, 6, 9] and [4.5, 9] are staggered, because
        none of their inner bricks end in the same place. They look
        something like this:

            |_____|_____|_____|
            |________|________|

        But [4.5, 9] and [4.5, 9] are not staggered, because both
        have bricks that end at 4.5. They look like this:

            |________|________|
            |________|________|

    Args:

        sequence_1
            A list of numbers representing a sequence of bricks.

        sequence_2
            A list of numbers representing a sequence of bricks.

    Returns:
        ``True`` if the sequences are staggered, ``False`` if not.

    """
    result = True
    slice_1 = sequence_1[:-1]
    slice_2 = sequence_2[:-1]
    for item in slice_1:
        if item in slice_2:
            result = False
            break
    return result


def get_neighbors(all_sequences):
    """Get all possible neigbors for every sequence.

    Note:
        Each sequence represents a row of bricks, and neigbors
        are rows of bricks that can be stacked one on top of the
        other. Two rows can be neighbors only if they are staggered.

        This function will find all possible neighbors for each sequence.

    Args:

        all_sequences
            A list of sequences generated by ``get_sequences()``.

    Returns:
        A list of pairs of this form:
        (<sequence>, [<neighbor_1>, <neighbor_2>, ... ])
        Each pair identifies all possible neighbors of a sequence.

    """
    result = []
    for sequence in all_sequences:
        neighbors = []
        for x in all_sequences:
            if x != sequence:
                if is_staggered(x, sequence):
                    neighbors.append(x)
        record = (sequence, neighbors)
        result.append(record)
    return result


def lookup_neighbors(target, all_neighbors, all_sequences):
    """Lookup which neighbors a sequence can have.

    Args:

        target
            A sequence included in ``all_sequences``.
            This will find the corresponding entry in ``all_neighbors``.

        all_neighbors
            A list of pairs generated by ``get_neighbors()``.

        all_sequences
            A list of sequences generated by ``get_sequences()``.
    """
    result = all_sequences
    for sequence, neighbors in all_neighbors:
        if sequence == target:
            result = neighbors
            break
    return result


def get_sequences(tree, values, desired_total, solutions):
    """Generate all possible ways to sequence some values to add up to a total.

    Note:
        The values represent bricks. The sequences are lists of numbers
        that represent where each brick ends when lined up end to end. 
        For instance, [3, 6, 9] represents three bricks in a row,
        each of which is 3 units long (the first ends at 3, the next
        ends at 6, and the last ends at 9).

    Args:

        tree
            A dict used to keep track of the calculations. It has this form:
            {"running_total": _, "current_vtalue": _, "next_values": _, "sequence": _}

        values
            A list of possible values (e.g., [3, 4.5]).

        desired_total
            A number sequences of values should add up to.

        solutions
            A list where successful sequences can be stored.

    Returns:
        The solutions list.

    """
    # If we've hit the desired total exactly, then this particular sequence of values
    # is good. We can add it to the list of solutions.
    if tree["running_total"] == desired_total:
        solutions.append(tree["sequence"])

    # Otherwise, we need to look at adding each of the next possible values to see
    # if we can reach the desired total.
    else:
        for value in values:

            # If adding this next value doesn't go past the desired_total,
            # then it can be added to the sequence.
            new_total = tree["running_total"] + value
            if new_total <= desired_total:

                # Add the next value to the tree.
                new_sequence = tree["sequence"].copy()
                new_sequence.append(new_total)
                next_value = {
                    "running_total": new_total,
                    "current_value": value,
                    "next_values": [],
                    "sequence": new_sequence}
                tree["next_values"].append(next_value)

                # Now check that value for solutions (recursively).
                solutions = get_sequences(next_value, values, desired_total, solutions)

    return solutions


def get_walls(tree, all_sequences, all_neighbors, current_layer, height, wall_count):
    """Get the number of ways to build a wall out of sequences of bricks.

    Args:

        tree
            A dict to help keep track of computed walls. It has the form:
            {"next_sequences": [], "layer": _, "sequence": _}

        all_sequences
            A list of sequences generated by ``get_sequences()``.

        all_neighbors
            A list of pairs generated by ``get_neighbors()``.

        current_layer
            The current layer (an int) we're computing.

        height
            The desired height of the wall (an int representing the number of layers
            in the wall).

        wall_count
            A running tally (int) of the number of walls we've successfully built.

    Returns:
        The wall count.

    """
    indent = "--" * (current_layer + 1)

    print("{} Computing possible sequence for layer: {}".format(indent, current_layer))

    is_final_layer = current_layer == height
    print("{}{} Is this the final layer? {}".format(indent, indent, is_final_layer))

    if is_final_layer:
        print("{}{} No need to move on to another layer.".format(indent, indent))
    else:
        print("{}{} Computing next layer.".format(indent, indent))

        next_layer = current_layer + 1
        print("{}{} Next layer: {}".format(indent, indent, next_layer))

        is_next_layer_final = next_layer == height
        print("{}{} Is the next layer the final layer? {}".format(indent, indent, is_next_layer_final))

        current_sequence = tree["sequence"]
        print("{}{} Current sequence: {}".format(indent, indent, current_sequence))

        neighbors = lookup_neighbors(current_sequence, all_neighbors, all_sequences)
        print("{}{} Possible sequences for next layer:".format(indent, indent))
        print("{}{} {}".format(indent, indent, neighbors))
        print("")

        for neighbor in neighbors:

            new_neighbors = {"next_sequences": [], "layer": next_layer, "sequence": neighbor}
            print("{}{} Next sequence dict: {}".format(indent, indent, new_neighbors))

            tree["next_sequences"].append(new_neighbors)

            if is_next_layer_final:
                wall_count += 1
                print("{}{} Next layer is final. The next sequence makes a wall. Counting it.".format(indent, indent))
                print("{}{} Wall count: {}".format(indent, indent, wall_count))
                print("")

            else:
                print("{}{} Moving on to next layer.".format(indent, indent))
                print("")
                wall_count = get_walls(new_neighbors, all_sequences, all_neighbors, next_layer, height, wall_count)

    return wall_count


def main(width, height):
    """The main entry point into the program."""
    print("FINDING POSSIBLE WALLS FOR:")
    print("- width: {}".format(width))
    print("- height: {}".format(height))
    print("")

    # How wide are the different bricks?
    bricks = [3, 4.5]

    print("BRICK WIDTHS:")
    print("- {}".format(bricks))
    print("")

     # Find all sequences of bricks that add up to the stipulated width.
    all_sequences = []
    tree = {"running_total": 0, "current_value": None, "next_values": [], "sequence": []}
    all_sequences = get_sequences(tree, bricks, width, all_sequences)

    print("ALL SEQUENCES:")
    for sequence in all_sequences:
        print("- {}".format(sequence))
    print("")

    # Find all neighbors that each sequence can have.
    all_neighbors = get_neighbors(all_sequences)

    print("ALL NEIGHBORS:")
    for sequence, neighbors in all_neighbors:
        print("- {} can have neighbors:".format(sequence))
        for neighbor in neighbors:
            print("- - {}".format(neighbor))
    print("")

    # Build up a tree of all possible layers of all possible brick sequences.
    wall_count = 0
    current_layer = 0
    tree = {"layer": 0, "sequence": None, "next_sequences": []}
    wall_count = get_walls(tree, all_sequences, all_neighbors, current_layer, height, wall_count)

    # The tree-builder should have counted the walls it could build.
    print("")
    print("TOTAL WALL COUNT (TOTAL WAYS TO MAKE THE WALL): {}".format(wall_count))


if __name__ == "__main__":
    """Collect command line arguments and call ``main()``."""

    program_help = (
        "Find all ways to build a wall " +
        "from 3x1 and 4.5x1 sized bricks.")
    parser = argparse.ArgumentParser(description=program_help)

    parser.add_argument("width", type=float, help="Width of wall, e.g., 12")
    parser.add_argument("height", type=float, help="Height of wall, e.g., 5")

    args = parser.parse_args()
    print(args)

    main(args.width, args.height)