# Ingest the Data -------------------------------------------------------------
function ingest(path)
    return open(path) do f
        outvectors = open(path) do f
            [collect(line) for line in readlines(f)]
        end
        toint(x) = parse(UInt8, x)

        # I transposed the matrix to make debugging easier, since 
        # otherwise it won't print in the same orientation as the input.
        (outmatrix
         = outvectors
         |> (x -> reduce(hcat, x))
         |> (x -> map(toint, x))
         |> transpose
         |> collect)
        return outmatrix
    end
end

# Some Useful Data Structures --------------------------------------------------
using DataStructures: BinaryMinHeap

# Helper Functions -------------------------------------------------------------

function neighbors(idx::CartesianIndex, M::AbstractMatrix)
    offsets = [CartesianIndex( 1, 0), CartesianIndex(0, 1),
               CartesianIndex(-1, 0), CartesianIndex(0, -1)]
    neigbhoridxs = [offset + idx for offset in offsets]

    # Only keep neighbor indices that are actually in the grid
    return filter(i -> checkbounds(Bool, M, i), neigbhoridxs)
end

# Find the minimum path from `start` to `finish` on `map` using Dijkstra's algorithm
function minpath(start, finish, map)
    distances = fill(typemax(UInt16), size(map))
    distances[1, 1] = 0

    heap = BinaryMinHeap([(0, CartesianIndex(1, 1))])
    visited = Set{CartesianIndex}()

    while !isempty(heap)
        (distance, current) = pop!(heap)
        current in visited && continue
        current == finish && return distances[finish]
        push!(visited, current)

        for neighbor in neighbors(current, map)
            traveldistance = distance + map[neighbor]

            if traveldistance < distances[neighbor]
                distances[neighbor] = traveldistance
            end

            push!(heap, (distances[neighbor], neighbor))
        end
    end
    error("Could not find a path from $start to $finish!")
end

# Solve Part One ---------------------------------------------------------------

function part1(input)
    start = CartesianIndex(1,1)
    finish = CartesianIndex(size(input))
    return minpath(start, finish, input)
end

# Helper Functions -------------------------------------------------------------

# Given a matrix `M`, return a matrix expanded by `amt` "tiles" horizontally
# and vertically, where each "tile" is a copy of the `M` matrix with values
# increased by the total row/column offset from the top left corner, as 
# described in the puzzle description.
function expandby(M::Matrix{T}, amt::Int64) where T <: Unsigned
    # Initialize a matrix large enough to hold the output
    expandeddims = size(M) .* (amt + 1)
    expanded = zeros(Int64, expandeddims)
    (rows, cols) = size(M)

    # Loop over each combination of row/column offset from the top
    # left corner
    for (rowoffset, coloffset) in Iterators.product(0:amt, 0:amt)
        # Calculate which portion of the `expanded` matrix to replace with
        # the values of the tile indicated by the row/col offset
        rowindices = collect(1:rows) .+ (rowoffset * rows)
        colindices = collect(1:cols) .+ (coloffset * cols)

        # Replace the zeros in `expanded` with the values from `M` and increase
        # those values by the total offset, wrapping all values greater than 9
        expanded[rowindices, colindices] = M
        expanded[rowindices, colindices] .+= (rowoffset + coloffset)
        expanded[expanded .> 9] .%= 9
    end
    return expanded    
end

# Solve Part Two ---------------------------------------------------------------

# Expand the input map and find the shortest path through it
function part2(input)
    expandedmap = expandby(input, 4)
    start = CartesianIndex(1,1)
    finish = CartesianIndex(size(expandedmap))
    return minpath(start, finish, expandedmap)
end