Here's a coding challenge:

Imagine you have n 2x1 bricks. How many different ways can those bricks be stacked to cover an nx2 area?

Stop! Take a second to think about the problem and come up with a solution before reading further!

Solution

On first learning about the challenge, I immediately thought about dynamic programming and recursion. The base cases are:

  • when n = 0, there is 1 way (0 bricks)
  • when n = 1, there is 1 way (1 horizontal brick)

However, I couldn't see the recursive step and turned to visualizations of the stacks for the next few values of n to try and find a pattern:

To cover a 2x2 space, 2 bricks can be stacked in 2 different orientations. To cover a 3x2 space, 3 bricks can be stacked in 3 different orientations. To cover a 4x2 space, 4 bricks can be stacked in 5 different orientations. To cover a 5x2 space, 5 bricks can be stacked in 8 different orientations.
Bricks can be stacked in these orientations to cover various areas from 0x2 to 5x2.

As n grows, the number of different stacks is 1, 1, 2, 3, 5, 8... the Fibonacci sequence! That was simpler than anticipated. But while coding the solution had become significantly simpler, I still didn't have a strong intuition for the recursive step. To build that intuition, I color-coded the n-2 and n-1 cases for a couple of values of n and then showed how the new stacks are built off of them:

The 3x2 stacks are built by adding one horizontal brick on top of each 2x2 stack or by adding two vertical bricks on top of each 1x2 stack.
The 3x2 stacks are built by adding one horizontal brick on top of each 2x2 stack or by adding two vertical bricks on top of each 1x2 stack.
The 4x2 stacks are built by adding one horizontal brick on top of each 3x2 stack or by adding two vertical bricks on top of each 2x2 stack.
The 4x2 stacks are built by adding one horizontal brick on top of each 3x2 stack or by adding two vertical bricks on top of each 2x2 stack.

Great! Recursive step finally understood.

And just for the sake of completion, here's a coded solution in Python that's even memoized:

from functools import cache

@cache
def stack(n):
    if n < 2:
        return 1
    else:
        return stack(n-1) + stack(n-2)