My answer last week seems to be wrong; I thought agreeing with LL would be enough. I will need to look more closely at it.
This week’s Classic is about stacking blocks. At first glance I thought it was Tower of Hanoi, but it’s a little different:
Mira has a toy with five rings of different diameters and a tapered column. Each ring has a “correct” position on the column, from the largest ring that fits snugly at the bottom to the smallest ring that fits snugly at the top.
Each ring she places will slide down to its correct position, if possible. Otherwise, it will rest on what was previously the topmost ring.
For example, if Mira stacks the smallest ring first, then she cannot stack any more rings on top. But if she stacks the second-smallest ring first, then she can stack any one of the remaining four rings above it, after which she cannot stack any more rings.
This got Mira thinking. How many unique stacks can she create using at least one ring?
I have an answer for the basic question, which this code will generate. The code iterates through all the possible combinations of disks, and for each combination, checks whether it would sit on the tapered column.
The combinations are generated by creating the power set of the set of disks (excluding the set of no disks!), and then trying each set in every possible ordering.
How do we know if an ordering of disks is valid, if it will fit on the tapering column? We need two numberings:
- Number the rings by size, so ring one is the smallest, and ring five is the largest.
- Number the positions in the stack, so that stack position one is the last ring in the stack, the ring that will be the highest. The ring at the bottom of the stack, the first ring to be placed on the column, has the highest stack position number. The stack position number of that ring is the same as the number of rings in the set that we’re considering.
For any ring in an ordering, the whole ordering is invalid if the stack position number is higher than the ring size number. On the other hand, if every ring has a size number equal to or greater than its stack position number, then the ordering is valid.
That check could be done iteratively or recursively, and a recursive method would also combine nicely with caching the results for reuse. I did it iteratively in my code, but with only five disks to consider, speed is not a concern. Once there are more than nine or ten disks, execution time becomes noticeable.
I don’t have a neat closed-form solution for the extra credit question. I can run the code with different numbers of disks, but that becomes impractical quite quickly. I can count the number of possible disk orderings for any number of disks, but I don’t know how to calculate how many of those orderings will fit on the column without checking them all individually.