How to count how many possible combination of 1x1, 1x2, 2x1 tiles to fill a 2 x N floor?

I just did a technical test and was confused with this task. My goal is to understand how to solve this 'Cover the floor' problem. Honestly, I have no idea where to start with.

The task is:

1. There is a floor 2 x N floor.
2. We have 1x1, 1x2, 2x1 tiles to fill the floor.

The problem is:

1. Solution(1) expected output is 2 and actual output is 2.
2. However, Solution(2) expected output is 7 and actual output is 3.

The current solution is to:

1. 1x1 always can fill 2 x N floor, so the possibleWays starts from 1.
2. If residual floor mod 2 is 0 then possibleWays increased by 1.

The problem of the current solution is that it do not differentiate between 1x2 and 2x1 tiles. So for Solution(2) the actual output is 3 instead of 7.

The code

package main

import "fmt"

// Solution is your solution code.
func Solution(n int) int {
	possibleWays := 1

	floorArea := 2 * n
	// Your code starts here.

	for i := floorArea - 1; i >= 0; i-- {
		residualFloorArea := floorArea - i
		fmt.Println(i, residualFloorArea)
		if residualFloorArea%2 == 0 {
			fmt.Println("punch")
			possibleWays += 1
		}
	}

	return possibleWays
}

func main() {
	fmt.Println(Solution(1))
	fmt.Println("next")
	fmt.Println(Solution(2))
}

This is mainly a simple combinatorial puzzle, rather than a programming exercise. The trick is to count the number of ways of tiling a 2xN grid, but also a 2xN grid with one of the first two squares already filled. This gives you recurrence relations, which can be solved for compuationally.

Let F(N) be the number of ways of tiling a 2xN grid, and G(N) the number of ways of tiling the grid with one of the first two squares already filled.

We can enumerate ways of starting filling the grids from the left (being careful not to count anything twice):

A...
A...

A...
BB..

AA..
B...

A...
B...

AA..
BB..

Thus, F(N) = 2F(N-1) + 2G(N-1) + F(N-2)

Same for G (here # is the piece that's already filled):

#...
A...

#...
AA..

So G(N) = F(N-1) + G(N-1)

We also have the base cases: F(0) = 1, G(0)=0, F(1) = 2, G(1) = 1.

From these recurrence relations, we can solve the problem iteratively in O(N) arithmetic operations:

package main

import "fmt"

func F(N int) int {
	f0, f1 := 1, 2
	g1 := 1
	for i := 0; i < N; i++ {
		f1, g1, f0 = 2*f1+2*g1+f0, f1+g1, f1
	}
	return f0
}

func main() {
	for i := 0; i < 10; i++ {
		fmt.Println(i, F(i))
	}
}

A more descriptive and trivially exhaustive attempt:

Call the number of ways to cover a 2xN grid is x_n, the number of ways to cover a 2xN+1 grid is y_n, and the number of ways to cover a 2xN + 2 grid is z_n.

Base cases:

• x_0 = 1, y_0 = 1, z_0 = 2
• x_1 = 2, y_1 = 3, z_1 = 5

Induction step, N >= 2:

       -- --
      |  |  |
 -- -- -- --  ...
|xx|  |  |  |
 -- -- -- --

Consider the leftmost cell of the 2xN + 2 grid, if it is covered by a 1x1 tile, then the remaining is a 2xN + 1 grid, otherwise, it is covered by a 1x2 tile, the remaining would be a 2xN grid. Hence,

z_n = x_n + y_n

    -- --
   |  |  |
 -- -- --  ...
|xx|  |  |
 -- -- --

Consider the leftmost cell of the 2xN + 1 grid, if it is covered by a 1x1 tile, the remaining would be a 2xN grid, otherwise, it is covered by a 1x2 tile, the remaining would be a 2x(N-1) + 1 grid. Hence,

y_n = x_n + y_(n-1)

 -- --
|xx|  |
 -- --  ...
|  |  |
 -- --

Consider the topleft corner of the 2xN grid, if it is covered by a 1x1 tile, the remaining would be a 2x(N-1) + 1 grid, if it is covered by a 1x2 tile, the remaining would be a 2x(N-2) + 2 grid, otherwise, it is covered by a 2x1 tile, the remaining would be a 2x(N-1) grid. Hence:

x_n = y_(n-1) + z_(n-2) + x_(n-1)

Replace z_n with x_n + y_n, we have:

• x_n = x_(n-1) + x_(n-2) + y_(n-1) + y_(n-2)
• y_n = x_n + y_(n-1)

Now, just iteratively calculate each value:

package main

import "fmt"

// Solution is your solution code.
func Solution(n int) int {
    if n == 0 {
        return 1
    } else if n == 1 {
        return 2
    }

    x := make([]int, n + 1)
    y := make([]int, n + 1)
    x[0] = 1
    y[0] = 1
    x[1] = 2
    y[1] = 3

    for i := 2; i <= n; i++ {
        x[i] = x[i - 1] + x[i - 2] + y[i - 1] + y[i - 2]
        y[i] = x[i] + y[i - 1]
    }

    return x[n]
}

func main() {
    fmt.Println(Solution(1))
    fmt.Println("next")
    fmt.Println(Solution(2))
}

You can do it without a slice but this is easier to understand. Playground demonstration