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).




with javascript_semantics
enum SUB=-1, NOP=0, ADD=1
 
function evaluate(sequence s)
integer res = 0, tmp = 0, op = ADD
    for i=1 to length(s) do
        if s[i]=NOP then
            tmp = tmp*10+i
        else
            res += op*tmp
            tmp = i
            op = s[i]
        end if
    end for
    return res + op*tmp
end function
 
procedure show(sequence s)
string res = ""
    for i=1 to length(s) do
        if s[i]!=NOP then
            res &= ','-s[i]
        end if          
        res &= '0'+i
    end for
    printf(1,"%s = %d\n",{res,evaluate(s)})
end procedure
 
-- Logically this intersperses -/nop/+ between each digit, but you do not actually need the digit.
sequence s = repeat(SUB,9)  -- (==> ..nop+add*8)
 
bool done = false
integer maxl = 0, maxr
integer count = 0
while not done do
    count += 1
    integer r = evaluate(s), k = getd_index(r)
    sequence solns = iff(k=0?{}:deep_copy(getd_by_index(k)))
    solns = append(solns,deep_copy(s))
    setd(r,solns)
    if r>0 and maxl<length(solns) then
        maxl = length(solns)
        maxr = r
    end if
    for i=length(s) to 1 by -1 do
        if i=1 and s[i]=NOP then
            done = true
            exit
        elsif s[i]!=ADD then
            s[i] += 1
            exit
        end if
        s[i] = SUB
    end for
end while
 
printf(1,"%d solutions considered (dictionary size: %d)\n",{count,dict_size()})
 
sequence s100 = getd(100)
printf(1,"There are %d sums to 100:\n",{length(s100)})
papply(s100,show)
 
printf(1,"The positive sum of %d has the maximum number of solutions: %d\n",{maxr,maxl})
 
integer prev = 0
function missing(integer key, sequence /*data*/, integer /*pkey*/, object /*user_data=-2*/)
    if key!=prev+1 then
        return 0
    end if
    prev = key
    return 1
end function
traverse_dict_partial_key(missing,1)
printf(1,"The lowest positive sum that cannot be expressed: %d\n",{prev+1})
 
sequence highest = {}
function top10(integer key, sequence /*data*/, object /*user_data*/)
    highest &= key
    return length(highest)<10
end function
--DEV named params on builtins need pre-loading...:
--traverse_dict(top10,rev:=1)
traverse_dict(top10,0,1,true)
printf(1,"The 10 highest sums: %v\n",{highest})
