Advent of Code 2020 - Day 23

By Eric Burden | December 24, 2020

In the spirit of the holidays (and programming), I’ll be posting my solutions to the Advent of Code 2020 puzzles here, at least one day after they’re posted (no spoilers!). I’ll be implementing the solutions in R because, well, that’s what I like! What I won’t be doing is posting any of the actual answers, just the reasoning behind them.

Also, as a general convention, whenever the puzzle has downloadable input, I’m saving it in a file named input.txt.

Day 23 - Crab Cups

Find the problem description HERE.

Part One - I’m Not Trapped on This Raft With You

This puzzle presents us with a lovely cup game, administered by a small crab on a raft. Who’d have ever imagined we end up here? The crab, that’s who. To help myself out, we’ve got a couple of functions to plot a nice network diagram to visualize the state. I won’t tell you exactly how many times I used that, mostly because I’m not sure I can count that high. The ‘three vector’ approach to keeping track of the game state wasn’t actually my first direction, but it was by far the fastest, which you know is going to matter. This is the second ( I think) puzzle where we’ve made good use of a closure. This first part required a good bit of code, but it could have been accomplished in a less round-about manner just by following the process outlined in the part one instructions.

# Setup ------------------------------------------------------------------------

test_input <- c(389125467)
real_input <- c(198753462)

library(igraph)    # For plotting networks, debugging
library(magrittr)  # Provides the `%>%` pipe operator


# Functions --------------------------------------------------------------------

# Given a vector of cup labels `cups`, a vector indicating the next cup in
# sequence `next_i`, the index (in `cups`) of the current cup `current_i`, 
# the index (in `cups`) of the destination cup `destination_i`, and the indices
# (in `cups`)  of any cups that have been picked up `picked_up_i`, plots
# a network diagram of the current state of the cups game
pplot <- function(cups, next_i, current_i, destination_i, picked_up_i) {
  g <- graph_from_edgelist(cbind(cups, cups[next_i])) %>% 
    set_vertex_attr('current', value = F) %>% 
    set_vertex_attr('current', index = cups[current_i], value = T) %>% 
    set_vertex_attr('destination', value = F) %>% 
    set_vertex_attr('destination', index = cups[destination_i], value = T) %>%
    set_vertex_attr('picked_up', value = F) %>% 
    set_vertex_attr('picked_up', index = cups[picked_up_i], value = T)
  
  V(g)$color <- ifelse(V(g)$destination, 'coral', 'lightgreen')
  V(g)$color <- ifelse(V(g)$current, 'lightblue', V(g)$color)
  V(g)$color <- ifelse(V(g)$picked_up, 'purple', V(g)$color)
  plot(g)
}


# Given the closure containing all the elements of the cup game in its 
# enclosing environment, extracts those elements from the enclosing environemnt
# and passes them to `pplot()`
pplot_func <- function(f) {
  e <- environment(f)
  pplot(e$cups, e$next_i, e$current_i, e$destination_i, e$picked_up_i)
}


# Given a number representing cup labels in order, returns a numeric vector
# representing cup labels, in order
parse_input <- function(input) {
  input %>% 
    as.character() %>% 
    strsplit('') %>% 
    unlist %>% 
    as.numeric()
}


# A closure whose enclosing environment will contain the current state of the
# cups game, including:
# - a vector representing the cup labels in the initial order `cups`
# - a vector where the value at each index represents the index of the next 
#   cup (in `cups`) in series `next_i` (Example, `cups[next_i[3]]` is the next 
#   cup in sequence after cup `3`)
# - a vector where the value at each index `i` represents the index in `cups`
#   containing the value `i`, essentially a reverse lookup for `cups` (Example,
#   `val_map[3]` returns the index in `cups` for the value `3`)
# - the maximum value of a cup label `max_cup`
# - a number representing the index in `cups` for the 'current' cup `current_i`
# - a number representing the index in `cups` for the `destination` cup 
#   `destination_i`
# - a vector representing the indices in `cups` for the cups that have been 
#   picked up `picked_up_i`
#   
# Returns a function that advances the game state according to the rules of 
# the game as described in the puzzle instructions
crab_mover <- function(input) {
  
  # Values representing the current game state, see comment for `crab_mover()`
  # for explanations of each
  cups <- parse_input(input)
  next_i <- c(2:length(cups), 1)
  val_map <- sort.list(cups)
  max_cup <- max(cups)
  
  current_i <- 1
  destination_i <- 0
  picked_up_i <- 0
  
  function() {
    # Pick up three cups. Note the use of the `<<-` assignment operator, 
    # assigning the values to `picked_up_i` in the enclosing environment
    picked_up_i <<- c(
      next_i[current_i],
      next_i[next_i[current_i]],
      next_i[next_i[next_i[current_i]]]
    )
    
    # Close the circle, setting the `next_i` for the current cup to the cup
    # after the last cup picked up
    next_i[current_i] <<- next_i[picked_up_i[3]]
    
    # Identify the 'destination' cup, the next cup in reverse label order from
    # the current cup. Can't be one of the cups picked up. If there are no cups
    # with labels lower than the current cup, loop back to the top of the cup 
    # label range (`max_cup`)
    destination_value <- cups[current_i]
    invalid_values <- c(destination_value, cups[picked_up_i])
    while (destination_value %in% invalid_values) {
      destination_value <- if (destination_value == 1) { 
        max_cup 
      } else { 
        destination_value - 1 
      }
    }
    destination_i <<- val_map[destination_value]
    
    # Add the picked up cups back to the circle. Set the next cup after the 
    # third picked up cup to the cup following the destination cup. Set the
    # next cup after the destination cup to the first picked up cup.
    next_i[picked_up_i[3]] <<- next_i[destination_i]
    next_i[destination_i] <<- picked_up_i[1]
    
    # Get the next current cup
    current_i <<- next_i[current_i]
  }
}


# Processing -------------------------------------------------------------------

move_cups <- crab_mover(real_input)   # Set up the game
for (i in 1:10) { move_cups() }       # Advance 10 times
e <- environment(move_cups)           # Extract the game state

# Get cup labels, in order, following the cup labeled '1'
current_cup <- 1
cups_in_order <- character(0)
for (i in 1:8) {
  # Get the cup following the cup with the value `current_cup`
  next_cup <- e$cups[e$next_i[e$val_map[current_cup]]]
  cups_in_order <- c(cups_in_order, next_cup)
  current_cup <- next_cup
}
answer1 <- paste(cups_in_order, collapse = '')

So, there you have it. I actually implemented it first using a graph and switching the edges about, but that turned out to be way too slow for…

Part Two - You’re Trapped on This Raft With Me

This crab is a maniac. Part two is the exact same process as part one, just… way…WAY…WAY more. This was the reason for the three vectors, referenced by index and in place without any copying (I don’t think) or iterating through. Having got most of the operations down to O(1), we’re able to get the time to process this down to under a minute. Yay!

# Setup ------------------------------------------------------------------------
                
source('exercise_1.R')


# Functions --------------------------------------------------------------------

# Now add the range from 10 to one million to our cup labels. Yeesh.
parse_input <- function(input) {
  input %>% 
    as.character() %>% 
    strsplit('') %>% 
    unlist %>% 
    as.numeric() %>% 
    c(10:1000000)
}


# Processing -------------------------------------------------------------------

move_cups <- crab_mover(real_input)  # Set up the game

# Progress the game 10 MILLION times, with a progress bar to keep tabs
rounds <- 10000000
pb <- txtProgressBar(min = 0, max = rounds, style = 3)
for (i in 1:rounds) {
  if (i %% 100000 == 0) { setTxtProgressBar(pb, i)}  # Update `pb` at each %
  move_cups()
}
close(pb)

e <- environment(move_cups)                        # Extract the environment
next_one <- e$cups[e$next_i[e$val_map[1]]]         # First cup after '1'
next_two <- e$cups[e$next_i[e$val_map[next_one]]]  # Second cup after '1'
answer2 <- next_one * next_two                     # The answer!

I swear to God, if this is that ‘Ferris’ crab trying to make a point about interpreted languages versus compiled languages, I will flip my lid.

Wrap-Up

So, this is way outside the scope of things I normally think about, but optimizing the heck out of the run time was a really good experience in thinking through how to make the code run as efficiently as I could. There are probably still optimizations to be made here, but the feeling of triumph when that progress bar started moving across my screen at a readily observable rate was a thing a beauty.

If you found a different solution (or spotted a mistake in one of mine), please drop me a line!

comments powered by Disqus