96 lines
2.9 KiB
Rust
96 lines
2.9 KiB
Rust
use std::collections::{VecDeque, HashMap};
|
|
use std::io::BufRead;
|
|
|
|
|
|
fn play(mut game: VecDeque<usize>, moves: usize) -> String {
|
|
let len = game.len();
|
|
for _ in 0..moves {
|
|
let current = game[0];
|
|
let mut selected: VecDeque<_> = game.drain(1..4).collect();
|
|
let idx_map: HashMap<usize, usize> = game.iter().enumerate().skip(1).map(|(i, v)| (*v, i)).collect();
|
|
|
|
let mut dest = current;
|
|
while !idx_map.contains_key(&dest) {
|
|
dest = (dest + len - 2) % len + 1;
|
|
}
|
|
|
|
let dest_index = idx_map[&dest];
|
|
|
|
let mut end = game.split_off(dest_index + 1);
|
|
game.append(&mut selected);
|
|
game.append(&mut end);
|
|
|
|
game.rotate_left(1);
|
|
}
|
|
|
|
game.iter().cycle().skip_while(|v| **v != 1).skip(1).take(len - 1).map(|v| v.to_string()).collect::<Vec<_>>().join("")
|
|
}
|
|
|
|
fn play_optimized(init: Vec<usize>, cup_count: usize, moves: usize) -> usize {
|
|
let init_len = init.len();
|
|
let mut game = vec![0; init_len];
|
|
game.reserve(cup_count - init_len);
|
|
for (idx, &el) in init.iter().take(init_len - 1).enumerate() {
|
|
game[el - 1] = init[idx + 1] - 1;
|
|
}
|
|
game[init[init_len - 1] - 1] = init_len;
|
|
for cup in init_len..(cup_count - 1) {
|
|
game.push(cup + 1)
|
|
}
|
|
game.push(init[0] - 1);
|
|
|
|
let mut current = init[0] - 1;
|
|
let mut selected = vec![0; 3];
|
|
let mut destination;
|
|
|
|
for _ in 0..moves {
|
|
selected[0] = game[current];
|
|
selected[1] = game[selected[0]];
|
|
selected[2] = game[selected[1]];
|
|
game[current] = game[selected[2]];
|
|
|
|
destination = current;
|
|
loop {
|
|
destination = (destination + cup_count - 1) % cup_count;
|
|
if destination != selected[0] && destination != selected[1] && destination != selected[2] {
|
|
break
|
|
}
|
|
}
|
|
|
|
game[selected[2]] = game[destination];
|
|
game[destination] = selected[0];
|
|
current = game[current];
|
|
}
|
|
|
|
(game[0] + 1) * (game[game[0]] + 1)
|
|
}
|
|
|
|
pub fn part1<F: BufRead> (mut input: F) {
|
|
let mut buffer = String::new();
|
|
input.read_to_string(&mut buffer).unwrap();
|
|
let game = buffer.trim().chars().map(|c| c as usize - '0' as usize).collect();
|
|
println!("{}", play(game, 100));
|
|
}
|
|
|
|
pub fn part2<F: BufRead> (mut input: F) {
|
|
let mut buffer = String::new();
|
|
input.read_to_string(&mut buffer).unwrap();
|
|
let game = buffer.trim().chars().map(|c| c as usize - '0' as usize).collect();
|
|
println!("{}", play_optimized(game, 1000000, 10000000));
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod test {
|
|
use super::*;
|
|
#[test]
|
|
fn test_game() {
|
|
assert_eq!("92658374", play((&[3, 8, 9, 1, 2, 5, 4, 6, 7]).iter().cloned().collect(), 10));
|
|
assert_eq!("67384529", play((&[3, 8, 9, 1, 2, 5, 4, 6, 7]).iter().cloned().collect(), 100));
|
|
}
|
|
|
|
#[test]
|
|
fn test_game_optimize() {
|
|
assert_eq!(149245887792, play_optimized(vec![3, 8, 9, 1, 2, 5, 4, 6, 7], 1000000, 10000000));
|
|
}
|
|
}
|