You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

98 lines
3.0 KiB

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