Task

Find solutions to the    sum to one hundred    puzzle.



Add (insert) the mathematical
operators      +    or    -      (plus
or minus)   before any of the digits in the

decimal numeric string    123456789    such that the
resulting mathematical expression adds up to a

particular sum   (in this iconic case,   100).



Example:

             123 + 4 - 5 + 67 - 89   =   100     

Show all output here.



   Show all solutions that sum to    100 
   Show the sum that has the maximum   number   of solutions   (from zero to infinity‡)
   Show the lowest positive sum that   can't   be expressed   (has no solutions),   using the rules for this task
   Show the ten highest numbers that can be expressed using the rules for this task   (extra credit)


‡   (where   infinity   would be a relatively small   123,456,789)



An example of a sum that can't be expressed   (within the rules of this task)   is:   5074

(which,   of course,   isn't the lowest positive sum that can't be expressed).




using Printf, IterTools, DataStructures
 
expr(p::String...)::String = @sprintf("%s1%s2%s3%s4%s5%s6%s7%s8%s9", p...)
function genexpr()::Vector{String}
    op = ["+", "-", ""]
    return collect(expr(p...) for (p) in Iterators.product(op, op, op, op, op, op, op, op, op) if p[1] != "+")
end
 
using DataStructures
 
function allexpr()::Dict{Int,Int}
    rst = DefaultDict{Int,Int}(0)
    for e in genexpr()
        val = eval(Meta.parse(e))
        rst[val] += 1
    end
    return rst
end
 
sumto(val::Int)::Vector{String} = filter(e -> eval(Meta.parse(e)) == val, genexpr())
function maxsolve()::Dict{Int,Int}
    ae = allexpr()
    vmax = maximum(values(ae))
    smax = filter(ae) do (v, f)
        f == vmax
    end
    return smax
end
function minsolve()::Int
    ae = keys(allexpr())
    for i in 1:typemax(Int)
        if i ∉ ae
            return i
        end
    end
end
function highestsums(n::Int)::Vector{Int}
    sums = collect(keys(allexpr()))
    return sort!(sums; rev=true)[1:n]
end
 
const solutions = sumto(100)
const smax = maxsolve()
const smin   = minsolve()
const hsums = highestsums(10)
 
println("100 =")
foreach(println, solutions)
 
println("\nMax number of solutions:")
for (v, f) in smax
    @printf("%3i -> %2i\n", v, f)
end
 
println("\nMin number with no solutions: $smin")
 
println("\nHighest sums representable:")
foreach(println, hsums)
 