Python - Painting the Fence Problem

Python – Painting the Fence Problem

The Painting the Fence Problem is a popular dynamic programming challenge frequently asked in technical interviews. Given a fence with n posts and k different colors, the goal is to calculate the number of ways to paint the fence such that no more than two consecutive posts have the same color.

Problem Statement

Given two integers n (the number of fence posts) and k (the number of colors), determine the total number of ways to paint the fence such that no more than two adjacent posts are painted with the same color.

For instance, if n is 0 there are no posts to paint, and if n is 1 there are exactly k ways to paint that single post.

Sample Input and Output

Example 1:

</>

Copy

# Input:
n = 3, k = 2

# Calculation:
# For 2 posts:
#   - same = k = 2 (both posts painted the same color)
#   - diff = k * (k - 1) = 2 * 1 = 2 (posts painted in different colors)
# Total ways for 2 posts = same + diff = 2 + 2 = 4
#
# For 3 posts:
#   - new_same = diff (from previous calculation) = 2
#   - new_diff = (same + diff) * (k - 1) = (2 + 2) * 1 = 4
# Total ways for 3 posts = new_same + new_diff = 2 + 4 = 6

# Output:
6

Explanation: With 3 posts and 2 colors, there are 6 valid ways to paint the fence. The approach breaks down the problem into two scenarios for the second post (same or different color) and then uses these to determine the valid arrangements for the third post.

Example 2:

</>

Copy

# Input:
n = 4, k = 3

# Calculation:
# For 2 posts:
#   - same = k = 3
#   - diff = k * (k - 1) = 3 * 2 = 6
# Total ways for 2 posts = 3 + 6 = 9
#
# For 3 posts:
#   - new_same = diff from previous step = 6
#   - new_diff = (same + diff) * (k - 1) = (3 + 6) * 2 = 18
# Total ways for 3 posts = 6 + 18 = 24
#
# For 4 posts:
#   - new_same = diff from previous step = 18
#   - new_diff = (same + diff) * (k - 1) = (6 + 18) * 2 = 48
# Total ways for 4 posts = 18 + 48 = 66

# Output:
66

Explanation: With 4 posts and 3 colors, the dynamic programming approach computes 66 valid ways to paint the fence. The solution builds on the calculations from the previous posts and updates the counts iteratively to satisfy the condition that no more than two adjacent posts have the same color.

Solution Approach

We solve the problem using dynamic programming by considering two scenarios for painting each post:

same: The number of ways to paint the current post the same color as the previous post.
diff: The number of ways to paint the current post a different color from the previous post.

For the first post, there are k ways to paint it. For the second post, you have two choices: paint it the same as the first post (same = k) or a different color (diff = k * (k - 1)). For posts 3 through n, the recurrence relations are:

new_same = diff (from the previous post)

new_diff = (same + diff) * (k – 1)

The total number of ways for each post is the sum of the two scenarios: same + diff.

Python Program

</>

Copy

def painting_fence(n, k):
    """
    Compute the number of ways to paint a fence with n posts using k colors such that
    no more than two adjacent posts have the same color.
    
    Parameters:
    n (int): Number of fence posts.
    k (int): Number of colors.
    
    Returns:
    int: Total number of valid ways to paint the fence.
    """
    # Base cases
    if n == 0:
        return 0
    if n == 1:
        return k

    # For 2 posts, initialize:
    same = k           # Ways where the 2 posts are painted the same color
    diff = k * (k - 1) # Ways where the 2 posts are painted in different colors

    # For posts 3 to n, update the values using the recurrence relations:
    # new_same = diff (previous post painted differently guarantees current post can match previous one)
    # new_diff = (same + diff) * (k - 1) (current post painted with a different color)
    for i in range(3, n + 1):
        new_same = diff
        new_diff = (same + diff) * (k - 1)
        same, diff = new_same, new_diff

    return same + diff

# Test examples
print("Example 1:")
print("Input: n = 3, k = 2")
print("Output:", painting_fence(3, 2))   # Expected output: 6

print("\nExample 2:")
print("Input: n = 4, k = 3")
print("Output:", painting_fence(4, 3))   # Expected output: 66

Explanation: The painting_fence function handles the base cases first. For two posts, it initializes the number of ways when both posts are painted the same (same) and when they are painted differently (diff). For each subsequent post, it updates these values using the recurrence relations explained above. Finally, the total number of ways to paint the fence is the sum of the two values for the last post.

Conclusion

In this tutorial, we explored the Painting the Fence Problem using dynamic programming. The problem was approached by dividing it into two scenarios—painting the current post the same as the previous post or a different color. We walked through two sample examples to illustrate the method and provided a detailed Python implementation. This approach ensures an efficient solution that adheres to the constraint of not having more than two adjacent posts with the same color.

TutorialKart

Python – Painting the Fence Problem