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