HEYNAIRB
BAN USERThis is the proper way to do it. Accept it's not exactly the same as the counting change problem. for N=5 11111 is not valid because each layer must be LESS THAN the layer below it. In the case above the layers are equal and therefore not valid. This requires a little modification to the counting change solution
- HEYNAIRB January 03, 2014Recursive solution in python below:
def rockstacking(amt):
if amt == 0:
return 0
if amt < 3:
return 1
else:
#this here is the tricky part
if amt%2 == 0:
result = 0
else:
result = 1
for i in xrange(amt/2+1):
result = result + rockstacking(i)
return result
Basically just think of it as a stack of dominos with each layer less then the layer below it.
The maximum amount of rocks that can go above the base layer is roughly equal to N/2.
Start off counting with all the rocks in the base layer and 0 rocks above it (+1 to the count). Then subtract 1 from the base layer and count the number of ways you can recursively make the structure with one rock; add that to the count. Subtract 2 rocks from the base layer and Count the amount of ways you can make the structure with 2 rocks; add that to the count... then 3 then 4... until you reach N/2.
This is the basic concept behind the solution, however it is not completely correct.
The tricky part is to know that when you have an even number of rocks you have to subtract One from your overall solution. Why? Lets take a look at an example:
Assume N=8. Everything works fine until the algorithm reaches N/2 or in this case Four rocks in the base layer. With Four rocks in the base layer that means the recursive algorithm will count the amount of ways you can create the structure above it with the other remaining 4 rocks.
To illustrate:
Total 8 rocks
At N/2
Base layer has four rocks and looks like this when the rocks are represented by underscores:
_ _ _ _
The two possible structures on top of the base layer look like this:
_
_ _ _
and:
_ _ _ _ <<<This is wrong, you can't lay four rocks on top of four rocks.
You will see that the recursive call is off by 1 because you can't overlay four rocks on four rocks when the problem clearly states that each layer is less then the layer below it. The algorithm will always count incorrectly in the same way illustrated above whenever N is even. Thus when the amount of rocks is even just subtract 1 from the overall solution.
- HEYNAIRB January 03, 2014
You're right! Except for n=11 a single layer of 11 rocks is a structure as well. Thus the count for n=11 is 12
- HEYNAIRB January 03, 2014