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




 
#define PERM 13122
 
'Between any two adjacent digits there can be nothing, a plus, or a minus.
'And the first term can only be + or -
'This is equivalent to an eight-digit base 3 number. We therefore only need
'to consider 2*3^8=13122 possibilities
 
function ndig(n as uinteger) as uinteger
    return 1+int(log(n+0.5)/log(10))
end function
 
function calculate( byval n as uinteger, outstr as string ) as integer
    'calculates the sum given by one of the 13122 possibilities, as well as
    'storing the equation itself as a string
    outstr = "9"
    dim as integer ret = 0, curr = 9
    dim as boolean firstplus = n>=PERM/2
    for i as integer = 8 to 1 step -1
        select case n mod 3
            case 0   'no symbol means we just prepend the next number
                curr += i*10^(ndig(curr))
            case 1   'addition: add the current term to the running sum, and clear the current term
                ret += curr
                curr = i
                outstr = " + " + outstr
            case 2   'subtraction: minus the current term from the running sum, and clear the current term
                ret -= curr
                curr = i
                outstr = " - " + outstr
        end select
        outstr = str(i) + outstr      'prepend the previous digit to the string
        n \= 3                        'get next symbol
    next i
    if firstplus = 0 then
        outstr = "-"+outstr
        ret -= curr
    else
        ret += curr
    end if
    outstr = outstr + " = " + str(ret)
    return ret
end function
 
'calculate and store all 13122 solutions
dim as string eqn
dim as integer n, sum(0 to PERM-1), curr
for n = 0 to PERM-1
    curr = calculate(n, eqn)
    sum(n) = curr
    if curr = 100 then print eqn
next n
 
'what is the sum that has the most solutions?
dim as integer champ = 0, cnum = 0, i, j, acc
for i = 0 to PERM-1
    acc = 0
    for j = i to PERM-1
        if sum(j) = sum(i) then acc+=1
    next j
    if acc>cnum then
        champ = sum(i)
        cnum=acc
    end if
next i
print "The sum with the most occurrences is ";champ;", which shows up ";cnum;" times."
 
'what is the first nonnegative number that has no solution
for i = 0 to 123456788
    for j = 0 to PERM-1
        if sum(j)=i then goto nexti
    next j
    print "The first number that has no solution is ";i
    exit for
    nexti:
next i
 
'What are the ten highest numbers?
'this partially destroys the information in the array, but who cares?
'We're almost done and these excessive questionnaires are the worst
'and most boring part of Rosetta Code tasks 
 
print "The ten highest numbers attainable are:"
champ = 0
for i = 1 to 10
    for j = 0 to PERM-1
        if sum(j)>sum(champ) then champ = j
    next j
    calculate(champ, eqn)
    print eqn
    sum(champ) = -9999   'overwrite to stop this being found a second time
next i