# Advent of Code 2020 - Day 22

By Eric Burden | December 23, 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 22 - Crab Combat

Find the problem description HERE.

## 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.

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

test_input <- c(
"Player 1:",
"9", "2", "6", "3", "1",
"",
"Player 2:",
"5", "8", "4", "7", "10"
)

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
)

# 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 out favor. Guess the crab wasn’t paying attention when it agreed to that rule. # 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!