const DAYS = 14;

const DAYS = 15;

    const day15 = @import("day15.zig");

    _ = @import("day15.zig");

Sensor at x=2983166, y=2813277: closest beacon is at x=3152133, y=2932891
Sensor at x=2507490, y=122751: closest beacon is at x=1515109, y=970092
Sensor at x=3273116, y=2510538: closest beacon is at x=3152133, y=2932891
Sensor at x=1429671, y=995389: closest beacon is at x=1515109, y=970092
Sensor at x=2465994, y=2260162: closest beacon is at x=2734551, y=2960647
Sensor at x=2926899, y=3191882: closest beacon is at x=2734551, y=2960647
Sensor at x=1022491, y=1021177: closest beacon is at x=1515109, y=970092
Sensor at x=1353273, y=1130973: closest beacon is at x=1515109, y=970092
Sensor at x=1565476, y=2081049: closest beacon is at x=1597979, y=2000000
Sensor at x=1841125, y=1893566: closest beacon is at x=1597979, y=2000000
Sensor at x=99988, y=71317: closest beacon is at x=86583, y=-1649857
Sensor at x=3080600, y=3984582: closest beacon is at x=3175561, y=4138060
Sensor at x=3942770, y=3002123: closest beacon is at x=3724687, y=3294321
Sensor at x=1572920, y=2031447: closest beacon is at x=1597979, y=2000000
Sensor at x=218329, y=1882777: closest beacon is at x=1597979, y=2000000
Sensor at x=1401723, y=1460526: closest beacon is at x=1515109, y=970092
Sensor at x=2114094, y=985978: closest beacon is at x=1515109, y=970092
Sensor at x=3358586, y=3171857: closest beacon is at x=3152133, y=2932891
Sensor at x=1226284, y=3662922: closest beacon is at x=2514367, y=3218259
Sensor at x=3486366, y=3717867: closest beacon is at x=3724687, y=3294321
Sensor at x=1271873, y=831354: closest beacon is at x=1515109, y=970092
Sensor at x=3568311, y=1566400: closest beacon is at x=3152133, y=2932891
Sensor at x=3831960, y=3146611: closest beacon is at x=3724687, y=3294321
Sensor at x=2505534, y=3196726: closest beacon is at x=2514367, y=3218259
Sensor at x=2736967, y=3632098: closest beacon is at x=2514367, y=3218259
Sensor at x=3963402, y=3944423: closest beacon is at x=3724687, y=3294321
Sensor at x=1483115, y=2119639: closest beacon is at x=1597979, y=2000000

const std = @import("std");
const PATH = "input/day15.txt";
const Str = []const u8;
pub fn first(allocator: std.mem.Allocator) !usize {
    var zone = try parseInput(allocator, @embedFile(PATH));
    defer zone.sens.deinit();
    // We have a beacon on that line, that's why the '-1'
    return try zone.noBeacon(allocator, 2_000_000) - 1;
}
pub fn second(allocator: std.mem.Allocator) !usize {
    const MAX = 4_000_000;
    var arena = std.heap.ArenaAllocator.init(allocator);
    defer arena.deinit();
    var zone = try parseInput(arena.allocator(), @embedFile(PATH));
    defer zone.sens.deinit();
    var line: isize = 0;
    while (line <= MAX) : (line += 1) {
        const ret = try zone.noBeaconLimit(arena.allocator(), line, 0, MAX);
        // std.debug.print("ret: {d}\n", .{ret});
        if (ret < MAX + 1) {
            // std.debug.print("{d}\n", .{line});
            return ret * 4_000_000 + @intCast(usize, line);
        }
    }
    unreachable;
}
test "day15a" {
    try std.testing.expectEqual(@as(usize, 6078701), try first(std.testing.allocator));
}
test "day15b" {
    try std.testing.expectEqual(@as(usize, 12567351400528), try second(std.testing.allocator));
}
const Coord = struct {
    x: isize,
    y: isize,
    fn lessThan(context: void, a: @This(), b: @This()) bool {
        _ = context;
        return a.x < b.x;
    }
};
const Pair = struct {
    sensor: Coord,
    manhattan: isize,
};
const Zone = struct {
    sens: std.ArrayList(Pair),
    fn noBeaconLimit(
        self: @This(),
        allocator: std.mem.Allocator,
        line_number: isize,
        min: isize,
        max: isize,
    ) !usize {
        var intervals = std.ArrayList(Coord).init(allocator);
        defer intervals.deinit();
        for (self.sens.items) |pair| {
            const perp = try std.math.absInt(pair.sensor.y - line_number);
            const diff = pair.manhattan - perp;
            if (diff < 0) continue;
            const interval = .{ .x = pair.sensor.x - diff, .y = pair.sensor.x + diff };
            try intervals.append(interval);
        }
        std.sort.sort(Coord, intervals.items, {}, Coord.lessThan);
        var unique = std.ArrayList(Coord).init(allocator);
        defer unique.deinit();
        try unique.append(intervals.items[0]);
        var idx: usize = 1;
        while (idx < intervals.items.len) : (idx += 1) {
            const item = intervals.items[idx];
            const top = unique.items[unique.items.len - 1];
            if (top.y < item.x) {
                try unique.append(item);
            } else if (top.y < item.y) {
                unique.items[unique.items.len - 1].y = item.y;
            }
        }
        var counter: usize = 0;
        for (unique.items) |item| {
            counter += @intCast(usize, std.math.min(item.y, max) - std.math.max(item.x, min)) + 1;
        }
        if (counter < max + 1) {
            return @intCast(usize, unique.items[0].y) + 1;
        }
        return counter;
    }
    fn noBeacon(self: @This(), allocator: std.mem.Allocator, line_number: isize) !usize {
        var intervals = std.ArrayList(Coord).init(allocator);
        defer intervals.deinit();
        for (self.sens.items) |pair| {
            const perp = try std.math.absInt(pair.sensor.y - line_number);
            const diff = pair.manhattan - perp;
            if (diff < 0) continue;
            const interval = .{ .x = pair.sensor.x - diff, .y = pair.sensor.x + diff };
            try intervals.append(interval);
        }
        std.sort.sort(Coord, intervals.items, {}, Coord.lessThan);
        var unique = std.ArrayList(Coord).init(allocator);
        defer unique.deinit();
        try unique.append(intervals.items[0]);
        var idx: usize = 1;
        while (idx < intervals.items.len) : (idx += 1) {
            const item = intervals.items[idx];
            const top = unique.items[unique.items.len - 1];
            if (top.y < item.x) {
                try unique.append(item);
            } else if (top.y < item.y) {
                unique.items[unique.items.len - 1].y = item.y;
            }
        }
        var counter: usize = 0;
        for (unique.items) |item| {
            // std.debug.print("{d} <-> {d}\n", .{ item.x, item.y });
            counter += @intCast(usize, item.y - item.x) + 1;
        }
        return counter;
    }
};
fn manhattan(a: Coord, b: Coord) !isize {
    const x = try std.math.absInt(a.x - b.x);
    const y = try std.math.absInt(a.y - b.y);
    return x + y;
}
fn parseInput(allocator: std.mem.Allocator, in: Str) !Zone {
    var zone: Zone = undefined;
    zone.sens = std.ArrayList(Pair).init(allocator);
    var lines = std.mem.tokenize(u8, in, "\n");
    while (lines.next()) |line| {
        var split = std.mem.tokenize(u8, line, ":");
        // Sensor
        var scrd = std.mem.tokenize(u8, split.next().?[10..], ", ");
        // std.debug.print("{s} {s}\n", .{ scrd.next().?, scrd.next().? });
        const sx = try std.fmt.parseInt(isize, scrd.next().?[2..], 10);
        const sy = try std.fmt.parseInt(isize, scrd.next().?[2..], 10);
        const s = .{ .x = sx, .y = sy };
        // Beacon
        var bcrd = std.mem.tokenize(u8, split.next().?[22..], ", ");
        // std.debug.print("{s} {s}\n", .{ bcrd.next().?, bcrd.next().? });
        const bx = try std.fmt.parseInt(isize, bcrd.next().?[2..], 10);
        const by = try std.fmt.parseInt(isize, bcrd.next().?[2..], 10);
        const b = .{ .x = bx, .y = by };
        const m = try manhattan(s, b);
        try zone.sens.append(.{ .sensor = s, .manhattan = m });
    }
    return zone;
}
const test_input =
    \\Sensor at x=2, y=18: closest beacon is at x=-2, y=15
    \\Sensor at x=9, y=16: closest beacon is at x=10, y=16
    \\Sensor at x=13, y=2: closest beacon is at x=15, y=3
    \\Sensor at x=12, y=14: closest beacon is at x=10, y=16
    \\Sensor at x=10, y=20: closest beacon is at x=10, y=16
    \\Sensor at x=14, y=17: closest beacon is at x=10, y=16
    \\Sensor at x=8, y=7: closest beacon is at x=2, y=10
    \\Sensor at x=2, y=0: closest beacon is at x=2, y=10
    \\Sensor at x=0, y=11: closest beacon is at x=2, y=10
    \\Sensor at x=20, y=14: closest beacon is at x=25, y=17
    \\Sensor at x=17, y=20: closest beacon is at x=21, y=22
    \\Sensor at x=16, y=7: closest beacon is at x=15, y=3
    \\Sensor at x=14, y=3: closest beacon is at x=15, y=3
    \\Sensor at x=20, y=1: closest beacon is at x=15, y=3
;