const std = @import("std");

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

const RetType = u12;

const exp_size = 5;
const grid_cols = 100;
const grid_rows = 100;
const GridValue = u4;
const Grid = [exp_size * grid_rows][exp_size * grid_cols]GridValue;

const Distance = [exp_size * grid_rows][exp_size * grid_cols]RetType;

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

fn lowerThan(context: void, a: Point, b: Point) std.math.Order {
    _ = context;
    return std.math.order(a.cost, b.cost);
}

const Queue = std.PriorityQueue(Point, void, lowerThan);

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

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

    var ret: Grid = undefined;

    var row: usize = 0;
    while (lines.next()) |line| : (row += 1) {
        for (line) |_, col| {
            const curr =
                try std.fmt.parseUnsigned(GridValue, line[col .. col + 1], 10);
            for ([_]usize{ 0, 1, 2, 3, 4 }) |x| {
                for ([_]usize{ 0, 1, 2, 3, 4 }) |y| {
                    ret[row + y * grid_rows][col + x * grid_cols] = @intCast(GridValue, (curr + x + y) % 10) + @intCast(GridValue, (curr + x + y) / 10);
                }
            }
        }
    }

    // for (ret) |line| {
    //     std.debug.print("\n", .{});
    //     for (line) |item, idx| {
    //         if (idx % 10 == 0) {
    //             std.debug.print("|", .{});
    //         }
    //         std.debug.print("{d}", .{item});
    //     }
    // }

    return ret;
}

pub fn second(allocator: ?std.mem.Allocator) anyerror!RetType {
    const g = try parseInput();

    var distance = [_][exp_size * grid_cols]RetType{[_]RetType{~@as(RetType, 0)} ** (exp_size * grid_cols)} ** (exp_size * grid_rows);
    distance[0][0] = 0;

    var queue = Queue.init(allocator.?, {});
    defer queue.deinit();

    // add starting item to the queue
    try queue.add(Point{ .row = 0, .col = 0, .cost = 0 });

    while (true) {
        var ret = try dijkstra(&g, &distance, &queue);
        if (ret != null) return ret.?;
        // XXX: distance grid is not finalized!
    }

    unreachable;
}

fn dijkstra(grid: *const Grid, dist: *Distance, queue: *Queue) !?RetType {
    const curr = queue.remove();
    // std.debug.print("D: {d} {d} -> {d}\n", .{curr.row, curr.col, curr.cost});

    if (curr.row == (exp_size * grid_rows - 1) and (curr.col == exp_size * grid_cols - 1)) return curr.cost;

    for (directions) |dir| {
        const diffrow = @intCast(isize, curr.row) + dir[0];
        if (diffrow < 0 or diffrow >= exp_size * grid_rows) continue;
        const dr = @intCast(usize, diffrow);

        const diffcol = @intCast(isize, curr.col) + dir[1];
        if (diffcol < 0 or diffcol >= exp_size * grid_cols) continue;
        const dc = @intCast(usize, diffcol);

        const d = dist[curr.row][curr.col] + grid[dr][dc];

        if (d < dist[dr][dc]) {
            try queue.add(Point{ .row = dr, .col = dc, .cost = d });

            // queue.update(Point{ .row = dr, .col = dc, .cost = dist[dr][dc] }, Point{ .row = dr, .col = dc, .cost = d }) catch |err| switch (err) {
            //     error.ElementNotFound => try queue.add(Point{ .row = dr, .col = dc, .cost = d }),
            //     else => return err,
            // };

            dist[dr][dc] = d;
        }
    }

    return null;
}

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

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

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

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

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