# println("I'm Julia. Nice to meet you!") function sums(total, limit=0, strict=false) # Return a list of all nondecreasing lists of positive integers # whose total is total, and whose greatest element is no more than # limit. (If limit is 0, no limit.) if total <= 0 if total == 0 return [Int64[]] else return [] end end ret = [] if limit == 0 limit = total end i = strict ? limit-1 : limit while i > 0 append!(ret, [push!(qq,i) for qq in sums(total-i, i, strict)]) i -= 1 end return ret end function permutations(lst) ret = [] if length(lst) == 0 return [[]] else for i in [1:length(lst);] lst_new = append!([], lst) splice!(lst_new, i) append!(ret, [push!(qq,lst[i]) for qq in permutations(lst_new)]) end return ret end end function total(arr) total = 0 for x in arr total += x end return total end function stack_coins(coins, num_piles=3) piles = [Set(), Set(), Set()] # invariant: piles will be sorted with respect to total while length(coins) > 0 push!(piles[1], pop!(coins)) sort!(piles, by=total) end return piles end function all_ways(coins) seen = Set() for perm in permutations(coins) X = stack_coins(perm) if !in(X, seen) push!(seen, X) end end return seen end function explore_limited_piles() num_coins = 3 while true num_coins += 1 best_coins = Int64[] best_ways = 9999999 total = num_coins _counter = 0 while best_ways > 1 for coins in sums(total, 0, true) if length(coins) != num_coins continue end _counter += 1 ways = length(all_ways(coins)) if _counter % 10000 == 0 println(coins) println(ways) println(best_coins) println(best_ways) end if ways < best_ways best_ways = ways best_coins = coins println("********") println(best_coins) println(best_ways) end end total += 1 end println("!!!!!!!") println(best_coins) println(best_ways) end end # explore_limited_piles() # for qq in all_ways([100,95,98,6,30]) # println(qq) # end function empty(coll) return coll[1:0] end function bisections(agenda, left=[], right=[]) if agenda == [] return [(left, right)] else return append!(bisections(agenda[2:end], append!(agenda[1:1], left), right), bisections(agenda[2:end], left, append!(agenda[1:1], right))) end end function partitions(lst, k) if k == 0 return (lst == []) ? [[lst]] : [[lst]][1:0] elseif k == 1 return (lst != []) ? [[lst]] : [[lst]][1:0] else ret = [[lst]][1:0] if lst == [] return [] end x = lst[1:1] for (left, right) in bisections(lst[2:end]) if length(right) >= k-1 push!(left, x[1]) append!(ret, [push!(qq, left) for qq in partitions(right, k-1)]) end end return ret end # return bisections(lst, empty(lst), empty(lst)) end function all_partitions(lst) ret = [] for k in 1:length(lst) append!(ret, partitions(lst, k)) end return ret end function index_partition(lst, partition) return [[lst[i] for i in p] for p in partition] end function fill_partition(partition, lst) ret = empty(lst) n = sum(map(x -> length(x), partition)) append!(ret, collect(1:n)) for p in 1:length(partition) for i in partition[p] ret[i] = lst[p] end end return ret end function has_equality_property(partition) # returns true if the given partition has the property that each # group has an element which, if removed, makes the sum of the # elements in the group no larger than the sum of the elements in # any other group. sums = map(sum, partition) maxs = map(maximum, partition) smallest = minimum(sums) return all([x <= smallest for x in map(-, sums, maxs)]) end # println(has_equality_property([[2,2],[3],[1,5]])) # println(partitions([0,1,2,3],1)) # #println(partitions([0,1,2,3],2)) # map(println, (partitions([1,2,3,4,5,6],3))) # println(length(partitions([1,2,3,4,5,6],3))) # # println(partitions([0,1,2,3],1)) # P = partitions([1,2,3,4,5,6],3) # println(index_partition(['A','B','C','D','E','F'], P[1]), P[1]) function compatible_partitions(partition_list, weights) return [p for p in partition_list if has_equality_property(index_partition(weights, p))] end function random_weights(num_coins, partition_list=[]) weights = [0.0][1:0] for i in 1:num_coins push!(weights, sqrt(rand())) end return (weights, compatible_partitions(partition_list, weights)) end function many_random_weights(num_coins, partition_list=[], num_samples=1, enforce_equal=[]) if enforce_equal == [] enforce_equal = [map(x->[x], 1:num_coins)] end ret = [] for i in 1:num_samples weights = [0.0][1:0] for j in 1:num_coins push!(weights, sqrt(rand())) end # println(weights) # println(enforce_equal[rand(1:end)]) # println(fill_partition(enforce_equal[1], [2,4,6,8,10,12,14,16])) weights = fill_partition(enforce_equal[rand(1:end)], weights) push!(ret, (weights, compatible_partitions(partition_list, weights))) end return ret end function covers(labels, label_sets) return all([intersect(Set(labels), Set(y)) != Set([]) for y in label_sets]) end function minimal_covering(label_sets, labels) if !covers(labels, label_sets) || labels == Set([]) return Set([]) else for i in 1:length(labels) ys_new = labels[1:end] splice!(ys_new, i) candidate = minimal_covering(label_sets, ys_new) if candidate != Set([]) return candidate end end return labels end end # P = partitions([1,2,3,4,5,6],3) # W = [1,4,5,6,100,100] # Q = compatible_partitions(P, W) # # map(println, map(x -> index_partition(W, x), Q)) # Y = many_random_weights(6, P, 1000) # # println(Y[1][1],"\t", length(Y[1][2])) # xs = map(x -> x[1], Y) # ys = map(x -> x[2], Y) # println("asdfasdf",minimal_covering(ys, P)) function group_by(f, coll, tally_only=false) if coll == [] return Dict() end ret = Dict(f(coll[1]) => coll[1:0]) for x in coll y = f(x) ret[y] = push!(get(ret, y, []), x) end if tally_only return Dict(x => length(ret[x]) for x in keys(ret)) end return ret end function covering_number(label_sets, labels) # zero when covering number is minimal return length(minimal_covering(label_sets, labels)) - 1 end function average_disorder(branch_score, dict) return mean(map(branch_score, values(dict))) end function decision_tree(branch_score, tests, points) # println(branch_score(points)) if branch_score(points) == 0 # homogeneous branch return nothing else # println(map(f, points)) # println(f(points[1])) # println(xs, ys, name, f) # println(points) possible_branches = [(name, f, group_by(f, points)) for (name, f) in tests] possible_branches = [(x,y,z) for (x,y,z) in possible_branches if length(values(z)) > 1] if possible_branches == [] return false end possible_disorders = [average_disorder(branch_score, groupdict) for (name, f, groupdict) in possible_branches] (disorder, indx) = findmin(possible_disorders) chosen_branch = possible_branches[indx] # possible_branches = [(average_disorder(branch_score, groupdict), name, f, groupdict) # for (name, f, groupdict) in possible_branches[1:10]] println(chosen_branch[1]) ret = [] push!(ret, chosen_branch[1]) remaining_tests = [(x,y) for (x,y,z) in possible_branches] for branch_points in values(chosen_branch[3]) push!(ret, decision_tree(branch_score, remaining_tests, branch_points)) end return ret # sort!(possible_branches, by=name_fn_group -> average_disorder(branch_score, name_fn_group[3])) # chosen_branch = possible_branches[1] # println(chosen_branch[1]) # ret = [] # push!(ret, chosen_branch[1]) # for branch_points in values(chosen_branch[3]) # # push!(ret, decision_tree(branch_score, tests, branch_points)) # end # return ret end end function tree_height(tree) if tree == nothing || tree == false return 0 else return 1 + maximum(map(tree_height, tree[2:end])) end end function play(num_coins, num_partitions=3) P = partitions(collect(1:num_coins),num_partitions) PP = all_partitions(collect(1:num_coins)) num_samples = 1000 Y = many_random_weights(num_coins, P, num_samples) append!(Y, many_random_weights(num_coins, P, num_samples*100,PP)) xs = map(x -> x[1], Y) ys = map(x -> x[2], Y) # println(covering_number(ys[1:3], P)) # println(P[60]) # print(xs[end-10:end]) weighing_vectors = map(p -> fill_partition(p, [1,-1]), partitions(collect(1:num_coins), 2)) append!(weighing_vectors,map(p -> fill_partition(p, [1,-1, 0]), partitions(collect(1:num_coins), 3))) weighing_tests = map(n -> (n, (xy -> sign(dot(n,xy[1])))), weighing_vectors) D = decision_tree(points -> covering_number(map(x->x[2], points), P), weighing_tests, Y) println(D) println(tree_height(D)) #println(weighing_tests[60]) end # println(group_by(x -> x %3, [1,2,3,4,5,6,7])) play(6)