109 lines
2.5 KiB
Rust
109 lines
2.5 KiB
Rust
#![feature(test)]
|
|
|
|
use itertools::Itertools;
|
|
use num::Integer;
|
|
use rayon::prelude::*;
|
|
use regex::Regex;
|
|
use rustc_hash::FxHashMap;
|
|
|
|
#[derive(Debug)]
|
|
struct Input {
|
|
instructions: Vec<Instruction>,
|
|
nodes: Vec<Node>,
|
|
start: usize,
|
|
goal: usize,
|
|
}
|
|
|
|
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
|
|
enum Instruction {
|
|
Left,
|
|
Right,
|
|
}
|
|
|
|
#[derive(Debug, Clone, Copy)]
|
|
struct Node {
|
|
left: usize,
|
|
right: usize,
|
|
start: bool,
|
|
goal: bool,
|
|
}
|
|
|
|
fn setup(input: &str) -> Input {
|
|
let instructions = input
|
|
.lines()
|
|
.next()
|
|
.unwrap()
|
|
.bytes()
|
|
.map(|b| match b {
|
|
b'L' => Instruction::Left,
|
|
b'R' => Instruction::Right,
|
|
_ => panic!(),
|
|
})
|
|
.collect();
|
|
|
|
let names = input
|
|
.lines()
|
|
.skip(2)
|
|
.enumerate()
|
|
.map(|(i, line)| (line.split_whitespace().next().unwrap(), i))
|
|
.collect::<FxHashMap<_, _>>();
|
|
|
|
let regex = Regex::new(r"([^, ]+) = \(([^, ]+), ([^, ]+)\)").unwrap();
|
|
let nodes = input
|
|
.lines()
|
|
.skip(2)
|
|
.map(|line| {
|
|
let captures = regex.captures(line).unwrap();
|
|
let left = names[&captures[2]];
|
|
let right = names[&captures[3]];
|
|
Node {
|
|
left,
|
|
right,
|
|
start: captures[1].ends_with('A'),
|
|
goal: captures[1].ends_with('Z'),
|
|
}
|
|
})
|
|
.collect();
|
|
|
|
Input {
|
|
instructions,
|
|
nodes,
|
|
start: names.get("AAA").copied().unwrap_or_default(),
|
|
goal: names.get("ZZZ").copied().unwrap_or_default(),
|
|
}
|
|
}
|
|
|
|
fn solve(input: &Input, start: usize, is_goal: impl Fn(usize) -> bool) -> usize {
|
|
Itertools::take_while_inclusive(
|
|
input
|
|
.instructions
|
|
.iter()
|
|
.cycle()
|
|
.scan(start, |p, instruction| {
|
|
let node = input.nodes[*p];
|
|
*p = match instruction {
|
|
Instruction::Left => node.left,
|
|
Instruction::Right => node.right,
|
|
};
|
|
Some(*p)
|
|
}),
|
|
|&p| !is_goal(p),
|
|
)
|
|
.count()
|
|
}
|
|
|
|
fn part1(input: &Input) -> usize {
|
|
solve(input, input.start, |p| p == input.goal)
|
|
}
|
|
|
|
fn part2(input: &Input) -> usize {
|
|
input
|
|
.nodes
|
|
.par_iter()
|
|
.enumerate()
|
|
.filter(|(_, node)| node.start)
|
|
.map(|(i, _)| solve(input, i, |p| input.nodes[p].goal))
|
|
.reduce(|| 1, |a, b| a.lcm(&b))
|
|
}
|
|
|
|
aoc::main!(2023, 8, ex: 1[a], 2[a], 3[b]);
|