Part 2 of my “Advent of Code 2023” series.

Like with Day 1, Day 5 part I started innocently enough. This time, it was modelling a pipeline of transformations. The puzzle input was broken down into sections, which came in order and could, thankfully, be processed atomically.

Having learnt a lesson from Day 1, I was no longer constrained to a single line, and so my initial naive solution looked something like this:

/*
 * Define a mapping range between:
 *      start -- end => (start + offset) -- (end + offset)
 */
record Range(long start, long end, long offset) {

    /*
     * Check if the given input number is contained in the `Range`.
     */
    boolean contains(final long input) {
        return input >= start && input <= end;
    }

    /*
     * Map the given input number based on this `Range`.
     */
    long map(final long input) {
        return input + offset;
    }

    /*
     * Create a new range.
     */
    static Range of(long outStart, long inStart, long length) {
        return new Range(inStart, inStart + length, outStart - inStart);
    }

}

/*
 * Process the entire almanac.
 */
private processAlmanac(final SolutionContext context) {
    final List<List<String>> batches = new ArrayList<>(context.readBatches());
    final List<Long> seeds  = batches.removeFirst().stream()
            .flatMap(line -> stream(line.split(" ")))
            .skip(1)
            .map(Long::valueOf)
            .toList();

    List<Long> processed = seeds;
    do {
        final List<String> batch = batches.removeFirst();
        final List<Range>  ranges = batch.stream()
                .skip(1)
                .map(line -> line.split(" "))
                .map(parts -> Range.of(Long.parseLong(parts[0]), Long.parseLong(parts[1]), Long.parseLong(parts[2])))
                .toList();

        processed = processed.stream()
                .map(input -> ranges.stream()
                        .filter(range -> range.contains(input))
                        .findFirst()
                        .orElse(new Range(input, input, 0))
                        .map(input))
                .toList();
    } while(!batches.isEmpty());

    return processed;
}

/*
 * Calculate part 1:
 */
public long calculateAnswerForPart1(final SolutionContext context) {
    return processAlmanac(context).stream()
            .mapToLong(l -> l)
            .min()
            .orElseThrow();
}

For part II, the problem was modified slightly. No longer was the initial line a list of individual seeds; now it is a list of ranges of seeds.

In theory, the only modification needed to part I would be to change the parsing of the first line:

final List<Long> seeds = new ArrayList<>();
final String[] parts = batches.removeFirst().removeFirst().split(" ");
for (int i = 1; i < parts.length; i+=2) {
    final long first = Long.parseLong(parts[i]);
    final long length = Long.parseLong(parts[i + 1]);
    LongStream.range(first, first + length)
            .forEach(seeds::add);
}

Unfortunately, theory and practice very rarely match up. In this case, the clue that this would be futile came from the data-type: parsing the inputs as longs meant the ranges were just too long.

Instead, a smarter approach was needed, and that’s ultimately made this an interesting problem. Rather than processing every input individually, the code needed to deal with a range of inputs. A small complication came from needing to deal with the fact that occasionally an input range would only partially overlap with a processing range. This would possibly cause a single input range to result in multiple output ranges. (It could also, in theory, lead to multiple input ranges merging - but this is a possible optimisation and isn’t necessary for to solve the problem.)

This ended up looking like this:

/*
 * A range of numbers.
 */
record Range(long start, long end) implements Comparable<Range> { /* snip */ }

/*
 * Map from a source `Range` to a destination `Range`.
 */
record RangeMap(Range source, Range destination) implements Comparable<RangeMap> { /* snip */ }

/*
 * Transform all numbers in a given `Range` according to the `RangeMap`s
 * provided.
 */
static Stream<Range> offset(final Range sourceRange, final SortedSet<RangeMap> bounds) {
    final Stream.Builder<Range> result = Stream.builder();
    final Iterator<RangeMap> boundsIterator = bounds.iterator();

    RangeMap currentBounds = null;
    long current = sourceRange.start;
    while (current <= sourceRange.end) {
        if (currentBounds == null) {
            if (!boundsIterator.hasNext()) {
                result.add(new Range(current, sourceRange.end));
                return result.build();
            }

            currentBounds = boundsIterator.next();
        }

        if (current < currentBounds.source.start) {
            final long end = Math.min(sourceRange.end, currentBounds.source.start - 1);
            if (end >= current)
                result.add(new Range(current, end));
            current = end + 1;
            continue;
        }

        if (current > currentBounds.source.end) {
            currentBounds = null;
            continue;
        }

        final long end = Math.min(currentBounds.source.end, sourceRange.end);
        result.add(new Range(currentBounds.offset(current), currentBounds.offset(end)));
        current = end + 1;
    }

    return result.build();
}

I found it a bit fiddly to get the offset logic right, so what I ended up with might not be optimum. But at least it works.

Full code: Day5.java.