Advent of Code 2024, using Rust

fn advent(filename: &str) -> (u32, u32)

#[cfg(test)]
mod tests {
    use super::*;
    use test::Bencher;
    #[test] fn example_input() { dbg!(advent("example.txt")); }
    #[test] fn final_input() { dbg!(advent("input.txt")); }
    #[test] fn ex1() { assert_eq!(advent("example.txt").0, 11) }
    #[test] fn final1() { assert_eq!(advent("input.txt").0, 1666427) }
    #[test] fn ex2() { assert_eq!(advent("example.txt").1, 31) }
    #[test] fn final2() { assert_eq!(advent("input.txt").1, 24316233) }

    #[bench] fn bench_advent(b: &mut Bencher) { b.iter(|| advent("input.txt")); }
}

// Expected number of lines (but also works if more lines)
const N: usize = 1000;

fn advent(filename: &str) -> (u32, u32) {
    let contents = read_to_string(filename)
        .expect("Something went wrong reading the input file");

    let (mut part1, mut part2) = (0, 0);
    let mut left: Vec<u32> = Vec::with_capacity(N);
    let mut right: Vec<u32> = Vec::with_capacity(N);

    for (a,b) in extract_numbers::<u32>(&contents).tuples() {
        // Destructure a line like
        //     123   456
        // into the variables a=123 and b=456
        left.push(a);
        right.push(b);
    }

    assert_eq!(left.len(), right.len());
    left.sort_unstable();
    right.sort_unstable();

    for i in 0..left.len() {
        part1 += left[i].abs_diff(right[i]);
        let occurrences = right.iter().filter(|&&x| x == left[i]).count() as u32;
        part2 += left[i] * occurrences;
    }

    (part1,part2)
}

fn advent(filename: &str) -> (u32, u32) {
    let contents = read_to_string(filename)
        .expect("Something went wrong reading the input file");
    let (mut part1, mut part2) = (0,0);

    for line in contents.lines() {
        let report = extract_numbers::<i32>(line).collect_vec();

        // Part 1: Check if the levels are safe
        if is_safe_report(report.iter().cloned()) {
            part1 += 1;
        }

        // Part 2: Check if the levels are safe, including when removing one level
        for i in 0..report.len() {
            // Create an iterator that skips over one level
            let skipped_iter = report.iter().enumerate()
                .filter_map(|(idx, &val)| if idx != i { Some(val) } else { None });

            if is_safe_report(skipped_iter) {
                part2 += 1;
                break; // Break once we find one level to remove safely
            }
        }
    }

    (part1, part2)
}

// Checks whether a report contains only safe levels.
// 
// The argument is an iterator over the levels to consider.
// 
// A report counts as safe if both of the following are true:
//  - The levels are either all increasing or all decreasing.
//  - Any two adjacent levels differ by at least one and at most three.
fn is_safe_report<I>(iter: I) -> bool
where
    I: Iterator<Item = i32> + Clone,
{
    // Differences between adjacent levels in the report
    let mut diffs = iter.tuple_windows().map(|(x, y)| y - x);
    // Check the safety condition
    diffs.clone().all(|x| x >=  1 && x <=  3)
         || diffs.all(|x| x >= -3 && x <= -1)
}

fn advent(filename: &str) -> (u32, u32) {
    let mem = read_to_string(filename)
        .expect("Something went wrong reading the input file");
    let part1 = muls_and_sum(&mem);
    let part2 = between_sums(&mem, "do()", "don't()", muls_and_sum);
    (part1, part2)
}

// Multiplies all occurences of "mul(a,b)" (= a*b) in [text] and sums them.
//
// Non-digits within the "mul(...)"" get correctly ignored.
// But "mul(a)" or "mul(a,b,c)" are not discarded.
//
// Note: If the beginning of [text] up until the first "mul(" is a number,
// or a comma separated list of numbers, these get multiplied and added to the result.
// Fortunately, this does not happen in my AoC input.
fn muls_and_sum(text: &str) -> u32 {
    between_sums(text, "mul(", ")",
        |s| s.split(",")
             // ignore non-digits in mul() instructions
             .map(|num| num.parse::<u32>().unwrap_or(0))
             .product::<u32>())
}

// Maps a function [f] on all substrings in [text] between sequential
// occurrences of [from] and [to]. Afterwards it sums the results.
// It also applies [f] to the beginning of the [text] up until the
// first occurence of [from].
// 
// Example:
//   Inputs: text = "(abc)def(ghi)j(klm)", from = "(", to = ")"
//   Applies [f] to "", "abc", "ghi", and "klm", and sums the results.
fn between_sums(text: &str, from: &str, to: &str, f: impl Fn(&str) -> u32) -> u32 {
    text.split(from).filter_map(|s| s.split(to).next()).map(f).sum()
}

const MAS: [u8; 3] = [b'M', b'A', b'S'];
const SAM: [u8; 3] = [b'S', b'A', b'M'];

fn advent(filename: &str) -> (u32, u32) {
    let map = Matrix::from_bytes(&read(filename).expect("could not read input file"));
    let (mut part1, mut part2) = (0,0);

    for r in 0..map.height {
        for c in 0..map.width {
            let p = Point::new(r,c);
            // Summing directions for part1
            for &dir in &[LEFT, RIGHT, UP, DOWN, NORTHEAST, NORTHWEST, SOUTHEAST, SOUTHWEST] {
                part1 += direction_contains_word(&map, p, dir, "XMAS") as u32;
            }
            // Check mas function for part2
            part2 += mas_pattern(&map, p) as u32;
        }
    }

    (part1, part2)
}

fn direction_contains_word(grid: &Matrix<u8>, p: Point, dir: Point, word: &str) -> bool {
    let mut chars = word.chars();
    (0..word.len() as i32).all(|i| {
        grid.get(p + dir*i).is_some_and(|&c| c == chars.next().unwrap() as u8)
    })
}

fn mas_pattern(grid: &Matrix<u8>, p: Point) -> bool {
    if !(grid.contains(p+SOUTHEAST) && grid.contains(p+NORTHWEST)) {return false;}

    let forward = [
        grid[p+SOUTHWEST],
        grid[p],
        grid[p+NORTHEAST],
    ];
    let backward = [
        grid[p+NORTHWEST],
        grid[p],
        grid[p+SOUTHEAST],
    ];
    (forward == MAS || forward == SAM) && (backward == MAS || backward == SAM)
}

const MAX_NUMBER: usize = 99;

fn advent(filename: &str) -> (u32, u32) {
    let input = read_to_string(filename).expect("could not read input file");
    let (rules, updates) = input.split_once("\n\n").expect("invalid input format");
    let (mut part1, mut part2) = (0, 0);

    // The 2D array [page_before] defines the order of the pages.
    // page_before[A][B] is true if page A should be printed before page B.
    // Otherwise it is false.
    //
    // The input seems to contain N different numbers between 11 and 99.
    // To define the order between every pair we need a rule for every subset of size 2.
    // For the example input, we have 7 different numbers, and indeed have C(7,2) = 21 rules.
    // As every rule is specified, we can safely assign a default value.
    // 
    // The rule format does not allow for equal order, therefore there are only two
    // possible orders (before/after).
    let mut page_before = [[false; MAX_NUMBER]; MAX_NUMBER];
    for (a,b) in extract_numbers::<usize>(&rules).tuples() {
        page_before[a][b] = true; // the other direction [b][a] is false by default
    }

    let mut update_buf = Vec::new();
    for update_line in updates.lines() {
        // Reuse a vector to avoid repeated memory allocations (~30 µs)
        update_buf.clear();
        update_buf.extend(extract_numbers::<usize>(&update_line));

        if update_buf.is_sorted_by(|&a, &b| page_before[a][b]) {
            part1 += update_buf[update_buf.len() / 2];
        } else {
            update_buf.sort_unstable_by(|&a, &b| if page_before[a][b] {Ordering::Less} else {Ordering::Greater});
            part2 += update_buf[update_buf.len() / 2];
        }
    }

    (part1 as u32, part2 as u32)
}

const WIDTH: usize = 130; // maximum width
const HEIGHT: usize = WIDTH;
type Generation = u16;

pub fn advent(filename: &str) -> (u32, u32) {
    let mut map =  Matrix::from_bytes(&read(filename).expect("could not read input file"));
    assert_eq!(map.height, map.width);
    assert!(WIDTH>=map.width as usize);
    
    let mut pos = map.find(b'^').expect("no start position found");
    let mut dir = Direction::Up;
    let mut gen: Generation = 0;

    // This array keeps track of map positions + directions that have been visited before.
    // Initialize all to zero. We will store generation numbers here, which get incremented for each
    // separate cycle check.
    let mut visited: [Generation; WIDTH * HEIGHT * 4] = [gen; WIDTH * HEIGHT * 4];

    let (mut part1, mut part2) = (1,0);

    while let Some(next_cell) = map.get(pos + dir.to_point()) {
        match next_cell {
            b'#' => dir = dir.clockwise(),
            b'.' => {
                let next = pos + dir.to_point();
                part1 += 1;

                map[next] = b'#';
                gen+=1;
                if is_cyclic(&map, &mut visited, gen, pos, dir) {
                    part2 += 1;
                }
                map[next] = b'^';
                pos = next;
            },
            b'^' => pos = pos + dir.to_point(),
            _ => break,
        }
    }
    
    (part1, part2)
}

// Check if continuing on this path results in a loop.
// We have a loop if we visit a previosuly visited tile.
#[inline]
fn is_cyclic(map: &Matrix<u8>, visited: &mut [Generation; WIDTH * HEIGHT * 4], gen: Generation, mut pos: Point, mut dir: Direction) -> bool {
    while let Some(next_cell) = map.get(pos+dir.to_point()) {
        if *next_cell == b'#' {
            let state_idx = ((pos.x as usize) * WIDTH + (pos.y as usize)) * 4 + dir.to_index();
            if visited[state_idx] == gen {
                return true;
            }
            visited[state_idx] = gen;
            dir = dir.clockwise();
            continue;
        }

        pos = pos + dir.to_point();
    }

    false
}

type Num = u64;
const MAX_NUMBERS_PER_LINE: u32 = 14;

pub fn advent(filename: &str) -> (u64, u64) {
    let input = read_to_string(filename).expect("could not read input file");
    let (mut part1, mut part2) = (0,0);

    // Buffer for tokens of each line (reused for each line)
    let mut tokens = Vec::with_capacity(MAX_NUMBERS_PER_LINE as usize);
    // Buffer that collects all operator combinations (reused for each line)
    let mut buf = vec![0 as Num; 3usize.pow(MAX_NUMBERS_PER_LINE-2)]; 

    for line in input.lines() {
        tokens.clear();
        tokens.extend(extract_numbers::<Num>(&line));
        let test = tokens[0];

        // First operand
        buf[0] = tokens[1];

        let mut prev_size = 1;
        for &op2 in &tokens[2..] {
            // Expand backwards to avoid overwriting unread values
            for idx in (0..prev_size).rev() {
                let op1 = buf[idx];
                let base = idx * 3;
                buf[base]     = op1 + op2;
                buf[base + 1] = op1 * op2;
                buf[base + 2] = concat(op1, op2);
            }
            prev_size *= 3;
        }

        // Now all results are in buf[0..prev_size].
        // Check if one operator combination results in the test value
        let mut part1_found = false;
        let mut part2_found = false;
        for (index, &val) in buf[..prev_size].iter().enumerate() {
            if val == test {
                if !part2_found {
                    part2 += test;
                    part2_found = true;
                }

                // part1 includes only those without any concat
                if !part1_found && !involved_concat(index)  {
                    part1 += test;
                    part1_found = true;
                }

                if part1_found && part2_found {
                    break;
                }
            }
        }
    }

    (part1, part2)
}

// Concatenates the numbers `n1` and `n2`.
// Example: concat(12, 345) = 12345`
const fn concat(n1: Num, n2: Num) -> Num {
    match n2 {
        0..=9 => n1 * 10 + n2,
        10..=99 => n1 * 100 + n2,
        100..=999 => n1 * 1000 + n2,
        _ => panic!("concat not implemented for numbers >= 1000"),
    }
}

// Find out based on the index if this result involved a concatenation.
#[inline]
fn involved_concat(index: usize) -> bool {
    if index == 0 {
        false
    } else if index % 3 == 2 {
        true
    } else {
        involved_concat(index / 3)
    }
}

pub fn advent(filename: &str) -> (u32, u32) {
    let map =  Matrix::from_bytes(&read(filename).expect("could not read input file"));
    assert_eq!(map.height, map.width);

    // Map to store antinodes with a '#'
    let mut antinodes1 = map.clone(); // part1
    let mut antinodes2 = map.clone(); // part2
    let mut antenna_positions: FxHashMap<u8, Vec<Point>> = FxHashMap::default();
    let (mut part1, mut part2) = (0,0);

    for x in 0..map.width {
        for y in 0..map.height {
            let p1 = Point::new(x,y);
            if map[p1] == b'.' { continue; }

            if let Some(positions) = antenna_positions.get(&map[p1]) {
                for &p2 in positions {
                    update_antinodes(&mut antinodes1, &mut antinodes2, p1, p2, &mut part1, &mut part2);
                    update_antinodes(&mut antinodes1, &mut antinodes2, p2, p1, &mut part1, &mut part2);
                }
            }
            antenna_positions.entry(map[p1]).or_default().push(p1);
        }
    }

    (part1, part2)
}

// Find and count all antinodes for the given antenna positions.
fn update_antinodes(antinodes1: &mut Matrix<u8>, antinodes2: &mut Matrix<u8>, p1: Point, p2: Point, part1: &mut u32, part2: &mut u32) {
    let dp = p2 - p1;
    for i in 0..antinodes1.width {
        let pos = p1 + dp*i;
        if !antinodes1.contains(pos) { break; }
        if i == 2 {
            *part1 += if antinodes1.update(pos, b'#') {1} else {0};
        }
        *part2 += if antinodes2.update(pos, b'#') {1} else {0}
    }
}

const FREE: u32 = u32::MAX;

pub fn advent(filename: &str) -> (usize, usize) {
    let input = read_to_string(filename).expect("could not read input file");
    let diskmap: Vec<u32> =  input.trim().chars().filter_map(|c| c.to_digit(10)).collect();
    let (mut part1, mut part2) = (0,0);
    let mut blocks1: Vec<u32> = Vec::new(); // Input format for part 1
    let mut blocks2: Vec<(u32,u32)> = Vec::new(); // Input format for part 2
    let mut file_id = 0;

    for (i, &len) in diskmap.iter().enumerate() {
        if i % 2 == 0 { // is a file
            blocks1.extend(vec![file_id; len as usize]);
            blocks2.push((file_id, len));
            file_id += 1;
        } else { // is free space
            blocks1.extend(vec![FREE; len as usize]);
            blocks2.push((FREE, len));
        }
    }

    // Part 1
    let mut last_idx_front = 0;
    // Iterate from the end of the vector
    for idx_back in (0..blocks1.len()).rev() {
        if last_idx_front >= idx_back { break; }
        if blocks1[idx_back] == FREE { continue; }

        for idx_front in last_idx_front..idx_back {
            // Find the next free space from the beginning
            if blocks1[idx_front] == FREE {
                //println!("Swapping {} (index {i}) to index {j}", blocks1[j]);
                blocks1.swap(idx_front, idx_back);
                last_idx_front = idx_front;
                break;
            }
        }
    }

    // Checksum part 1
    for (idx, &file_id) in blocks1.iter().enumerate() {
        if file_id == FREE { break; }
        part1 += idx*(file_id as usize);
    }

    // Part 2
    // Iterate from the end of the vector
    for idx_back in (0..blocks2.len()).rev() {
        let (back_id, back_len) = blocks2[idx_back];
        if back_id == FREE { continue; }

        // Find the next free space from the beginning
        for idx_front in 0..idx_back {
            let (front_id, front_len) = blocks2[idx_front];

            if front_id == FREE && front_len >= back_len {
                //println!("Shifting block {back_id} to beginning");
                blocks2[idx_back].0 = FREE;

                if front_len == back_len {
                    blocks2[idx_front].0 = back_id;
                } else {
                    blocks2[idx_front].1 -= back_len;
                    blocks2.insert(idx_front, (back_id, back_len));
                }

                break;
            }

        }
    }

    // Checksum part 2
    let mut idx: usize = 0; 
    for (id, size) in blocks2 {
        if id != FREE {
            for _ in 0..size {
                part2 += idx*id as usize;
                idx += 1;
            }
        } else {
            idx += size as usize;
        }
    }

    (part1, part2)
}

pub fn advent(filename: &str) -> (usize, usize) {
    let map =  Matrix::from_bytes_as_digits(&read(filename).expect("could not read input file"));
    let (mut part1, mut part2) = (0,0);
    let mut trailends: Vec<Point> = Vec::new();
    let mut unique_trailends: FxHashSet<Point> = FxHashSet::default();

    // Look backwards from 9->0 as my map contains less `9` than `0`
    for trailhead in map.find_all(9) {
        // Collects distinct trailends in `trailends`.
        distinct_trails(trailhead, 9, &map, &mut trailends);
        // Part 1: Unique trails
        part1 += trailends.iter().collect_into::<FxHashSet<Point>>(&mut unique_trailends).len();
        // Part 2: Total trails
        part2 += trailends.len();
        // Clear buffers for next iteration
        trailends.clear();
        unique_trailends.clear();
    }

    (part1, part2)
}

// Collects distinct trailends in `trailends`.
fn distinct_trails<'a>(start: Point, height: u8, map: &Matrix<u8>, trailends: &'a mut Vec<Point>) -> &'a mut Vec<Point> {
    for neighbor in [start+LEFT, start+RIGHT, start+UP, start+DOWN] {
        let target_height = height-1;
        if map.contains(neighbor) && map[neighbor] == target_height {
            if target_height == 0 {
                trailends.push(neighbor);
            } else {
                distinct_trails(neighbor, target_height, map, trailends);
            }
        }
    }
    trailends
}

pub fn advent(filename: &str) -> (u64, u64) {
    let input =  read_to_string(filename).expect("could not read input file");
    let (mut part1, mut part2) = (0,0);

    let mut cache: FxHashMap<(u64, u32), u64> = FxHashMap::default();

    for num in extract_numbers::<u64>(&input) {
        part1 += length_after_blinks(num, 25, &mut cache);
        part2 += length_after_blinks(num, 75, &mut cache);
    }

    (part1, part2)
}

fn length_after_blinks(stone: u64, blinks: u32, cache: &mut FxHashMap<(u64, u32), u64>) -> u64 {
    if blinks == 0 { 1 }
    else if stone == 0 {
        length_after_blinks(1, blinks-1, cache)
    } else {
        let ndigits = stone.ilog10() + 1;
        if ndigits&1 == 0 { // even?
            // Cache this expensive path
            if let Some(cached) = cache.get(&(stone, blinks)) {
                return *cached;
            }
            let split = 10u64.pow(ndigits / 2);
            let len = length_after_blinks(stone / split, blinks - 1, cache)
                    + length_after_blinks(stone % split, blinks - 1, cache);
            cache.insert((stone, blinks), len);
            len
        } else {
            length_after_blinks(stone*2024, blinks-1, cache)
        }
    }  
}

pub fn advent(filename: &str) -> (usize, usize) {
    let map =  Matrix::from_bytes_as_digits(&read(filename).expect("could not read input file"));
    let mut seen = Matrix::new(map.width, map.height, false);
    let (mut part1, mut part2) = (0,0);
    let mut current_region: VecDeque<Point> = VecDeque::new();

    for y in 0..map.height {
        for x in 0..map.width {
            let cur = Point::new(x, y);
            if seen[cur] { continue; }
            seen[cur] = true;

            let (mut area, mut perimeter, mut sides) = (0, 0, 0);
            let plant_type = map[cur];
            current_region.push_front(Point::new(x, y));

            while let Some(cur) = current_region.pop_front() {
                area += 1;
                for dir in [LEFT, RIGHT, UP, DOWN] {
                    let neighbor = cur + dir;
                    if map.get(neighbor) == Some(&plant_type) {
                        if !seen[neighbor] {
                            current_region.push_back(neighbor);
                            seen[neighbor] = true;
                        }
                    } else {
                        perimeter += 1;
                        sides += (map.get(cur+dir.clockwise()) != Some(&plant_type)
                               || map.get(cur+dir.clockwise()+dir) == Some(&plant_type)) as usize;
                    }
                }
            }
            //println!("Plant {plant_type} has area {area} and perimeter {perimeter}.");
            part1 += area*perimeter;
            part2 += area*sides;
        }
    }

    (part1, part2)
}

type Num = i64;

pub fn advent(filename: &str) -> (Num, Num) {
    let input =  read_to_string(filename).expect("could not read input file");
    let lines = input.lines().collect::<Vec<_>>();
    let (mut part1, mut part2) = (0,0);

    let extract_pair = |l: &str| {
        let mut nums = extract_numbers::<Num>(l);
        (nums.next().unwrap(), nums.next().unwrap())
    };

    for config in lines.chunks(4) {
        let a = extract_pair(config[0]);
        let b = extract_pair(config[1]);
        let d = extract_pair(config[2]);
        let d2 = (d.0 + 10000000000000, d.1 + 10000000000000);

        part1 += tokens(a, b, d).unwrap_or(0);
        part2 += tokens(a, b, d2).unwrap_or(0);
    }

    (part1, part2)
}

// Computes the integer coefficients `i` and `j` that solve the 2D vector
// equation `i*a + j*b = d`.
//
// The function attempts to find integers `i` and `j` such that the linear
// combinations of vectors `a` and `b` result in vector `d`. Specifically,
// it solves the equations:
// 
//   `ax * i + bx * j = dx`
//   `ay * i + by * j = dy`
// 
// The function returns the amount of tokens `3*i + j`. Here:
//   `i` corresponds to the amount of A button presses, and
//   `j` corresponds to the amount of B button presses.
#[inline]
fn tokens(a: (Num, Num), b: (Num, Num), d: (Num, Num)) -> Option<Num> {
    let det = a.0*b.1 - a.1*b.0; // Determinant (should not be zero)
    let j = (d.1*a.0 - a.1*d.0) / det;
    let i = (d.0 - b.0*j) / a.0;

    if a.0*i + b.0*j == d.0 && a.1*i + b.1*j == d.1 {
        Some(3*i + j)
    } else {
        None
    }
}

type Num = i32;

pub fn advent(filename: &str, width: Num, height: Num) -> (Num, Num) {
    let input =  read_to_string(filename).expect("could not read input file");
    let (thresh_x, thresh_y) = (width / 2, height / 2);
    let (mut northwest, mut northeast, mut southwest, mut southeast) = (0,0,0,0);
    let mut robots = Vec::new();
    let mut buf = Vec::new();

    for line in input.lines() {
        buf.clear();
        extract_numbers_signed::<Num>(line).collect_into(&mut buf);
        let (px, py, vx, vy) = (buf[0], buf[1], buf[2], buf[3]);
        robots.push((px, py, vx, vy));

        // Calculate future positions
        let px = (px + 100*vx).rem_euclid(width);
        let py = (py + 100*vy).rem_euclid(height);

        if px < thresh_x {
            if py < thresh_y { northwest += 1; }
            else if py > thresh_y { northeast += 1; }
        } else if px > thresh_x {
            if py < thresh_y { southwest += 1; }
            else if py > thresh_y { southeast += 1; }
        }
    }
    let part1 = northwest * northeast * southwest * southeast;

    // Part 2
    let mut part2 = 0;
    for i in 101..10000 {
        let mut map = vec![vec![0u32; width as usize]; height as usize];
        for &(px, py, vx, vy) in &robots {
            let px = (px + i * vx).rem_euclid(width);
            let py = (py + i * vy).rem_euclid(height);
            map[py as usize][px as usize] += 1;
        }

        if map.iter().any(|row| row.iter()
            .fold((0,0), |(consec, max), &val|
                if val == 1 { (consec + 1, max.max(consec+1)) }
                else { (0, max) }).1 >= 30)
            { part2 = i; break; }
    }

    (part1, part2)
}

type Num = i32;

pub fn advent(filename: &str) -> (Num, Num) {
    let input =  read_to_string(filename).expect("could not read input file");
    let (map, moves) = input.split_once("\n\n").expect("cannot find map and moves");

    let mut map1 = Matrix::from_str(map); // Map for part 1
    let mut map2 = Matrix::new(2 * map1.width, map1.height, b'.'); // Map for part 2

    for y in 0..map1.height {
        for x in 0..map1.width {
            let (c1, c2) = (Point::new(2 * x, y), Point::new(2 * x + 1, y));
            match map1[Point::new(x, y)] {
                b'#' => { map2[c1] = b'#'; map2[c2] = b'#' }
                b'O' => { map2[c1] = b'['; map2[c2] = b']' }
                b'@' => { map2[c1] = b'@' }
                _ => {}
            };
        }
    }

    let mut pos1 = map1.find(b'@').expect("cannot find robot in map");
    let mut pos2 = Point::new(2 * pos1.x, pos1.y);

    let mut seen = FxHashSet::default();
    let mut buf = Vec::new();

    for dir_char in moves.lines().flat_map(str::chars) {
        let dir = match dir_char {
            '^' => UP,
            '<' => LEFT,
            'v' => DOWN,
            '>' => RIGHT,
            _ => unreachable!("invalid direction character")
        };

        move_robot(&mut map1, &mut pos1, dir, &mut buf, &mut seen);
        move_robot(&mut map2, &mut pos2, dir, &mut buf, &mut seen);
    }

    let part1 = map1.find_all(b'O').map(|b| 100 * b.y + b.x).sum::<i32>();
    let part2 = map2.find_all(b'[').map(|b| 100 * b.y + b.x).sum::<i32>();
    (part1, part2)
}

fn move_robot(map: &mut Matrix<u8>, pos: &mut Point, dir: Point, bfs: &mut Vec<Point>, seen: &mut FxHashSet<Point>) {
    seen.clear();
    bfs.clear(); bfs.push(*pos);

    let mut i = 0;
    while i < bfs.len() {
        let next = bfs[i] + dir; i+=1;

        match map[next] {
            b'#' => return, // blocked by a wall
            b'[' | b']' | b'O' => {
                // If we haven't seen this box yet, enqueue it.
                if seen.insert(next) {
                    bfs.push(next);
                    // For vertical pushes, if it's part of a two-tile box, enqueue its partner.
                    if dir.y != 0 && (map[next] == b'[' || map[next] == b']') {
                        let other = next + if map[next] == b'[' { RIGHT } else { LEFT };
                        if seen.insert(other) { bfs.push(other); }
                    }
                }
            }
            _ => continue // empty space
        }
    }

    // Move all boxes in reverse order to avoid overwriting
    for &tile in bfs.iter().rev() {
        (map[tile], map[tile + dir]) = (map[tile + dir], map[tile]);
    }
    *pos += dir;
    //println!("Moving {:?}. Robot now at {:?}", dir, pos);
    //map.print();
}

type Num = usize;

pub fn advent(filename: &str) -> (Num, Num) {
    let input =  read(filename).expect("could not read input file");
    let map = Matrix::from_bytes(&input);
    let start = map.find(b'S').expect("no start position");
    let mut scores = Matrix::new(map.width, map.height, [Num::MAX; 4]);

    // Part 1: Dijkstra to find path with minimum score.
    // Using a minheap, check all tiles in order of minimum score to construct a
    // minimum score path to the destination.
    let mut todo = BinaryHeap::new();
    todo.push(MinHeapEntry {key: 0, data: (start, Direction::Right) });
    scores[start][Direction::Right.to_index()] = 0;

    let mut part1 = Num::MAX;
    while let Some(MinHeapEntry{ key: score, data: (pos, dir)}) = todo.pop() {
        if map[pos] == b'E' { part1 = score; break; } 
        if score > scores[pos][dir.to_index()] || map[pos] == b'#' { continue; }

        // Queue the different movement options
        let forward = (pos + dir.to_point(), dir,               score + 1);
        let right =   (pos,                  dir.clockwise(),   score + 1000);
        let left =    (pos,                  dir.counterwise(), score + 1000);

        for &(npos, ndir, nscore) in &[forward, right, left] {
            // Only queue this movement if it doesn't move into a wall or if it is a more costly path
            if map[npos] != b'#' && nscore < scores[npos][ndir.to_index()] {
                scores[npos][ndir.to_index()] = nscore;
                todo.push(MinHeapEntry{key: nscore, data: (npos, ndir)});
            }
        }
    }

    // Part 2: BFS backwards from the end, marking minimal-path cells
    // based on whether the path matches the calculated scores in `scores`.
    let end = map.find(b'E').expect("no end position");
    let mut seen = FxHashSet::default();
    let mut todo = VecDeque::new();
    for dir in Direction::VALUES {
        if scores[end][dir.to_index()] == part1 {
            todo.push_back((end, dir));
            seen.insert(end);
        }
    }

    while let Some((pos, dir)) = todo.pop_front() {
        let score = scores[pos][dir.to_index()];
        let back_forward = (pos - dir.to_point(), dir,               1);
        let back_right =   (pos,                  dir.clockwise(),   1000);
        let back_left =    (pos,                  dir.counterwise(), 1000);

        for &(npos, ndir, diff) in &[back_forward, back_right, back_left] {
            if diff <= score && scores[npos][ndir.to_index()] == score - diff {
                todo.push_back((npos, ndir));
                seen.insert(npos);
            }
        }
    }

    (part1, seen.len())
}

type Num = i64;

pub fn advent(filename: &str) -> (String, Num) {
    let input =  read_to_string(filename).expect("could not read input file");
    let lines = input.lines().collect::<Vec<_>>();

    let a = extract_numbers::<Num>(lines[0]).next().unwrap();
    let b = extract_numbers::<Num>(lines[1]).next().unwrap();
    let c = extract_numbers::<Num>(lines[2]).next().unwrap();
    let insts: Vec<_> = extract_numbers::<Num>(lines[4]).collect();

    let mut out: Vec<Num> = Vec::new();
    run_program(&insts, a, b, c, &mut out);
    let part1 = out.iter().join(",");

    let part2 = find_a_quine(0, 0, b, c, &insts, &mut out).unwrap_or_default();

    (part1, part2)
}

// Brute force `a` with three bits at a time, from LSB to MSB.
// The lowest three bits must be 000, so start with that. Then,
// find all higher three bits that result in the next correct output
// value from left to right.
fn find_a_quine(i: usize, a: Num, b: Num, c: Num, insts: &[Num], out: &mut Vec<Num>) -> Option<Num> {
    run_program(insts, a, b, c, out);
    if out == insts { return Some(a); } // We found the quine
    if i >= insts.len() {return None; }
    if i==0 || out[0] == insts[insts.len()-i] {
        for n in 0..8 {
            if let Some(found) = find_a_quine(i + 1, (a << 3) + n, b, c, insts, out) {
                return Some(found);
            }
        }
    }
    None
}

fn run_program(insts: &[Num], a: Num, b: Num, c: Num, output: &mut Vec<Num>) {
    output.clear();
    let mut ip: usize = 0;
    let mut a = a;
    let mut b = b;
    let mut c = c;

    while ip+1<insts.len() {
        let (opcode, operand) = (insts[ip], insts[ip+1]);
        let combo = || match operand {
            0..=3 => operand,
            4 => a,
            5 => b,
            6 => c,
            _ => unreachable!()
        };

        //println!("IP={ip}: opcode {opcode}, operand {operand}");
        match opcode {
            0 => a = a >> combo(),                              // ADV instruction
            1 => b ^= operand,                                  // BXL instruction
            2 => b = combo() % 8,                               // BST instruction
            3 => if a!=0 {ip = operand as usize; continue;},    // JNZ instruction
            4 => b ^= c,                                        // BXC instruction
            5 => output.push(combo() % 8),                      // OUT instruction
            6 => b = a >> combo(),                              // BDV instruction
            7 => c = a >> combo(),                              // CDV instruction
            _ => unreachable!()
        }
        ip += 2;
    }
}

type Num = i32;

pub fn advent(filename: &str, width: usize, part1_bytes: usize) -> (Num, String) {
    let input =  read_to_string(filename).expect("could not read input file");
    let mut map = Matrix::new(width as i32, width as i32, b'.');

    let extract_pair = |l: &str| {
        let mut nums = extract_numbers::<Num>(l);
        (nums.next().unwrap(), nums.next().unwrap())
    };

    let mut part1 = 0;
    let mut part2: String = String::new();

    let mut todo = VecDeque::new();
    let mut seen = Matrix::new(map.width, map.height, Num::MAX);
    let mut current_min_length = 0;


    for (i, line) in input.lines().enumerate() {
        let (x,y) = extract_pair(line);
        let pos = Point::new(x,y);
        map[pos] = b'#';

        if i == part1_bytes - 1 {
            // Part 1: Shortest path length after given number of obstacles
            let start = Point::new(0, 0);
            todo.push_back(start);
            seen[start] = 0;
            part1 = shortest_path(&mut map, &mut todo, &mut seen).expect("end must be reachable for part 1");
            current_min_length = part1;
        } else if i >= part1_bytes {
            // Part 2: Find after which new obstacle there is no possible path anymore
            let obstacle_step = seen[pos];
            // If the obstacle is on an unreachable tile, it won't harm
            if obstacle_step == Num::MAX { continue; }
            // If the obstacle is somewhere after having reached the end, it won't harm
            if obstacle_step >= current_min_length { continue; }

            // Reset all tiles with higher step count than obstacle (so they can be explored again)
            for steps in seen.elements.iter_mut() {
                if *steps > obstacle_step {
                    *steps = Num::MAX;
                }
            }

            // Continue search from all tiles with same step count as obstacle.
            todo.clear();
            let mut alternative_route_available = false;
            for npos in seen.find_all(obstacle_step) {
                if npos != pos {
                    alternative_route_available = true;
                    todo.push_back(npos);
                }
            }
            // If there are no other tiles with the same step counts, this obstacle blocks the only path.
            if !alternative_route_available {
                part2 = format!("{x},{y}");
                break;
            }
            // See if there is a route remaining
            if let Some(result) = shortest_path(&mut map, &mut todo, &mut seen) {
                current_min_length = result;
            } else {
                part2 = format!("{x},{y}");
                break;
            }
        }
    }
    (part1, part2)
}

// Compute shortest paths from top-left to all reachable cells using BFS.
// Returns shortest path steps to the bottom-right if reachable.
fn shortest_path(map: &mut Matrix<u8>, todo: &mut VecDeque<Point>, seen: &mut Matrix<Num>) -> Option<Num> {
    let end = Point::new(map.width - 1, map.height - 1);
    let mut minlength = None;

    while let Some(pos) = todo.pop_front() {
        let steps = seen[pos];
        if pos == end && minlength.is_none() { minlength = Some(steps); }
        if map[pos] == b'#' { continue; }

        for &npos in &[pos + LEFT, pos + RIGHT, pos + UP, pos + DOWN] {
            let nsteps = steps + 1;
            if map.contains(npos) && map[npos] != b'#' && nsteps < seen[npos] {
                seen[npos] = nsteps;
                todo.push_back(npos);
            }
        }
    }
    minlength
}

type Num = usize;

pub fn advent(filename: &str) -> (Num, Num) {
    let input =  read_to_string(filename).expect("could not read input file");
    let mut lines = input.lines();
    let available: Vec<_> = lines.next().unwrap().split(", ").collect();
    lines.next(); // skip empty line

    let (mut part1, mut part2) = (0,0);
    let mut cache = vec![usize::MAX; 100];
    for pattern in lines {
        cache.fill(usize::MAX);
        let c = num_combinations(&pattern, 0, &available, &mut cache);
        part1 += (c > 0) as usize;
        part2 += c;
    }

    (part1, part2)
}

fn num_combinations(target: &str, idx: usize, available: &[&str], cache: &mut [usize]) -> usize {
    if idx == target.len() {return 1}
    if cache[idx] != usize::MAX {return cache[idx]}
    let mut total = 0;
    for &p in available {
        if target[idx..].starts_with(p) {
            total += num_combinations(target, idx+p.len(), available, cache);
        }
    }
    cache[idx] = total;
    total
}

type Num = usize;
const MIN_PICO: usize = 100;

pub fn advent(filename: &str) -> (Num, Num) {
    let input =  read(filename).expect("could not read input file");
    let map = Matrix::from_bytes(&input);
    let start = map.find(b'S').expect("no start position");
    let end = map.find(b'E').expect("no end position");
    let mut picos = Matrix::new(map.width, map.height, Num::MAX);
    picos[start] = 0;
    let mut next_pico = 1;

    // BFS to find path from start to end
    let mut todo = VecDeque::new();
    todo.push_back(start);
    let mut path = vec![start];
    while let Some(pos) = todo.pop_front() {
        if pos == end { break; } 
        for &npos in &[pos + LEFT, pos + RIGHT, pos + UP, pos + DOWN] {
            if map.contains(npos) && map[npos] != b'#' && picos[npos] > next_pico {
                picos[npos] = next_pico;
                todo.push_back(npos);
                path.push(npos);
            }
        }
        next_pico+=1;
    }

    let (mut part1, mut part2) = (0,0);

    // Check every pair in path: If distance is smaller than 20, it's a potential cheat.
    let total_time = path.len();
    for i in 0..total_time.saturating_sub(MIN_PICO) {
        let start = path[i];
        for j in (i+MIN_PICO)..total_time {
            let end = path[j];
            let cheat_time = (start.x-end.x).abs() + (start.y-end.y).abs();
            if cheat_time > 20 {continue;}
            let old_time = (j-i) as i32;
            if old_time - cheat_time >= MIN_PICO as i32 {
                part2 += 1;
                if cheat_time <= 2 {
                    part1 += 1;
                }
            }
        }
    }

    (part1, part2)
}

type Num = usize;
const NUMPAD: &str = "789\n456\n123\n 0A";
const DIRPAD: &str = " ^A\n<v>";

pub fn advent(filename: &str) -> (Num, Num) {
    let input =  read_to_string(filename).expect("could not read input file");

    let numpad = Matrix::from_str(NUMPAD);
    let dirpad = Matrix::from_str(DIRPAD);

    let (mut part1, mut part2) = (0,0);
    let mut seq_cache = FxHashMap::default();

    for line in input.lines() {
        if line.is_empty() {break;}
        let numeric_part: usize = extract_numbers::<usize>(line).next().unwrap();

        let (mut seq_len1, mut seq_len2) = (0, 0);
        let mut prev_key = b'A';
        
        for key in line.bytes() {
            let mut prev_dir = b'A';
            for dir in seq_from_to(prev_key, key, &numpad) {
                seq_len1 += shortest_seq_len(prev_dir, dir, &dirpad, 2, &mut seq_cache);
                seq_len2 += shortest_seq_len(prev_dir, dir, &dirpad, 25, &mut seq_cache);
                prev_dir = dir;
            }
            prev_key = key;
        }
        part1 += numeric_part * seq_len1;
        part2 += numeric_part * seq_len2;
    }

    (part1, part2)
}

// DP[from][to][layers]. The parameter [layers] holds the remaining number
// of dirpad robot layers to consider. Memoization using [cache].
// 
// Returns the length of the shortest sequence after that many layers
// from start to finish.
fn shortest_seq_len(from: u8, to: u8, pad: &Matrix<u8>, layers: u8, cache: &mut FxHashMap<(u8,u8,u8), usize>) -> usize {
    if let Some(result) = cache.get(&(from, to, layers)) {return *result}
    let mut result = 0;

    let seq = seq_from_to(from, to, &pad);
    if layers == 1 { result = seq.len() }
    else {
        let mut prev = b'A';
        for key in seq {
            result += shortest_seq_len(prev, key, pad, layers-1, cache);
            prev = key;
        }
    }
    cache.insert((from, to, layers), result);
    result
}

// The optimal way to get from start to end is by minimizing the direction
// changes along the path. So either move all the way horizontally first
// and then vertically or the other way round (in case that would cross the
// missing corner in the pad). Second, prefer going left (horizontal) first
// if we have to go left. Otherwise, go vertical first.
fn seq_from_to(from: u8, to: u8, pad: &Matrix<u8>) -> Vec<u8> {
    let start = pad.find(from).expect("no start found");
    let end = pad.find(to).expect("no end found");
    
    let d = end-start;
    let vert = if d.y >=0 {b'v'} else {b'^'}; // vertical direction
    let hori = if d.x >=0 {b'>'} else {b'<'}; // horizontal direction

    let mut resulting_path = Vec::with_capacity(d.x.abs()as usize+d.y.abs()as usize);
    if (d.x < 0 && pad[Point::new(end.x, start.y)] != b' ')
       || pad[Point::new(start.x, end.y)] == b' ' {
        for _ in 0..d.x.abs() { resulting_path.push(hori) } // horizontal first
        for _ in 0..d.y.abs() { resulting_path.push(vert) }
    } else {
        for _ in 0..d.y.abs() { resulting_path.push(vert) } // vertical first
        for _ in 0..d.x.abs() { resulting_path.push(hori) }
    }
    resulting_path.push(b'A');
    resulting_path
}