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

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 input = std::fs::read_to_string("./input.txt").unwrap(); 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); } } 

parse :: String -> ([Int], [Int]) parse is = let xs = splitWhen (=="Player 2:") (lines is) players = (filter (/="") (tail (head xs)), head (tail xs)) in bimap (map read) (map read) players 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] task1 players = task1 (round players) 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 print (task1 is) print (task2 is) 

"""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: seen.add(str(p1) + str(p2)) 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)) 

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 i++; // skip the header 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`; return fs.readFileSync(fname, 'utf8').split('\n'); }; main(); 

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)))) 

var players = File.ReadAllText("input.txt") .Split(":").Where(p => !p.StartsWith("Player")) .Select((p, i) => (Player: i + 1, Deck: new Queue<int>(p.Split('\n').Where(n => char.IsNumber(n, 0)).Select(q => int.Parse(q))))) .ToArray(); int Play((int Player, Queue<int> Deck)[] players, bool enableSubgame = false) { HashSet<string> previousRounds = new(); while (players.Count(p => p.Deck.Any()) > 1) { if (!previousRounds.Add(string.Join("@", players.Select(p => $"{string.Join("", p.Deck)}")))) return 1; var roundPlayerCards = players.Select(p => (p.Player, Card: p.Deck.Dequeue())).ToArray(); var (roundWinningPlayer, winningDeck) = players.First(p => p.Player == roundPlayerCards.MaxBy(p => p.Card).Player); var haveSubgame = roundPlayerCards.All(cp => players.Any(c => c.Player == cp.Player && c.Deck.Count >= cp.Card)); if (haveSubgame && enableSubgame) { var subgame = players.Select(p => (p.Player, Deck: new Queue<int>(p.Deck.Take(roundPlayerCards.First(c => c.Player == p.Player).Card)))).ToArray(); roundWinningPlayer = Play(subgame, enableSubgame); (_, winningDeck) = players.First(p => p.Player == roundWinningPlayer); } foreach (var (_, card) in roundPlayerCards.OrderByDescending(p => p.Player == roundWinningPlayer)) winningDeck.Enqueue(card); } return players.First(p => p.Deck.Any()).Player; } var playerWinning = Play(players, enableSubgame: true); var score = players.First(p => p.Player == playerWinning).Deck.Reverse().Select((v, i) => v * (i + 1)).Sum();