Riddler Classic

By Zach Wissner-Gross

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:

Four possible arrangements of stacks 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?

My Solution

Computers are pretty cool. They can do math really fast:

library(gtools)

permuteRings <- function (totalRings) {
  uniqueRingStacks <- c()
  
  ringCombos <- combinations((2*totalRings) - 1,
                             totalRings, 
                             c(rep.int(0, totalRings - 1), 1:totalRings), 
                             set = FALSE, 
                             repeats.allowed = FALSE)
  for (combo in 1:nrow(ringCombos)) {
    combo <- ringCombos[combo,]
    combo <- combo[combo != 0]
    # ring 1 is biggest and 5 is the smallest (0 = no ring)
    ringPermutations <- permutations(n = length(combo), r = length(combo), v = combo, repeats.allowed = FALSE)
    ringStacksTemp <- c()
    # resolve the permuation into an actual ring stack
    for (row in 1:nrow(ringPermutations)) {
      finalStack <- c()
      fullStack <- FALSE
      for (col in 1:length(combo)) {
        ring <- ringPermutations[row, col]
        topRing <- finalStack[length(finalStack)]
        
        if (is.null(topRing)) {
          finalStack <- ring
        } else if (!fullStack) {
          finalStack <- c(finalStack, ring)
        }
        
        for (ringPos in 1:length(finalStack)) {
          if (ringPos + rev(finalStack)[ringPos] == totalRings + 1) {
            fullStack <- TRUE
          }
        }
      }
      # element 1 is bottom, element 5 is top
      ringStacksTemp <- c(ringStacksTemp, paste(finalStack, collapse = ""))
    }
    uniqueRingStacks <- c(uniqueRingStacks, unique(ringStacksTemp))
  }
  return(unique(uniqueRingStacks))
}

print(paste("There are", length(permuteRings(5)), "possible stacks with 5 rings."))
## [1] "There are 65 possible stacks with 5 rings."

I want to learn how to draw cool visualizations, so let’s try it out!

library(ggplot2)
library(stringr)

ring1 <- data.frame(x = c(2.5, 2.5, 7.5, 7.5), col = "red")
ring2 <- data.frame(x = c(3, 3, 7, 7), col = "orange")
ring3 <- data.frame(x = c(3.5, 3.5, 6.5, 6.5), col = "darkgreen")
ring4 <- data.frame(x = c(4, 4, 6, 6), col = "blue")
ring5 <- data.frame(x = c(4.5, 4.5, 5.5, 5.5), col = "purple")

drawCol <- data.frame(
  x = c(2.5, 5, 7.5),
  y = c(0, 10, 0)
)

drawRingStack <- function (stack) {
  p <- ggplot() + 
    geom_polygon(data = drawCol, aes(x=x, y=y), fill = "gray50") +
    xlim(c(2,8)) +
    ylim(c(0,10)) +
    theme_void()
  stack <- unlist(str_split(stack, ""))
  highestRing <- 0
  for (ringPos in 1:length(stack)) {
    ringSize <- stack[ringPos]
    ringHeight <- max(highestRing + 1, as.numeric(ringSize))
    trueRingPos <- c(0,2,2,0) + ((ringHeight - 1) *  2)
    highestRing <- ringHeight
    p <- p + geom_polygon(data = eval(parse(text = paste("ring", ringSize, sep = ""))),
                          aes(x=x), 
                          y=trueRingPos,
                          fill = eval(parse(text = paste("ring", ringSize, "$col", sep = ""))), 
                          alpha = 0.7)
  }
  return(p)
}
library(ggpubr)

ringStacks <- permuteRings(5)
plotList <- vector('list', length(ringStacks))
plotList <- lapply(ringStacks, drawRingStack)

do.call(ggarrange, c(plotList[1:65], list(nrow = 6, ncol = 11)))

The extra credit should be pretty simple – I’ll just keep brute forcing this. People are saying on Twitter that it’s taking them a pretty long time to brute force and I’m not a computer scientist, so I’m pretty sure mine will be even slower.

for (i in 1:8) {
  print(paste("There are", length(permuteRings(i)), "possible stacks with", i, "rings."))
}
## [1] "There are 1 possible stacks with 1 rings."
## [1] "There are 3 possible stacks with 2 rings."
## [1] "There are 8 possible stacks with 3 rings."
## [1] "There are 22 possible stacks with 4 rings."
## [1] "There are 65 possible stacks with 5 rings."
## [1] "There are 209 possible stacks with 6 rings."
## [1] "There are 732 possible stacks with 7 rings."
## [1] "There are 2780 possible stacks with 8 rings."

Hmm.. So 8 rings is probably the most that I can push my computer to realistically calculate. But, hey look: it’s a sequence of integers! More specifically, it’s A003101 on OEIS. There’s no need to do or understand math, when people in the past have already figured it out.

The number of unique stacks of \(N\) rings is:

\[\sum_{k = 1..N} (N - k + 1)^k\]

(probably)