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

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?

-
If I solve this - maybe I can get the interview! – Catchops Aug 1 '11 at 14:52
Better fit for code golf SE. – Karl Bielefeldt Aug 1 '11 at 15:28
Are you going to tell the interviewer that you got an answer from stackexchange, or are you going to present our work as your own? I don't think they asked you this question to see how well you could get assistance from the internet, but to see if you were able to design simple search algorithms. Presumably if they hire you, you will be expected to make progress on more complex problems of this type. Are you planning to just post all your work assignments to stackexchange? – kevin cline Aug 1 '11 at 16:38
This question doesn't belong here. It belongs to stackoverflow. – Alexandru Aug 1 '11 at 16:52
NB This is Project Euler problem 215 - the width is halved, but otherwise it's just a scale. One of the PE problems I had most fun with. – Peter Taylor Aug 1 '11 at 16:54

## migrated from programmers.stackexchange.comAug 1 '11 at 16:26

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

-

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.

-