Gobbel2000

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!();

fn part1(input: String) {
    let mut id: u64 = 0;
    let mut disk = Vec::new();
    let mut file = true;
    for b in input.trim().bytes() {
        let num: usize = (b - b'0') as usize;
        if file {
            disk.extend(vec![Some(id); num]);
            id += 1;
        } else {
            disk.extend(vec![None; num]);
        }
        file = !file;
    }

    let mut first_free = 0;
    while disk[first_free].is_some() {
        first_free += 1
    }

    let mut last_file = disk.len() - 1;
    while disk[last_file].is_none() {
        last_file -= 1
    }

    while first_free < last_file {
        disk[first_free] = disk[last_file];
        disk[last_file] = None;
        while disk[first_free].is_some() {
            first_free += 1
        }
        while disk[last_file].is_none() {
            last_file -= 1
        }
    }

    let checksum = disk
        .iter()
        .filter_map(|e| *e)
        .enumerate()
        .map(|(i, id)| i as u64 * id)
        .sum::<u64>();
    println!("{checksum}");
}

fn part2(input: String) {
    // Tuples of (idx, size)
    let mut free_spaces = Vec::new();
    // Tuples of (idx, size, id)
    let mut files = Vec::new();

    let mut id: u64 = 0;
    let mut disk_len = 0;
    let mut file = true;
    for b in input.trim().bytes() {
        let num = (b - b'0') as u64;
        if file {
            files.push((disk_len, num, id));
            id += 1;
        } else {
            free_spaces.push((disk_len, num));
        }
        disk_len += num;
        file = !file;
    }

    for (idx, size, _id) in files.iter_mut().rev() {
        match free_spaces
            .iter_mut()
            // Only search spaces left of file
            .take_while(|(sp_idx, _space)| sp_idx < idx)
            .find(|(_sp_idx, space)| space >= size)
        {
            None => {} // No space found
            Some((sp_idx, space)) => {
                // Move file into space
                *idx = *sp_idx;
                // Reduce free space
                *sp_idx += *size;
                *space -= *size;
            }
        }
    }

    let sum_range = |n| if n == 0 { 0 } else { (n * (n - 1)) / 2 };
    let checksum = files
        .iter()
        .map(|(idx, size, id)| (sum_range(idx + size) - sum_range(*idx)) * id)
        .sum::<u64>();
    println!("{checksum}");
}

util::aoc_main!();

use euclid::default::*;

const N_ANTENNAS: usize = (b'z' - b'0') as usize + 1;
// For each frequency (from b'0' to b'z') the list of antenna positions
type Antennas = Box<[Vec<Point2D<i32>>]>;

fn parse(input: String) -> (Antennas, Rect<i32>) {
    let mut antennas = vec![Vec::new(); N_ANTENNAS].into_boxed_slice();
    let mut width = 0;
    let mut height = 0;
    for (y, l) in input.lines().enumerate() {
        height = y + 1;
        if width == 0 {
            width = l.len()
        } else {
            assert!(width == l.len())
        }
        for (x, b) in l.bytes().enumerate().filter(|(_, b)| *b != b'.') {
            antennas[(b - b'0') as usize].push(Point2D::new(x, y).to_i32())
        }
    }
    let bounds = Rect::new(Point2D::origin(), Size2D::new(width, height).to_i32());
    (antennas, bounds)
}

fn part1(input: String) {
    let (antennas, bounds) = parse(input);
    let mut antinodes = vec![vec![false; bounds.width() as usize]; bounds.height() as usize];
    for list in antennas.iter().filter(|l| !l.is_empty()) {
        for (i, &a) in list.iter().enumerate().skip(1) {
            for &b in list.iter().take(i) {
                let diff = b - a;
                let ax = a - diff;
                if bounds.contains(ax) {
                    antinodes[ax.y as usize][ax.x as usize] = true;
                }
                let bx = b + diff;
                if bounds.contains(bx) {
                    antinodes[bx.y as usize][bx.x as usize] = true;
                }
            }
        }
    }
    let sum = antinodes
        .iter()
        .map(|row| row.iter().map(|b| u32::from(*b)).sum::<u32>())
        .sum::<u32>();
    println!("{sum}");
}

fn part2(input: String) {
    let (antennas, bounds) = parse(input);
    let mut antinodes = vec![vec![false; bounds.width() as usize]; bounds.height() as usize];
    for list in antennas.iter().filter(|l| !l.is_empty()) {
        for (i, &a) in list.iter().enumerate().skip(1) {
            for &b in list.iter().take(i) {
                let diff = b - a;
                // Start at antenna a, keep going until hitting bounds
                let mut ax = a;
                while bounds.contains(ax) {
                    antinodes[ax.y as usize][ax.x as usize] = true;
                    ax -= diff;
                }
                let mut bx = b;
                while bounds.contains(bx) {
                    antinodes[bx.y as usize][bx.x as usize] = true;
                    bx += diff;
                }
            }
        }
    }
    let sum = antinodes
        .iter()
        .map(|row| row.iter().map(|b| u32::from(*b)).sum::<u32>())
        .sum::<u32>();
    println!("{sum}");
}

util::aoc_main!();

use euclid::default::{Point2D, Vector2D};
use euclid::vec2;

fn parse(input: String) -> (Vec<Vec<bool>>, Point2D<i32>) {
    let mut field = Vec::new();
    let mut start = Point2D::zero();
    for (y, line) in input.lines().enumerate() {
        let mut row = Vec::new();
        for (x, c) in line.chars().enumerate() {
            row.push(c == '#');
            if c == '^' {
                start = Point2D::new(x, y).to_i32();
            }
        }
        field.push(row);
    }
    (field, start)
}

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

fn visited(field: &[Vec<bool>], start: Point2D<i32>) -> Vec<Vec<bool>> {
    let width = field[0].len();
    let height = field.len();
    let mut visited = vec![vec![false; width]; height];
    // Start up, then turn right
    let mut dir = 0;
    let mut pos = start;
    loop {
        visited[pos.y as usize][pos.x as usize] = true;
        let next = pos + DIRS[dir];
        // Guard leaves area
        if next.x < 0 || next.y < 0 || next.x >= width as i32 || next.y >= height as i32 {
            break;
        }
        // Path blocked
        if field[next.y as usize][next.x as usize] {
            dir = (dir + 1) % 4; // Turn right, don't move yet
        } else {
            pos = next
        }
    }
    visited
}

fn part1(input: String) {
    let (field, start) = parse(input);
    let count = visited(&field, start)
        .iter()
        .map(|r| r.iter().map(|b| u32::from(*b)).sum::<u32>())
        .sum::<u32>();
    println!("{count}")
}

fn is_loop(field: &[Vec<bool>], start: Point2D<i32>) -> bool {
    let width = field[0].len();
    let height = field.len();
    let mut visited = vec![vec![0; width]; height];

    // Start up, then turn right
    let mut dir = 0;
    let mut pos = start;
    loop {
        // Loop detected
        if visited[pos.y as usize][pos.x as usize] & (1 << dir) > 0 {
            break true;
        }
        // Record all walked directions at all fields
        visited[pos.y as usize][pos.x as usize] |= 1 << dir;
        let next = pos + DIRS[dir];
        // Guard leaves area
        if next.x < 0 || next.y < 0 || next.x >= width as i32 || next.y >= height as i32 {
            break false;
        }
        // Path blocked
        if field[next.y as usize][next.x as usize] {
            dir = (dir + 1) % 4 // Turn right, don't move yet
        } else {
            pos = next
        }
    }
}

fn part2(input: String) {
    let (mut field, start) = parse(input);
    let width = field[0].len();
    let height = field.len();
    let normal_visited = visited(&field, start); // Part 1 solution
    let mut count = 0;
    for x in 0..width {
        for y in 0..height {
            // Only check places that are visited without any obstacles, and don't check start
            if normal_visited[y][x] && !(x as i32 == start.x && y as i32 == start.y) {
                field[y][x] = true; // Set obstacle
                count += is_loop(&field, start) as u32;
                field[y][x] = false; // Remove obstacle
            }
        }
    }
    println!("{count}");
}

util::aoc_main!();

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

fn parse_lists(input: &str) -> Vec<Vec<u32>> {
    input.lines()
        .map(|l| l.split(',').map(|e| e.parse().unwrap()).collect())
        .collect()
}

fn parse_relation(input: String) -> (HashSet<(u32, u32)>, Vec<Vec<u32>>) {
    let (ordering, lists) = input.split_once("\n\n").unwrap();
    let relation = ordering.lines()
        .map(|l| {
            let (a, b) = l.split_once('|').unwrap();
            (a.parse().unwrap(), b.parse().unwrap())
        })
        .collect();
    (relation, parse_lists(lists))
}

fn parse_graph(input: String) -> (Vec<Vec<u32>>, Vec<Vec<u32>>) {
    let (ordering, lists) = input.split_once("\n\n").unwrap();
    let mut graph = Vec::new();
    for l in ordering.lines() {
        let (a, b) = l.split_once('|').unwrap();
        let v: u32 = a.parse().unwrap();
        let w: u32 = b.parse().unwrap();
        let new_len = v.max(w) as usize + 1;
        if new_len > graph.len() {
            graph.resize(new_len, Vec::new())
        }
        graph[v as usize].push(w);
    }
    (graph, parse_lists(lists))
}


fn part1(input: String) {
    let (relation, lists) = parse_relation(input); 
    let mut sum = 0;
    for l in lists {
        let mut valid = true;
        for i in 0..l.len() {
            for j in 0..i {
                if relation.contains(&(l[i], l[j])) {
                    valid = false;
                    break
                }
            }
            if !valid { break }
        }
        if valid {
            sum += l[l.len() / 2];
        }
    }
    println!("{sum}");
}


// Topological order of graph, but limited to nodes in the set `subgraph`.
// Otherwise the graph is not acyclic.
fn topological_sort(graph: &[Vec<u32>], subgraph: &HashSet<u32>) -> Vec<u32> {
    let mut order = VecDeque::with_capacity(subgraph.len());
    let mut marked = vec![false; graph.len()];
    for &v in subgraph {
        if !marked[v as usize] {
            dfs(graph, subgraph, v as usize, &mut marked, &mut order)
        }
    }
    order.into()
}

fn dfs(graph: &[Vec<u32>], subgraph: &HashSet<u32>, v: usize, marked: &mut [bool], order: &mut VecDeque<u32>) {
    marked[v] = true;
    for &w in graph[v].iter().filter(|v| subgraph.contains(v)) {
        if !marked[w as usize] {
            dfs(graph, subgraph, w as usize, marked, order);
        }
    }
    order.push_front(v as u32);
}

fn rank(order: &[u32]) -> HashMap<u32, u32> {
    order.iter().enumerate().map(|(i, x)| (*x, i as u32)).collect()
}

// Part 1 with topological sorting, which is slower
fn _part1(input: String) {
    let (graph, lists) = parse_graph(input);
    let mut sum = 0;
    for l in lists {
        let subgraph = HashSet::from_iter(l.iter().copied());
        let rank = rank(&topological_sort(&graph, &subgraph));
        if l.is_sorted_by_key(|x| rank[x]) {
            sum += l[l.len() / 2];
        }
    }
    println!("{sum}");
}

fn part2(input: String) {
    let (graph, lists) = parse_graph(input);
    let mut sum = 0;
    for mut l in lists {
        let subgraph = HashSet::from_iter(l.iter().copied());
        let rank = rank(&topological_sort(&graph, &subgraph));
        if !l.is_sorted_by_key(|x| rank[x]) {
            l.sort_unstable_by_key(|x| rank[x]);            
            sum += l[l.len() / 2];
        }
    }
    println!("{sum}");
}

util::aoc_main!();