Gobbel2000

use regex::Regex;
use rustc_hash::FxHashMap;

fn parse(input: &str) -> (Vec<&str>, Vec<&str>) {
    let (towels, designs) = input.split_once("\n\n").unwrap();
    (towels.split(", ").collect(), designs.lines().collect())
}

fn part1(input: String) {
    let (towels, designs) = parse(&input);
    let pat = format!("^({})*$", towels.join("|"));
    let re = Regex::new(&pat).unwrap();
    let count = designs.iter().filter(|d| re.is_match(d)).count();
    println!("{count}");
}

fn n_arrangements<'a>(
    design: &'a str,
    towels: &[&str],
    cache: &mut FxHashMap<&'a str, u64>,
) -> u64 {
    if design.is_empty() {
        return 1;
    }
    if let Some(n) = cache.get(design) {
        return *n;
    }
    let n = towels
        .iter()
        .filter(|t| design.starts_with(*t))
        .map(|t| n_arrangements(&design[t.len()..], towels, cache))
        .sum();
    cache.insert(design, n);
    n
}

fn part2(input: String) {
    let (towels, designs) = parse(&input);
    let sum: u64 = designs
        .iter()
        .map(|d| n_arrangements(d, &towels, &mut FxHashMap::default()))
        .sum();
    println!("{sum}");
}

util::aoc_main!();

use std::collections::VecDeque;

use euclid::{default::*, vec2};

fn parse(input: &str) -> Vec<Point2D<i32>> {
    input
        .lines()
        .map(|l| {
            let (x, y) = l.split_once(',').unwrap();
            Point2D::new(x.parse().unwrap(), y.parse().unwrap())
        })
        .collect()
}

const BOUNDS: Rect<i32> = Rect::new(Point2D::new(0, 0), Size2D::new(71, 71));
const START: Point2D<i32> = Point2D::new(0, 0);
const TARGET: Point2D<i32> = Point2D::new(70, 70);
const N_BYTES: usize = 1024;
const DIRS: [Vector2D<i32>; 4] = [vec2(1, 0), vec2(0, 1), vec2(-1, 0), vec2(0, -1)];

fn adj(
    field: &[[bool; BOUNDS.size.width as usize]],
    v: Point2D<i32>,
) -> impl Iterator<Item = Point2D<i32>> + use<'_> {
    DIRS.iter()
        .map(move |&d| v + d)
        .filter(|&next| BOUNDS.contains(next) && !field[next.y as usize][next.x as usize])
}

fn find_path(field: &[[bool; BOUNDS.size.width as usize]]) -> Option<u32> {
    let mut seen = [[false; BOUNDS.size.width as usize]; BOUNDS.size.height as usize];
    let mut q = VecDeque::from([(START, 0)]);
    seen[START.y as usize][START.x as usize] = true;
    while let Some((v, dist)) = q.pop_front() {
        for w in adj(field, v) {
            if w == TARGET {
                return Some(dist + 1);
            }
            if !seen[w.y as usize][w.x as usize] {
                seen[w.y as usize][w.x as usize] = true;
                q.push_back((w, dist + 1));
            }
        }
    }
    None
}

fn part1(input: String) {
    let bytes = parse(&input);
    let mut field = [[false; BOUNDS.size.width as usize]; BOUNDS.size.height as usize];
    for b in &bytes[..N_BYTES] {
        field[b.y as usize][b.x as usize] = true;
    }
    println!("{}", find_path(&field).unwrap());
}

fn part2(input: String) {
    let bytes = parse(&input);
    let mut field = [[false; BOUNDS.size.width as usize]; BOUNDS.size.height as usize];
    for (i, b) in bytes.iter().enumerate() {
        field[b.y as usize][b.x as usize] = true;
        // We already know from part 1 that below N_BYTES there is a path
        if i > N_BYTES && find_path(&field).is_none() {
            println!("{},{}", b.x, b.y);
            break;
        }
    }
}

util::aoc_main!();

use rustc_hash::FxHashMap;

fn parse(input: &str) -> Option<Program> {
    let mut lines = input.lines();
    let a = lines.next()?.split_once(": ")?.1.parse().ok()?;
    let b = lines.next()?.split_once(": ")?.1.parse().ok()?;
    let c = lines.next()?.split_once(": ")?.1.parse().ok()?;
    lines.next()?;
    let program = lines
        .next()?
        .split_once(": ")?
        .1
        .split(',')
        .map(|s| s.parse())
        .collect::<Result<Vec<u8>, _>>()
        .ok()?;
    Some(Program {
        a,
        b,
        c,
        out: vec![],
        program,
        ip: 0,
    })
}

#[derive(Debug, Clone, Default)]
struct Program {
    a: u64,
    b: u64,
    c: u64,
    out: Vec<u8>,
    program: Vec<u8>,
    ip: usize,
}

impl Program {
    fn run(&mut self) {
        while self.step() {}
    }

    // Returns true if a step was taken, false if it halted
    fn step(&mut self) -> bool {
        let Some(&[opcode, operand]) = &self.program.get(self.ip..self.ip + 2) else {
            return false;
        };
        self.ip += 2;
        match opcode {
            0 => self.adv(self.combo(operand)),
            1 => self.bxl(operand),
            2 => self.bst(self.combo(operand)),
            3 => self.jnz(operand),
            4 => self.bxc(),
            5 => self.out(self.combo(operand)),
            6 => self.bdv(self.combo(operand)),
            7 => self.cdv(self.combo(operand)),
            _ => panic!(),
        }
        true
    }

    fn combo(&self, operand: u8) -> u64 {
        match operand {
            0..=3 => operand as u64,
            4 => self.a,
            5 => self.b,
            6 => self.c,
            _ => unreachable!(),
        }
    }

    fn adv(&mut self, x: u64) {
        self.a >>= x
    }

    fn bxl(&mut self, x: u8) {
        self.b ^= x as u64
    }

    fn bst(&mut self, x: u64) {
        self.b = x % 8
    }

    fn jnz(&mut self, x: u8) {
        if self.a != 0 {
            self.ip = x as usize
        }
    }

    fn bxc(&mut self) {
        self.b ^= self.c
    }

    fn out(&mut self, x: u64) {
        self.out.push((x % 8) as u8)
    }

    fn bdv(&mut self, x: u64) {
        self.b = self.a >> x
    }

    fn cdv(&mut self, x: u64) {
        self.c = self.a >> x
    }
}

fn part1(input: String) {
    let mut program = parse(&input).unwrap();
    program.run();
    if let Some(e) = program.out.first() {
        print!("{e}")
    }
    for e in program.out.iter().skip(1) {
        print!(",{e}")
    }
    println!()
}

// Some assumptions on the input:
// * There is exactly one jump instruction at the end of the program, jumping to 0
// * Right before that, an output is generated
// * Right before that, register a is shifted right by 3: adv(3)
//
// Each output depends on at most 10 bits of a (it is used with a shift of at most 7).
// Therefore we look at all 10-bit a's and group them by the first number that is output.
// Then we just need to combine these generators into a chain that fits together.
fn number_generators(mut program: Program) -> [Vec<u16>; 8] {
    let mut out = [const { vec![] }; 8];
    for a in 1..(1 << 10) {
        program.a = a as u64;
        program.out.clear();
        program.ip = 0;
        program.run();
        let &output = program.out.first().unwrap();
        out[output as usize].push(a);
    }
    out
}

fn part2(input: String) {
    let mut program = parse(&input).unwrap();
    let generators = number_generators(program.clone());

    let output = program.program.clone();
    // a_candidates maps from 7-bit required prefixes to the lower bits of a that
    // generate the required numbers so far.
    let mut a_candidates: FxHashMap<u8, u64> = generators[output[0] as usize]
        .iter()
        .rev() // Collects the values for each prefix
        .map(|&a| ((a >> 3) as u8, a as u64 % 8))
        .collect();
    let len = output.len();
    for (i, x) in output.iter().enumerate().skip(1) {
        let mut next_candidates = FxHashMap::default();
        for (prefix, val) in generators[*x as usize]
            .iter()
            .filter(|&a| {
                // Take only short candidates in the end to ensure that not too many numbers are generated
                let max_bits = (len - i) * 3;
                (*a as u64) < (1u64 << max_bits)
            })
            // Only use generators that match any required prefix
            .filter(|&a| a_candidates.contains_key(&((a % (1 << 7)) as u8)))
            .map(|&a| {
                let prefix = (a >> 3) as u8;
                let val = a as u64 % 8;
                let prev = a_candidates[&((a % (1 << 7)) as u8)];
                (prefix, (val << (i * 3)) | prev)
            })
        {
            // Only insert first (smallest) encountered value
            next_candidates.entry(prefix).or_insert(val);
        }
        a_candidates = next_candidates;
    }
    println!("{}", a_candidates[&0]);

    // Verify result
    program.a = a_candidates[&0];
    program.run();
    assert_eq!(program.out, program.program);
}

util::aoc_main!();

use std::cmp::{Ordering, Reverse};

use euclid::{default::*, vec2};
use priority_queue::PriorityQueue;
use rustc_hash::{FxHashMap, FxHashSet};

const DIRS: [Vector2D<i32>; 4] = [vec2(1, 0), vec2(0, 1), vec2(-1, 0), vec2(0, -1)];

type Node = (Point2D<i32>, u8);

fn parse(input: &str) -> (Vec<Vec<bool>>, Point2D<i32>, Point2D<i32>) {
    let mut start = None;
    let mut end = None;
    let mut field = Vec::new();
    for (y, l) in input.lines().enumerate() {
        let mut row = Vec::new();
        for (x, b) in l.bytes().enumerate() {
            if b == b'S' {
                start = Some(Point2D::new(x, y).to_i32());
            } else if b == b'E' {
                end = Some(Point2D::new(x, y).to_i32());
            }
            row.push(b == b'#');
        }
        field.push(row);
    }
    (field, start.unwrap(), end.unwrap())
}

fn adj(field: &[Vec<bool>], (v, dir): Node) -> Vec<(Node, u32)> {
    let mut adj = Vec::with_capacity(3);
    let next = v + DIRS[dir as usize];
    if !field[next.y as usize][next.x as usize] {
        adj.push(((next, dir), 1));
    }
    adj.push(((v, (dir + 1) % 4), 1000));
    adj.push(((v, (dir + 3) % 4), 1000));
    adj
}

fn shortest_path_length(field: &[Vec<bool>], start: Node, end: Point2D<i32>) -> u32 {
    let mut dist: FxHashMap<Node, u32> = FxHashMap::default();
    dist.insert(start, 0);
    let mut pq: PriorityQueue<Node, Reverse<u32>> = PriorityQueue::new();
    pq.push(start, Reverse(0));
    while let Some((v, _)) = pq.pop() {
        for (w, weight) in adj(field, v) {
            let dist_w = dist.get(&w).copied().unwrap_or(u32::MAX);
            let new_dist = dist[&v] + weight;
            if dist_w > new_dist {
                dist.insert(w, new_dist);
                pq.push_increase(w, Reverse(new_dist));
            }
        }
    }
    // Shortest distance to end, regardless of final direction
    (0..4).map(|dir| dist[&(end, dir)]).min().unwrap()
}

fn part1(input: String) {
    let (field, start, end) = parse(&input);
    let distance = shortest_path_length(&field, (start, 0), end);
    println!("{distance}");
}

fn shortest_path_tiles(field: &[Vec<bool>], start: Node, end: Point2D<i32>) -> u32 {
    let mut parents: FxHashMap<Node, Vec<Node>> = FxHashMap::default();
    let mut dist: FxHashMap<Node, u32> = FxHashMap::default();
    dist.insert(start, 0);
    let mut pq: PriorityQueue<Node, Reverse<u32>> = PriorityQueue::new();
    pq.push(start, Reverse(0));
    while let Some((v, _)) = pq.pop() {
        for (w, weight) in adj(field, v) {
            let dist_w = dist.get(&w).copied().unwrap_or(u32::MAX);
            let new_dist = dist[&v] + weight;
            match dist_w.cmp(&new_dist) {
                Ordering::Greater => {
                    parents.insert(w, vec![v]);
                    dist.insert(w, new_dist);
                    pq.push_increase(w, Reverse(new_dist));
                }
                // Remember both parents if distance is equal
                Ordering::Equal => parents.get_mut(&w).unwrap().push(v),
                Ordering::Less => {}
            }
        }
    }
    let mut path_tiles: FxHashSet<Point2D<i32>> = FxHashSet::default();
    path_tiles.insert(end);

    // Shortest distance to end, regardless of final direction
    let shortest_dist = (0..4).map(|dir| dist[&(end, dir)]).min().unwrap();
    for dir in 0..4 {
        if dist[&(end, dir)] == shortest_dist {
            collect_tiles(&parents, &mut path_tiles, (end, dir));
        }
    }
    path_tiles.len() as u32
}

fn collect_tiles(
    parents: &FxHashMap<Node, Vec<Node>>,
    tiles: &mut FxHashSet<Point2D<i32>>,
    cur: Node,
) {
    if let Some(pars) = parents.get(&cur) {
        for p in pars {
            tiles.insert(p.0);
            collect_tiles(parents, tiles, *p);
        }
    }
}

fn part2(input: String) {
    let (field, start, end) = parse(&input);
    let tiles = shortest_path_tiles(&field, (start, 0), end);
    println!("{tiles}");
}

util::aoc_main!();

use euclid::{default::*, vec2};

// Common type for both parts. In part 1 all boxes are BoxL.
#[derive(Clone, Copy)]
enum Spot {
    Empty,
    BoxL,
    BoxR,
    Wall,
}

impl From<u8> for Spot {
    fn from(value: u8) -> Self {
        match value {
            b'.' | b'@' => Spot::Empty,
            b'O' => Spot::BoxL,
            b'#' => Spot::Wall,
            other => panic!("Invalid spot: {other}"),
        }
    }
}

fn parse(input: &str) -> (Vec<Vec<Spot>>, Point2D<i32>, Vec<Vector2D<i32>>) {
    let (field_s, moves_s) = input.split_once("\n\n").unwrap();
    let mut field = Vec::new();
    let mut robot = None;
    for (y, l) in field_s.lines().enumerate() {
        let mut row = Vec::new();
        for (x, b) in l.bytes().enumerate() {
            row.push(Spot::from(b));
            if b == b'@' {
                robot = Some(Point2D::new(x, y).to_i32())
            }
        }
        field.push(row);
    }

    let moves = moves_s
        .bytes()
        .filter(|b| *b != b'\n')
        .map(|b| match b {
            b'^' => vec2(0, -1),
            b'>' => vec2(1, 0),
            b'v' => vec2(0, 1),
            b'<' => vec2(-1, 0),
            other => panic!("Invalid move: {other}"),
        })
        .collect();
    (field, robot.unwrap(), moves)
}

fn gps(field: &[Vec<Spot>]) -> u32 {
    let mut sum = 0;
    for (y, row) in field.iter().enumerate() {
        for (x, s) in row.iter().enumerate() {
            if let Spot::BoxL = s {
                sum += x + 100 * y;
            }
        }
    }
    sum as u32
}

fn part1(input: String) {
    let (mut field, mut robot, moves) = parse(&input);
    for m in moves {
        let next = robot + m;
        match field[next.y as usize][next.x as usize] {
            Spot::Empty => robot = next, // Move into space
            Spot::BoxL => {
                let mut search = next + m;
                let can_move = loop {
                    match field[search.y as usize][search.x as usize] {
                        Spot::BoxL => {}
                        Spot::Wall => break false,
                        Spot::Empty => break true,
                        Spot::BoxR => unreachable!(),
                    }
                    search += m;
                };
                if can_move {
                    robot = next;
                    field[next.y as usize][next.x as usize] = Spot::Empty;
                    field[search.y as usize][search.x as usize] = Spot::BoxL;
                }
            }
            Spot::Wall => {} // Cannot move
            Spot::BoxR => unreachable!(),
        }
    }
    println!("{}", gps(&field));
}

// Transform part 1 field to wider part 2 field
fn widen(field: &[Vec<Spot>]) -> Vec<Vec<Spot>> {
    field
        .iter()
        .map(|row| {
            row.iter()
                .flat_map(|s| match s {
                    Spot::Empty => [Spot::Empty; 2],
                    Spot::Wall => [Spot::Wall; 2],
                    Spot::BoxL => [Spot::BoxL, Spot::BoxR],
                    Spot::BoxR => unreachable!(),
                })
                .collect()
        })
        .collect()
}

// Recursively find out whether or not the robot can move in direction `dir` from `start`.
fn can_move_rec(field: &[Vec<Spot>], start: Point2D<i32>, dir: Vector2D<i32>) -> bool {
    let next = start + dir;
    match field[next.y as usize][next.x as usize] {
        Spot::Empty => true,
        Spot::BoxL => can_move_rec(field, next, dir) && can_move_rec(field, next + vec2(1, 0), dir),
        Spot::BoxR => can_move_rec(field, next - vec2(1, 0), dir) && can_move_rec(field, next, dir),
        Spot::Wall => false,
    }
}

// Recursively execute a move for vertical directions into boxes.
fn do_move(field: &mut [Vec<Spot>], start: Point2D<i32>, dir: Vector2D<i32>) {
    let next = start + dir;
    match field[next.y as usize][next.x as usize] {
        Spot::Empty | Spot::Wall => {}
        Spot::BoxL => {
            do_move(field, next, dir);
            do_move(field, next + vec2(1, 0), dir);
            let move_to = next + dir;
            field[next.y as usize][next.x as usize] = Spot::Empty;
            field[next.y as usize][next.x as usize + 1] = Spot::Empty;
            field[move_to.y as usize][move_to.x as usize] = Spot::BoxL;
            field[move_to.y as usize][move_to.x as usize + 1] = Spot::BoxR;
        }
        Spot::BoxR => {
            do_move(field, next - vec2(1, 0), dir);
            do_move(field, next, dir);
            let move_to = next + dir;
            field[next.y as usize][next.x as usize - 1] = Spot::Empty;
            field[next.y as usize][next.x as usize] = Spot::Empty;
            field[move_to.y as usize][move_to.x as usize - 1] = Spot::BoxL;
            field[move_to.y as usize][move_to.x as usize] = Spot::BoxR;
        }
    }
}

fn part2(input: String) {
    let (field1, robot1, moves) = parse(&input);
    let mut field = widen(&field1);
    let mut robot = Point2D::new(robot1.x * 2, robot1.y);
    for m in moves {
        let next = robot + m;
        match field[next.y as usize][next.x as usize] {
            Spot::Empty => robot = next, // Move into space
            Spot::BoxL | Spot::BoxR if m.y == 0 => {
                let mut search = next + m;
                let can_move = loop {
                    match field[search.y as usize][search.x as usize] {
                        Spot::BoxL | Spot::BoxR => {}
                        Spot::Wall => break false,
                        Spot::Empty => break true,
                    }
                    search += m;
                };
                if can_move {
                    robot = next;
                    // Shift boxes by array remove/insert
                    field[next.y as usize].remove(search.x as usize);
                    field[next.y as usize].insert(next.x as usize, Spot::Empty);
                }
            }
            Spot::BoxL | Spot::BoxR => {
                if can_move_rec(&field, robot, m) {
                    do_move(&mut field, robot, m);
                    robot = next;
                }
            }
            Spot::Wall => {} // Cannot move
        }
    }
    println!("{}", gps(&field));
}

util::aoc_main!();

use euclid::default::*;
use regex::Regex;

fn parse(input: &str) -> Vec<(Point2D<i32>, Vector2D<i32>)> {
    let re = Regex::new(r"p=(\d+),(\d+) v=(-?\d+),(-?\d+)").unwrap();
    re.captures_iter(input)
        .map(|cap| {
            let (_, [p0, p1, v0, v1]) = cap.extract();
            (
                Point2D::new(p0.parse().unwrap(), p1.parse().unwrap()),
                Vector2D::new(v0.parse().unwrap(), v1.parse().unwrap()),
            )
        })
        .collect()
}

const ROOM: Size2D<i32> = Size2D::new(101, 103);
const TIME: i32 = 100;

fn part1(input: String) {
    let robots = parse(&input);
    let new_pos: Vec<Point2D<i32>> = robots.iter()
        .map(|&(p, v)| (p + v * TIME).rem_euclid(&ROOM))
        .collect();

    assert_eq!(ROOM.width % 2, 1);
    assert_eq!(ROOM.height % 2, 1);
    let mid_x = ROOM.width / 2;
    let mid_y = ROOM.height / 2;
    
    let mut q = [0u32; 4];
    for p in new_pos {
        use std::cmp::Ordering::*;
        match (p.x.cmp(&mid_x), p.y.cmp(&mid_y)) {
            (Less, Less) => q[0] += 1,
            (Greater, Less) => q[1] += 1,
            (Less, Greater) => q[2] += 1,
            (Greater, Greater) => q[3] += 1,
            _ => {}
        };
    }
    let prod = q[0] * q[1] * q[2] * q[3];
    println!("{prod}");
}

fn print_map(map: &[Vec<bool>]) {
    for row in map {
        for p in row {
            if *p { print!("#") } else { print!(".") }
        }
        println!();
    }
    println!();
}


fn part2(input: String) {
    let mut robots = parse(&input);
    let mut map = vec![vec![false; ROOM.width as usize]; ROOM.height as usize];
    for i in 1.. {
        let mut overlap = false;
        for (p, v) in &mut robots {
            *p = (*p + *v).rem_euclid(&ROOM);
            if map[p.y as usize][p.x as usize] {
                // Found two robots on the same spot,
                // which is used as a heuristic for detecting the easter egg.
                overlap = true;
            } else {
                map[p.y as usize][p.x as usize] = true;
            }
        }
        if !overlap {
            print_map(&map);
            println!("Round: {i}");
            break;
        }
        for row in &mut map {
            row.fill(false);
        }
    }
}

util::aoc_main!();

use std::sync::LazyLock;

use regex::Regex;

#[derive(Debug)]
struct Machine {
    a: (i64, i64),
    b: (i64, i64),
    prize: (i64, i64),
}

impl Machine {
    fn tokens_100(&self) -> i64 {
        for b in 0..=100 {
            for a in 0..=100 {
                let pos = (self.a.0 * a + self.b.0 * b, self.a.1 * a + self.b.1 * b);
                if pos == self.prize {
                    return b + 3 * a;
                }
            }
        }
        0
    }

    fn tokens_inv(&self) -> i64 {
        // If [ab] is the matrix containing our two button vectors: [ a.0 b.0 ]
        //                                                          [ a.1 b.1 ]
        // then prize = [ab] * x, where x holds the number of required button presses
        // for a and b, (na, nb).
        // By inverting [ab] we get
        //
        // x = [ab]⁻¹ * prize
        let det = (self.a.0 * self.b.1) - (self.a.1 * self.b.0);
        if det == 0 {
            panic!("Irregular matrix");
        }
        let det = det as f64;
        // The matrix [ a b ] is the inverse of [ a.0 b.0 ] .
        //            [ c d ]                   [ a.1 b.1 ]
        let a = self.b.1 as f64 / det;
        let b = -self.b.0 as f64 / det;
        let c = -self.a.1 as f64 / det;
        let d = self.a.0 as f64 / det;
        // Multiply [ab] * prize to get the result
        let na = self.prize.0 as f64 * a + self.prize.1 as f64 * b;
        let nb = self.prize.0 as f64 * c + self.prize.1 as f64 * d;

        // Only integer solutions are valid, verify rounded results:
        let ina = na.round() as i64;
        let inb = nb.round() as i64;
        let pos = (
            self.a.0 * ina + self.b.0 * inb,
            self.a.1 * ina + self.b.1 * inb,
        );
        if pos == self.prize {
            inb + 3 * ina
        } else {
            0
        }
    }

    fn translate(&self, tr: i64) -> Self {
        let prize = (self.prize.0 + tr, self.prize.1 + tr);
        Machine { prize, ..*self }
    }
}

impl From<&str> for Machine {
    fn from(s: &str) -> Self {
        static RE: LazyLock<(Regex, Regex)> = LazyLock::new(|| {
            (
                Regex::new(r"Button [AB]: X\+(\d+), Y\+(\d+)").unwrap(),
                Regex::new(r"Prize: X=(\d+), Y=(\d+)").unwrap(),
            )
        });
        let (re_btn, re_prize) = &*RE;
        let mut caps = re_btn.captures_iter(s);
        let (_, [a0, a1]) = caps.next().unwrap().extract();
        let a = (a0.parse().unwrap(), a1.parse().unwrap());
        let (_, [b0, b1]) = caps.next().unwrap().extract();
        let b = (b0.parse().unwrap(), b1.parse().unwrap());
        let (_, [p0, p1]) = re_prize.captures(s).unwrap().extract();
        let prize = (p0.parse().unwrap(), p1.parse().unwrap());
        Machine { a, b, prize }
    }
}

fn parse(input: String) -> Vec<Machine> {
    input.split("\n\n").map(Into::into).collect()
}

fn part1(input: String) {
    let machines = parse(input);
    let sum = machines.iter().map(|m| m.tokens_100()).sum::<i64>();
    println!("{sum}");
}

const TRANSLATION: i64 = 10000000000000;

fn part2(input: String) {
    let machines = parse(input);
    let sum = machines
        .iter()
        .map(|m| m.translate(TRANSLATION).tokens_inv())
        .sum::<i64>();
    println!("{sum}");
}

util::aoc_main!();

use std::collections::{HashSet, VecDeque};

use euclid::{default::*, point2, vec2};

type Fences = HashSet<(Point2D<i32>, Point2D<i32>)>;
const DIRS: [Vector2D<i32>; 4] = [vec2(0, -1), vec2(1, 0), vec2(0, 1), vec2(-1, 0)];

fn parse(input: &str) -> Vec<&[u8]> {
    input.lines().map(|l| l.as_bytes()).collect()
}

fn price(field: &[&[u8]], start: (usize, usize), visited: &mut [Vec<bool>]) -> (u32, Fences) {
    let crop = field[start.1][start.0];
    let width = field[0].len();
    let height = field.len();
    let mut area_visited = vec![vec![false; width]; height];
    let mut area = 0;
    let mut fences: Fences = HashSet::new();

    area_visited[start.1][start.0] = true;
    visited[start.1][start.0] = true;
    let start = point2(start.0 as i32, start.1 as i32);
    let bounds = Rect::new(Point2D::origin(), Size2D::new(width, height).to_i32());
    let mut frontier = VecDeque::from([start]);
    while let Some(p) = frontier.pop_front() {
        area += 1;
        for dir in DIRS {
            let next = p + dir;
            if bounds.contains(next) {
                let next_u = next.to_usize();
                if area_visited[next_u.y][next_u.x] {
                    continue;
                }
                if field[next_u.y][next_u.x] == crop {
                    visited[next_u.y][next_u.x] = true;
                    area_visited[next_u.y][next_u.x] = true;
                    frontier.push_back(next);
                    continue;
                }
            }
            fences.insert((p, next));
        }
    }
    (area, fences)
}

fn part1(input: String) {
    let field = parse(&input);
    let width = field[0].len();
    let height = field.len();
    let mut visited = vec![vec![false; width]; height];
    let mut total_price = 0;
    for y in 0..height {
        for x in 0..width {
            if !visited[y][x] {
                let (area, fences) = price(&field, (x, y), &mut visited);
                total_price += area * fences.len() as u32;
            }
        }
    }
    println!("{total_price}");
}

fn count_perimeter(mut fences: Fences) -> u32 {
    let list: Vec<_> = fences.iter().copied().collect();
    let mut perimeter = 0;
    for (v, w) in list {
        if fences.contains(&(v, w)) {
            perimeter += 1;
            let dir = w - v;
            let orth = dir.yx();
            let mut next = v + orth;
            while fences.remove(&(next, next + dir)) {
                next += orth;
            }
            let mut next = v - orth;
            while fences.remove(&(next, next + dir)) {
                next -= orth;
            }
        }
    }
    perimeter
}

fn part2(input: String) {
    let field = parse(&input);
    let width = field[0].len();
    let height = field.len();
    let mut visited = vec![vec![false; width]; height];
    let mut total_price = 0;
    for y in 0..height {
        for x in 0..width {
            if !visited[y][x] {
                let (area, fences) = price(&field, (x, y), &mut visited);
                total_price += area * count_perimeter(fences);
            }
        }
    }
    println!("{total_price}");
}

util::aoc_main!();

use std::collections::HashMap;

fn parse(input: String) -> Vec<u64> {
    input
        .split_whitespace()
        .map(|w| w.parse().unwrap())
        .collect()
}

fn part1(input: String) {
    let mut stones = parse(input);
    for _ in 0..25 {
        let mut new_stones = Vec::with_capacity(stones.len());
        for s in &stones {
            match s {
                0 => new_stones.push(1),
                n => {
                    let digits = s.ilog10() + 1;
                    if digits % 2 == 0 {
                        let cutoff = 10u64.pow(digits / 2);
                        new_stones.push(n / cutoff);
                        new_stones.push(n % cutoff);
                    } else {
                        new_stones.push(n * 2024)
                    }
                }
            }
        }
        stones = new_stones;
    }
    println!("{}", stones.len());
}

fn expansion(s: u64, rounds: u32, cache: &mut HashMap<(u64, u32), u64>) -> u64 {
    // Recursion anchor
    if rounds == 0 {
        return 1;
    }
    // Calculation is already cached
    if let Some(res) = cache.get(&(s, rounds)) {
        return *res;
    }

    // Recurse
    let res = match s {
        0 => expansion(1, rounds - 1, cache),
        n => {
            let digits = s.ilog10() + 1;
            if digits % 2 == 0 {
                let cutoff = 10u64.pow(digits / 2);
                expansion(n / cutoff, rounds - 1, cache) +
                expansion(n % cutoff, rounds - 1, cache)
            } else {
                expansion(n * 2024, rounds - 1, cache)
            }
        }
    };
    // Save in cache
    cache.insert((s, rounds), res);
    res
}

fn part2(input: String) {
    let stones = parse(input);
    let mut cache = HashMap::new();
    let sum: u64 = stones.iter().map(|s| expansion(*s, 75, &mut cache)).sum();
    println!("{sum}");
}

util::aoc_main!();

use std::collections::HashSet;

fn parse(input: &str) -> Vec<&[u8]> {
    input.lines().map(|l| l.as_bytes()).collect()
}

fn adj(grid: &[&[u8]], (x, y): (usize, usize)) -> Vec<(usize, usize)> {
    let n = grid[y][x];
    let mut adj = Vec::with_capacity(4);
    if x > 0 && grid[y][x - 1] == n + 1 {
        adj.push((x - 1, y))
    }
    if y > 0 && grid[y - 1][x] == n + 1 {
        adj.push((x, y - 1))
    }
    if x + 1 < grid[0].len() && grid[y][x + 1] == n + 1 {
        adj.push((x + 1, y))
    }
    if y + 1 < grid.len() && grid[y + 1][x] == n + 1 {
        adj.push((x, y + 1))
    }
    adj
}

fn solve(input: String, trailhead: fn(&[&[u8]], (usize, usize)) -> u32) -> u32 {
    let grid = parse(&input);
    let mut sum = 0;
    for (y, row) in grid.iter().enumerate() {
        for (x, p) in row.iter().enumerate() {
            if *p == b'0' {
                sum += trailhead(&grid, (x, y));
            }
        }
    }
    sum
}

fn part1(input: String) {
    fn score(grid: &[&[u8]], start: (usize, usize)) -> u32 {
        (1..=9)
            .fold(HashSet::from([start]), |frontier, _| {
                frontier.iter().flat_map(|p| adj(grid, *p)).collect()
            })
            .len() as u32
    }
    println!("{}", solve(input, score))
}

fn part2(input: String) {
    fn rating(grid: &[&[u8]], start: (usize, usize)) -> u32 {
        (1..=9)
            .fold(vec![start], |frontier, _| {
                frontier.iter().flat_map(|p| adj(grid, *p)).collect()
            })
            .len() as u32
    }
    println!("{}", solve(input, rating))
}

util::aoc_main!();