5 Creative Ways to Count the Number of Ways to Fill a 3 x n Box with 2 x 1 Dominos in Python

Rate this post

πŸ’‘ Problem Formulation: The task is to compute the number of unique ways to completely fill a 3 x n grid with 2 x 1 dominos without overlapping or leaving any empty spaces. For example, if n=2, the output should be 3 since there are three distinct arrangements for placing the dominos.

Method 1: Dynamic Programming Approach

This method uses dynamic programming to solve the problem by breaking it down into smaller, manageable subproblems. The function countWays(n) calculates the number of ways to fill a 3 x n board using 2×1 dominos by keeping track of solutions to previous subproblems.

Here’s an example:

def countWays(n):
    # Base cases
    if n % 2 != 0:
        return 0
    if n == 0:
        return 1
    if n == 2:
        return 3

    # Initialize the list with base cases
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[2] = 3

    # Fill the rest of the entries in dp[] using the recurrence relation
    for i in range(4, n + 1, 2):
        # Count the ways using previously computed values
        dp[i] = 4 * dp[i - 2] - dp[i - 4]

    return dp[n]

# Testing the function
print(countWays(6))

Output: 11

This code snippet defines a function countWays(n) that utilizes dynamic programming to compute different ways to fill the board. The series of previously solved subproblems contribute to the solution of the larger problem, providing an efficient way to calculate the answer.

Method 2: Recursive Solution

The recursive solution involves defining a function countWaysRecursive(n) that will count the number of arrangements by recursively solving for smaller values of n and combining their results to reach the final solution.

Here’s an example:

def countWaysRecursive(n):
    # Base cases
    if n % 2 != 0:
        return 0
    if n == 0:
        return 1
    if n == 2:
        return 3
        
    # Recursive case
    return 4 * countWaysRecursive(n - 2) - countWaysRecursive(n - 4)

# Testing the function
print(countWaysRecursive(6))

Output: 11

The recursive code calls countWaysRecursive(n) for smaller instances of the problem size and uses the overlapping subproblems to compute the result. However, this approach can be less efficient than dynamic programming due to redundant calculations.

Method 3: Matrix Exponentiation

Matrix exponentiation provides a fast way to reach the solution by raising a transformation matrix to the nth power. The function countWaysMatrixExpo(n) implements this method, which is efficient for large n.

Here’s an example:

import numpy as np

def matrix_power(matrix, n):
    return np.linalg.matrix_power(matrix, n)

def countWaysMatrixExpo(n):
    if n % 2 != 0:
        return 0
    if n == 0:
        return 1
    if n == 2:
        return 3

    # Define the transformation matrix
    T = np.array([[4, -1], [1, 0]])

    # Compute T^(n/2)
    T_n_div_2 = matrix_power(T, n // 2)

    # The number of ways will be the top left element of T^(n/2)
    return T_n_div_2[0][0]

# Testing the function
print(countWaysMatrixExpo(6))

Output: 11

The function countWaysMatrixExpo(n) uses matrix exponentiation to obtain the number of ways quickly, especially for large values of n. This method is significantly faster than the recursive and dynamic programming approaches for bigger inputs.

Method 4: Memoization (Top-Down Dynamic Programming)

Memoization is an optimization technique that involves storing the results of expensive function calls and reusing them when the same inputs occur again, preventing the need for re-computation. The function countWaysMemoization(n) applies this concept to our problem.

Here’s an example:

def countWaysMemoization(n, memo):
    if n % 2 != 0:
        return 0
    if n == 0:
        return 1
    if n in memo:
        return memo[n]

    # Compute the result and store it in memo
    memo[n] = 4 * countWaysMemoization(n - 2, memo) - countWaysMemoization(n - 4, memo)
    return memo[n]

# Testing the function with an empty memo dictionary
print(countWaysMemoization(6, {}))

Output: 11

The function countWaysMemoization(n, memo) avoids redundant calculations by storing previously computed values within a dictionary memo, making it more efficient than plain recursion.

Bonus One-Liner Method 5: Functional Approach Using functools

The functools module in Python offers a lru_cache decorator that can automatically memoize function calls. The following one-liner makes use of this feature for our domino counting problem.

Here’s an example:

from functools import lru_cache

@lru_cache(maxsize=None)
def countWaysOneLiner(n):
    return 0 if n % 2 != 0 else (1 if n == 0 else (3 if n == 2 else 4 * countWaysOneLiner(n - 2) - countWaysOneLiner(n - 4)))

# Testing the function
print(countWaysOneLiner(6))

Output: 11

The one-liner countWaysOneLiner(n) function efficiently computes the number of ways to fill the board thanks to the lru_cache decorator from functools which caches results for quick subsequent access.

Summary/Discussion

Method 1: Dynamic Programming. Efficient method for larger n. Needs extra space.
Method 2: Recursive Solution. Simple to understand and implement. Inefficient for large n due to overheads of recursive calls.
Method 3: Matrix Exponentiation. Fastest for large n. Requires knowledge of matrix operations.
Method 4: Memoization. Optimizes the recursive approach. Requires additional space for the memo dictionary.
Method 5: Functional Approach Using functools. Clean and concise syntax. Automatic caching with lru_cache. Difficult to read for those unfamiliar with decorators.