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!

The Leaderboards

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
Haskell	1

Merry Coding!

Comments

[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 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);
    }
}

[Benedict Gaster]

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

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

[Yuan Gao]

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

[Mustafa Haddara]

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

[Bruno AMS]

In .NET 6 (1s)

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

[Thibaut Patel]

My JavaScript video walkthrough: