How many ways to build a "perfect fault-free" lego wall?

So, I applied for a job at a local company that has a large high-performance application written primarily in Perl. They sent me back a "spec" for a programming puzzle with the request that I send back the answer to the puzzle and the code I wrote to solve it. "Spec" is in quotes because it's not really one, but it was enough info to figure out what they wanted. :-)

At first glance I thought this would be simple, even though I am not even close to being an 'algorithms person.' I failed Calc I in college five times. However, I do enjoy programming and puzzles and I think I have a knack for problem solving.

Anyhow, you're probably here because I was on IRC begging for help... but I didn't really want help, at least not until I figured out a passable solution for myself! Now that I have one, I'd love to see what others can come up with, and better yet, if anybody can improve my solution even more!

So read on, noble hacker!

Puzzle Description

Your nephew little billy loves Legos and is insanely OCD. He just got a new set of lego blocks and is busy building and re-building walls with them that have a few interesting properties.

The walls Billy builds are all perfectly rectangular, contain no empty spaces, and are made only from blocks 1 block high (and 1 unit deep, if you're picturing this in 3-D, though that's not important.) However, these walls have 1 especially important property - they are all "perfectly fault-free." This means that the seams between two blocks never line up from one row to the next!

Also, Billy is only using blocks of just a few different lengths, and has a pretty much unlimited supply of each type of block he uses.

For example, an unacceptable wall:

  |        |     |     |     |
  |     |     |        |     |
  |        |        |        |

And one that makes the voices happy:

  |        |        |        |
  |     |     |        |     |
  |        |        |        |

Given the info above, write code that can answer this question:

Using any combination of bricks of only the given lengths (set of B), how many different ways are there to make a perfectly fault-free wall of length l and height h?


One thing I should mention - the original spec never mentioned the term "fault-free" but I've adopted it because I think it describes well the desired construction pattern. That said, I probably spent three hours researching "fault free tiling" on the 'tubes and none of that helped me at all. I think this is a different problem entirely, it just shares the one cosmetic property of a restriction on "fault lines" through a tessellation.

Also, I ended up asking if the only input it would be run on would be the examples given in the spec or if they wanted a solution that would handle more general parameters. It was suggested that there would be no penalty for solving only the specified example problems but a general solution would be "desirable". 

Example Parameters & Solutions:

All the examples were using an unlimited number of blocks/bricks of the following lengths:
  • 3"
  • 4.5”
The given example wall dimensions with solutions for those brick lengths are the following:
  • a 7.5" x 1" wall has 2 solutions for the given block sizes
  • 7.5" x 2" also has 2 solutions
  • 12" x 3" has 4
  • 27" x 5" has 7958

Requested Solution:
  • 48" x 10" has ? solutions


The original spec states that the fastest solution they have devised in Perl completes in under a second on a 2.5 GHz Xeon. (So far my fastest takes about 13.0 8.8 4.5 seconds on my 2GHz Core2-based laptop)

Also, thanks to tybalt89 for his advice and analysis. While I did not steal any of your code, the sheer brevity of your solution inspired me to take a stab at combining several sub-steps into one operation and that's what got me that last 4.3 second gain! :)

I have ideas to make it even faster, but I think what I have now strikes the best possible balance between speed and readability, even if it is a bit dense in parts. I will find a way to post it but I want there to be some restriction so that this company doesn't find my solution all over the web and think I cheated (or am helping others to cheat)
Stephen Scaffidi,
Jul 28, 2010, 4:55 PM