R/day23.R

In tjmahr/adventofcode20: Advent of Code 2020

#' Day 23: Crab Cups
#'
#' [Crab Cups](https://adventofcode.com/2020/day/23)
#'
#' @name day23
#' @rdname day23
#' @details
#'
#' **Part One**
#'
#' The small crab challenges *you* to a game! The crab is going to mix up
#' some cups, and you have to predict where they\'ll end up.
#'
#' The cups will be arranged in a circle and labeled *clockwise* (your
#' puzzle input). For example, if your labeling were `32415`, there would
#' be five cups in the circle; going clockwise around the circle from the
#' first cup, the cups would be labeled `3`, `2`, `4`, `1`, `5`, and then
#' back to `3` again.
#'
#' Before the crab starts, it will designate the first cup in your list as
#' the *current cup*. The crab is then going to do *100 moves*.
#'
#' Each *move*, the crab does the following actions:
#'
#' -   The crab picks up the *three cups* that are immediately *clockwise*
#'     of the *current cup*. They are removed from the circle; cup spacing
#'     is adjusted as necessary to maintain the circle.
#' -   The crab selects a *destination cup*: the cup with a *label* equal
#'     to the *current cup\'s* label minus one. If this would select one of
#'     the cups that was just picked up, the crab will keep subtracting one
#'     until it finds a cup that wasn\'t just picked up. If at any point in
#'     this process the value goes below the lowest value on any cup\'s
#'     label, it *wraps around* to the highest value on any cup\'s label
#'     instead.
#' -   The crab places the cups it just picked up so that they are
#'     *immediately clockwise* of the destination cup. They keep the same
#'     order as when they were picked up.
#' -   The crab selects a new *current cup*: the cup which is immediately
#'     clockwise of the current cup.
#'
#' For example, suppose your cup labeling were `389125467`. If the crab
#' were to do merely 10 moves, the following changes would occur:
#'
#'     -- move 1 --
#'     cups: (3) 8  9  1  2  5  4  6  7
#'     pick up: 8, 9, 1
#'     destination: 2
#'
#'     -- move 2 --
#'     cups:  3 (2) 8  9  1  5  4  6  7
#'     pick up: 8, 9, 1
#'     destination: 7
#'
#'     -- move 3 --
#'     cups:  3  2 (5) 4  6  7  8  9  1
#'     pick up: 4, 6, 7
#'     destination: 3
#'
#'     -- move 4 --
#'     cups:  7  2  5 (8) 9  1  3  4  6
#'     pick up: 9, 1, 3
#'     destination: 7
#'
#'     -- move 5 --
#'     cups:  3  2  5  8 (4) 6  7  9  1
#'     pick up: 6, 7, 9
#'     destination: 3
#'
#'     -- move 6 --
#'     cups:  9  2  5  8  4 (1) 3  6  7
#'     pick up: 3, 6, 7
#'     destination: 9
#'
#'     -- move 7 --
#'     cups:  7  2  5  8  4  1 (9) 3  6
#'     pick up: 3, 6, 7
#'     destination: 8
#'
#'     -- move 8 --
#'     cups:  8  3  6  7  4  1  9 (2) 5
#'     pick up: 5, 8, 3
#'     destination: 1
#'
#'     -- move 9 --
#'     cups:  7  4  1  5  8  3  9  2 (6)
#'     pick up: 7, 4, 1
#'     destination: 5
#'
#'     -- move 10 --
#'     cups: (5) 7  4  1  8  3  9  2  6
#'     pick up: 7, 4, 1
#'     destination: 3
#'
#'     -- final --
#'     cups:  5 (8) 3  7  4  1  9  2  6
#'
#' In the above example, the cups\' values are the labels as they appear
#' moving clockwise around the circle; the *current cup* is marked with
#' `( )`.
#'
#' After the crab is done, what order will the cups be in? Starting *after
#' the cup labeled `1`*, collect the other cups\' labels clockwise into a
#' single string with no extra characters; each number except `1` should
#' appear exactly once. In the above example, after 10 moves, the cups
#' clockwise from `1` are labeled `9`, `2`, `6`, `5`, and so on, producing
#' *`92658374`*. If the crab were to complete all 100 moves, the order
#' after cup `1` would be *`67384529`*.
#'
#' Using your labeling, simulate 100 moves. *What are the labels on the
#' cups after cup `1`?*
#'
#' **Part Two**
#'
#' Due to what you can only assume is a mistranslation (you\'re [not
#' exactly fluent in
#' Crab]{title="If I were going for a programming language pun here, I'd say you were a little... RUSTy."}),
#' you are quite surprised when the crab starts arranging *many* cups in a
#' circle on your raft - *one million* (`1000000`) in total.
#'
#' Your labeling is still correct for the first few cups; after that, the
#' remaining cups are just numbered in an increasing fashion starting from
#' the number after the highest number in your list and proceeding one by
#' one until one million is reached. (For example, if your labeling were
#' `54321`, the cups would be numbered `5`, `4`, `3`, `2`, `1`, and then
#' start counting up from `6` until one million is reached.) In this way,
#' every number from one through one million is used exactly once.
#'
#' After discovering where you made the mistake in translating Crab
#' Numbers, you realize the small crab isn\'t going to do merely 100 moves;
#' the crab is going to do *ten million* (`10000000`) moves!
#'
#' The crab is going to hide your *stars* - one each - under the *two cups
#' that will end up immediately clockwise of cup `1`*. You can have them if
#' you predict what the labels on those cups will be when the crab is
#' finished.
#'
#' In the above example (`389125467`), this would be `934001` and then
#' `159792`; multiplying these together produces *`149245887792`*.
#'
#' Determine which two cups will end up immediately clockwise of cup `1`.
#' *What do you get if you multiply their labels together?*
#'
#' @param x some data
#' @param n Number of turns to play the crab cup game.
#' @return For Part One, `play_crab_cups(x, n)` returns plays `n` turns of the
#'   crab cup game. `sort_crab_cups()` prints the numbers after 1 in a string.
#'   ... For Part Two, `f23b(x)` returns ....
#' @export
#' @examples
#' play_crab_cups(example_crab_cups(), 1)
#' sort_crab_cups(play_crab_cups(example_crab_cups(), 1))
#' f23b()
play_crab_cups <- function(x, n = 1) {
  c0 <- x %>% as.character() %>% strsplit("") %>% unlist() %>% as.numeric()
  while (n != 0) {
    n <- n - 1
    c1 <- c0
    c0 <- step_crab_cups(c0)
  }
  c0
}


#' @rdname day23
#' @export
sort_crab_cups <- function(x) {
  # This shows the main trick I learned on this exercise. How to count indices
  # down and wrap around.
  m <- length(x)
  i <- which(x == 1)
  indices <- mod1(i - 1 + seq_len(m), m)

  rest <- indices[-1]
  x[rest] %>%
    paste0(collapse = "") %>%
    as.numeric()
}


play_super_crab_cups <- function(x, n = 1) {
  # Not solved yet
  c0 <- x %>% as.character() %>% strsplit("") %>% unlist() %>% as.numeric()
  c0 <- c(c0, 10:1000000)
  c1 <- step_crab_cups(c0)
  c2 <- step_crab_cups(c1)
  c3 <- step_crab_cups(c2)
  c4 <- step_crab_cups(c3)
  c5 <- step_crab_cups(c4)
  c6 <- step_crab_cups(c5)
  x <- c0
  while (n != 0) {
    n <- n - 1
    # c1 <- c0
    # c0 <- step_crab_cups(c0)
    v_three <- x[2:4]
    x2 <- x[-(2:4)]
    m <- length(x)

    destination_set <- mod1(seq(m, 1, by = -1) + x[1] - 1, m)
    v_destination <- setdiff(destination_set, v_three)[1]
    i_destination <- which(x2 == v_destination)

    s1 <- seq(1, i_destination)
    # Include i because if i is last element, then the seq() is c(6). We then drop
    # first item to get a (correct) empty vector.
    s2 <- seq(i_destination, length(x2), by = 1)[-1]
    shifted <- c(x2[s1], v_three, x2[s2])

    # Always make the first item the active position
    x <- c(shifted[-1], shifted[1])
  }
  head(c0)
  head(c1)

  tail(c0, 40)
  tail(c1, 40)
  tail(c2, 40)
  tail(c3, 40)
  tail(c4, 40)
  tail(c5, 40)
  tail(c6, 40)
  tail(x, 40)

  # For n = 25, the last 22 are 10 to 94 by 4
  tail(x, 22)
  tail(x, 100)

  # >   tail(x, 100)
  # [1]  999998  999999 1000000       8       9      11      12      13      15      16
  # [11]      17      19      20      21      23      24      25      27      28      29
  # [21]      31      32      33      35      36      37      39      40      41      43
  # [31]      44      45      47      48      49      51      52      53      55      56
  # [41]      57      59      60      61      63      64      65      67      68      69
  # [51]      71      72      73      75      76      77      79      80      81      83
  # [61]      84      85      87      88      89      91      92      93      95      96
  # [71]      97       1       3       4       6       7       2       5      10      14
  # [81]      18      22      26      30      34      38      42      46      50      54
  # [91]      58      62      66      70      74      78      82      86      90      94

  # 10 14 18 22 26 30 34 38 42 46
  # [29] 50 54 58 62 66 70 74 78 82 86 90 94
}


step_crab_cups <- function(x) {
  v_three <- x[2:4]
  x2 <- x[-(2:4)]
  m <- length(x)

  destination_set <- mod1(seq(m, 1, by = -1) + x[1] - 1, m)
  v_destination <- setdiff(destination_set, v_three)[1]
  i_destination <- which(x2 == v_destination)

  s1 <- seq(1, i_destination)
  # Include i because if i is last element, then the seq() is c(6). We then drop
  # first item to get a (correct) empty vector.
  s2 <- seq(i_destination, length(x2), by = 1)[-1]
  shifted <- c(x2[s1], v_three, x2[s2])

  # Always make the first item the active position
  c(shifted[-1], shifted[1])
}


mod1 <- function(x, m) {
  r <- x %% m
  ifelse(r == 0, m, r)
}


#' @param example Which example data to use (by position or name). Defaults to
#'   1.
#' @rdname day23
#' @export
example_crab_cups <- function(example = 1) {
  l <- list(
    a = 389125467
  )
  l[[example]]
}