Skip to content

Instantly share code, notes, and snippets.

@typester
Created December 10, 2023 17:00
Show Gist options
  • Save typester/6e36f09be77a72e6cb683f5156bdd5ef to your computer and use it in GitHub Desktop.
Save typester/6e36f09be77a72e6cb683f5156bdd5ef to your computer and use it in GitHub Desktop.
2023 Advent of Code Day 8
use std::collections::HashMap;
use lazy_static::lazy_static;
use regex::Regex;
const INPUT: &str = "..snip..";
fn main() {
let mut iter = INPUT.lines();
let ops = parse_op(iter.next().unwrap());
let mut op_iter = ops.iter().cycle().enumerate();
let paths = parse_paths(&mut iter);
let mut count = 0;
let mut p = String::from("AAA");
while let Some((i, op)) = op_iter.next() {
if p == "ZZZ" {
count = i;
break;
}
let path = paths.get(&p).unwrap();
match op {
Op::L => p = path.0.clone(),
Op::R => p = path.1.clone(),
}
}
println!("part1: {}", count);
let mut p: Vec<String> = paths.keys().filter(|k| k.ends_with("A")).map(|k| k.clone()).collect();
let mut op_iter = ops.iter().cycle().enumerate();
let mut loops: HashMap<usize, usize> = HashMap::new();
while let Some((i, op)) = op_iter.next() {
p = p.iter().enumerate().map(|(n, s)| {
if s.ends_with("Z") {
loops.entry(n).or_insert(i);
};
let path = paths.get(s).unwrap();
match op {
Op::L => path.0.clone(),
Op::R => path.1.clone(),
}
}).collect();
if loops.len() == p.len() {
break;
}
}
let loops: Vec<usize> = loops.values().map(|v| *v).collect();
println!("part2: {}", lcm_of_list(&loops));
}
enum Op {
L,
R,
}
fn parse_op(s: &str) -> Vec<Op> {
s.chars().map(|c| match c {
'L' => Op::L,
'R' => Op::R,
_ => panic!("invalid op"),
}).collect()
}
fn parse_paths(lines: &mut dyn Iterator<Item = &str>) -> HashMap<String, (String, String)> {
lazy_static! {
static ref RE: Regex = Regex::new(r"(\w+) = \((\w+), (\w+)\)").unwrap();
}
let mut paths: HashMap<String, (String, String)> = HashMap::new();
while let Some(s) = lines.next() {
if s == "" { continue }
if let Some(caps) = RE.captures(s) {
paths.insert(caps[1].to_string(), (caps[2].to_string(), caps[3].to_string()));
}
}
paths
}
fn gcd(a: usize, b: usize) -> usize {
if b == 0 {
a
} else {
gcd(b, a % b)
}
}
fn lcm(a: usize, b: usize) -> usize {
a / gcd(a, b) * b
}
fn lcm_of_list(numbers: &[usize]) -> usize {
numbers.iter().fold(1, |l, &num| lcm(l, num))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment