Nvim stuff

I've really been appreciating tpope/vim-fugitive. It might unironically be the first time that I prefer to work with a plugin rather than CLI git directly.

I'm loving Vim controls, but nothing makes you feel dumber than off-by-1 typo'ing a multi-character command and completely mangling everything without even knowing what you just did. At least Nvim's undo is insanely good.

The task itself

Code

Relatively complicated parsing notwithstanding, the first part isn't actually that bad. Instead of using the provided (destination, source, length) triplets, I convert them to ((start of range, end of range), offset), where offset is simply destination - source—so that adding offset to a number in the source range maps it to the destination range. It just felt easier to think about the task like that for me.

type Mappings = Vec<(Range<i64>, i64)>;
type Seeds = Vec<i64>;

/// Parses the puzzle input into a list of seeds and list mapping tables.
fn parse(input: &str) -> Option<(Seeds, Vec<Mappings>)> {
    let mut chunks = input.split("\r\n\r\n");
    let (_, seeds) = chunks.next()?.split_once(": ")?;

    let seeds = seeds
        .split_whitespace()
        .filter_map(|n| n.parse::<i64>().ok());
    let mappings = chunks.map(|chunk| {
        chunk
            .lines()
            .skip(1)
            .filter_map(|line| {
                let mut tokens = line
                    .split_whitespace()
                    .filter_map(|n| n.parse::<i64>().ok());
                let destination = tokens.next()?;
                let source = tokens.next()?;
                let length = tokens.next()?;

                Some((source..source + length, destination - source))
            })
            .collect()
    });

    Some((seeds.collect(), mappings.collect()))
}

The first part is very much a warmup for the second part. You just have to actually run the mapping for all seeds, and find the smallest one.

pub fn one(input: &str) -> crate::Result<i64> {
    let (mut seeds, mappings) = parse(input).ok_or("parse failed")?;

    for mapping in mappings {
        for seed in &mut seeds {
            let offset = mapping
                .iter()
                .find_map(|(r, o)| r.contains(&*seed).then_some(*o))
                .unwrap_or(0);

            *seed += offset;
        }
    }

    seeds.into_iter().min().ok_or("no result".into())
}

There's not much to say here—for every seed, we just find the source range it's in, and get the corresponding offset. If there's none, we use offset 0 (the puzzle explicitly states that not being in any source range means a number maps to itself, so... offset 0).

Part 2 is a great twist, honestly. Now, instead of having singular seeds to map, you have ranges of seeds. So you're mapping ranges using other ranges. It's rad. Overlapping ranges is gonna be very useful, so I wrote this little utility:

fn interval_overlap((s1, e1): (i64, i64), (s2, e2): (i64, i64)) -> Option<(i64, i64)> {
    let s = s1.max(s2);
    let e = e1.min(e2);

    (s < e).then_some((s, e))
}

It just returns the overlap of two ranges, given as (i64, i64). If you don't know about bool::then_some, it's equivalent to this:

if s < e {
	Some((s, e))
} else {
    None
}

It's a handy utility; frequently you'll have the structure of "if something is true, return this value", and that's exactly what this is.

Anyway, back to the task at hand. My solution sketch is relatively simple, conceptually:

For each seed range, find all source ranges it overlaps. For each such overlap, overlap + offset is a new range for the next mapping table. Repeat for each mapping table.

There's a couple fiddly bits with the actual implementation, but I ended up with this:

pub fn two(input: &str) -> crate::Result<i64> {
    let (seeds, mappings) = parse(input).ok_or("parse failed")?;
    let mut seed_ranges: Vec<_> = seeds.chunks(2).map(|c| (c[0], c[0] + c[1])).collect();

    for mapping in mappings {
        let mut new_ranges = vec![];

        while let Some(range) = seed_ranges.pop() {
            let overlap = mapping
                .iter()
                .find_map(|(r, o)| interval_overlap(range, (r.start, r.end)).map(|v| (v, o)));

            if let Some(((s, e), offset)) = overlap {
                new_ranges.push((s + offset, e + offset));

                if s > range.0 {
                    seed_ranges.push((range.0, s));
                }
                if e < range.1 {
                    seed_ranges.push((e, range.1));
                }
            } else {
                new_ranges.push(range);
            }
        }

        seed_ranges = new_ranges;
    }

    seed_ranges
        .into_iter()
        .map(|r| r.0)
        .min()
        .ok_or("no result".into())
}

So during each mapping step, we have two Vecs we operate on:

• seed_ranges: the ranges we still have process;
• new_ranges: processed ranges, will become seed_ranges at the end of the iteration.

Specifically, I treat seed_ranges as a stack of ranges to process. I take the topmost range, find a source range it overlaps, and then split it up into up to three ranges (the overlap, the part before it, the part after it). The overlap gets offset, and is now done being processed; the parts before and after return to seed_ranges as new, smaller ranges to process.

Eventually, I end up with a list of fully-processed ranges of seeds. Out of curiosity, I checked how many I end up with—it's 75 smaller ranges, for my input; out of 10 starting ranges. That's a very reasonable number to end up with.

Pretty happy with how quickly I came up with this. Any attempt at actually reusing the single seed processing from part 1 would be much slower, but as is, I managed another sub-one millisecond solution.