Riddler Classic July 10, 2020 (https://fivethirtyeight.com/features/can-you-make-24/)

01_Riddler_Stacking_Rings.md

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:

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?

02_5RingSolution.md

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

where P_(n,k) =

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]

03_ring_stacking.py

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)

04_ring_stacking_output.txt

There are 65 unique solutions when there are 5 rings

05_Extra_Credit.md

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:

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.