Sum to 100

Sum to 100 is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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

An example of a sum that can't be expressed (within the rules of this task) is:   5074
which, of course, is not the lowest 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=123456789 /*LOW specified as zero with leading 0s*/ 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 sum not equal to answer? Then 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.