How can I loop through all the possibilites of building a panel with two diffenent block sizes?

Question

Im trying to land an interview for a company in Austin, Tx. before I can be considered they asked me to solve a programming puzzle. I really need this interview.

Your niece was given a set of blocks for her birthday, and she has decided to build a panel using 3”×1” and 4.5”×1" blocks. For structural integrity, the spaces between the blocks must not line up in adjacent rows. There are 2 ways in which to build a 7.5”×1” panel, 2 ways to build a 7.5”×2” panel, 4 ways to build a 12”×3” panel, and 7958 ways to build a 27”×5” panel. How many different ways are there for your niece to build a 48”×10” panel? The answer will fit in a 64-bit integer. Write a program to calculate the answer.

The program should be non-interactive and run as a single-line command which takes two command-line arguments, width and height, in that order. Given any width between 3 and 48 that is a multiple of 0.5, inclusive, and any height that is an integer between 1 and 10, inclusive, your program should calculate the number of valid ways there are to build a wall of those dimensions. Your program’s output should simply be the solution as a number, with no line-breaks or white spaces.

My problem is I don't know how to loop through all posibilities of a certain sized panel and ensure that no spaces line up with the previous roll. Any suggestions?

Answer 1

Here are some hints:

• Just think of one row. Could you write a function that gives you all permutations of your two block types that make a 48" row?

• your panel is a permutation of these rows. Write a function that gives you all permutations of 10 out of your calculated rows

• filter these permutations for ones that do not meet the no-spaces-line-up-criterion

Answer 2

The easiest, although perhaps not the most efficient, way to "loop" through all the permutations of a row is to use a recursive algorithm. Put each block down if it fits, then call it recursively with the remaining space.

I'd probably use some sort of adjacency matrix to record the permutations with cracks that don't line up.

Then it's a matter of traversing the matrix to record the possibilities.

If they're talking about numbers on the order of 64 bits, there are probably some significant shortcuts that must be taken, once you have a more brute force algorithm that can help you see the patterns.