Painting fence problem [Part 1 - Non Optimized]

-> Day7/100

Q: Given a fence with n posts and k colors, find out the number of ways of painting the fence such that at most 2 adjacent posts have the same color.

I found 2 approaches to tackle this problem.

1: Do it recursively

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def findWaysUtil(postCount, arrayOfColors, string):
# Base case: There is a way with this combination string
if postCount == 0:
return 1

sum = 0

for i in range(len(arrayOfColors)):
# If current color is the same as the last color of the string
# check if string contains two consecutive colors already,
# because we can only have maximum 2 colors side by side
isThreeColorsInARow = len(
string) > 1 and string[-2:-1] == string[-1:] == str(
arrayOfColors[i])

if not isThreeColorsInARow:
sum += findWaysUtil(postCount - 1, arrayOfColors,
string + str(arrayOfColors[i]))

return sum


def findWays(postCount, numberOfColors):
# Check for invalid number of post
if postCount == 0:
return 0

# We will use number to represent colors
arrayOfColors = [i for i in range(numberOfColors)]

# We will pass down the combinaton of colors stored in a string
EMPTY_STRING = ''

return findWaysUtil(postCount, arrayOfColors, EMPTY_STRING)


print findWays(0, 3) # 0
print findWays(1, 3) # 3
print findWays(2, 3) # 9
print findWays(3, 3) # 24

2: Do it using pattern

We need to start with a base case of just 1 post. I am lazy to draw so we will use [ ] to represent a post. We should test all cases of n and k in numbers, so we will focus at the base cases of n, and keep k a constant variable.

Base case, test with 1 post where n = 1 and k colors.

1
2
3
4
5
[], red black

if n = 1 and k = 2,
[] can be [red] or [black]
numberOfWays = 2

Ok, now we test with 2 posts.

1
2
3
4
5
[][], red black

if n = 2 and k = 2
[][] can be [red][red], [black][black], [red][black], [black][red]
numberOfWays = 4

We split into 2 cases; check if [Post a] and [Post b] are the same or different color:

  1. Both posts are the same color: [red][red], [black][black]
    sameColorAdjacentPost
    = (k colors to choose from) x (1 way to follow previous post color)
    = k * 1 = k = 2 * 1 = 2

  2. Both posts are of different color: [red][black], [black][red]
    differentColorAdjacentPosts
    = (k colors to choose from) x (don’t choose the previous color means k - 1 ways)
    = k * (k - 1) = 2 * 1 = 2

numberOfWays = sameColorAdjacentPost + differentColorAdjacentPosts = k + k(k - 1)

Our last base case:
3 posts with n = 3

1
2
3
4
5
6
7
8
9
10
11
[][][], red black

if n = 3 and k
[][][] can be

[red][black][black]
[red][red][black]
[red][black][red]
[black][red][black]
[black][red][red]
[black][black][red]

differentColorAdjacentPosts
= [post a][post b][post c]
= [All the number of ways from previous n which has [post a][post b]][just choose color that is not in post b which is k - 1 ways]
= (k + k(k-1)) * (k-1 ways since it cannot be same as previous color only)

sameColorAdjacentPost
= [post a][post b][post c]
= [k colors][k - 1 colors][post c to follow post b so it has 1 way only]
= [red][black][black] = k * (k-1)

numberOfWays
= sameColorAdjacentPost + differentColorAdjacentPosts

Until here we are able to see a pattern forming. Thankfully.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
if n == 1:
numberOfWays = k

if n == 2:
sameColorAdjacentPost
= k * (1 way to be same as the post before)
= k

differentColorAdjacentPosts
= k * (k - 1 ways to be different from the post before)
= k(k - 1)

numberOfWays
= sameColorAdjacentPost + differentColorAdjacentPosts
= k + k(k - 1)

if n == 3:
sameColorAdjacentPost
= k * (k - 1) * (1 way to be same as the post before)
= k(k - 1) that looks like differentColorAdjacentPosts in n=2
# this is because we cannot have 3 of the same color in a row
# know the previous 2 colors are different, we can expand on it

differentColorAdjacentPosts =
= (all the number of ways in n=2) (k - 1)
= (k + k(k - 1))(k - 1)
= (numberOfWays in n=2)(k - 1)
# if you know all the ways for 2 posts, just * (k-1) to all to get different color from the post before

numberOfWays
= sameColorAdjacentPost + differentColorAdjacentPosts
= k(k - 1) + (k + k(k - 1))(k - 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
NUMBER_OF_WAY_0 = 0


def findWaysUtil(n, k):
if n <= 0:
return (NUMBER_OF_WAY_0, NUMBER_OF_WAY_0)

elif n == 1:
return (NUMBER_OF_WAY_0, k)

elif n == 2:
numberOfWaysCurrentPostAndPreviousPostToBeSameColor = k
numberOfWaysCurrentPostAndPreviousPostToBeDifferentColor = k * (k - 1)

else:
# for n >= 3, at every point of time, we are only looking at current post
# adding on top of the number of ways from (post - 1)

result = findWaysUtil(n - 1, k)
numberOfWaysCurrentPostAndPreviousPostToBeSameColor = result[0]
numberOfWaysCurrentPostAndPreviousPostToBeDifferentColor = result[1] * (
k - 1)

totalNumberOfWays = numberOfWaysCurrentPostAndPreviousPostToBeSameColor + numberOfWaysCurrentPostAndPreviousPostToBeDifferentColor

return (numberOfWaysCurrentPostAndPreviousPostToBeDifferentColor,
totalNumberOfWays)


def findWays(n, k):
if n <= 0:
return NUMBER_OF_WAY_0

# findWaysUtil returns a tuple (number of ways with different colors for last and second last post, total number of ways)
result = findWaysUtil(n, k)
totalNumberOfWays = result[1]

return totalNumberOfWays


print findWays(0, 3) # 0
print findWays(1, 3) # 3
print findWays(2, 3) # 9
print findWays(3, 3) # 24

Time / space complexity is terrible. Exponential.
We will use another post to optimize it. I promise.

p/s: Added a level on blackbox. linxea.github.io/blackbox