Pizza.jl

module Pizza

import Base: getindex, setindex!, read, write



struct PizzaInput
    mintopping::Int
    maxsize::Int
    cells::Matrix{Bool}
end
function read(io::IO, ::Type{PizzaInput})
    r,c,l,h = parse.(Int, split(readline(io)))

    cells = reduce(vcat, ( [ c == 'T' for i=i:i, c in readline(io)] for i = 1:r) )

    return PizzaInput(l,h,cells)
end

struct Slice
    row1::Int
    row2::Int
    column1::Int
    column2::Int
end

struct WorkingPizza
    input::PizzaInput # reference pizza
    cells::Array{Union{Bool, Nothing}}
    ratio::Float64

    WorkingPizza(input::PizzaInput) = new(input, Array{Union{Bool,Nothing}}(input.cells), count(input.cells)/length(input.cells))
end

function takeslice!(pizza::WorkingPizza, slice::Slice)
    pizza.cells[slice] = nothing
end

function validslice(pizza::WorkingPizza, slice::Slice)
    h,w = size(pizza.cells)
    if !( 1 ≤ slice.row1 ≤ slice.row2 ≤ h && 1 ≤ slice.column1 ≤ slice.column2 ≤ w )
        return false
    end
    sliceCells = pizza.cells[slice]

    if length(sliceCells) > pizza.input.maxsize
        return false
    end

    tomatos = 0
    for cell in sliceCells
        if cell === nothing
            return false
        end

        tomatos += cell
    end

    if tomatos < pizza.input.mintopping || length(sliceCells) - tomatos < pizza.input.mintopping
        return false
    end

    return true
end

getindex(collection::AbstractMatrix, slice::Slice) where T = @view collection[slice.row1:slice.row2, slice.column1:slice.column2]
setindex!(collection::AbstractMatrix, value, slice::Slice) = view(collection, slice.row1:slice.row2, slice.column1:slice.column2) .= value

struct PizzaOutput
    slices::Vector{Slice}
end

function write(io::IO, output::PizzaOutput)
    println(io, length(output.slices))
    for slice in output.slices
        println(io, "$(slice.row1-1) $(slice.column1-1) $(slice.row2-1) $(slice.column2-1)")
    end
end

function tryslice(pizza::WorkingPizza, row, col)
    h,w = size(pizza.cells)

    mxsz = min((h - row + 1) * (w - col + 1), pizza.input.maxsize)
    mnsz = 2*pizza.input.mintopping
    for sz = mxsz:-1:mnsz
        f = 1
        while f*f <= sz
            if sz % f == 0
                g = sz ÷ f

                slice = Slice(row, row+f-1, col, col+g-1)
                if validslice(pizza, slice)
                    return slice
                end

                if f ≠ g
                    slice = Slice(row, row+g-1, col, col+f-1)
                    if validslice(pizza, slice)
                        return slice
                    end
                end
            end
            f += 1
        end
    end

end

using DataStructures

# Random solver
function solve(input::PizzaInput, mxiter = 1000)
    h,w = size(input.cells)

    pizza = WorkingPizza(input)

    slices = Slice[]

    iters = 0

    points = Queue{Tuple{Int,Int}}()
    enqueue!(points, (1,1))

    i = 0

    while !isempty(points) && i < mxiter
        i,j = dequeue!(points)

        if pizza.cells[i,j] === nothing
            continue
        end

        slice = tryslice(pizza, i, j)
        if slice !== nothing
            push!(slices, slice)

            takeslice!(pizza, slice)

            slice.row2 < h && enqueue!(points, (slice.row2+1, j))
            slice.column2 < w && enqueue!(points, (i,slice.column2+1))
        else
            i < h && enqueue!(points, (i+1, j))
            j < w && enqueue!(points, (i, j+1))
        end
    end

    idx = findfirst(x->x!==nothing,pizza.cells)

    while idx !== nothing && i < mxiter

        slice = tryslice(pizza, idx[1], idx[2])
        if slice !== nothing
            push!(slices, slice)
            @show slice
            takeslice!(pizza, slice)
        end

        idx = findnext(x->x!==nothing,pizza.cells,idx)

        i += 1
    end

    if !isempty(points)
        @show length(points)
    end

    PizzaOutput(slices)
end

function score(output::PizzaOutput)
    sum = 0
    for slice in output.slices
        sum += (slice.row2 - slice.row1 + 1) * (slice.column2 - slice.column1 + 1)
    end
    return sum
end

function generate_outputs(best = Dict{String, Pair{Int, PizzaOutput}}())

    inputs = Dict(file => read(joinpath("inputs", file), Pizza.PizzaInput) for file in readdir("inputs"))

    for (file,input) in inputs
        if !haskey(best, file)
            best[file] = 0 => PizzaOutput(Pizza.Slice[])
        end
    end

    for (k,input) in inputs
        @show k
        output = solve(input, 10000)
        _score = score(output)
        if _score > first(best[k])
            best[k] = _score => output
            println("$k has new best: $_score")
        end
    end

    for (k,(s,o)) in best
        k,_ = splitext(k)
        write("outputs/$k.out", o)
    end

    best
end

end