import DataStructures: PriorityQueue, enqueue!, dequeue!;

const test_input = "12/test_input.txt";
const input = "12/input.txt";

const START = -1;
const END = -2;

const MAX_DIFF = 1;

function read_map(fh::IOStream)::Matrix{Int}
    lines = readlines(fh);
    m = zeros(Int, length(lines), length(lines[1]));
    for (i, line) in enumerate(lines)
        for (j, char) in enumerate(line)
            m[i,j] = char - 'a';
            if char == 'E'
                m[i,j] = END;
            elseif char == 'S'
                m[i,j] = START;
            end
        end
    end
    m
end

function find_start_end(m::Matrix{Int})::Tuple{CartesianIndex, CartesianIndex}
    findnext((==)(START), m, CartesianIndex((1,1))), findnext((==)(END), m, CartesianIndex((1,1)))
end

function reconstruct_path(parents::Matrix{CartesianIndex{2}}, start::CartesianIndex, endd::CartesianIndex)::Vector{CartesianIndex}
    v = Vector{CartesianIndex}();
    current = endd;
    while current != start 
        push!(v, current);
        current = parents[(current)];
    end
    reverse!(v);
    v
end

function find_path(m::Matrix{Int}; start::Union{Nothing, CartesianIndex}=nothing)::Vector{CartesianIndex}
    s, e = find_start_end(m);
    if !isnothing(start)
        s = start;
    end

    current_best = zeros(Int, size(m)) .+ 10000;
    parents = [CartesianIndex((-1,-1)) for i = 1:size(m, 1), j = 1:size(m, 2)];
    top = PriorityQueue{Tuple{CartesianIndex,Int}, Int}();
    enqueue!(top, (s, 0), 0);

    valid(x) = x[1] > 0 && x[1] <= size(m, 1) && x[2] > 0 && x[2] <= size(m, 2);

    while length(top) > 0
        (cb, dist) = dequeue!(top);
        for mov in [(0,1),(0,-1),(1,0),(-1,0)]
            nb = cb + CartesianIndex(mov);
            if !valid(nb)
                continue
            end
            if m[nb] == END && m[cb] >= 24
                parents[nb] = cb;
                return reconstruct_path(parents, s, nb)
            elseif m[nb] == END || (m[nb]-m[cb]) > 1
                continue;
            end
            if current_best[nb] > dist + 1
                current_best[nb] = dist + 1;
                parents[nb] = cb;
                enqueue!(top, (nb, dist + 1), dist + 1);
            end
        end
    end
    []
end

function find_any_shortest_path(m::Matrix{Int})::Vector{Int}
    positions = findall(x -> x == START || x == 0, m);
    lengths = [length(find_path(m; start=p)) for p in positions];
    sort!(lengths);
    lengths
end

open(input; read=true) do fh
    m = read_map(fh);
    for c in eachrow(m)
        println(c);
    end
    @time p = find_path(m);
    println("PART 1: Path $p with length $(length(p))");

    println("PART 2: All path lengths are $(find_any_shortest_path(m))");
end