Ryan Palo

Posted on

# Advent of Code 2020 Solution Megathread - Day 22: Crab Combat

We're getting close. I can comfortably say that it's Christmas Eve Eve Eve. Three Eves. We Three Eves. Actually, not a bad band name. Sort of a holiday-themed Destiny's Child vibe. Anyways, on to the puzzle.

## The Puzzle

In today’s puzzle, we have gotten so bored on our journey that we've inexplicably taught a crab how to play cards. We're playing Combat (which I've played as War). Whoever has the highest card each round takes both cards into the bottom of their deck and play proceeds until someone has all the cards. Good luck!

As always, this is the spot where I’ll plug any leaderboard codes shared from the community.

``````Ryan's Leaderboard: 224198-25048a19
``````

If you want to generate your own leaderboard and signal boost it a little bit, send it to me either in a DEV message or in a comment on one of these posts and I'll add it to the list above.

## Yesterday’s Languages

Updated 07:10AM 12/22/2020 PST.

Language Count
JavaScript 2
Rust 1
Python 1

Merry Coding!

Neil Gall

I got there in the end on this one but I have to admit I don't know why. I was storing the complete game state (both players) in a HashSet for recording the history. This passed the tests but gave the wrong answer for the final score. After reading another thread online (the first time I've looked this year!) someone suggested you only need to store the first player's state as this is enough to uniquely identity a game position. That feels like an optimisation, not a logic change but I did it anyway and now it produces the correct answer. I feel bad for writing code I don't understand!

``````use log::debug;
use std::collections::{HashSet, HashMap, VecDeque};
use parser::*;

// -- model

type Card = i64;
type Score = i64;
type PlayerID = usize;
type Player = VecDeque<Card>;
type GameState = Vec<Player>;
type GameMemos = HashMap<Player, PlayerID>;

#[derive(Debug, Copy, Clone, PartialEq)]
enum Rules {
Normal,
Recursive
}

#[derive(Debug, PartialEq)]
struct Game {
players: GameState,
history: HashSet<Player>,
prefix: String,
round: usize
}

impl Game {
fn new(players: GameState) -> Self {
Game {
players,
history: HashSet::new(),
prefix: "".to_string(),
round: 0
}
}

fn make_sub_game(&self, drawn: &Vec<(PlayerID, Card)>) -> Game {
let mut game = Game::new(
drawn.iter().map(|(player, card)|
self.players[*player].iter().take(*card as usize).copied().collect()
).collect()
);
game.prefix = format!("{}  ", self.prefix);
game
}

fn cards(&self, player: PlayerID) -> Vec<Card> {
self.players[player].iter().copied().collect()
}

fn should_recurse(&self, cards: &Vec<(PlayerID, Card)>) -> bool {
cards.iter().all(|(player, card)| self.players[*player].len() >= *card as usize)
}

fn play_round(&mut self, rules: Rules, memos: &mut GameMemos) {
self.round += 1;
debug!("{}round {}", self.prefix, self.round);
debug!("{}player 1 {:?}", self.prefix, self.players[0]);
debug!("{}player 2 {:?}", self.prefix, self.players[1]);

let repeats_previous_round = self.history.contains(&self.players[0]);
self.history.insert(self.players[0].clone());

let mut top_cards: Vec<(PlayerID, Card)> =
self.players.iter_mut().filter_map(|p| p.pop_front()).enumerate().collect();

let mut winner = None;

if rules == Rules::Recursive {
if repeats_previous_round {
winner = Some(0);

} else if self.should_recurse(&top_cards) {
match memos.get(&self.players[0]) {
Some(w) => {
winner = Some(*w);
}
None => {
let mut sub_game = self.make_sub_game(&top_cards);
sub_game.play_until_over(Rules::Recursive, memos);
let w = sub_game.winner();
winner = Some(w);
memos.insert(self.players[0].clone(), w);
}
}
}
}

if winner == None {
// normal rules
winner = top_cards.iter().max_by_key(|(_, card)| card).map(|(player, _)| *player);
}

let winner = winner.unwrap();

top_cards.sort_by_key(|(player, _)| *player != winner);

for (_, card) in top_cards {
self.players[winner].push_back(card);
}

}

fn over(&self) -> bool {
self.players.iter().any(|p| p.is_empty())
}

fn play_until_over(&mut self, rules: Rules, memos: &mut GameMemos) {
while !self.over() {
self.play_round(rules, memos);
}
}

fn winner(&self) -> PlayerID {
self.players.iter().enumerate().find(|(_, cards)| !cards.is_empty()).unwrap().0
}

fn winning_score(&self) -> Score {
let winner: &Player = self.players.iter().find(|p| !p.is_empty()).unwrap();
winner.iter().rev().enumerate().fold(
0,
|score, (index, card)| score + card * ((index+1) as Score)
)
}
}

// -- parser

fn parse_input(input: &str) -> ParseResult<Game> {
let player_tag = integer.between(match_literal("Player "), match_literal(":"));
let cards = one_or_more(whitespace_wrap(integer)).map(|cards| cards.into_iter().collect());
let player = right(player_tag, cards);
let game = one_or_more(player).map(Game::new);
game.parse(input)
}

// -- problems

fn part1(game: &mut Game) -> Score {
game.play_until_over(Rules::Normal, &mut GameMemos::new());
game.winning_score()
}

fn part2(game: &mut Game) -> Score {
game.play_until_over(Rules::Recursive, &mut GameMemos::new());
game.winning_score()
}

fn main() {
env_logger::init();
let mut game = parse_input(&input).unwrap().1;
println!("part 1 {}", part1(&mut game));

let mut game = parse_input(&input).unwrap().1;
println!("part 2 {}", part2(&mut game))
}

#[cfg(test)]
mod tests {
use super::*;

fn test_game() -> Game {
Game::new(vec![
vec![9, 2, 6, 3, 1].into_iter().collect(),
vec![5, 8, 4, 7, 10].into_iter().collect()
])
}

#[test]
fn test_parser() {
let game = parse_input(
"Player 1:
9
2
6
3
1

Player 2:
5
8
4
7
10");
assert_eq!(game, Ok(("", test_game())));
}

#[test]
fn test_play_round() {
let mut game = test_game();
game.play_round(Rules::Normal, &mut GameMemos::new());
assert_eq!(game.cards(0), vec![2, 6, 3, 1, 9, 5]);
assert_eq!(game.cards(1), vec![8, 4, 7, 10]);

game.play_round(Rules::Normal, &mut GameMemos::new());
assert_eq!(game.cards(0), vec![6, 3, 1, 9, 5]);
assert_eq!(game.cards(1), vec![4, 7, 10, 8, 2]);

game.play_round(Rules::Normal, &mut GameMemos::new());
assert_eq!(game.cards(0), vec![3, 1, 9, 5, 6, 4]);
assert_eq!(game.cards(1), vec![7, 10, 8, 2]);
}

#[test]
fn test_game_over() {
let mut game = test_game();
game.play_until_over(Rules::Normal, &mut GameMemos::new());
assert_eq!(game.round, 29);
}

#[test]
fn test_score() {
let mut game = test_game();
game.play_until_over(Rules::Normal, &mut GameMemos::new());
assert_eq!(game.winning_score(), 306);
}

#[test]
fn test_infinite_recursion_rule_works() {
let mut game = Game::new(vec![
vec![43, 19].into_iter().collect(),
vec![2, 29, 14].into_iter().collect()
]);
game.play_until_over(Rules::Recursive, &mut GameMemos::new());
}

#[test]
fn test_play_recursive() {
let mut game = test_game();
game.play_until_over(Rules::Recursive, &mut GameMemos::new());

assert_eq!(game.winning_score(), 291);
assert_eq!(game.round, 17);
assert_eq!(game.winner(), 1);
}
}
``````

Benedict Gaster • Edited

Ah today Haskell was a great choice, had fun and got it done really quick, which was lucky as spent a large amount of the day baking ginger bread houses for the kids to cover in icing and sweets :-)

``````parse :: String -> ([Int], [Int])
parse is = let xs = splitWhen (=="Player 2:") (lines is)

task1 :: ([Int], [Int]) -> Int
task1 ([], p2) = sum \$ zipWith (*) p2 [length p2, length p2-1..1]
task1 (p1, [])  = sum \$ zipWith (*) p1 [length p1, length p1-1..1]
where
round (t:ts, t':ts') | t > t'    = (ts ++ [t,t'], ts')
| otherwise =  (ts, ts' ++ [t',t])

task2 = result . game S.empty
where
result ([], p2) = sum \$ zipWith (*) p2 [length p2, length p2-1..1]
result (p1, []) = sum \$ zipWith (*) p1 [length p1, length p1-1..1]

game _ (xs, []) = (xs, [])
game _ ([], ys) = ([], ys)
game s (xs, ys) | (xs, ys) `S.member` s = (xs, [])
| otherwise             = round (S.insert (xs, ys) s) xs ys

round s (x:xs) (y:ys)
| (x > length xs || y > length ys) && x < y = game s (xs, ys ++ [y, x])
| (x > length xs || y > length ys) && x > y = game s (xs ++ [x, y], ys)
| otherwise = case game S.empty (take x xs, take y ys) of
(_, []) -> game s (xs ++ [x, y], ys)
([], _) -> game s (xs, ys ++ [y, x])

main = do
is <- readFile "day22_input" <&> parse
``````

Ryan Palo

This one seemed pretty straightforward, so I knocked it out in Python in an effort to get caught up. I forgot about the "no repeats" rule and stared at my terminal recursing infinitely for a while. Also, `deque` was a great idea, but I didn't realize you couldn't slice a `deque` in Python, which made copying them partially a bit awkward.

``````"""Day 22: Crab Combat

Play a crab in Combat (War) and calculate the score of the winner.
"""

from collections import deque
from copy import deepcopy

def parse(filename):
"""Parses the input file into a list of players numbers.  Input file
has the format:
Player 1:
1
2
3

Player 2:
4
5
6

Supports arbitrary numbers of players.
"""
players = [deque()]
current = 0
with open(filename, "r") as f:
for line in f:
line = line.strip()

if line.isnumeric():
players[current].append(int(line))
continue

if not line:
current += 1
players.append(deque())

return players

def part1(players):
"""Simulate a game of war and then calculate the score of the
winner.
"""
while all(player for player in players):
plays = [player.popleft() for player in players]
winner = max((value, ind) for (ind, value) in enumerate(plays))
players[winner[1]].extend(sorted(plays, reverse=True))

return max(calculate_score(player) for player in players)

def recursive_war(p1, p2):
"""Recursive war follows these rules:

1. If a particular configuration has been seen before in a game,
Player 1 automatically wins.
2. Otherwise, if either player's number is greater than the number
of cards they have, the player with the highest number wins.
3. Otherwise, the winner is the winner of a sub-game, where
players play with the 1-nth cards in their deck where n is the
value of their 0th card.

Subgames do not affect parent games' decks (i.e. they are played
with copies).

Returns the calculated score of the winner of the root game's deck.
Not designed for arbitrary #'s of players.  Only two.
"""
seen = set()

while p1 and p2:
if str(p1) + str(p2) in seen:
return 0, calculate_score(p1)
else:
v1, v2 = p1.popleft(), p2.popleft()

if v1 <= len(p1) and v2 <= len(p2):
winner, _score = recursive_war(deque(list(p1)[:v1]), deque(list(p2)[:v2]))
else:
winner = 0 if v1 > v2 else 1

if winner == 0:
p1.extend([v1, v2])
else:
p2.extend([v2, v1])

if p1:
return 0, calculate_score(p1)
else:
return 1, calculate_score(p2)

def calculate_score(player):
"""Calculate the "score" of a player's deck.  Their bottom card
times 1 plus their second bottom card times 2 plus ...
"""
return sum(val * ind
for ind, val in enumerate(reversed(player), start=1))

def part2(players):
"""Calculate the score of a winner of recursive War."""
winner, score = recursive_war(*players)
return score

if __name__ == "__main__":
players = parse("data/day22_test.txt")
assert part1(deepcopy(players)) == 306
assert part2(players) == 291
print("All tests passed!")

players = parse("data/day22.txt")
print("Part 1: ", part1(deepcopy(players)))
print("Part 2: ", part2(players))
``````

Yuan Gao • Edited

A quick bit of python, didn't want to spend too long on it

``````data = open("input.txt").read().splitlines()
player1 = list(map(int, data[1:26]))
player2 = list(map(int, data[28:54]))

def game(depth, player1, player2):
records = {}

while player1 and player2:
key = str(player1)+str(player2)
if key in records:
return 0
records[key] = None

card1 = player1.pop(0)
card2 = player2.pop(0)

if len(player1) >= card1 and len(player2) >= card2:
winner = game(depth+1, player1[:card1], player2[:card2])
else:
winner = card2 > card1

if winner:
player2.extend([card2, card1])
else:
player1.extend([card1, card2])

if depth == 0:
return (player2 if winner else player1)

return winner

windeck = game(0, player1, player2)
print("sum", sum((a+1) * b for a, b in enumerate(reversed(windeck))))
``````

I got mine done but it runs really slowly (~50s)...I'm pretty sure I did something dumb here. There's a lot of loops and I suspect I accidentally went O(n2) or possibly even O(n3)

``````import fs = require('fs');

const solve = (lines: string[]): number => {
let i = 1;
const p1 = [];
const p2 = [];
while (lines[i] !== '') {
p1.push(parseInt(lines[i]));
i++;
}

i++; // skip the blank line
while (lines[i] !== '') {
p2.push(parseInt(lines[i]));
i++;
}

const winning_deck: number[] = conflict(p1, p2);

return winning_deck.map((card, idx) => card * (winning_deck.length - idx)).reduce((total, value) => total + value, 0);
};

const testInput = ['Player 1:', '9', '2', '6', '3', '1', '', 'Player 2:', '5', '8', '4', '7', '10', ''];
// export const testInput = ['Player 1:', '43', '19', '', 'Player 2:', '2', '29', '14', ''];

const conflict = (p1: number[], p2: number[], game_num = 1): number[] => {
const turns = [];
while (p1.length !== 0 && p2.length !== 0) {
// recursive check
if (turn_happened_before(turns, p1, p2)) {
return p1;
}
turns.push([[...p1], [...p2]]);

const p1card = p1.shift(); // removes
const p2card = p2.shift(); // removes

if (p1card <= p1.length && p2card <= p2.length) {
// recurse to determine winner
const subp1 = p1.slice(0, p1card);
const subp2 = p2.slice(0, p2card);
conflict(subp1, subp2, game_num + 1);

// subp1 and subp2 get mutated
if (subp1.length === 0) {
// p2 won
p2.push(p2card);
p2.push(p1card);
} else {
// p1 won
p1.push(p1card);
p1.push(p2card);
}
} else if (p1card > p2card) {
p1.push(p1card);
p1.push(p2card);
} else {
p2.push(p2card);
p2.push(p1card);
}
}
if (p1.length === 0) return p2;
else return p1;
};

const turn_happened_before = (turns: [number[], number[]][], p1: number[], p2: number[]): boolean => {
return turns.some((turn) => arr_eq(turn[0], p1) && arr_eq(turn[1], p2));
};

const arr_eq = (a1: number[], a2: number[]): boolean => a1.every((val, idx) => val === a2[idx]);

const main = () => {
const lines = getLinesFromFile();
console.log(solve(lines));
};

const getLinesFromFile = () => {
const fname = `inputs/day22.txt`;