11
\$\begingroup\$

I have an interview coming up in the next few weeks, and I'm choosing to be interviewed in Python. I began programming in Python (it was about four years ago), so the syntax is natural to me, but I only learned about some useful tools of Python just this past year, when I took a class that recommended using it.

The Problem

We'll say there are \$N\$ houses, where \$N\$ is some integer. Each house can be painted in either Red, Green or Blue. The cost of coloring each house in each of the colors is different.

Figure out how to color each house so no two adjacent houses have the same color and the total cost of coloring all the houses is as low as possible.

My Solution

# Assume the prices of painting each house in a specific color is
# given by an array of size 3xN, giving the price to paint each house
# for each specific color
def find_cheap_house_painters(N, prices):
    # initialize the totals array
    totals = [[0 for i in range(N)] for j in range(3)]

    # the first houses are special case
    # we just paint them, that's it.
    for color in range(3):
        totals[color][0] = prices[color][0]

    # after that, dynamic programming does its magic.
    # at each step, add the price of painting this house
    # to the minimum of the total painting of the other two colors
    colors = set(range(3))
    for house in range(1, N):
        for color in colors:
            previous_totals = [totals[other_color][house-1] for other_color in (colors - {color})]
            totals[color][house] = prices[color][house] + min(previous_totals)

    # so now we have the totals to paint up to each house
    # we'll just work backwards to find the coloring of the houses.
    colorings = [3 for i in range(N)]
    colorings[-1] = min(colors, key=lambda x : totals[x][-1])
    for house in range(N-2, -1, -1):
        # take the index of the smaller option
        other_colors = colors - {colorings[house+1]}
        colorings[house] = min(other_colors, key=lambda x : totals[x][house])

    # convert to a human-readable string
    color_names = "RGB"
    house_colorings = "".join([color_names[colorings[house]] for house in range(N)])
    return house_colorings

My Questions

  • Are there specifically Pythonic structures, idioms, or "things" that I should be aware of that would help in this specific problem? If you're so inclined, I'm also looking for a list of generally useful and Pythonic "things". I became aware of list comprehension, any(), all(), and lambdas only recently, so tools at about that level are helpful.
  • I have yet to take my university's Programming Studio class, in which I'd learn a lot about writing readable, sensible, and maintainable code. How is my variable naming, commenting, etc? Again, if you're so inclined, if you want to provide a list of common errors and bad habits, I'd appreciate it.
  • Anything that strikes you. Just because I didn't specifically ask for it here doesn't mean it'll won't help me write better code.
\$\endgroup\$
7
\$\begingroup\$

I do have a lot of comments, but I find your solution pretty good. The algorithm makes sense, and your comments make it easy to follow.

The function is closer to a computation than a search, so I wouldn't call it find…. The N parameter is redundant, since it can be deduced from the dimensions of prices. On the other hand, color_names is hard-coded (and worse, 3 is hard-coded in several places); I would make it parameterized. The comment on the function should be a docstring.

I would prefer to return a list; the caller can join them into a string if desired.

I can understand crashing if there are 0 colors (because the problem would be ill-defined in that case), but the function should not crash if there are 0 houses.

The algorithm works by "walking up and down the street", evaluating the color choice at each house. Therefore, the code would be more natural if you transposed the matrices,1 such that the primary axis is the house number, and the secondary axis is the color. You can observe the benefit when writing the totals for the first house: your solution slices prices; my solution below just copies an element.

You initialize totals to a matrix of 0s and colorings to a list of 3s. I prefer to allocate empty lists using [None] * n.

You perform set operations on colors. I prefer to use list comprehensions with an if filter. I suspect that that the filtered list comprehension should be faster, though your set operations might be easier to understand.

def cheapest_house_coloring(prices, color_names='ROYGBIV'):
    """
    Finds the cheapest way to color a list of N houses using C colors such that
    no two consecutive houses have the same color.

    prices is an N-by-C array containing the price to paint the house n with
    color c.

    color_names is a sequence containing the names of the colors.
    """
    num_houses = len(prices)
    if not num_houses:
        return []
    num_colors = len(prices[0])

    totals = [None] * num_houses
    totals[0] = prices[0][:]

    # After the first house, dynamic programming does its magic.
    # At each step, add the price of painting this house
    # to the minimum of the total painting of the other colors.
    for house in range(1, num_houses):
        totals[house] = [
            prices[house][color] +
            min(totals[house - 1][c] for c in range(num_colors) if c != color)
            for color in range(num_colors)
        ]

    # Now we have the totals to paint up to each house.
    # We'll just work backwards to find the coloring of the houses.
    colorings = [None] * num_houses
    colorings[-1] = min(range(num_colors), key=lambda c: totals[-1][c])
    for house in range(num_houses - 2, -1, -1):
        # Take the index of the cheapest option (infinite cost
        # prohibits consecutive houses with the same color)
        colorings[house] = min(range(num_colors),
            key=lambda c: totals[house][c] if c != colorings[house + 1]
                else float('Infinity'))

    # Convert color indexes to names
    return [color_names[colorings[house]] for house in range(num_houses)]

1 If you need to transpose a matrix, use list(zip(*matrix)).

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.