import Base.Collections: heapify!, heappush!, heappop!
using DataStructures
include("gray_calhoun.jl")
include("io_util.jl"); import IOUtil
#include("bio_util.jl"); import BioUtil
#include("graph_util.jl"); import GraphUtil

INPUT = """\
-10 -8 -7 -6 -5 -4 -3 -3 -2 -2 0 0 0 0 0 2 2 3 3 4 5 6 7 8 10
"""
fp = IOBuffer(INPUT)
fp = open("rosalind_2i.txt");

ΔA = map(parseint, split(readline(fp)))
close(fp)

#ΔA = sort([18,14,16,12,12,14,7,10,10,11,4,5,8,7,6,2,2,3,5,2,4])
#ΔA = [ΔA, -ΔA, [0, 0, 0, 0, 0, 0, 0]]

println("ΔA=$(size(ΔA))")

#------------------------------------------------------------------------

N = int(sqrt(length(ΔA)))
@assert N^2 == length(ΔA)
@assert N > 2
@assert sum(ΔA) == 0
@assert count(x -> x== 0, ΔA) == N

positive_ΔA = filter(x -> x > 0, ΔA)
d_max = maximum(positive_ΔA)

@assert d_max < 99999

function turnpike(positive_ΔA, N)
    
    ordered_values = sort(unique(positive_ΔA), rev=true)
    
    # return max unused value in ΔA, move ptr to next 
    function find_next_unused_value(ptr)
        # linear search for next unused, probably not most efficient
        for i in ptr:length(ordered_values)
            if counts[ordered_values[i]] > 0
                return i
            end
        end
        throw(ErrorException("no more usused value"))
    end        
        
    function try_assign(i, j, value, stack)    
        if value <= 0 || counts[value] <= 0
#            println("Fail to find $value -> $i,$j")
            return false
        end
        D[i, j] = value
        counts[value] -= 1
        push!(stack, (i, j, value))
        return true
    end        
        
    function turnpike_next(m, n, unused_ptr, place_right)
        if m == n
            # success, all diagonal values are found
            return true
        end

        stack = (Int, Int, Int)[]        
        max_value = ordered_values[unused_ptr]
#=
        println("m=$(m) n=$(n)\n$D") # $D
        @printf("\nPlace %s max_value=%d -> (%d, %d)\n", 
            place_right ? "right" : "top",
            max_value, 
            place_right ? m+1 : 1,
            place_right ? N : n-1
        )
=#
        
        if place_right

            # place left
            if m+2 >= N                
                return false    # don't place on or below diagonal
            end        
            try_assign(m+1, N, max_value, stack)

            # assign diagonal value
            d_m = D[m,N] - D[m+1, N]
#            println(d_m <= 0 ? 
#                "diagonal value = $(d_m)?" : 
#                "diagonal value = $(d_m)$(counts[d_m]>0 ? '!' : '?') -> $(m),$(m+1)")            

            if try_assign(m, m+1, d_m, stack)
                
                # assign bottom row, empty list mean true
                from_idx = max(n, m+2)
#                println("bottom row $(m+1),$(from_idx:N-1)")
                if @all [try_assign(m+1, k, D[m,k] - d_m, stack) for k in from_idx:N-1]
                
                    # next recusion step
                    unused_ptr = find_next_unused_value(unused_ptr)
                    if turnpike_next(m+1, n, unused_ptr, false) ||  turnpike_next(m+1, n, unused_ptr, true)
                        return true
                    end                        
                end
            end            
        else

            # place top
            if n-1 <= 2                
                return false    # don't place on or below diagonal
            end        
            try_assign(1, n-1, max_value, stack)

            # assign diagonal value
            d_n = D[1,n] - D[1,n-1]
#            println(d_n <= 0 ?
#                "diagonal value = $(d_n)?" : 
#                "diagonal value = $(d_n)$(counts[d_n]>0 ? '!' : '?') -> $(n-1),$(n)")            
            if try_assign(n-1, n, d_n, stack)

                # assign left column, empty list mean true
                to_idx = min(m, n-3)
#                println("left column $(2:to_idx),$(n-1)")
                if @all [try_assign(k, n-1, D[k,n] - d_n, stack) for k in 2:to_idx]
                    
                    # next recusion step
                    unused_ptr = find_next_unused_value(unused_ptr)
                    if turnpike_next(m, n-1, unused_ptr, true) ||  turnpike_next(m, n-1, unused_ptr, false)
                        return true
                    end
                end
            end                            
        end

        # failed, backtrack
        for (i,j,v) in stack
            D[i,j] = 0
            counts[v] += 1
        end            
        return false
    end
                        
    #counts = Dict(counter(positive_ΔA))
    # use sparse array for counts rather than dictionary
    d_max = maximum(positive_ΔA)
    @assert d_max < 99999
    counts = zeros(Int, d_max)
    for x in positive_ΔA
        counts[x] += 1
    end
    
    D = zeros(Int, (N,N))
    # assign d_max to top right corner
    d_max = ordered_values[1]
    D[1,N] = d_max
    counts[d_max] -= 1
    unused_ptr = 2
    
    result = turnpike_next(1, N, unused_ptr, true) || turnpike_next(1, N, unused_ptr, false)
    return result, D, counts
end

function build_A(D, N)
    [0, [cumsum([D[i,i+1] for i in 1:N-1])]]
end


#result, D, counts = turnpike(positive_ΔA, N)
result, D, counts = turnpike(positive_ΔA, N)
if result
    A = build_A(D, N)
    IOUtil.write_vector("out", A)
else
    println("failed")
    D
end