aoc2020/src/bin/day22.rs

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

type Deck = VecDeque<u32>;

const INPUT: &str = include_str!("../../data/day22");

fn parse_player(block: &str) -> (u32, Deck) {
    let block = block.strip_prefix("Player ").unwrap();
    let player = block[..1].parse::<u32>().unwrap();
    let block = block[1..].strip_prefix(":").unwrap().trim();
    let deck = block.lines().map(|s| s.parse::<u32>().unwrap()).collect();
    (player, deck)
}

fn score(deck: &Deck) -> u64 {
    deck.iter().rev().enumerate().map(|(pos, &value)| {
        ((pos + 1) as u64) * (value as u64)
    }).sum::<u64>()
}

fn crab(mut deck1: Deck, mut deck2: Deck) {
    while !deck1.is_empty() && !deck2.is_empty() {
        let c1 = deck1.pop_front().unwrap();
        let c2 = deck2.pop_front().unwrap();
        if c1 > c2 {
            deck1.push_back(c1);
            deck1.push_back(c2);
        } else {
            assert!(c2 > c1);
            deck2.push_back(c2);
            deck2.push_back(c1);
        }
    }
    if deck2.is_empty() {
        println!("Player 1 won: {:?}", deck1);
        println!("Score: {}", score(&deck1));
    } else {
        println!("Player 2 won: {:?}", deck2);
        println!("Score: {}", score(&deck2));
    }
}

fn _crab_rec(deck1: &mut Deck, deck2: &mut Deck) -> bool {
    // println!("Rec Combat: {:?}, {:?}", deck1, deck2);
    let mut previous_rounds = HashSet::new();
    while !deck1.is_empty() && !deck2.is_empty() {
        if !previous_rounds.insert((deck1.clone(), deck2.clone())) {
            // prevent infinite loop; player 1 wins
            return true;
        }
        let c1 = deck1.pop_front().unwrap();
        let c2 = deck2.pop_front().unwrap();
        let p1_won = if deck1.len() >= c1 as usize && deck2.len() >= c2 as usize {
            let mut deck1: Deck = deck1.iter().copied().take(c1 as usize).collect();
            let mut deck2: Deck = deck2.iter().copied().take(c2 as usize).collect();
            assert_eq!(deck1.len(), c1 as usize);
            assert_eq!(deck2.len(), c2 as usize);
            // recurse
            _crab_rec(&mut deck1, &mut deck2)
        } else {
            assert_ne!(c1, c2);
            c1 > c2
        };
        if p1_won {
            deck1.push_back(c1);
            deck1.push_back(c2);
        } else {
            deck2.push_back(c2);
            deck2.push_back(c1);
        }
    }
    deck2.is_empty()
}

fn crab_rec(mut deck1: Deck, mut deck2: Deck) {
    let p1_won = _crab_rec(&mut deck1, &mut deck2);
    if p1_won {
        println!("Player 1 won recursive combat: {:?}", deck1);
        println!("Score: {}", score(&deck1));
    } else {
        println!("Player 2 won recursive combat: {:?}", deck2);
        println!("Score: {}", score(&deck2));
    }
}

fn main() {
    let (deck1, deck2) = {
        let pos = INPUT.find("\n\n").unwrap();
        let (id1, deck1) = parse_player(&INPUT[..pos]);
        let (id2, deck2) = parse_player(&INPUT[pos+2..]);
        assert_eq!(id1, 1);
        assert_eq!(id2, 2);
        (deck1, deck2)
    };

    crab(deck1.clone(), deck2.clone());
    crab_rec(deck1, deck2);
}