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




local expressionsLength = 0
function compareExpressionBySum(a, b)
    return a.sum - b.sum
end
 
local countSumsLength = 0
function compareCountSumsByCount(a, b)
    return a.counts - b.counts
end
 
function evaluate(code)
    local value = 0
    local number = 0
    local power = 1
    for k=9,1,-1 do
        number = power*k + number
        local mod = code % 3
        if mod == 0 then
            -- ADD
            value = value + number
            number = 0
            power = 1
        elseif mod == 1 then
            -- SUB
            value = value - number
            number = 0
            power = 1
        elseif mod == 2 then
            -- JOIN
            power = 10 * power
        else
            print("This should not happen.")
        end
        code = math.floor(code / 3)
    end
    return value
end
 
function printCode(code)
    local a = 19683
    local b = 6561
    local s = ""
    for k=1,9 do
        local temp = math.floor((code % a) / b)
        if temp == 0 then
            -- ADD
            if k>1 then
                s = s .. '+'
            end
        elseif temp == 1 then
            -- SUB
            s = s .. '-'
        end
        a = b
        b = math.floor(b/3)
        s = s .. tostring(k)
    end
    print("\t"..evaluate(code).." = "..s)
end
 
-- Main
local nexpr = 13122
 
print("Show all solutions that sum to 100")
for i=0,nexpr-1 do
    if evaluate(i) == 100 then
        printCode(i)
    end
end
print()
 
print("Show the sum that has the maximum number of solutions")
local nbest = -1
for i=0,nexpr-1 do
    local test = evaluate(i)
    if test>0 then
        local ntest = 0
        for j=0,nexpr-1 do
            if evaluate(j) == test then
                ntest = ntest + 1
            end
            if ntest > nbest then
                best = test
                nbest = ntest
            end
        end
    end
end
print(best.." has "..nbest.." solutions\n")
 
print("Show the lowest positive number that can't be expressed")
local code = -1
for i=0,123456789 do
    for j=0,nexpr-1 do
        if evaluate(j) == i then
            code = j
            break
        end
    end
    if evaluate(code) ~= i then
        code = i
        break
    end
end
print(code.."\n")
 
print("Show the ten highest numbers that can be expressed")
local limit = 123456789 + 1
for i=1,10 do
    local best=0
    for j=0,nexpr-1 do
        local test = evaluate(j)
        if (test<limit) and (test>best) then
            best = test
        end
    end
    for j=0,nexpr-1 do
        if evaluate(j) == best then
            printCode(j)
        end
    end
    limit = best
end