So read on, noble hacker!
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?
Notes:
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:
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
Footnotes:
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)
