const std = @import("std");

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

const RetType = u9;

const grid_cols = 100;
const grid_rows = 100;
const GridValue = u4;
const Grid = [grid_rows][grid_cols]GridValue;

const Distance = [grid_rows][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| {
            ret[row][col] = try std.fmt.parseUnsigned(GridValue, line[col .. col + 1], 10);
        }
    }

    return ret;
}

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

    var distance = [_][grid_cols]RetType{[_]RetType{~@as(RetType, 0)} ** grid_cols} ** 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 == grid_rows - 1 and curr.col == grid_cols - 1) return curr.cost;

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

        const diffcol = @intCast(isize, curr.col) + dir[1];
        if (diffcol < 0 or diffcol >= 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: [10_000]u8 = undefined;
    var fba = std.heap.FixedBufferAllocator.init(&buf);

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

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

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

test "day15a" {
    try std.testing.expectEqual(@as(RetType, 366), try first(std.testing.allocator));
}