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




MODULE SumTo100;
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
 
PROCEDURE Evaluate(code : INTEGER) : INTEGER;
VAR
    value,number,power,k : INTEGER;
BEGIN
    value := 0;
    number := 0;
    power := 1;
 
    FOR k:=9 TO 1 BY -1 DO
        number := power * k + number;
        IF code MOD 3 = 0 THEN
            (* ADD *)
            value := value + number;
            number := 0;
            power := 1
        ELSIF code MOD 3 = 1 THEN
            (* SUB *)
            value := value - number;
            number := 0;
            power := 1
        ELSE
            (* CAT *)
            power := power * 10
        END;
        code := code / 3
    END;
 
    RETURN value
END Evaluate;
 
PROCEDURE Print(code : INTEGER);
VAR
    expr,buf : ARRAY[0..63] OF CHAR;
    a,b,k,p : INTEGER;
BEGIN
    a := 19683;
    b := 6561;
    p := 0;
 
    FOR k:=1 TO 9 DO
        IF (code MOD a) / b = 0 THEN
            IF k > 1 THEN
                expr[p] := '+';
                INC(p)
            END
        ELSIF (code MOD a) / b = 1 THEN
            expr[p] := '-';
            INC(p)
        END;
 
        a := b;
        b := b / 3;
        expr[p] := CHR(k + 30H);
        INC(p)
    END;
    expr[p] := 0C;
 
    FormatString("%9i = %s\n", buf, Evaluate(code), expr);
    WriteString(buf)
END Print;
 
(* Main *)
CONST nexpr = 13122;
VAR
    i,j : INTEGER;
    best,nbest,test,ntest,limit : INTEGER;
    buf : ARRAY[0..63] OF CHAR;
BEGIN
    WriteString("Show all solution that sum to 100");
    WriteLn;
    FOR i:=0 TO nexpr-1 DO
        IF Evaluate(i) = 100 THEN
            Print(i)
        END
    END;
    WriteLn;
 
    WriteString("Show the sum that has the maximum number of solutions");
    WriteLn;
    nbest := -1;
    FOR i:=0 TO nexpr-1 DO
        test := Evaluate(i);
        IF test > 0 THEN
            ntest := 0;
            FOR j:=0 TO nexpr-1 DO
                IF Evaluate(j) = test THEN
                    INC(ntest)
                END;
                IF ntest > nbest THEN
                    best := test;
                    nbest := ntest
                END
            END
        END
    END;
    FormatString("%i has %i solutions\n\n", buf, best, nbest);
    WriteString(buf);
 
    WriteString("Show the lowest positive number that can't be expressed");
    WriteLn;
    FOR i:=0 TO 123456789 DO
        FOR j:=0 TO nexpr-1 DO
            IF i = Evaluate(j) THEN
                BREAK
            END
        END;
        IF i # Evaluate(j) THEN
            BREAK
        END
    END;
    FormatString("%i\n\n", buf, i);
    WriteString(buf);
 
    WriteString("Show the ten highest numbers that can be expressed");
    WriteLn;
    limit := 123456789 + 1;
    FOR i:=1 TO 10 DO
        best := 0;
        FOR j:=0 TO nexpr-1 DO
            test := Evaluate(j);
            IF (test < limit) AND (test > best) THEN
                best := test
            END
        END;
        FOR j:=0 TO nexpr-1 DO
            IF Evaluate(j) = best THEN
                Print(j)
            END
        END;
        limit := best
    END;
 
    ReadChar
END SumTo100.