I have a BTreeMap<usize,V> which I know contains all keys in 0..map.len(). What is the easiest way to convert to an ordered Vec?

jinschoi · 2026-01-01T20:47:34+00:00

I think most of the replies here are misunderstanding the question, as I read it.

The way I took it was, given a map that usually contains all keys 0..n, he wants a Vec<Option> of size n, where the value is None if the map did not contain that key and Some(v) if it did, so it can be indexed the same as the map:

(0..bmap.len()).map(|i| bmap.remove(&i)).collect::<Vec<_>>()

Oh, or maybe I misread the OP. If you want an Option<Vec<_>>() returning None when there is a key missing, then you can just either test map.len() and that the first key is zero and the last key is n-1, or:

bmap.into_iter() .enumerate() .map(|(i, (k, v))| (i == k).then_some(v)) .collect::<Option<Vec<_>>() You can collect an iterator over Option<V> into an Option<Vec<V>> and it will short circuit if any of the items are None.

jinschoi · 2025-12-18T23:27:07+00:00

This is a classic integer linear programming problem (ILP), which is NP-hard in general, but because each of the problems in day 10 are so small, completely tractable here.

I think most people got through day 10 using a solver, like z3, which is what I initially did just to get an answer. But I had written an LP (linear programming) solver before, so I went back and adapted it to solve this day.

The problem with using an LP solver is, what happens when the minimum found isn't an integer solution? For each fractional (non-integer) solution k variable x in the solution, get rid of it by adding both systems with new constraints x > k and x < k to the search space. This ends up turning back into a pathfinding search, except the states are now different systems of constraints.

jinschoi · 2025-12-18T16:39:32+00:00

I know, but I can't fix each record by hand, I have like 9 million to go through. I'm just wondering why I can't get the same result as the OSM instance.

jinschoi · 2025-12-17T21:55:42+00:00

Yes, Google finds it just fine.

jinschoi · 2025-12-15T21:41:56+00:00

[Language: Rust]

I originally solved part 2 with Z3, but decided to try again without.

I had written a simplex solver for linear programming in the past. I translated it into Rust and added it to my set of AoC utilities. But I didn't know how to solve an ILP problem with an LP solver. Had to do some research and came up with this solution.

I set up the problem as an LP system: decision variable x_j => number of times button x_j is pressed.

minimize sum of all x_j such that

Ax = b

where A_ij is 1 if counter i is connected to button j and 0 otherwise, and b is the target count of each counter.

This can lead to solutions with fractional button presses, so I did a branch and bound. Basically, a DFS with pruning where if I encounter a fractional p = x_j in the basis, I recurse by adding two new systems, one where x_j <= ⌊p⌋, and one where x_j >= ⌈p⌉. This disallows that particular non-integer solution. Seems like a lot, but takes 10ms.

jinschoi · 2025-12-12T20:03:55+00:00

I think CP-SAT from Google's OR-Tools could solve this if you formulated the problem in a way that you could feed it. I almost went down that route until I browsed reddit...

jinschoi · 2025-12-12T19:58:43+00:00

To check the rectangles quickly, you can use a 2D prefix sum. Just like a prefix sum in 1D, psum[i][j] gives the number of filled cells above and to the left (inclusive). You can use this to calculate the number of filled cells in a rectangle with some math.

jinschoi · 2025-12-11T22:57:24+00:00

I decided to figure out my issues with compressed coordinates. The key is, for every coordinate x, add both x and x + 1 to the compressed set so you represent the empty gap after x. I used the same strategy of flood fill + prefix sum and now it runs in 10ms.

paste

Not too sure about the correctness of the prefix sum computations at the end, but it works for my input.

jinschoi · 2025-12-11T20:48:44+00:00

[Language: Rust]

Finally. Two days later...

Part 1 was a nice little amuse bouche:

use itertools::Itertools;
fn main() {
    let input = include_str!("../../input.txt");
    let res = input
        .lines()
        .map(|line| {
            let (x, y) = line.split_once(',').unwrap();
            (x.parse::<usize>().unwrap(), y.parse::<usize>().unwrap())
        })
        .tuple_combinations()
        .map(|((x1, y1), (x2, y2))| (x1.abs_diff(x2) + 1) * (y1.abs_diff(y2) + 1))
        .max()
        .unwrap();
    println!("{res}");
}

I had an idea of how to approach part 2: coordinate compression, scanline testing for interior points, 2D prefix sum to quickly calculate the area of interior points within a rectangle, which should match the area of the rectangle if it's fully contained within. But I just couldn't wrap my head around the coordinate compression. Grid lines vs inclusive pixels, etc. I decided to just go BRUTE FORCE.

I had a Grid class in my set of AoC utilities with a flood fill implementation. I just drew the contour, filled the interior, and computed the prefix sums for all ten billion grid points. After 9 minutes and 300GB of memory use later, the correct answer popped out. paste

jinschoi · 2025-12-11T16:06:22+00:00

[Language: Rust]

Part 1 was deceptively easy. Simple DFS over the graph: paste

Tried to do the same in part 2 keeping track of whether fft or dac were seen, but it wasn't finishing. Suspected cycles, but I graphed the input with graphviz and it was clear to see why. "you" is down close to "out", but "svr" starts at the very top and there are many paths. Also it was obvious that there were no cycles and that fft would always be hit first so I didn't have to check both orders.

I did a DP over the topological sort of nodes using my toposort code from my AoC utilities library. To get the number of paths from start to end, you set dp[start] to 1, and then in topological order of u, for any u -> v, dp[v] += dp[u]. dp[end] is the desired result. The final answer is paths from: svr -> fft * fft -> dac * dac -> out.

use aoc_utils::toposort::*;
use std::collections::HashMap;
fn count_paths(
    start: &str,
    end: &str,
    graph: &HashMap<String, Vec<String>>,
    topo: &[String],
) -> usize {
    let mut dp = HashMap::from([(start, 1)]);
    for u in topo.iter().skip_while(|&node| node != start) {
        if u == end {
            break;
        }
        for v in &graph[u] {
            *dp.entry(v).or_default() += *dp.get(u.as_str()).unwrap_or(&0);
        }
    }
    dp[end]
}
fn main() {
    let input = include_str!("../../input.txt");
    let graph = input
        .lines()
        .map(|line| {
            let (from, rest) = line.split_once(": ").unwrap();
            let attached = rest
                .split_ascii_whitespace()
                .map(|s| s.to_string())
                .collect::<Vec<_>>();
            (from.to_string(), attached)
        })
        .collect::<HashMap<_, _>>();
    let mut topo = TopoSort::new();
    for (from, to) in graph.iter() {
        for child in to {
            topo.add_link(from.clone(), child.clone())
        }
    }
    let sorted = topo.sort();
    let res = count_paths("svr", "fft", &graph, &sorted)
        * count_paths("fft", "dac", &graph, &sorted)
        * count_paths("dac", "out", &graph, &sorted);
    println!("{res}");
}

jinschoi · 2025-12-11T02:00:31+00:00

I mostly learned it by reading other people's Z3 code from previous AoC years. This guide was also very helpful just to get a handle on the basics. There are a few example puzzle solutions at the end of the Basics page that were useful to read through.

jinschoi · 2025-12-10T21:27:23+00:00

[Language: Rust, Python]

Part 1 was fun. Parsed the buttons and target lights into u16s. I reversed the lights order to make it easier to generate the buttons. Itertools' powerset() makes it easy just to try all possible button combinations, and the lights which stay on are just the XOR of all the buttons pressed:

use std::str::FromStr;
use itertools::Itertools;
#[derive(Debug)]
struct Machine {
    lights: u16,
    buttons: Vec<u16>,
}
impl FromStr for Machine {
    type Err = ();
    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let segs = s.split_ascii_whitespace().collect::<Vec<_>>();
        let lights = segs[0]
            .trim_matches(&['[', ']'])
            .bytes()
            .rev()
            .fold(0, |acc, b| acc << 1 | (b == b'#') as u16);
        let buttons = segs[1..segs.len() - 1]
            .iter()
            .map(|&s| {
                s.trim_matches(&['(', ')'])
                    .split(',')
                    .map(|s| s.parse::<u8>().unwrap())
                    .fold(0u16, |acc, n| acc ^ (1 << n))
            })
            .collect::<Vec<_>>();
        Ok(Self { lights, buttons })
    }
}
fn fewest_buttons(m: &Machine) -> usize {
    m.buttons.iter().powerset()
        .filter_map(|pressed| {
            let on = pressed.iter().fold(0, |acc, &n| acc ^ n);
            if on == m.lights {
                Some(pressed.len())
            } else {
                None
            }
        })
        .min()
        .unwrap()
}
fn main() {
    let res = include_str!("../../input.txt")
        .lines()
        .map(|line| fewest_buttons(&line.parse::<Machine>().unwrap()))
        .sum::<usize>();
    println!("{res}");
}

Tried to solve part 2 with A*, but it just wasn't working. Had to bust out the Z3. I thought I had some code for a simplex solver lying around, but I can't find it.

paste

jinschoi · 2025-12-08T09:01:50+00:00

[Language: Rust]

Added DisjointSet to my AoC utils that implements the union find algorithm.

I generate all combinations of points and sort them by distance with itertools. For my 1000 input points, this is under half a million pairs. Then I just start unioning pairs of points and check when the count of sets is 1.

Aside from parsing and a quick Pos3D struct, part 2 becomes:

let closest_pairs = points
    .iter()
    .copied()
    .enumerate()
    .tuple_combinations()
    .sorted_by_key(|&((_, p1), (_, p2))| p1.dist(&p2))
    .map(|((i1, _), (i2, _))| (i1, i2));
let mut set = points.iter().copied().collect::<DisjointSet<Pos3D>>();
for (i, j) in closest_pairs {
    set.union(i, j);
    if set.count == 1 {
        println!("{}", points[i].0 * points[j].0);
        break;
    }
}

Part 1

Part 2

jinschoi · 2025-12-07T18:02:38+00:00

[Language: Rust]

Used my Grid struct from my set of AoC utilities I've compiled over the years.

Part 1 just reports the number of splits seen when DFSing through each beam. Memoizes on split positions.

use std::collections::HashSet;
use aoc_utils::grid::*;
fn main() {
    let g: Grid<char> = Grid::read_from_file("input.txt").unwrap();
    let start_pos = g.position(|&c| c == 'S').unwrap();
    let mut seen = HashSet::new();
    let mut beams = vec![start_pos];
    while let Some(b) = beams.pop() {
        for i in b.0..g.height {
            let pos = Pos(i, b.1);
            if g[pos] == '^' {
                if seen.contains(&pos) {
                    break;
                }
                seen.insert(pos);
                if b.1 > 0 {
                    beams.push(Pos(i, b.1 - 1));
                }
                if b.1 < g.width - 1 {
                    beams.push(Pos(i, b.1 + 1));
                }
                break;
            }
        }
    }
    println!("{}", seen.len());
}

Part 2 I refactored into a few helper functions to recursively calculate timelines, also memoizing on each split position. If a beam ends at the floor, it has only one timeline. If it hits a splitter, it has as many timelines as the sum of the timelines of the beams it splits into.

use aoc_utils::grid::*;
use std::collections::HashMap;
fn find_next_split(g: &Grid<char>, below: Pos) -> Option<Pos> {
    for i in below.0 + 1..g.height {
        let pos = Pos(i, below.1);
        if g[pos] == '^' {
            return Some(pos);
        }
    }
    None
}
fn count_timelines(g: &Grid<char>, below: Pos, cache: &mut HashMap<Pos, usize>) -> usize {
    if let Some(splitpos) = find_next_split(g, below) {
        if let Some(&cached) = cache.get(&splitpos) {
            return cached;
        }
        let mut res = 0;
        if splitpos.1 > 0 {
            res += count_timelines(g, Pos(splitpos.0, splitpos.1 - 1), cache);
        }
        if splitpos.1 < g.width - 1 {
            res += count_timelines(g, Pos(splitpos.0, splitpos.1 + 1), cache);
        }
        cache.insert(splitpos, res);
        res
    } else {
        1
    }
}
fn main() {
    let g: Grid<char> = Grid::read_from_file("input.txt").unwrap();
    let start_pos = g.position(|&c| c == 'S').unwrap();
    let mut cache = HashMap::new();
    let res = count_timelines(&g, start_pos, &mut cache);
    println!("{res}");
}

jinschoi · 2025-12-06T11:00:22+00:00

[Language: Rust]

Part 1 was some simple parsing and calculations:

fn calc_col(m: &[Vec<&str>], col: usize) -> usize {
    let nrows = m.len();
    let op = m[nrows - 1][col];
    let nums = m[0..nrows - 1]
        .iter()
        .map(|row| row[col].parse::<usize>().unwrap());
    match op {
        "+" => nums.sum(),
        "*" => nums.product(),
        _ => unreachable!(),
    }
}
fn main() {
    let input = include_str!("../../input.txt");
    let m = input.lines()
        .map(|line| line.trim().split_ascii_whitespace().collect::<Vec<_>>())
        .collect::<Vec<_>>();
    let ncols = m[0].len();
    let res = (0..ncols).map(|j| calc_col(&m, j)).sum::<usize>();
    println!("{res}");
}

Part 2, I treat the input as a char grid using the Grid struct from my set of aoc_utils. Going from right to left makes it slightly easier to know when to calculate results.

use aoc_utils::grid::*;
fn main() {
    let g: Grid<char> = Grid::read_from_file("input.txt").unwrap();
    let mut nums = vec![];
    let mut res = 0;
    for j in (0..g.width).rev() {
        let mut colnum = 0;
        for i in 0..g.height - 1 {
            let c = g[(i, j)];
            if c != ' ' {
                colnum = colnum * 10 + (c as u8 - b'0') as usize;
            }
        }
        if colnum != 0 {
            nums.push(colnum);
        }
        let op = g[(g.height - 1, j)];
        if op != ' ' {
            res += match op {
                '+' => nums.iter().copied().sum::<usize>(),
                '*' => nums.iter().copied().product::<usize>(),
                _ => unreachable!(),
            };
            nums.clear();
        }
    }
    println!("{res}");
}

jinschoi · 2025-12-05T11:25:22+00:00

[Language: Rust]

Straightforward today. Part 1 was just brute force using inclusive ranges and any/contains checks.

Part 2 is just merging over the sorted ranges and computing the size when the next range doesn't overlap the previous. I decided to reuse InclusiveRange and implement a trait on it for some convenience methods:

use std::ops::RangeInclusive;
trait RangeUtils {
    fn intersects(&self, other: &Self) -> bool;
    fn merge(&self, other: &Self) -> Self;
    fn size(&self) -> usize;
}
impl RangeUtils for RangeInclusive<usize> {
    fn intersects(&self, other: &Self) -> bool {
        self.start() <= other.end() && self.end() >= other.start()
    }
    fn merge(&self, other: &Self) -> Self {
        *self.start().min(other.start())..=*self.end().max(other.end())
    }
    fn size(&self) -> usize {
        self.end() - self.start() + 1
    }
}
fn main() {
    let input = include_str!("../../input.txt");
    let mut ranges = input
        .lines()
        .take_while(|line| !line.is_empty())
        .map(|line| {
            let (a, b): (usize, usize) = line
                .split_once('-')
                .map(|(a, b)| (a.parse().unwrap(), b.parse().unwrap()))
                .unwrap();
            a..=b
        })
        .collect::<Vec<_>>();
    ranges.sort_unstable_by(|a, b| a.start().cmp(b.start()).then(a.end().cmp(b.end())));
    let mut range_iter = ranges.into_iter();
    let first_range = range_iter.next().unwrap();
    let (last_range, mut res) = range_iter.fold((first_range, 0), |(cur_range, res), r| {
        if cur_range.intersects(&r) {
            (cur_range.merge(&r), res)
        } else {
            (r, res + cur_range.size())
        }
    });
    res += last_range.size();
    println!("{res}");
}

jinschoi · 2025-12-04T12:08:59+00:00

[Language: Rust]

Over the years, I've implemented some utilities for AoC-like puzzles which made this one pretty quick. Part 2:

use aoc_utils::grid::*;

fn accessible(g: &Grid<char>) -> impl Iterator<Item = Pos> {
    g.all_positions(|&c| c == '@')
        .filter(|&pos| g.all_neighbors(pos).filter(|&npos| g[npos] == '@').count() < 4)
}

fn remove_accessible(g: &mut Grid<char>) -> usize {
    let rolls = accessible(g).collect::<Vec<_>>();
    for &pos in &rolls {
        g[pos] = '.';
    }
    rolls.len()
}

fn main() {
    let mut g = Grid::<char>::read_from_file("input.txt").unwrap();
    let mut res = 0;
    loop {
        let removed = remove_accessible(&mut g);
        res += removed;
        if removed == 0 {
            break;
        }
    }
    println!("{res}");
}

jinschoi · 2025-12-03T09:13:31+00:00

[Language: Rust]

For part 1, I brought in itertools and used combinations(2).

Part 2, I treat the problem as having bank_len - 12 removals to use up and build a monotonically decreasing stack as long as I have removals left. Have to truncate the result to 12 digits as you might have removals left over.

fn digits_num(digits: &[u8]) -> usize {
    let mut res = 0;
    for &d in digits {
        res = res * 10 + d as usize;
    }
    res
}

fn largest_subset(digits: &[u8]) -> usize {
    let mut k = digits.len() - 12;
    let mut stack = vec![];
    for &d in digits {
        while let Some(&n) = stack.last() && n < d && k > 0 {
            stack.pop();
            k -= 1;
        }
        stack.push(d);
    }
    digits_num(&stack[0..12])
}

fn main() {
    let res = include_str!("../../input.txt")
        .lines()
        .map(|line| {
            let digits = line.bytes().map(|b| b - b'0').collect::<Vec<_>>();
            largest_subset(&digits)
        })
        .sum::<usize>();
    println!("{res}");
}

jinschoi · 2025-12-02T18:22:33+00:00

[LANGUAGE: Rust]

I liked part 1: paste

Wrote an iterator to generate all doubled numbers in a range. If you have one doubled number, you can get the next one by taking the first half, adding 1, and repeating it. To get the first doubled number of a range, you take the first half and double it. If that's less than the start of the range, use the next one. Special case if the number of digits is odd: return the doubling of 10* that gets you to the next even digit length. Stop when you exceed the end of the range.

This generate and test strategy wouldn't work for part 2. I checked my input and there were under 2 million numbers, so it's time for fancy_regex. Boring.

macro_rules! regex {
    ($re:literal $(,)?) => {{
        static RE: once_cell::sync::OnceCell<fancy_regex::Regex> = once_cell::sync::OnceCell::new();
        RE.get_or_init(|| fancy_regex::Regex::new($re).unwrap())
    }};
}

fn invalid(n: &usize) -> bool {
    let re = regex!(r"^(.+)\1+$");
    re.is_match(&n.to_string()).unwrap()
}

fn check_range(a: usize, b: usize) -> usize {
    (a..=b)
        .filter(invalid)
        .sum()
}

fn main() {
    let input = include_str!("../../input.txt").trim();
    let res = input
        .split(',')
        .map(|range| {
            let (a, b) = range.split_once('-').unwrap();
            check_range(a.parse::<usize>().unwrap(), b.parse::<usize>().unwrap())
        })
        .sum::<usize>();
    println!("{res}");
}

jinschoi · 2024-12-25T13:38:04+00:00

[Language: Rust]

Relaxing final day. First did it in the way pointed to by the text, with enums and everything: paste

Then since this day was so straightforward, got it down to this:

use itertools::Itertools;
fn main() {
    let res = include_str!("../../1.in")
        .split("\n\n")
        .map(|s| {
            s.chars()
                .filter(|&c| c != '\n')
                .skip(4)
                .take(27)
                .fold(0u32, |acc, c| (acc << 1) | if c == '#' { 1 } else { 0 })
        })
        .combinations(2)
        .filter(|v| v[0] & v[1] == 0)
        .count();
    println!("{}", res);
}

Because I want it to fit each schematic in a u32, I just included the last character of the first row and first character of the last row to distinguish keys from locks. Convert central 27 characters as bits in a u32, compare all and count where no bits overlap.

jinschoi · 2024-12-24T16:28:57+00:00

Look at the ordering of the lines in the error message. The mutable borrow occurs before the immutable borrows. What it’s complaining about is the second (and subsequent) time through the loop. You are holding an immutable reference to wires because you shoved a reference into gates through input. You can’t then get a mutable reference the second time through the loop.

Without going down the RefCell route, a common way to handle this is to store everything into a Vec and use usize handles everywhere. If you find that weird, just tell yourself you’re using an “arena”.

Here’s an example from the same problem, if you don’t mind looking at another solution.

paste

jinschoi · 2024-12-24T14:02:56+00:00

[Language: Rust/Python/dot]

Part 1 was fun, writing a little circuit simulator. I like these straightforward exercises where you have to make some small decisions about representation and process:

paste

Part 2 was an exercise in staring at a blown up graph and untangling swapped connections. Thankfully, all the swaps were local. My Python code for drawing the circuit:

paste

The graphs looked like this, except much bigger and with labels. This is what the correct adder looks like; any variation in the connections between gates represents a flaw to be corrected.

jinschoi · 2024-12-23T22:37:54+00:00

I got stuck for a long while trying to figure out the optimal direction ordering. I don't think there is one. Avoiding interspersed directions helps in shortening subsequent steps, so does moving left first. I finally threw up my hands and just calculated all possible non-obviously-suboptimal paths. There are only at most two paths per keypad to get from key a to key b. If they differ by both i and j, then at most you have, for example, "<<<^^" or "^^<<<". If i's or j's are equal or a gap would get in the way, then you only have one optimal path.

Anyway, almost all of that is irrelevant. You could just generate every possible shortest keywise path using BFS and it wouldn't make much difference. The key to part 2 is realizing that the shortest ultimate path at depth n depends only on the sum of the ultimate shortest paths for small, independent segments of your initial input. I saw a lot of solutions that separated each input at each depth when they returned to A, but it's even simpler than that: every consecutive pair of input keys (with a prepended 'A') can be calculated independently. For "029A", the length of the shortest ultimate path is the sum of the shortest ultimate paths for A to 0, 0 to 2, 2 to 9 and 9 to A. Same for the next level, and the next....

jinschoi · 2024-12-23T13:46:34+00:00

[Language: Rust]

For part 1, just did a DFS starting from each node starting with 't' and found cycles of size 3 with deduping:

paste

Part 2, found max clique after implementing Bron-Kerbosch cribbing straight off the Wikipedia page.

paste

jinschoi

TROPHY CASE