const std = @import("std");

const path = "data/day09/input.txt";

const RetType = u21;

const directions = [4][2]i2{
    .{ 1, 0 },
    .{ 0, 1 },
    .{ -1, 0 },
    .{ 0, -1 },
};

const Point = struct {
    row: usize,
    col: usize,
};

const grid_row = 100;
const grid_col = 100;
const GridType = u4;
const GridArray = [grid_row][grid_col]GridType;

const Grid = struct {
    array: GridArray,
    seen: std.AutoHashMap(Point, void),

    pub fn getBasin(self: *@This(), p: Point) anyerror!RetType {
        if (self.seen.contains(p)) {
            return 0;
        }
        try self.seen.put(p, {});

        var ret: RetType = 1;

        for (directions) |dir| {
            const diffrow = @intCast(i10, p.row) + dir[0];
            const diffcol = @intCast(i10, p.col) + dir[1];
            if ((diffrow < 0) or (diffrow >= grid_row)) continue;
            if ((diffcol < 0) or (diffcol >= grid_col)) continue;
            if (self.array[@intCast(usize, diffrow)][@intCast(usize, diffcol)] != 9) {
                ret += try self.getBasin(Point{ .row = @intCast(usize, diffrow), .col = @intCast(usize, diffcol) });
            }
        }

        return ret;
    }
};

pub fn parseInput() anyerror!GridArray {
    const input = @embedFile(path);
    var lines = std.mem.split(u8, input, "\n");

    var g: GridArray = undefined;

    var row: usize = 0;
    while (lines.next()) |line| : (row += 1) {
        for (line) |_, col| {
            g[row][col] = try std.fmt.parseUnsigned(GridType, line[col .. col + 1], 10);
        }
    }

    return g;
}

fn greaterThan(context: void, a: RetType, b: RetType) std.math.Order {
    _ = context;
    return std.math.order(a, b).invert();
}

pub fn second(allocator: ?std.mem.Allocator) anyerror!RetType {
    var grid: Grid = .{
        .array = try parseInput(),
        .seen = undefined,
    };

    grid.seen = std.AutoHashMap(Point, void).init(allocator.?);
    defer grid.seen.deinit();

    var basins = std.PriorityQueue(RetType, void, greaterThan).init(allocator.?, {});
    defer basins.deinit();

    for (grid.array) |line, row| {
        items: for (line) |item, col| {
            for (directions) |dir| {
                const diffrow = @intCast(i10, row) + dir[0];
                const diffcol = @intCast(i10, col) + dir[1];
                if ((diffrow < 0) or (diffrow >= grid_row)) continue;
                if ((diffcol < 0) or (diffcol >= grid_col)) continue;
                if (item >= grid.array[@intCast(usize, diffrow)][@intCast(usize, diffcol)]) {
                    continue :items;
                }
            }
            const basin = try grid.getBasin(Point{ .row = row, .col = col });
            try basins.add(basin);
            grid.seen.clearRetainingCapacity();
        }
    }

    return basins.items[0] * basins.items[1] * basins.items[2];
}

pub fn main() anyerror!void {
    var buf: [10_000]u8 = undefined;
    var fba = std.heap.FixedBufferAllocator.init(&buf);

    var timer = try std.time.Timer.start();
    const ret = try second(fba.allocator());
    const f = timer.lap() / 1000;

    try std.testing.expectEqual(ret, @as(RetType, 1100682));

    std.debug.print("Day 9b result: {d} \t\ttime: {d}us\n", .{ ret, f });
}

test "day09b" {
    try std.testing.expectEqual(@as(RetType, 1100682), try second(std.testing.allocator));
}