Advent of Code 2020 - Day 22
Published: 2021-11-28 02:43:22

---
title: Advent of Code 2020 - Day 22
published: true
date: 2020-12-23 00:00:00 UTC
tags: 
canonical_url: https://ericburden.work/blog/2020/12/23/advent-of-code-2020-day-22/
---

In the spirit of the holidays (and programming), I’ll be posting my solutions to the [Advent of Code 2020](https://adventofcode.com/) 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 22 - Crab Combat

Find the problem description [HERE](https://adventofcode.com/2020/day/22).

## Part One - Know When to Hold’em

Let’s play cards with a crustacean! Win or lose, this crab is a triumph. It doesn’t even have thumbs! I guess we’ll need to shuffle the deck… The game itself involves simulating a modified game of _War_ where the high card (number) always wins and the winner gets both cards. I added a pretty-print (`pprint()`) function to help with debugging.

```r
# Setup ------------------------------------------------------------------------

test_input <- c(
  "Player 1:",
  "9", "2", "6", "3", "1",
  "",
  "Player 2:",
  "5", "8", "4", "7", "10"
)
real_input <- readLines('input.txt')

library(dequer)

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

# Helper function, given a vector of input lines returns an environment
# containing both player's (player1 and player2) decks and a starting number
# for the number of rounds the game has progressed
parse_input <- function(input) {
  hands <- list(
    player1 = queue(), # A queue for handling player 1's deck
    player2 = queue(), # A queue for handling player 2's deck
    round = 1 # Start with round == 1
  )
  
  # Starting from scratch, for every line in the input
  current_player <- ''
  for (line in input) {
    if (line == '') { next } # Skip blank lines
    
    # If the line indicates a player, set `current_player` to a string
    # indicating that player's name. Otherwise, add the number on the line
    # to `current_player`'s deck.
    if (grepl('Player', line)) { 
      current_player <- tolower(gsub('[:]', '', line)) 
    } else {
      pushback(hands[[current_player]], as.numeric(line))
    }
  }
  list2env(hands, new.env()) # Return an environment
}

# Purely for debugging purposes, prints important bits from the game state
# to the console
pprint <- function(game_state) {
  cat('\n\n')
  cat('-- Round ', game_state$round, ' --', '\n')
  cat(
    'Player 1 deck: ', 
    game_state$p1_card, ', ', 
    paste(unlist(as.list(game_state$player1)), collapse = ', '), 
    '\n',
    sep = ''
  )
  cat(
    'Player 2 deck: ', 
    game_state$p2_card, ', ', 
    paste(unlist(as.list(game_state$player2)), collapse = ', '), 
    '\n',
    sep = ''
  )
  cat('Player 1 plays:', game_state$p1_card, '\n')
  cat('Player 2 plays:', game_state$p2_card, '\n')
  cat('Winner: ', game_state$winner, '\n')
}

# Given an environment `env` representing the game state, updates the game 
# state by simulating a round of play and returns the game state.
next_state <- function(env) {
  # Both players draw. It's not strictly necessary to include the player's
  # cards or the name of the player who won the round in the environment,
  # but it helps with debugging
  env$p1_card <- pop(env$player1)
  env$p2_card <- pop(env$player2)
  
  # pprint(env) # Prints important bits of the game state to console
  
  # Identify the winner and add the cards to the winner's deck
  env$winner <- if (env$p1_card > env$p2_card) { 'player1' } else { 'player2' }
  if (env$winner == 'player1') {
    pushback(env$player1, env$p1_card)
    pushback(env$player1, env$p2_card)
  } else {
    pushback(env$player2, env$p2_card)
    pushback(env$player2, env$p1_card)
  }
  
  env$round <- env$round + 1 # Advance the round count
  
  # If a player's deck is empty, the other player won the game. Add the winning
  # player's current deck to the environment `env`
  if (length(env$player1) == 0) { env$winner_deck <- unlist(as.list(env$player2)) }
  if (length(env$player2) == 0) { env$winner_deck <- unlist(as.list(env$player1)) }
  
  env # Return the modified environment
}

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

game_state <- parse_input(real_input) # Parse the input

# Until a player wins, advance the game state to the next state
while (is.null(game_state$winner_deck)) { game_state <- next_state(game_state) }
cards_in_winner_deck <- length(game_state$winner_deck)
answer1 <- sum(game_state$winner_deck * cards_in_winner_deck:1)

```

And…the crab won. (Depending on your individual input.)

## Part Two - Know When to Fold’em

According to the puzzle text, we lost round one to the crab. So, just like a petulant grade-schooler, it’s time to change the rules! Specifically, we’re introducing recursive sub-games to the mix and breaking all infinite loops in our favor. Guess the crab wasn’t paying attention when it agreed to that rule.

```r
# Setup ------------------------------------------------------------------------

source('exercise_1.R')

test_input <- c(
  "Player 1:",
  "9", "2", "6", "3", "1",
  "",
  "Player 2:",
  "5", "8", "4", "7", "10"
)
infinite_input <- c(
  "Player 1:",
  "43", "19",
  "",
  "Player 2:",
  "2", "29", "14"
)
real_input <- readLines('input.txt')

library(dequer)
library(digest) # For the `digest()` function

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

# Update the `next_state()` function to support the rules of `Recursive Combat`
next_state <- function(env) {
  # The `current_state` is a hash of the two player's hands
  current_state <- digest(list(as.list(env$player1), as.list(env$player2)))
  
  # The first time through, `env$past_states` will be NULL
  # If `current_state` is in the list of recorded states for this game,
  # Player 1 wins the game! This prevents infinite loops. Note, recursive
  # games start with the `past_states` of their parent game.
  if (current_state %in% env$past_states) {
    env$winner <- 'player1'
    env$winning_hand <- unlist(as.list(env$player1))
    return(env)
  }
    
  # Otherwise, add the current state to the list of past states
  env$past_states <- c(env$past_states, current_state)
  
  # Both players draw
  env$p1_card <- pop(env$player1)
  env$p2_card <- pop(env$player2)
  
  # If either player draws a number larger than the number of cards in
  # their hand, play as normal
  if (env$p1_card > length(env$player1) | env$p2_card > length(env$player2)) {
    env$winner <- if (env$p1_card > env$p2_card) { 'player1' } else { 'player2' }
  } else { # Otherwise, recursion!
    
    # Create a new environment and initialize it with the necessary data, 
    # including the top `n` cards from each players deck where `n` is the 
    # value of that players card and the `past_states` of the parent state
    sub_game <- new.env()
    sub_game$player1 <- as.queue(as.list(env$player1)[1:env$p1_card])
    sub_game$player2 <- as.queue(as.list(env$player2)[1:env$p2_card])
    sub_game$past_states <- env$past_states
    sub_game$round <- 1

    # Play out the sub game
    while (is.null(sub_game$winning_hand)) { sub_game <- next_state(sub_game) }
    env$winner <- sub_game$winner
  }

  # pprint(env)
  
  # Add the cards to the winner's deck
  if (env$winner == 'player1') {
    pushback(env$player1, env$p1_card)
    pushback(env$player1, env$p2_card)
  } else {
    pushback(env$player2, env$p2_card)
    pushback(env$player2, env$p1_card)
  }
  
  # If a player's deck is empty, the other player won the game. Add the winning
  # player's current deck to the environment `env`
  env$round <- env$round + 1
  if (length(env$player1) == 0) { env$winning_hand <- unlist(as.list(env$player2)) }
  if (length(env$player2) == 0) { env$winning_hand <- unlist(as.list(env$player1)) }
  
  env # Return the modified environment
}

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

game_state <- parse_input(real_input)

while (is.null(game_state$winning_hand)) { 
  game_state <- next_state(game_state) 
  if (game_state$round %% 25 == 0) { pprint(game_state) }
}

cards_in_winning_hand <- length(game_state$winning_hand)
answer2 <- sum(game_state$winning_hand * cards_in_winning_hand:1)

```

I guess that’ll show that crab. Unless you lost again…

Important to note that, to successfully get a hash of the game state, the `player1` and `player2` stacks (representing hands) need to be converted to lists, otherwise you’re just hashing two pointers (that don’t change) over and over again.

## Wrap-Up

This one was a bit fiddly (hence the `pprint()` function). There always seemed to be one small detail I missed from the instructions. Like passing the list of prior hands to the recursive sub-games, for example. I initially thought each sub-game was supposed to start with it’s own set of `past_states`. I also initially missed the fact that sub-game decks only consisted of the first `n` cards from that deck, where `n` was the number each player played in the round that initiated the sub-game. Once I re-read the instructions enough times (and made a couple of educated guesses), it all came out. The feeling of success was palpable!

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