deffindWaysUtil(postCount, arrayOfColors, string): # Base case: There is a way with this combination string if postCount == 0: return1

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) > 1and string[-2:-1] == string[-1:] == str( arrayOfColors[i])

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 = 1and 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 = 2and 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:

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

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

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)

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

deffindWays(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]