1 files changed, 270 insertions, 6 deletions

diff --git a/day05/solution.zig b/day05/solution.zig
index 059a120..c22af8b 100644
--- a/day05/solution.zig
+++ b/day05/solution.zig
@@ -9,15 +9,279 @@ const fin = mem.trim(u8, @embedFile("./input.txt"), &std.ascii.whitespace);
 var gpa = std.heap.GeneralPurposeAllocator(.{}){};
 const allocator = gpa.allocator();
 
-pub fn part1() void {
-    // Part 1 goes here
+//
+// I represent the input in the form of:
+//
+// Input = [
+//     Map [
+//         Translation {
+//              src = Range {
+//                  begin,
+//                  len,
+//              },
+//              dst = Range {
+//                  begin,
+//                  len,
+//              }
+//         }
+//         ...
+//     ]
+//     ...
+// ]
+//
+// I filled unmapped areas with identity maps (1-1 translation src -> dest)
+// to avoid edge cases.
+//
+//
+const Range = struct {
+    begin: i64,
+    len: i64,
+};
+
+const Translation = struct {
+    src: Range,
+    dst: Range,
+};
+
+const Map = struct {
+    ranges: ArrayList(Translation),
+
+    pub fn init() Map {
+        const ranges = ArrayList(Translation).init(allocator);
+
+        return Map{
+            .ranges = ranges,
+        };
+    }
+
+    pub fn deinit(self: *@This()) void {
+        self.ranges.deinit();
+    }
+};
+
+fn parseSeeds(text: []const u8) ArrayList(i64) {
+    var result = ArrayList(i64).init(allocator);
+    var textNumbers = mem.splitScalar(u8, text, ' ');
+
+    // Ignore header
+    _ = textNumbers.next();
+
+    while (textNumbers.next()) |textNum| {
+        const n = std.fmt.parseInt(i64, textNum, 10) catch unreachable;
+        result.append(n) catch unreachable;
+    }
+
+    return result;
+}
+
+fn parseTranslation(text: []const u8) Translation {
+    var splitNums = mem.splitScalar(u8, text, ' ');
+    const dst_begin = std.fmt.parseInt(i64, splitNums.next().?, 10) catch unreachable;
+    const src_begin = std.fmt.parseInt(i64, splitNums.next().?, 10) catch unreachable;
+    const len = std.fmt.parseInt(i64, splitNums.next().?, 10) catch unreachable;
+
+    return Translation{
+        .src = .{
+            .begin = src_begin,
+            .len = len,
+        },
+        .dst = .{
+            .begin = dst_begin,
+            .len = len,
+        },
+    };
+}
+
+fn translationLess(@"_": void, lhs: Translation, rhs: Translation) bool {
+    return rangeLess(@"_", lhs.src, rhs.src);
+}
+
+fn parseMap(text: []const u8) Map {
+    var splitLines = mem.splitScalar(u8, text, '\n');
+    var translations = ArrayList(Translation).init(allocator);
+    defer translations.deinit();
+
+    // Ignore header
+    _ = splitLines.next();
+
+    while (splitLines.next()) |line| {
+        translations.append(parseTranslation(line)) catch unreachable;
+    }
+    mem.sort(Translation, translations.items, {}, translationLess);
+
+    var gapFilled = ArrayList(Translation).init(allocator);
+    const items = translations.items;
+
+    // Fill gap from 0 up to the first segment
+    if (items[0].src.begin > 0) {
+        gapFilled.append(.{ .src = .{
+            .begin = 0,
+            .len = items[0].src.begin,
+        }, .dst = .{
+            .begin = 0,
+            .len = items[0].src.begin,
+        } }) catch unreachable;
+    }
+
+    // Fill intermediate gaps
+    for (items[0 .. items.len - 1], 0..) |tr, i| {
+        const curr = tr.src;
+        const next = items[i + 1].src;
+        gapFilled.append(items[i]) catch unreachable;
+        if (rangeAdjacent(curr, next) == null) {
+            gapFilled.append(.{ .src = .{
+                .begin = curr.begin + curr.len,
+                .len = next.begin - curr.begin - curr.len,
+            }, .dst = .{
+                .begin = curr.begin + curr.len,
+                .len = next.begin - curr.begin - curr.len,
+            } }) catch unreachable;
+        }
+    }
+
+    // Fill gap from the end of the last segment to +infinity
+    const len = items.len;
+    gapFilled.append(.{ .src = .{
+        .begin = items[len - 1].src.begin,
+        .len = 4_000_000_000,
+    }, .dst = .{
+        .begin = items[len - 1].src.begin,
+        .len = 4_000_000_000,
+    } }) catch unreachable;
+
+    return Map{
+        .ranges = gapFilled,
+    };
+}
+
+fn evalSeed(seed: i64, maps: []const Map) i64 {
+    var s = seed;
+
+    for (maps) |map| {
+        for (map.ranges.items) |range| {
+            if (range.src.begin <= s and s < range.src.begin + range.src.len) {
+                s += range.dst.begin - range.src.begin;
+                break;
+            }
+        }
+    }
+
+    return s;
+}
+
+fn rangeLess(_: void, lhs: Range, rhs: Range) bool {
+    return lhs.begin < rhs.begin or (lhs.begin == rhs.begin and lhs.len > rhs.len);
+}
+
+fn rangeMin(lhs: Range, rhs: Range) Range {
+    return if (rangeLess({}, lhs, rhs)) lhs else rhs;
 }
 
-pub fn part2() void {
-    // Part 2 goes here
+fn rangeMax(lhs: Range, rhs: Range) Range {
+    return if (rangeLess({}, lhs, rhs)) rhs else lhs;
+}
+
+fn rangeOverlap(lhs: Range, rhs: Range) ?Range {
+    const min = rangeMin(lhs, rhs);
+    const max = rangeMax(lhs, rhs);
+
+    if (min.begin + min.len <= max.begin) {
+        return null;
+    }
+
+    return Range{
+        .begin = max.begin,
+        .len = @min(min.begin + min.len - max.begin, max.len),
+    };
+}
+
+fn rangeAdjacent(lhs: Range, rhs: Range) ?Range {
+    const min = rangeMin(lhs, rhs);
+    const max = rangeMax(lhs, rhs);
+
+    if (min.begin + min.len != max.begin) {
+        return null;
+    }
+
+    return Range{
+        .begin = max.begin,
+        .len = @min(min.begin + min.len - max.begin, max.len),
+    };
+}
+
+pub fn part1(seeds: []const i64, maps: []const Map) void {
+    var ans: i64 = std.math.maxInt(i64);
+
+    for (seeds) |seed| {
+        const s = evalSeed(seed, maps);
+        ans = @min(ans, s);
+    }
+
+    print("{d}\n", .{ans});
+}
+
+fn evalNextState(m: Map, ranges: ArrayList(Range)) ArrayList(Range) {
+    var result = ArrayList(Range).init(allocator);
+
+    // Translate all seed range(s)
+    for (ranges.items) |r| {
+
+        // For every translation
+        for (m.ranges.items) |t| {
+            const overlap = rangeOverlap(t.src, r) orelse continue;
+
+            result.append(.{
+                .begin = t.dst.begin + overlap.begin - t.src.begin,
+                .len = overlap.len,
+            }) catch unreachable;
+        }
+    }
+
+    assert(result.items.len > 0);
+    mem.sort(Range, result.items, {}, rangeLess);
+
+    return result;
+}
+
+fn evalLowest(startRange: Range, maps: []const Map) i64 {
+    var ranges = ArrayList(Range).init(allocator);
+    defer ranges.deinit();
+
+    // Start with a single seed range
+    ranges.append(startRange) catch unreachable;
+
+    // For every map
+    for (maps) |m| {
+        const nextRanges = evalNextState(m, ranges);
+        ranges.deinit();
+        ranges = nextRanges;
+    }
+
+    return ranges.items[0].begin;
+}
+
+pub fn part2(seeds: []const i64, maps: []const Map) void {
+    var ans: i64 = std.math.maxInt(i64);
+
+    for (0..seeds.len / 2) |i| {
+        const begin: i64 = @intCast(seeds[i * 2]);
+        const len: i64 = @intCast(seeds[i * 2 + 1]);
+
+        ans = @min(ans, evalLowest(.{ .begin = begin, .len = len }, maps));
+    }
+    print("{d}\n", .{ans});
 }
 
 pub fn main() !void {
-    part1();
-    part2();
+    var splitLines = mem.splitSequence(u8, fin, "\n\n");
+    const seedsText = splitLines.next().?;
+    const seeds = parseSeeds(seedsText);
+
+    var maps = ArrayList(Map).init(allocator);
+    while (splitLines.next()) |mapText| {
+        maps.append(parseMap(mapText)) catch unreachable;
+    }
+
+    part1(seeds.items, maps.items);
+    part2(seeds.items, maps.items);
 }