const DAYS = 11;

const DAYS = 12;

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

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

abcccccccccccccccccccccccccccccccccccccaaaaaaacccccccaaaaaaaaaaaccccccccccccccccccccaaacaaaaaaaacccccccccccccccccccccccccccccccccccaaaaa
abccccccccccccccccccaaccaacccccccccccccaaaaaaaccccccccaaaaaaaaaaacccccccaaaaccccccccaaaaaaaaaaaaacccccccccccccccccccccccccccccccccaaaaaa
abccccccccccccccccccaaaaaaccccccccccaaaccaaaaaacccccccaaaaaaaaaaccccccccaaaaccccccaaaaaaaaaaaaaaacccccccccccccccccccaaacccccccccccaaaaaa
abcccccccccccccccccccaaaaacccccccccccaaccaacaaaccccccaaaaaaaaaaaccccccccaaaacccccaaaaaaaaacaaaaaaacccccccccccccccccaaaacccccccccccaaacaa
abccccccccccccccccccaaaaaaccccccccaacaaaaaacccccccccaaaaaaaaaaaaacaaaccccaaccccccaaaaaaaaacaacccccccccccccccccaaaccaaaacccccccccccccccaa
abcccccccccccccccccaaaaaaaacccccccaaaaaaaaccccccaaaaaaaacaaaacaaaaaaacccccccccaaccccaaaaaacaaacccccccccccccccaaaakkkaaccccccccccccccccaa
abcccccccccccccccccaaaaaaaaccccccccaaaaaccccaacccaaaaaaaaaaaacaaaaaaccccccccccaacccaaaaaaaaaaaacccccccccccccccakkkkkklcccccccccccccccccc
abaaacccccccccccaaccccaaccccccccccccaaaaaccaaacccaaaaaaaaaaaaaaaaaaaaccccccaaaaaaaacaacccaaaaaaccccccccccccccckkkkkkkllcccccccaaaccccccc
abaaaacccccccaacaaccccaacccccccccccaaacaaaaaaaccccaaaaaaaaaaaaaaaaaaaacccccaaaaaaaaaaaccccaaaaacccccccccccccckkkksssllllccccccaaaaaacccc
abaaaacccccccaaaaacccccccccccaaaccccaacaaaaaaccccaaaaaacaaaaaaaaaaaaaacccccccaaaaccccccccaaaaacccccccccccccckkkksssssllllcccccaaaaaacccc
abaaacccccccccaaaaaaccccccccaaaaccccccccaaaaaaaacaaaaaaaaaaaaacaaacaaacccccccaaaaacccccccaaaaacccccccccccccjkkkrssssssllllccccccaaaccccc
abccccccccccaaaaaaaaccccccccaaaacccccccaaaaaaaaacaacaaaaaaaaaacaaaccccccccccaaacaaccccccccccccccccccccccccjjkkrrsuuussslllllcccccaaccccc
abccaaacccccaaaaacccccccccccaaaaccccccaaaaaaaaaacccccaaaaaaaaaacaaccccccccccaacccacccccccccccccccccccccjjjjjjrrrsuuuussslllllmcccddacccc
abcccaaaccaccacaaaccccccccccccccccccccaaaaaaaccccccccccaaaaaaaaccccccaacccccccccccaaaaacccccccccccccccjjjjjjrrrruuuuuusssllmmmmmddddcccc
abccaaaaaaaacccaaaccccccccccccccccaaacccccaaaccccccccccccaaacccccccccaacccccccccccaaaaacccccccccccccjjjjjrrrrrruuuxuuussqqqqmmmmmdddcccc
abcaaaaaaaacccaaaaaacaaaaaccccccaaaaaaccccaaacccaaccccccccaaccccccaaaaaaaaccaaacccaaaaaaccccccccccccjjjjrrrrrruuuxxxuuuqqqqqqqmmmdddcccc
abaaaaaaaaaccccaaaaacaaaaaccccccaaaaaaaaccccccaaaaaaccccccccccccccaaaaaaaaccaaacaaaaaaaacccccccccccjjjjrrrtttuuuuxxxyvvvvvqqqqmmmdddcccc
abaaaaaaaaaccaaaaaaacaaaaaaccccccaaaaaaaacccccaaaaaaccccccccccccccccaaaaccaaaaaaaaaaaaaacccccccccaaiijqqqrttttuuuxxyyvvvvvvvqqmmmdddcccc
abcaaaaaaaaccaaaaaaaaaaaaaacccccaaaaaaaacccccccaaaacccccaaaaccccccccaaaaacaaaaaaaaccaaccccccccccaaaiiiqqqttttxxxxxxyyyyyyvvvqqmmmdddcccc
abcccaaaaaaacaaaaaaaaaaaaaacccccaaaaaaaaaaaccccaaaaccccaaaaacccccccaaaaaacaaaaaaacccccccccccccccaaaiiiqqqtttxxxxxxxyyyyyyvvqqqmmmdddcccc
SbcccaacccaccccaaacacccaaacccccccccaaaaaaaaacccaccaccccaaaaaaccccccaaccaacccaaaaaccccccccccccccccaaiiiiqqtttxxxxEzzzyyyyvvvqqqmmmddccccc
abccaaaccccccccaaccccccccccccccccccaaaaaaaaccccccccccccaaaaaaccccccccccccccaaacaaaccaacccccccccccccciiiqqqttttxxxyyyyyvvvvqqqmmmdddccccc
abccccccccccccccccccccccccccccccccaaaaaaaccccccccccccccaaaaaacccccccccccccccaacccccaaaaaaaccccccccccciiiqqqttttxxyyyyyvvvrrrnnneeecccccc
abcaaaaccccccccccccccccccccccccccaaaaaaaaccccccccccccccccaacccccccccccccccccccccccccaaaaacccccccccccciiiqqqqttxxyyyyyyyvvrrnnnneeecccccc
abcaaaaacccccccccccccccccccccccccaaaacaaacccaccaaacccccccccccccccccccccccccaaaccccaaaaaaaccccccccccccciiiqqqttwwyywwyyywwrrnnneeeccccccc
abaaaaaacccaccaccccccccccccccccccaaaaccaacccaaaaaaccccccccccccccccaaaccccaaaaaacccaaaaaaaacccccccccccciiiqqqtswwwwwwwwwwwrrnnneeeccccccc
abaaaaaacccaaaaccccccccaaaacccccccaaacccccccaaaaaacccccccccccccccaaaaaaccaaaaaacccaaaaaaaacaaccccccaaciiiqppsswwwwsswwwwwrrrnneeeccccccc
abcaaaaacccaaaaacccccccaaaacccccccccccccccccaaaaaaaccccccccccccccaaaaaaccaaaaaacccccaaaaaaaaaccccccaaaahhpppssswwsssswwwwrrrnneeeacccccc
abcaaaccccaaaaaacccccccaaaaccccccccccccccccaaaaaaaaccccccccccccccaaaaacccaaaaaccccccaacaaaaaaaaccaaaaaahhpppsssssssssrrrrrrnnneeeacccccc
abccccccccaaaaaaccccccccaacccccccccccccccccaaaaaaaaccccaacccccccccaaaaaccaaaaacccccccccaaaaaaaaccaaaaachhpppssssssoosrrrrrrnnneeeaaacccc
abccccccccccaaccccccccccccccccaaaaaccccccaacccaaacccaaaaacccccccccaacaacccccccccccccccccaaaaaaacccaaaaahhhppppssppooooorroonnffeaaaacccc
abaaccccccccccccccccccccccccccaaaaaccccccaacccaaaccccaaaaacccccccccccccccccccccccccccaacaaaaacccccaacaahhhppppppppoooooooooonfffaaaacccc
abaccccccccccccccccccccccccccaaaaaacccaaaaaaaacccccccaaaaaccccccccccccccccccccccccaaaaaaaaaaaccccccccccchhhpppppppgggoooooooffffaacccccc
abaccccccccccccccccccccccccccaaaaaacccaaaaaaaaccccccaaaaaccccccacccaacccccccccccccaaaaaccccaaccccccccccchhhhhhggggggggfffffffffaaacccccc
abaacccccccccccccccccccccccccaaaaaacccccaaaacccccccccaaaacccaacaacaaacccccccccccccaaaaaaacccccccccccccccchhhhgggggggggffffffffccaacccccc
abcccccccaacccccccccccccccccccaaaccccccaaaaaccccccccaaaaccaaaacaaaaacccccccccccccaaaaaaaaccccccccccccccccchhhggggaaaagffffffcccccccccccc
abcccccccaacccccccccccccaacccccccccccccaaaaaaccaaccccaaaaaaaaacaaaaaacccccccaaaacaaaaaaaacccccccccccaacccccccaaaacaaaacccccccccccccccccc
abccccaaaaaaaacccccccaacaaaccccccccccccaaccaacaaaacccaaaaaaaacaaaaaaaaccccccaaaaccacaaaccaaaccccaaaaaacccccccaacccaaaacccccccccccccaaaaa
abccccaaaaaaaacccccccaaaaaccccccccccccccccccccaaaaccccaaaaaaacaaaaaaaaccccccaaaaccccaaaccaaaaaccaaaaaaaacccccccccccaaaccccccccccccccaaaa
abccccccaaaaccccccccccaaaaaaccccccccccccccccccaaaacccaaaaaaaaaaccaaccccccccccaacccccccccaaaaacccaaaaaaaacccccccccccaaaccccccccccccccaaaa
abcccccaaaaaacccccccaaaaaaaacccccccccccccccccccccccaaaaaaaaaaaaaaaacccccccccccccccccccccaaaaaacccaaaaaaaccccccccccccccccccccccccccaaaaaa

const std = @import("std");
const PATH = "input/day12.txt";
const Str = []const u8;
// const ROWS = 5;
// const COLS = 8;
const ROWS = 41;
const COLS = 136;
const DistType = u9;
const Point = struct {
    coord: [2]usize,
    cost: usize,
    fn lessThan(context: void, a: @This(), b: @This()) std.math.Order {
        _ = context;
        return std.math.order(a.cost, b.cost);
    }
};
const Queue = std.PriorityQueue(Point, void, Point.lessThan);
const Part = enum {
    first,
    second,
};
pub fn first(allocator: std.mem.Allocator) !usize {
    var hill = parseInput(@embedFile(PATH));
    hill.dist = [_][COLS]DistType{[_]DistType{~@as(DistType, 0)} ** COLS} ** ROWS;
    hill.dist[hill.start[0]][hill.start[1]] = 0;
    hill.queue = Queue.init(allocator, {});
    defer hill.queue.deinit();
    try hill.queue.add(.{ .coord = .{ hill.start[0], hill.start[1] }, .cost = 0 });
    while (true) {
        const ret = try hill.dijkstra(.first);
        if (ret != null) return ret.?;
    }
    return error.PathNotFound;
}
pub fn second(allocator: std.mem.Allocator) !usize {
    var hill = parseInput(@embedFile(PATH));
    hill.dist = [_][COLS]DistType{[_]DistType{~@as(DistType, 0)} ** COLS} ** ROWS;
    hill.dist[hill.stop[0]][hill.stop[1]] = 0;
    hill.queue = Queue.init(allocator, {});
    defer hill.queue.deinit();
    try hill.queue.add(.{ .coord = .{ hill.stop[0], hill.stop[1] }, .cost = 0 });
    while (true) {
        const ret = try hill.dijkstra(.second);
        if (ret != null) return ret.?;
    }
    return error.PathNotFound;
}
test "day12a" {
    try std.testing.expectEqual(@as(usize, 456), try first(std.testing.allocator));
}
test "day12b" {
    try std.testing.expectEqual(@as(usize, 454), try second(std.testing.allocator));
}
const Hill = struct {
    grid: [ROWS][COLS]u8,
    dist: [ROWS][COLS]DistType,
    start: [2]usize,
    stop: [2]usize,
    queue: Queue,
    const directions = [4][2]i2{
        .{ -1, 0 },
        .{ 1, 0 },
        .{ 0, -1 },
        .{ 0, 1 },
    };
    fn dijkstra(self: *@This(), comptime part: Part) !?usize {
        const curr = self.queue.remove();
        // std.debug.print("{c}", .{self.grid[curr.coord[0]][curr.coord[1]]});
        if (part == .first)
            if (curr.coord[0] == self.stop[0] and curr.coord[1] == self.stop[1]) return curr.cost;
        if (part == .second)
            if (self.grid[curr.coord[0]][curr.coord[1]] == 'a') return curr.cost;
        for (directions) |dir| {
            const diffrow = @intCast(isize, curr.coord[0]) + dir[0];
            if (diffrow < 0 or diffrow >= ROWS) continue;
            const dr = @intCast(usize, diffrow);
            const diffcol = @intCast(isize, curr.coord[1]) + dir[1];
            if (diffcol < 0 or diffcol >= COLS) continue;
            const dc = @intCast(usize, diffcol);
            // only 1 step up/down allowed
            if (part == .first)
                if (self.grid[dr][dc] > self.grid[curr.coord[0]][curr.coord[1]] + 1) continue;
            if (part == .second)
                if (self.grid[dr][dc] + 1 < self.grid[curr.coord[0]][curr.coord[1]]) continue;
            const d = self.dist[curr.coord[0]][curr.coord[1]] + 1;
            if (d < self.dist[dr][dc]) {
                try self.queue.add(.{ .coord = .{ dr, dc }, .cost = d });
                self.dist[dr][dc] = d;
            }
        }
        return null;
    }
};
fn parseInput(in: Str) Hill {
    var ret: Hill = undefined;
    var lineNo: usize = 0;
    var lines = std.mem.tokenize(u8, in, "\n");
    while (lines.next()) |line| : (lineNo += 1) {
        for (line) |ch, idx| {
            switch (ch) {
                'S' => {
                    ret.grid[lineNo][idx] = 'a';
                    ret.start = .{ lineNo, idx };
                },
                'E' => {
                    ret.grid[lineNo][idx] = 'z';
                    ret.stop = .{ lineNo, idx };
                },
                'a'...'z' => {
                    ret.grid[lineNo][idx] = ch;
                },
                else => unreachable,
            }
        }
    }
    return ret;
}
const test_input =
    \\Sabqponm
    \\abcryxxl
    \\accszExk
    \\acctuvwj
    \\abdefghi
;