t22.rs

use std::collections::{HashSet, VecDeque};

use anyhow::Context as _;

pub type Card = usize;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Winner {
    Player1,
    Player2,
}

#[derive(Debug, Clone, Hash, PartialEq, Eq)]
pub struct Deck(VecDeque<Card>);

impl Deck {
    pub fn len(&self) -> usize {
        self.0.len()
    }

    pub fn is_empty(&self) -> bool {
        self.0.is_empty()
    }

    pub fn peek(&mut self) -> Option<Card> {
        self.0.get(0).copied()
    }

    pub fn draw(&mut self) -> Option<Card> {
        self.0.pop_front()
    }

    pub fn put(&mut self, card: Card) -> &mut Self {
        self.0.push_back(card);
        self
    }

    pub fn score(&self) -> usize {
        self.0
            .iter()
            .rev()
            .enumerate()
            .map(|(idx, card)| (idx + 1) * card)
            .sum()
    }

    pub fn clone_depth(&self, depth: usize) -> Self {
        Self(self.0.iter().copied().take(depth).collect())
    }
}

#[derive(Debug, Clone, Hash, PartialEq, Eq)]
pub struct Game {
    player1: Deck,
    player2: Deck,
}

impl Game {
    pub fn winner(&self) -> (Winner, usize) {
        if self.player1.is_empty() {
            (Winner::Player2, self.player2.score())
        } else {
            (Winner::Player1, self.player1.score())
        }
    }

    pub fn draw2(&mut self) -> Option<(Card, Card)> {
        if self.player1.is_empty() || self.player2.is_empty() {
            None
        } else {
            Some((self.player1.draw()?, self.player2.draw()?))
        }
    }

    pub fn clone_depth(&self, depth1: usize, depth2: usize) -> Self {
        Self {
            player1: self.player1.clone_depth(depth1),
            player2: self.player2.clone_depth(depth2),
        }
    }
}

peg::parser! {
    grammar parse() for str {
        rule card() -> Card
            = n:$(['0'..='9']+) { n.parse().unwrap() }

        rule deck() -> Deck
            = d:(card() ** "\n") "\n" {
                Deck(d.into_iter().collect())
            }

        pub rule input() -> Game
            = "Player 1:\n" player1:deck() "\n" "Player 2:\n" player2:deck() {
                Game { player1, player2 }
            }
    }
}

fn play_normal(mut game: Game) -> (Winner, usize) {
    while let Some((card1, card2)) = game.draw2() {
        if card1 > card2 {
            game.player1.put(card1).put(card2);
        } else {
            game.player2.put(card2).put(card1);
        }
    }
    game.winner()
}

fn play_recursive(mut game: Game) -> (Winner, usize) {
    let mut previous_states: HashSet<Game> = HashSet::new();
    loop {
        if previous_states.contains(&game) {
            break (Winner::Player1, game.player1.score());
        }

        previous_states.insert(game.clone());

        if let Some((card1, card2)) = game.draw2() {
            if game.player1.len() < card1 || game.player2.len() < card2 {
                if card1 > card2 {
                    game.player1.put(card1).put(card2);
                } else {
                    game.player2.put(card2).put(card1);
                }
            } else {
                match play_recursive(game.clone_depth(card1, card2)) {
                    (Winner::Player1, _) => game.player1.put(card1).put(card2),
                    (Winner::Player2, _) => game.player2.put(card2).put(card1),
                };
            }
        } else {
            break game.winner();
        }
    }
}

fn main() -> anyhow::Result<()> {
    let game = {
        use std::io::{self, Read as _};

        let mut buf = String::new();
        io::stdin()
            .read_to_string(&mut buf)
            .context("failed to read STDIN")?;
        parse::input(&buf).context("failed to parse input")?
    };

    let (winner, score) = play_normal(game.clone());
    println!("Part 1: {} (winner: {:?})", score, winner);

    let (winner, score) = play_recursive(game);
    println!("Part 2: {} (winner: {:?})", score, winner);

    Ok(())
}