# Today's input is essentially a big block of numbers (0-9).
# Ingest it by reading each line, breaking it into characters,
# storing all the character vectors in a big vector, then 
# converting the 2D vector into a Matrix{Int}
function ingest(path)
    outvectors = open(path) do f
        [collect(line) for line in readlines(f)]
    end
    toint(x) = parse(Int8, 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

# Takes an integer matrix and adds a "ring" of `9`'s to the outside
# of it, essentially "padding" the matrix with the number `9`
function pad(M::Matrix{T}) where T <: Integer
    (rows, cols) = size(M)
    rowpadding = fill(9, (1, cols))
    colpadding = fill(9, (rows + 2, 1))
    
    (vcat(rowpadding, M, rowpadding)
     |> (x -> hcat(colpadding, x, colpadding)))
end

# Find the points in a numeric matrix where the value in that
# position is smaller than the values in the four cardinal 
# directions, if viewed as a map. 
function findlowpoints(heightmap::Matrix{T}) where T <: Integer
    # Create a copy of the heightmap padded with `9`'s
    (rows, cols) = size(heightmap)
    padded = pad(heightmap)

    # Take views of the heightmap that are the same size but
    # shifted either up, down, left, or right. The padding ensures
    # that the `upshift` has a bottom row of all `9`. This ensures
    # that values in  the bottom row of `heightmap` will identify
    # as a 'lowest point' if the values above, to the left, and to
    # the right are also larger. This similarly holds true for values
    # on all four edges of `heightmap`.
    upshift    = view(padded, 1:rows,     2:(cols+1))
    downshift  = view(padded, 3:(rows+2), 2:(cols+1))
    leftshift  = view(padded, 2:(rows+1), 3:(cols+2))
    rightshift = view(padded, 2:(rows+1), 1:cols)

    # Check `heightmap` against all four views. For any point where the
    # value at the corresponding position in all four `shifts` is greater
    # than the value at that point in `heightmap`, that position in the
    # returned BitMatrix will be `1`, otherwise it will be `0`.
    shifts = [rightshift, leftshift, upshift, downshift]
    return mapreduce(S -> S .> heightmap, .&, shifts)
end

# Identify each position in the input that represents a 'low point', 
# and return the sum of the values at those positions.
function part1(input)
    lowpoints = findlowpoints(input)
    return sum(input[lowpoints] .+ 1)
end

# Given a matrix and an index, return the indices of the positions
# above, below, to the left, and to the right of the given index,
# accouting for edges.
function neighborindices(matrix::AbstractMatrix, idx::CartesianIndex)::Vector{CartesianIndex}
    out = []; sizehint!(out, 4)
    (rows, cols) = size(matrix)
    if idx[1] > 1;    push!(out, idx - CartesianIndex(1, 0)); end
    if idx[1] < rows; push!(out, idx + CartesianIndex(1, 0)); end
    if idx[2] > 1;    push!(out, idx - CartesianIndex(0, 1)); end
    if idx[2] < cols; push!(out, idx + CartesianIndex(0, 1)); end
    return out
end

# Given a BitMatrix were a `1` indicates a part of a basin and a `0` 
# indicates a part of a ridge and an index to start search from,
# perform a breadth-first search of `heightmap`, to find all adjacent
# 'basin' points that can be reached from the starting point.
function basinsizeat(heightmap::BitMatrix, idx::CartesianIndex)::Int
    queue = [idx]           # Points to check
    visited = Set(queue)    # Points we've already checked
    cells = 1               # Number of points that have been checked

    # As long as there are still more points to check...
    while !isempty(queue)
        # Take an index from the top of the queue 
        location = pop!(queue)

        # For all of that index's neighbors...
        for neighbor in neighborindices(heightmap, location)
            # If it's already been checked, skip it
            neighbor in visited && continue

            # Mark it as checked
            push!(visited, neighbor)

            # If that neighboring index is part of the basin, add that
            # index to the front of the queue and increment our count
            if heightmap[neighbor]
                pushfirst!(queue, neighbor)
                cells += 1
            end
        end
    end

    return cells
end

# Transform our input into a BitMatrix, where `1`'s indicate basins,
# positions where the value is less than 9. For each lowpoint, in
# the input, perform a breadth-first search for neighboring basin 
# cells and return the count. Once all the basins have been measured,
# get the sizes (by number of included indices) of the three largest
# and return the product of all three.
function part2(input)
    basins = input .< 9
    lowpoints = findlowpoints(input)
    basinsizes = []; sizehint!(basinsizes, sum(lowpoints))
    for index in findall(lowpoints)
        push!(basinsizes, basinsizeat(basins, index))
    end
    sort!(basinsizes, rev = true)
    return prod(basinsizes[1:3])
end