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

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

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

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