Sum to 100
- 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 first positive sum that can't be expressed
* (where infinity would be a relatively small 123,456,789)
REXX
<lang rexx>/*REXX pgm solves a puzzle: using the string 123456789, insert - or + to sum to 100*/ parse arg LO HI . /*obtain optional arguments from the CL*/ if LO== | LO=="," then LO=100 /*Not specified? Then use the default.*/ if HI== | HI=="," then HI=LO /* " " " " " " */ if LO==00 then HI=999999 /* " " " " " " */ ops= '+-'; sol="solution"; L=length(ops) + 1 /*define operators (and their length). */ @.=; do i=1 to L-1; @.i=substr(ops,i,1) /* " some handy-dandy REXX literals*/
end /*i*/ /* " individual operators for speed*/
mx=0; mn=999999; mxL=; mnL= /*initialize some minimums and maximums*/ tell= (LO==HI); do j=LO to HI until LO==00 & mn==0 /*solve with a range of sums*/
z=solve(j); y=z; if y==0 then y='no' /*find # solutionson for J.*/
if tell then say y sol ||s(y) 'found.' /*Not a range? Show number.*/
if z> mx then mxL= /*see if this is a new max. */
if z>=mx then do; mxL=mxL j; mx=z; end /*remember this new maximum.*/
if z< mn then mnL= /*see if this is a new min. */
if z<=mn then do; mnL=mnL j; mn=z; end /*remember this new minimum.*/
end /*j*/
if tell then exit /*should we show max and min*/ @@= 'number of solutions: ' _=words(mxL); say 'sum's(_) "of" mxL ' 's(_,"have",'has') 'the maximum' @@ mx _=words(mnL); say 'sum's(_) "of" mnL ' 's(_,"have",'has') 'the minimum' @@ mn exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ s: if arg(1)==1 then return arg(3); return word(arg(2) "s",1) /*simple pluralizer*/ /*──────────────────────────────────────────────────────────────────────────────────────*/ solve: parse arg answer; #=0 /*obtain the answer (sum) to the puzzle*/
do a=L-1 to L; aa= @.a'1' /*choose one of - or nothing. */
do b=1 for L; bb=aa || @.b'2' /* " " " - +, or abutment.*/
do c=1 for L; cc=bb || @.c'3' /* " " " " " " " */
do d=1 for L; dd=cc || @.d'4' /* " " " " " " " */
do e=1 for L; ee=dd || @.e'5' /* " " " " " " " */
do f=1 for L; ff=ee || @.f'6' /* " " " " " " " */
do g=1 for L; gg=ff || @.g'7' /* " " " " " " " */
do h=1 for L; hh=gg || @.h'8' /* " " " " " " " */
do i=1 for L; ii=hh || @.i'9' /* " " " " " " " */
interpret '$=' ii /*calculate the sum of modified string.*/
if $\==answer then iterate /*Is the sum not equal to answer? Skip*/
#=#+1; if tell then say 'solution: ' $ " ◄───► " ii
end /*i*/
end /*h*/
end /*g*/
end /*f*/
end /*e*/
end /*d*/
end /*c*/
end /*b*/
end /*a*/ ; return # /*return the number of solutions found.*/</lang>
output when the default input is used:
solution: 100 ◄───► -1+2-3+4+5+6+78+9 solution: 100 ◄───► 1+2+3-4+5+6+78+9 solution: 100 ◄───► 1+2+34-5+67-8+9 solution: 100 ◄───► 1+23-4+5+6+78-9 solution: 100 ◄───► 1+23-4+56+7+8+9 solution: 100 ◄───► 12+3+4+5-6-7+89 solution: 100 ◄───► 12+3-4+5+67+8+9 solution: 100 ◄───► 12-3-4+5-6+7+89 solution: 100 ◄───► 123+4-5+67-89 solution: 100 ◄───► 123+45-67+8-9 solution: 100 ◄───► 123-4-5-6-7+8-9 solution: 100 ◄───► 123-45-67+89 12 solutions found.
output when the following input is used: 00
sum of 9 has the maximum number of solutions: 46 sum of 211 has the minimum number of solutions: 0
For those that are interested, the 46 solutions (for the sum of 9) are:
solution: 9 ◄───► -1+2+3+4+5+6+7-8-9 solution: 9 ◄───► -1+2+3-4+5-6-7+8+9 solution: 9 ◄───► -1+2+3-4-5+6+7-8+9 solution: 9 ◄───► -1+2+3-45+67-8-9 solution: 9 ◄───► -1+2+34+56+7-89 solution: 9 ◄───► -1+2-3+4+5-6+7-8+9 solution: 9 ◄───► -1+2-3+4-5+6+7+8-9 solution: 9 ◄───► -1+23+4+5+67-89 solution: 9 ◄───► -1+23+4-5-6-7-8+9 solution: 9 ◄───► -1+23-4+5-6-7+8-9 solution: 9 ◄───► -1+23-4-5+6+7-8-9 solution: 9 ◄───► -1-2+3+4+5+6-7-8+9 solution: 9 ◄───► -1-2+3+4+5-6+7+8-9 solution: 9 ◄───► -1-2+3-4-5-6+7+8+9 solution: 9 ◄───► -1-2+3-4-56+78-9 solution: 9 ◄───► -1-2-3+4-5+6-7+8+9 solution: 9 ◄───► -1-2-3+45-6-7-8-9 solution: 9 ◄───► -1-2-3-4+5+6+7-8+9 solution: 9 ◄───► -1-2-34+56+7-8-9 solution: 9 ◄───► -1-23+45-6-7-8+9 solution: 9 ◄───► -12+3-45-6+78-9 solution: 9 ◄───► -12+34+5+6-7-8-9 solution: 9 ◄───► -12+34+56-78+9 solution: 9 ◄───► -12-34+5+67-8-9 solution: 9 ◄───► 1+2+3+4-5-6-7+8+9 solution: 9 ◄───► 1+2+3-4+5-6+7-8+9 solution: 9 ◄───► 1+2+3-4-5+6+7+8-9 solution: 9 ◄───► 1+2-3+4+5+6-7-8+9 solution: 9 ◄───► 1+2-3+4+5-6+7+8-9 solution: 9 ◄───► 1+2-3-4-5-6+7+8+9 solution: 9 ◄───► 1+2-3-4-56+78-9 solution: 9 ◄───► 1+2-34-56+7+89 solution: 9 ◄───► 1+23+4-5-6-7+8-9 solution: 9 ◄───► 1+23-4+5-6+7-8-9 solution: 9 ◄───► 1+23-45+6+7+8+9 solution: 9 ◄───► 1-2+3+4+5+6-7+8-9 solution: 9 ◄───► 1-2+3-4-5+6-7+8+9 solution: 9 ◄───► 1-2-3+4+5-6-7+8+9 solution: 9 ◄───► 1-2-3+4-5+6+7-8+9 solution: 9 ◄───► 1-2-3-4+5+6+7+8-9 solution: 9 ◄───► 1-2-3-4-5-67+89 solution: 9 ◄───► 1-23+4+5-67+89 solution: 9 ◄───► 1-23+45-6-7+8-9 solution: 9 ◄───► 1-23-4+5+6+7+8+9 solution: 9 ◄───► 1-23-45-6-7+89 solution: 9 ◄───► 12-34-56+78+9 46 solutions found.