# 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 `n`th 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.