const day15a = @import("day15a.zig");
const day15b = @import("day15b.zig");

    _ = try day15a.first();
    _ = try day15b.second();

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() anyerror!RetType {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    const allocator = gpa.allocator();
    var 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: *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]) {
            dist[dr][dc] = d;
            try queue.add(Point{ .row = dr, .col = dc, .cost = d });
            // XXX: queue.update() needs == operator, which does not work with
            // structs. We just grow the queue bigger and bigger...
            // 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,
            // };
        }
    }
    return null;
}
pub fn main() anyerror!void {
    var timer = try std.time.Timer.start();
    const ret = try second();
    const t = timer.lap() / 1000;
    try std.testing.expectEqual(@as(RetType, 2829), ret);
    std.debug.print("Day 15b result: {d} \t\ttime: {d}µs\n", .{ ret, t });
}
test "day15a" {
    try std.testing.expectEqual(@as(RetType, 2829), try second());
}

const days = 14;

const days = 15;