Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

Riddler Clasic

July 10, 2020

From Austin Shapiro comes a story of stacking that may stump you:

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.

Here are a four different stacks Mira could make:

alt text

This got Mira thinking. How many unique stacks can she create using at least one ring?

Extra credit: Instead of five rings, suppose the toy has N rings. Now how many unique stacks can Mira create?

Solution

My methodology involves two main steps. First, enumerate all the possible orders that Mira can place rings. Then, simulate all of these orders and remove the duplicates. This leaves you with all the unique ways that the rings could be stacked for the given size of rod/number of rings.

Enumerate Possible Orders

Bring out your combinatorics. Mira must choose at least one ring, up to 5 rings. Order matters here, so the total number of possible orders is equal to
\sum_{k=1}^{5} P_{5,k}
where P(n,k) = Alt Text

For a ring size of 5, there are 325 possible orders Mira can choose. We'll simulate all of these in our code. This list of possible orders is created with get_permutations().

Eliminate Duplicate Stacks

The hardest part of this problem to codify is the algorithm for stacking rings on the rod. To determine a ring's final resting place, my function loops over the rod, checking if the rod is empty "_" or if the rod already has a ring on it. There are 3 possible outcomes when putting a ring on the rod:

  • The ring slides all the way down until the rod itself becomes too wide for it to fit
  • The ring is stacked on top of the topmost ring already on the rod
  • The rod is full, so you can not stack anymore rings.

Once that algorithm is written, it's time for Mira to stack all 325 orders of rings she came up with!

Mira isn't so smart to figure it out, but most of the stacks she will create will be duplicates. Good thing she is good at keeping track without miscounting! Removing the duplicate solutions is made simple in python because you can compare lists (and their orders!) using == (or in my case, using == "under the hood").

After all duplicates have been removed, Mira is left with 65 unique solutions.
[1, '_', '_', '_', '_']
['_', 2, '_', '_', '_']
['_', '_', 3, '_', '_']
['_', '_', '_', 4, '_']
['_', '_', '_', '_', 5]
[1, 2, '_', '_', '_']
[3, 2, '_', '_', '_']
[4, 2, '_', '_', '_']
[5, 2, '_', '_', '_']
[1, '_', 3, '_', '_']
['_', 2, 3, '_', '_']
['_', 4, 3, '_', '_']
['_', 5, 3, '_', '_']
[1, '_', '_', 4, '_']
['_', 2, '_', 4, '_']
['_', '_', 3, 4, '_']
['_', '_', 5, 4, '_']
[1, '_', '_', '_', 5]
['_', 2, '_', '_', 5]
['_', '_', 3, '_', 5]
['_', '_', '_', 4, 5]
[1, 2, 3, '_', '_']
[4, 2, 3, '_', '_']
[5, 2, 3, '_', '_']
[1, 4, 3, '_', '_']
[2, 4, 3, '_', '_']
[5, 4, 3, '_', '_']
[1, 5, 3, '_', '_']
[2, 5, 3, '_', '_']
[4, 5, 3, '_', '_']
[1, 2, '_', 4, '_']
[3, 2, '_', 4, '_']
[5, 2, '_', 4, '_']
[1, '_', 3, 4, '_']
['_', 2, 3, 4, '_']
['_', 5, 3, 4, '_']
[1, '_', 5, 4, '_']
['_', 2, 5, 4, '_']
['_', 3, 5, 4, '_']
[1, 2, '_', '_', 5]
[3, 2, '_', '_', 5]
[4, 2, '_', '_', 5]
[1, '_', 3, '_', 5]
['_', 2, 3, '_', 5]
['_', 4, 3, '_', 5]
[1, '_', '_', 4, 5]
['_', 2, '_', 4, 5]
['_', '_', 3, 4, 5]
[1, 2, 3, 4, '_']
[5, 2, 3, 4, '_']
[1, 5, 3, 4, '_']
[2, 5, 3, 4, '_']
[1, 2, 5, 4, '_']
[3, 2, 5, 4, '_']
[1, 3, 5, 4, '_']
[2, 3, 5, 4, '_']
[1, 2, 3, '_', 5]
[4, 2, 3, '_', 5]
[1, 4, 3, '_', 5]
[2, 4, 3, '_', 5]
[1, 2, '_', 4, 5]
[3, 2, '_', 4, 5]
[1, '_', 3, 4, 5]
['_', 2, 3, 4, 5]
[1, 2, 3, 4, 5]
import numpy as np
from sympy.utilities.iterables import multiset_permutations
def get_permutations(num_rings):
'''
This function returns the possible orders in which you can drop rings on to your rod.
And it lets you pick the number of rings!
:param num_rings: Number of rings on your rod
:return: list of lists - contains all possible orders you could drop rings on the rod
'''
arr = np.array(range(1, num_rings+1))
perms = []
for i in range(1,num_rings+1):
for elem in multiset_permutations(arr, i):
perms.append(elem)
return perms
def resolve(order, rod_size):
'''
"Put" the rings on the rod in the order provided. Return the final state of the rod.
Uses "_" to represent the rod's section has no ring on it.
:param order: The order the rings will be placed on the rod
:param rod_size: The number of rings the rod can hold. Should equal the number of rings
:return: list (length of rod_size) - the final state of the rings on the rod
'''
final_state = ['_' for _ in range(rod_size)]
for ring in order:
topmost_index = -1
for rod_index, link in enumerate(final_state):
# Look for where the link should land
if link == '_':
if ring == rod_index + 1:
# Place ring due to rod width
if len(final_state) >= rod_index + 1:
final_state[rod_index] = str(ring)
break
else:
continue
else:
# Already a ring here! Don't continue to loop over rod
topmost_index = rod_index
break
if topmost_index != -1:
if topmost_index - 1 in range(0,len(final_state)):
final_state[topmost_index - 1] = ring
else:
# the ring can't be placed because you are out of bounds
pass
return final_state
def solve(rings):
all_possible_orders = get_permutations(rings)
solutions = []
for order in all_possible_orders:
solutions.append(resolve(order, rings))
unique_solutions = []
for solution in solutions:
if solution not in unique_solutions:
unique_solutions.append(solution)
print(f'There are {len(unique_solutions)} unique solutions when there are {rings} rings')
if __name__ == '__main__':
solve(5)
There are 65 unique solutions when there are 5 rings

Extra Credit

By re-using code above (and burning cpu oil), we find the following results:

There are 1 unique solutions when there are 1 rings

There are 3 unique solutions when there are 2 rings

There are 8 unique solutions when there are 3 rings

There are 22 unique solutions when there are 4 rings

There are 65 unique solutions when there are 5 rings

There are 209 unique solutions when there are 6 rings

There are 732 unique solutions when there are 7 rings

There are 2780 unique solutions when there are 8 rings

There are 11377 unique solutions when there are 9 rings

...

We can extrapolate this further by utilizing the following formula:
f(x) = \sum_{k = 1}^{x} (x - k + 1)^k
where x is the number of rings that Mira can choose from, and f(x) is the number of unique states the stack can be in.

We can find this sequence in our trusty Online Encyclopedia of Integer Sequences. Although I'm sure more rigorous proof is out there.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.