Hi, I recently got this question as an interview question and I have been racking my brains to solve it. I tried coming up with some sort of formula/algo to do it but then I figured out I am better of using dynamic programming in C#/Java. The problem being I have not done this kind of thing before and I dont know how to start. The question is as follows. Any help will be highly appreciated.
Suppose you want to build a solid panel out of rows of 4×1 and 6×1 Lego blocks. For structural strength, the spaces between the blocks must never line up in adjacent rows. As an example, the 18×3 panel shown below is not acceptable, because the spaces between the blocks in the top two rows line up (shown by the dotted line).
There are 2 ways to build a 10×1 panel, 2 ways to build a 10×2 panel, 8 ways to build an 18×3 panel, and 7958 ways to build a 36×5 panel.
How many different ways are there to build a 64×10 panel? The answer will fit in a 64-bit signed integer.
This Question has been solved and asker verified All Experts Exchange premium technology solutions are available to subscription members.
Experts Exchange has been collecting answers to technology questions since 1996…3 million and counting! If you have a question, chances are we already have your answer.
If you can't find the exact answer you're looking for, ask our exclusive community of 50,000 experts. You’ll get a personalized answer from a trusted professional.
Thousands of free tech tips, tricks, how-to’s and tutorials are available in our peer reviewed articles section. See for yourself how smart our experts are, no login required.
Save solutions to your questions, answers you’ve discovered through searching plus helpful articles in your personal knowledgebase for easy future access.
Access the answers to your technology questions today.
30-day free trial. Register in 60 seconds.
Members of the expert community talk about why the experience at Experts Exchange is different than what you will find anywhere else.
Try it out and discover for yourself.
30-day free trial. Register in 60 seconds.
Join the community of experts here and help other tech pros by answering question in your area of expertise. You can earn FREE access to all Experts Exchange's premium features and resources.
sorry, that should be
3329 ways to build 64×1
37120 ways to build 64×2
592050 ways to build 64×3
10178548 ways to build 64×4
199541122 ways to build 64×5
3919649942 ways to build 64×6
83141220006 ways to build 64×7
1722438038790 ways to build 64×8
37941687807654 ways to build 64×9
806844323190414 ways to build 64×10
Illustrating a smaller example
44444 can stack on 6446
4466 can stack on 6464 or 6644
4646 can stack on 6644
6446 can stack on 44444
6464 can stack on 4466
6644 can stack on 4466 or 4646
1 ways to build 20x1 ending with 44444
1 ways to build 20x1 ending with 4466
1 ways to build 20x1 ending with 4646
1 ways to build 20x1 ending with 6446
1 ways to build 20x1 ending with 6464
1 ways to build 20x1 ending with 6644
1 ways to build 20x2 ending with 44444
2 ways to build 20x2 ending with 4466
1 ways to build 20x2 ending with 4646
1 ways to build 20x2 ending with 6446
1 ways to build 20x2 ending with 6464
2 ways to build 20x2 ending with 6644
1 ways to build 20x3 ending with 44444
3 ways to build 20x3 ending with 4466
2 ways to build 20x3 ending with 4646
1 ways to build 20x3 ending with 6446
2 ways to build 20x3 ending with 6464
3 ways to build 20x3 ending with 6644
1 ways to build 20x4 ending with 44444
5 ways to build 20x4 ending with 4466
3 ways to build 20x4 ending with 4646
1 ways to build 20x4 ending with 6446
3 ways to build 20x4 ending with 6464
5 ways to build 20x4 ending with 6644
1 ways to build 20x5 ending with 44444
8 ways to build 20x5 ending with 4466
5 ways to build 20x5 ending with 4646
1 ways to build 20x5 ending with 6446
5 ways to build 20x5 ending with 6464
8 ways to build 20x5 ending with 6644
So did I:
a 0 × 1 panel can only be built by using no bricks
for width= 0..64
for all ways to build a width × 1 panel
a (width+4) × 1 panel can be built by adding a 4×1 brick
a (width+6) × 1 panel can be built by adding a 6×1 brick
for all possible 64 × 1 rows
find which other possible rows form acceptable adjacent rows with it
for height =1
for all possible 64 × 1 rows
number of ways to build a 64 × height panel with that row on top = 1
for height =2..10
for all possible 64 × 1 rows
number of ways to build a 64 × height panel with that row on top =
sum over all acceptable adjacent rows of (number of ways to build a 64 × (height-1) panel with that adjacent row on top)
number or ways to build a 64 × 10 panel =
sum over all possible 64 × 1 rows of (number of ways to build a 64 × 10 panel with that row on top)
Business Accounts
Answer for Membership
by: RobinDPosted on 2009-06-02 at 01:20:03ID: 24524625
When given the idea of lego blocks and a wall, the instinctive way to think is to build in layers (rows).
With this question, the major criteria is to have no vertical edges above each other so I would look at building just the first brick in each row above each other. The left hand brick of the first column must alternate 6:4:6:4 etc, else the edges would join.
Next column, the lower two cannot be 6 against 4 and 4 against 6, 4+4 is ok so is 6+6, or 4+4 and 6+4, or 4+6 and 6+6.
All odd rows can be the same and so can the even rows. The final part of the problem is to make sure the row length adds to 64.