Day 312

[vaskoz]

Good morning! Here's your coding interview problem for today.

This problem was asked by Wayfair.

You are given a 2 x N board, and instructed to completely cover the board with the following shapes:

Dominoes, or 2 x 1 rectangles.
Trominoes, or L-shapes.
For example, if N = 4, here is one possible configuration, where A is a domino, and B and C are trominoes.

A B B C
A B C C

Given an integer N, determine in how many ways this task is possible.

[vaskoz]

Writing this out by hand on paper showed that the pattern is Fibonacci. Below I've included the pattern worked out to N=5.

N = 1, answer = 1

1 # vertical only domino
1

N = 2, answer = 2

12 # 2 vertical dominos
12

11 # 2 horizontal dominos
22

N = 3, answer = 3

123 # 3 vertical dominos
123

113 # 2 horizontal dominos and 1 vertical domino
223

112 # 2 trominos
122

N = 4, answer = 5

1234 # 4 vertical dominos
1234

1122 # 4 horizontal dominos
3344

1134 # 2 horizontal, 2 vertical dominos
2234

1123 # 2 trominos and 1 vertical domino
1223

1122 # 2 trominos and 1 horizontal domino
1332

N = 5, answer = 8

11223 # 4 horizontal dominos and 1 vertical domino
44553

12345 # 4 vertical dominos
12345

11234 # 2 horizontal dominos and 3 vertical dominos
55234

12245 # 2 middle horizontal dominos and 3 vertical dominos 
13345

11234 # 2 vertical dominos and 2 trominos
12234

11233 # 2 horizontal dominos and 2 trominos
12244

11334 # 2 trominos, 1 vertical and 1 horizontal domino.
12234

11334 # 2 horizontal dominos and 2 trominos
12244