path: root/day05/solution.zig

const std = @import("std");
const print = std.debug.print;
const assert = std.debug.assert;
const ArrayList = std.ArrayList;
const HashMap = std.HashMap;
const mem = std.mem;

const fin = mem.trim(u8, @embedFile("./input.txt"), &std.ascii.whitespace);
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();

//
// 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;
}

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 {
    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);
}