142 lines
4.5 KiB
Rust
142 lines
4.5 KiB
Rust
use std::collections::{VecDeque, HashSet, HashMap};
|
|
use std::io::BufRead;
|
|
|
|
fn play(mut deck1: VecDeque<u32>, mut deck2: VecDeque<u32>) -> VecDeque<u32> {
|
|
if deck1.len() == 0 {
|
|
deck2
|
|
} else if deck2.len() == 0 {
|
|
deck1
|
|
} else {
|
|
let card1 = deck1.pop_front().unwrap();
|
|
let card2 = deck2.pop_front().unwrap();
|
|
if card1 > card2 {
|
|
deck1.push_back(card1);
|
|
deck1.push_back(card2);
|
|
} else {
|
|
deck2.push_back(card2);
|
|
deck2.push_back(card1);
|
|
}
|
|
|
|
play(deck1, deck2)
|
|
}
|
|
}
|
|
|
|
// play recusive not recursive because of stack overflow
|
|
fn play_recursive(deck1: VecDeque<u32>, deck2: VecDeque<u32>) -> u32 {
|
|
let mut all_previous = HashMap::<u32, HashSet<(Vec<u32>, Vec<u32>)>>::new();
|
|
let mut stack: Vec<(u32, VecDeque<u32>, VecDeque<u32>)> = Vec::new();
|
|
let mut nb_games = 0;
|
|
let mut score = 0;
|
|
|
|
stack.push((0, deck1, deck2));
|
|
|
|
while score == 0 {
|
|
let (game, mut deck1, mut deck2) = stack.pop().unwrap();
|
|
if deck1.len() == 0 || deck2.len() == 0 {
|
|
if let Some((super_game, mut super_deck1, mut super_deck2)) = stack.pop() {
|
|
let card1 = super_deck1.pop_front().unwrap();
|
|
let card2 = super_deck2.pop_front().unwrap();
|
|
if deck2.len() == 0 {
|
|
super_deck1.push_back(card1);
|
|
super_deck1.push_back(card2);
|
|
} else {
|
|
super_deck2.push_back(card2);
|
|
super_deck2.push_back(card1);
|
|
}
|
|
stack.push((super_game, super_deck1, super_deck2));
|
|
all_previous.remove(&game);
|
|
} else {
|
|
score = compute_score(deck1) + compute_score(deck2);
|
|
}
|
|
} else {
|
|
let current_config = (deck1.iter().cloned().collect(), deck2.iter().cloned().collect());
|
|
let previous = all_previous.entry(game).or_insert(HashSet::new());
|
|
|
|
if previous.contains(¤t_config) {
|
|
// make player 2 loses so player 1 wins, short circuit infite loop
|
|
stack.push((game, deck1, VecDeque::new()));
|
|
} else {
|
|
let card1 = deck1.pop_front().unwrap();
|
|
let card2 = deck2.pop_front().unwrap();
|
|
|
|
if deck1.len() >= card1 as usize && deck2.len() >= card2 as usize {
|
|
nb_games += 1;
|
|
let sub_deck1 = deck1.iter().cloned().take(card1 as usize).collect();
|
|
let sub_deck2 = deck2.iter().cloned().take(card2 as usize).collect();
|
|
deck1.push_front(card1);
|
|
deck2.push_front(card2);
|
|
stack.push((game, deck1, deck2));
|
|
stack.push((nb_games, sub_deck1, sub_deck2));
|
|
} else {
|
|
previous.insert(current_config);
|
|
if card1 > card2 {
|
|
deck1.push_back(card1);
|
|
deck1.push_back(card2);
|
|
} else {
|
|
deck2.push_back(card2);
|
|
deck2.push_back(card1);
|
|
}
|
|
stack.push((game, deck1, deck2));
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
score
|
|
}
|
|
|
|
fn compute_score(deck: VecDeque<u32>) -> u32 {
|
|
deck.iter().rev().enumerate().map(|(idx, card)| (idx + 1) as u32 * card).sum()
|
|
}
|
|
|
|
|
|
fn parse_deck(s: &str) -> VecDeque<u32> {
|
|
s.lines().skip(1).map(|card| card.parse::<u32>().unwrap()).collect()
|
|
}
|
|
|
|
|
|
fn parse_input<F: BufRead> (mut input: F) -> VecDeque<VecDeque<u32>> {
|
|
let mut buffer = String::new();
|
|
input.read_to_string(&mut buffer).unwrap();
|
|
buffer.split("\n\n").map(parse_deck).collect()
|
|
}
|
|
|
|
pub fn part1<F: BufRead> (input: F) {
|
|
let mut decks = parse_input(input);
|
|
let deck1 = decks.pop_front().unwrap();
|
|
let deck2 = decks.pop_front().unwrap();
|
|
let final_deck = play(deck1, deck2);
|
|
println!("{:?}", compute_score(final_deck));
|
|
}
|
|
|
|
pub fn part2<F: BufRead> (input: F) {
|
|
let mut decks = parse_input(input);
|
|
let deck1 = decks.pop_front().unwrap();
|
|
let deck2 = decks.pop_front().unwrap();
|
|
let score = play_recursive(deck1, deck2);
|
|
println!("{:?}", score);
|
|
}
|
|
|
|
|
|
#[cfg(test)]
|
|
mod test {
|
|
use super::*;
|
|
#[test]
|
|
fn test_rec() {
|
|
let input = "Player 1:
|
|
43
|
|
19
|
|
|
|
Player 2:
|
|
2
|
|
29
|
|
14";
|
|
|
|
let mut decks = parse_input(input.as_bytes());
|
|
let deck1 = decks.pop_front().unwrap();
|
|
let deck2 = decks.pop_front().unwrap();
|
|
// test if no stack overflow
|
|
play_recursive(deck1, deck2);
|
|
}
|
|
}
|