# Count number of ways to paint a fence with N posts using K colors

A friend sent me this question, and I'd love somebody to review this and give his opinion.

Write an algorithm that counts the number of ways you can paint a fence with N posts using K colors such that no more than 2 adjacent fence posts are painted with the same color"

Is this algorithm accurate? Could it be implemented in a better way? Is there anything really un-pythonic that I did there? I hope I haven't made any embarrassing mistakes.

def find_combinations(n, colours):

combos_list = []

for i in range(1, n+1):

#Check if the combos_list is empty (happens when post number == 1)
if not combos_list:
#Add all variations for when there's only one post
for c in colours:
combos_list.append([c])
else:
new_combo_list = []
for combo in combos_list:
for c in colours:
#Check if last 2 posts are from the same colour, meaning we can't add another one
if not combo[len(combo) - 2:] == [c, c]:
combos_list = new_combo_list[:]

return combos_list, len(combos_list)

colours = ["black", "white"]
n = 4

print find_combinations(n, colours)


Example of input:

colours = ["a", "b"]
n = 3

Output:

• a, a, b
• a, b, a
• a, b, b
• b, a, a
• b, a, b
• b, b, a

Number of combos - 6

### 1. Code review

1. The question says, "Write an algorithm that counts the number of ways" but the program does not only do this: it also builds a list of the combinations. This means that the program is limited to values of $N$ and $K$ that are small enough that the list of combinations fits in the storage space of the computer. Whereas a program that did not have to produce this list could work for much larger values of $N$ and $K$, as we'll see in §3 below.

2. It's good practice to write a docstring for each function, describing what the function does, the arguments that it takes, and what it returns.

3. If a function returns a list, it does not also need to return the length of the list. If the caller needs that information, it can call len just as easily. So the function could just return combos_list.

4. In the line:

combos_list = new_combo_list[:]


it's unnecessary (and wasteful) to take a copy of new_combo_list. The new list can just be assigned to the old name, like this:

combos_list = new_combo_list

5. When a loop index (here i) is not used, it's conventional to name it _.

6. The code that's guarded by the line:

if not combos_list:


only runs once (on the first iteration of the loop), so it would be simpler to move it out of the loop, have one fewer iteration of the loop, and so avoid the if ... else .... Like this:

combos_list = []
for c in colours:
combos_list.append([c])
for _ in range(1, n):
new_combo_list = []
# etc.


combos_list = []
for c in colours:
combos_list.append([c])


use a list comprehension and write:

combos_list = [[c] for c in colours]

8. These lines:

combo_to_add = combo[:]


could be simplified to:

new_combo_list.append(combo + [c])

9. This condition:

if not combo[len(combo) - 2:] == [c, c]:


could be simplified to:

if combo[-2:] != [c, c]:


(since Python allows you index a list backwards from the end using negative numbers).

### 2. Revised code

def find_combinations(n, colours):
"""Return a list of combinations of n items from the sequence colours,
with the constraint that no colour appears three times in a row.

>>> [''.join(combo) for combo in find_combinations(3, 'ab')]
['aab', 'aba', 'abb', 'baa', 'bab', 'bba']

"""
combos = [[c] for c in colours]

for _ in range(1, n):
new_combos = []
for combo in combos:
for c in colours:
# Check that last two colours aren't both c.
if combo[-2:] != [c, c]:
new_combos.append(combo + [c])
combos = new_combos

return combos


Note the example code in the docstring. This can be run as a test case using the doctest module.

### 3. Let me count the ways

The question asked for "an algorithm that counts the number of ways", so here's how I'd go about that.

I'll start with some notation. Assume that $k$ is fixed. Then:

• $T(n)$ is the total number of ways to paint $n$ fenceposts with $k$ colours, subject to the constraint that no three adjacent posts are the same colour.

• $D(n)$ is the number of ways to paint $n$ fenceposts with $k$ colours such that the last two fenceposts are different colours (or $n < 2$).

• $S(n)$ is the number of ways to paint $n$ fenceposts with $k$ colours such that the last two fenceposts are the same colour.

And then the following recurrence relations are clear:

1. $D(n) = (k−1)(D(n−1) + S(n−1))$ for $n ≥ 2$
2. $S(n) = D(n−1)$ for $n ≥ 2$
3. $T(n) = D(n) + S(n)$

We can use (2) to eliminate $S$ (being careful about the bound on $n$ as we do so), getting the recurrences:

1. $D(n) = (k−1)(D(n−1) + D(n−2))$ for $n ≥ 3$
2. $T(n) = D(n) + D(n−1)$ for $n ≥ 2$

And then substitute (5) into (4), getting:

1. $D(n) = (k−1)(T(n−1))$ for $n ≥ 3$

and so:

1. $T(n) = (k−1)(T(n−1) + T(n−2))$ for $n ≥ 3$

Since the recurrence depends only on the last two values of the sequence, it's easy to program:

def triple_free_combinations(n, k):
"""Return the number of ways to choose n items (with k choices for
each item), subject to the constraint that no colour appears three
times in a row.

"""
if n == 0:
return 1
a, b = k, k * k
for _ in range(n - 1):
a, b = b, (k - 1) * (a + b)
return a


(You should recognize this as a very simple example of the tabular method, aka "dynamic programming".)

The effort that went into find_combinations is not wasted, because now we can use that function as source of test cases:

>>> from itertools import product
>>> all(triple_free_combinations(n, k)
...     == len(find_combinations(n, list(range(k))))
...     for n, k in product(range(1, 8), repeat=2))
True


Another useful source of test cases is the On-Line Encyclopedia of Integer Sequences. For example, when $k=2$ we have sequence A128588:

>>> [triple_free_combinations(i, 2) for i in range(16)]
[1, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974]


and similarly when $k=3,4,5,\ldots$ we have A121907, A123620, A123871, ....

Finally, note that triple_free_combinations is capable of computing values that are far beyond the reach of the original function:

>>> triple_free_combinations(40, 40)
472189463994618801762969606024644975976973566598588071193029590400

• Stop typing faster than me! – vnp Sep 22 '14 at 21:36
• Stop thinking and typing faster than me to both of you, Gareth and @vnp! Right when I had figured things out, you both have had your answers here for about five minutes. – Simon Forsberg Sep 22 '14 at 21:53

Even though you have some other answers already, I wanted to provide my re-write of the method (in Java, but should be easy to translate into Python), and also another little comment.

I quickly realized that combinatorics played a big role in your question, and I enjoyed the challenge very much. I got stuck thinking in one way, so then I started thinking in another, which helped.

The concept is the same as Gareth and vnp has suggested. One option for "pick same twice in a row" and one option for "pick different", this led me to the following recursive method:

static int fenceColors(int fence, int colors) {
if (fence <= 0) {
return 0;
}
if (fence <= 2) {
return (int)Math.pow(colors, fence);
}
int sum = 0;
sum += (colors - 1) * fenceColors(fence - 2, colors);
sum += (colors - 1) * fenceColors(fence - 1, colors);
return sum;
}


I hope this method shows the problem in a better way, and when you understand this method, you can probably find even better ways (like Gareth already has, apparently)

One of the first things I did was to modify these two lines:

colours = ["black", "white"]
n = 4


So that the user could input the values. A program where you need to change the source code to get what you want from it is not very useful at all times :) A simple input method helped me a lot in testing what the correct answers were. (I did not find any erroneous output by your program, well done on that bit)

So I changed those two lines above to:

n = int(raw_input("Number of fences: "))
num_colours = raw_input("Number of colors: ")
colours = range(1, int(num_colours)+1)


I found it a lot easier to work with numbers as the names of the colors really doesn't matter.

The chosen approach works, but results in a combinatorical explosion with a prohibitive complexity. You should consider a better algorithm.

Notice that the task requires only a number of ways to be found; not the actual ways. This means that a combos_list is not necessary at all (and it could grow very large indeed). We only need to track how many colourings end up in two particular colours. In fact, due to a colour symmetry we only need 2 values to track: number of ways ending with the same 2 colours (say, same), and number of ways ending in 2 different colours (say, different). Each same colouring can be extended in k-1 ways, always resulting in a "different" colourings; each different may be extended in one way resulting in "same", and in k-1 ways resulting in "different". This gives us a recurrence:

same, different = different, (same + different) * (k-1)


($O(n)$ - in fact, $O(log n)$ if implemented correctly) time, $O(1)$ space) and of course

total = same + different

• I'm not convinced by the big-O analysis here. The answer is between (K−1)^N and K^N, and so it has Θ(N log K) digits, so computing it must take at least that much space and time. – Gareth Rees Sep 22 '14 at 22:09
• @GarethRees: Usual disclaimer (about + and * being constant time) applies. Otherwise you are totally right. – vnp Sep 22 '14 at 22:13

(Revised version) It is unnecessary to write a search algorithm if you find an equation for the answer. If there is no restriction on adjacent posts of same color then

                  N
Number of ways = K


If no adjacent posts of same color are allowed then

                              (N - 1)
Number of ways = K * ( K - 1 )


The question actually allows maximum 2 adjacent posts of same color, which needs a different equation.

You can even avoid computation by storing this table of results (revised).

Colors K --->  2     3     4     5
Posts N
1        2     3     4     5
2        4     9    16    25
3        6    24    60   120
4       10    66   228   580
5       16   180   864  2800
6       34   492  3276 13520

• I'm not sure that I understand/agree with the first part of your answer. – Simon Forsberg Sep 24 '14 at 18:34
• About the second part of your answer, sure it can help to store the table of the results, but you need to calculate those results somehow in the first place, don't you? – Simon Forsberg Sep 24 '14 at 18:35
• The table need be calculated only once, using the equation. – cuddlyable3 Sep 25 '14 at 16:16
• If K=2, N=2, your equation gives 2, but the correct answer is 4. – Gareth Rees Sep 25 '14 at 16:17
• Additionally, if N=2, K=3, the answer should be 9 but this says 6. In fact, there's very few of those numbers that are correct. – Simon Forsberg Sep 25 '14 at 19:56