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




C ROSSETACODE: SUM TO 100, FORTRAN IV
C FIND SOLUTIONS TO THE "SUM TO ONE HUNDRED" PUZZLE
C =================================================

      PROGRAM SUMTO100
      DATA NEXPRM1/13121/
      WRITE(6,110)
 110  FORMAT(1X/1X,34HSHOW ALL SOLUTIONS THAT SUM TO 100/)
      DO 10 I = 0,NEXPRM1
  10  IF ( IEVAL(I) .EQ. 100 ) CALL PREXPR(I)

      WRITE(6,120)
 120  FORMAT(1X/1X,
     153HSHOW THE SUM THAT HAS THE MAXIMUM NUMBER OF SOLUTIONS/)
      NBEST = -1
      DO 30 I = 0, NEXPRM1
      ITEST = IEVAL(I)
      IF ( ITEST .LT. 0 ) GOTO 30
      NTEST = 0
      DO 20 J = 0, NEXPRM1
  20  IF ( IEVAL(J) .EQ. ITEST ) NTEST = NTEST + 1
      IF ( NTEST .LE. NBEST ) GOTO 30
      IBEST = ITEST
      NBEST = NTEST
  30  CONTINUE
      WRITE(6,121) IBEST, NBEST
 121  FORMAT(1X,I8,5H HAS ,I8,10H SOLUTIONS/)

      WRITE(6,130)
 130  FORMAT(1X/1X,
     155HSHOW THE LOWEST POSITIVE NUMBER THAT CAN'T BE EXPRESSED/)     
      DO 50 I = 0,123456789
      DO 40 J = 0,NEXPRM1
  40  IF ( I .EQ. IEVAL(J) ) GOTO 50
      GOTO 60
  50  CONTINUE
  60  WRITE(6,131) I
 131  FORMAT(1X,I8)

      WRITE(6,140)
 140  FORMAT(1X/1X,
     150HSHOW THE TEN HIGHEST NUMBERS THAT CAN BE EXPRESSED/)
      ILIMIT = 123456789
      DO 90 I = 1,10
      IBEST = 0
      DO 70 J = 0, NEXPRM1
      ITEST = IEVAL(J)
  70  IF( (ITEST .LE. ILIMIT) .AND. (ITEST .GT. IBEST)) IBEST = ITEST
      DO 80 J = 0, NEXPRM1
  80  IF ( IEVAL(J) .EQ. IBEST ) CALL PREXPR(J)
  90  ILIMIT = IBEST - 1
      END

C     EVALUATE THE VALUE OF THE GIVEN ENCODED EXPRESSION
C     --------------------------------------------------
      FUNCTION IEVAL(ICODE)
      IC = ICODE
      IEVAL = 0
      N = 0
      IP = 1
      DO 50 K = 9,1,-1
      N = IP*K + N
      GOTO (10,20,40,30) MOD(IC,3)+1
  10  IEVAL = IEVAL + N
      GOTO 30
  20  IEVAL = IEVAL - N
  30  N = 0
      IP = 1
      GOTO 50
  40  IP = IP * 10
  50  IC = IC / 3
      END

C     PRINT THE ENCODED EXPRESSION IN THE READABLE FORMAT
C     ---------------------------------------------------
      SUBROUTINE PREXPR(ICODE)
      DIMENSION IH(9),IHPMJ(4)
      DATA IHPMJ/1H+,1H-,1H ,1H?/
      IA = 19683
      IB =  6561
      DO 10 K = 1,9
      IH(K) = IHPMJ(MOD(ICODE,IA) / IB+1)
      IA = IB
  10  IB = IB / 3
      IVALUE = IEVAL(ICODE)
      WRITE(6,110) IVALUE, IH
 110  FORMAT(I9,3H = 1A1,1H1,1A1,1H2,1A1,1H3,1A1,1H4,1A1,1H5,1A1,1H6,1A1
     1,1H7,1A1,1H8,1A1,1H9)
      END