Select Page

A dude recently posted some programming challenges on his blog (here) that were mentioned on Reddit r/programming.

Problem 5 caught my eye and below, I’ve posted a short and sweet Lua brute-force to solve it:

expertoption demo
Prizma FX
Write a program that outputs all possibilities to put + or – or nothing between the numbers 1, 2, …, 9 (in this order) such that the result is always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.

a = {
1, "", 2, "", 3, "", 4, "", 5, "",
6, "", 7, "", 8, "", 9
}
function inc(a)
for i=2,#a,2 do
if a[i] == "" then a[i] = "+" return true end
if a[i] == "+" then a[i] = "-" return true end
if a[i] == "-" then a[i] = "" end
end
return false
end
function eval(a)
local s = table.concat(a)
if loadstring("return " .. s)() == 100 then print(s) end
end
repeat eval(a) until inc(a) == false

Output looks like:

123-45-67+89
12-3-4+5-6+7+89
12+3+4+5-6-7+89
123+4-5+67-89
1+2+3-4+5+6+78+9
12+3-4+5+67+8+9
1+23-4+56+7+8+9
1+2+34-5+67-8+9
1+23-4+5+6+78-9
123+45-67+8-9
123-4-5-6-7+8-9