Brute Force

Brute Force

http://www.theguardian.com/science/alexs-adventures-in-numberland/2015/may/20/can-you-do-the-maths-puzzle-for-vietnamese-eight-year-olds-that-has-stumped-parents-and-teachers

The above was doing the rounds a few weeks back, so I thought I'd have a crack at it. I'm no mathematician as my colleagues will attest, so rather than any genius solution here's a brute force solution in Progress.

Throw random numbers at it until the solution comes out:

/*
Brute force problem solver:

*/

DEFINE VARIABLE iX AS INTEGER     NO-UNDO.
DEFINE VARIABLE iY AS INTEGER     NO-UNDO.
DEFINE VARIABLE iZ AS INTEGER     NO-UNDO.
DEFINE VARIABLE iA AS INTEGER     NO-UNDO EXTENT 9.
DEFINE VARIABLE et AS INTEGER     NO-UNDO.
DEFINE VARIABLE vMin AS INTEGER     NO-UNDO INIT 1.
DEFINE VARIABLE vMax AS INTEGER     NO-UNDO INIT 9.
DEFINE VARIABLE vfValid AS LOGICAL     NO-UNDO.

DEF STREAM io.

DEF TEMP-TABLE ttResult
    FIELD iGuess AS INT
    FIELD dResult AS DECIMAL
    FIELD cResult AS CHAR
    FIELD fWin AS LOGICAL
    INDEX i1 dResult
    INDEX i2 cResult.

et = ETIME.

DO iX = 1 TO 100000:    

    DO iY = 1 TO 9: /* Reset to 0 */

        iA[iY] = 0.

    END.
    
    DO iY = 1 TO 9:
       
        REPEAT:

            vfValid = TRUE.

            iA[iY] = RANDOM(vMin,vMax).

            DO iZ = 1 TO 9:

                IF iZ = iY THEN NEXT.

                IF iA[iY] = iA[iZ] THEN DO:
                    vfValid = FALSE.
                    LEAVE.
                END.                    

            END.

            IF vfValid THEN LEAVE.

        END.
        
    END.

    IF CAN-FIND(FIRST ttResult WHERE ttResult.cResult = STRING(iA[1]) + " + 13 x " + 
                            STRING(iA[2]) + " / " + 
                            STRING(iA[3]) + " + " + 
                            STRING(iA[4]) + " + 12 x " + 
                            STRING(iA[5]) + " - " + 
                            STRING(iA[6]) + " - 11 + " + 
                            STRING(iA[7]) + " x " + 
                            STRING(iA[8]) + " / " + 
                            STRING(iA[9]) + " - 10 = 66" ) THEN NEXT.

    CREATE ttResult.

    ASSIGN
        ttResult.iGuess =iX
        ttResult.cResult =  STRING(iA[1]) + " + 13 x " + 
                            STRING(iA[2]) + " / " + 
                            STRING(iA[3]) + " + " + 
                            STRING(iA[4]) + " + 12 x " + 
                            STRING(iA[5]) + " - " + 
                            STRING(iA[6]) + " - 11 + " + 
                            STRING(iA[7]) + " x " + 
                            STRING(iA[8]) + " / " + 
                            STRING(iA[9]) + " - 10 = 66"
        ttResult.dResult =  iA[1] + 13 * iA[2] / iA[3] + iA[4] + 12 * iA[5] - iA[6] - 11 + iA[7] * iA[8] / iA[9] - 10.

    IF ( iA[1] + 13 * iA[2] / iA[3] + iA[4] + 12 * iA[5] - iA[6] - 11 + iA[7] * iA[8] / iA[9] - 10 ) = 66 THEN ttResult.fWin = TRUE.

    /* IF ttResult.fWin THEN LEAVE. <--- Uncomment to exit after finding first correct result */

    RELEASE ttResult.
        
END.

DISPLAY ETIME - et. /* How long did it take? */

OUTPUT STREAM io TO VALUE("c:\rubbish\maths.txt").

FOR EACH ttResult WHERE ttResult.fWin: /* Spit it out to a text file */

    PUT STREAM io UNFORMATTED "Guess #" ttResult.iGuess ") " ttResult.cResult "~t" ttResult.dResult CHR(10).

END.


OUTPUT STREAM io CLOSE.

/* Results

1 + 13 x 2 / 6 + 4 + 12 x 7 - 8 - 11 + 5 x 3 / 9 - 10 = 66 66
1 + 13 x 4 / 8 + 2 + 12 x 7 - 9 - 11 +3 x 5 / 6 - 10 = 66 66
1 + 13 x 5 / 2 + 3 + 12 x 4 - 8 - 11 + 9 x 7 / 6 - 10 = 66 66
1 + 13 x 8 / 3 + 7 + 12 x 4 - 5 - 11 + 6 x 2 / 9 - 10 = 66 66
2 + 13 x 1 / 4 + 3 + 12 x 7 - 9 - 11 + 6 x 5 / 8 - 10 = 66 66
3 + 13 x 2 / 4 + 8 + 12 x 5 - 1 - 11 + 7 x 9 / 6 - 10 = 66 66
3 + 13 x 2 / 4 + 8 + 12 x 5 - 1 - 11 + 9 x 7 / 6 - 10 = 66 66
3 + 13 x 2 / 8 + 6 + 12 x 5 - 1 - 11 + 7 x 9 / 4 - 10 = 66 66
3 + 13 x 2 / 8 + 6 + 12 x 5 - 1 - 11 + 9 x 7 / 4 - 10 = 66 66
3 + 13 x 9 / 2 + 8 + 12 x 1 - 5 - 11 + 6 x 7 / 4 - 10 = 66 66
4 + 13 x 3 / 9 + 1 + 12 x 7 - 8 - 11 + 2 x 5 / 6 - 10 = 66 66
4 + 13 x 3 / 9 + 1 + 12 x 7 - 8 - 11 + 5 x 2 / 6 - 10 = 66 66
5 + 13 x 2 / 1 + 3 + 12 x 4 - 7 - 11 + 9 x 8 / 6 - 10 = 66 66
5 + 13 x 3 / 1 + 7 + 12 x 2 - 6 - 11 + 8 x 9 / 4 - 10 = 66 66
6 + 13 x 9 / 3 + 5 + 12 x 2 - 1 - 11 + 8 x 7 / 4 - 10 = 66 66
7 + 13 x 2 / 8 + 9 + 12 x 6 - 5 - 11 + 1 x 3 / 4 - 10 = 66 66
7 + 13 x 3 / 4 + 1 + 12 x 6 - 5 - 11 + 2 x 9 / 8 - 10 = 66 66
7 + 13 x 3 / 4 + 1 + 12 x 6 - 5 - 11 + 9 x 2 / 8 - 10 = 66 66
7 + 13 x 9 / 6 + 1 + 12 x 5 - 2 - 11 + 4 x 3 / 8 - 10 = 66 66
8 + 13 x 6 / 9 + 2 + 12 x 5 - 1 - 11 + 7 x 4 / 3 - 10 = 66 66
8 + 13 x 7 / 2 + 5 + 12 x 3 - 9 - 11 + 6 x 1 / 4 - 10 = 66 66
8 + 13 x 9 / 2 + 3 + 12 x 1 - 5 - 11 + 6 x 7 / 4 - 10 = 66 66
9 + 13 x 1 / 2 + 5 + 12 x 6 - 7 - 11 + 3 x 4 / 8 - 10 = 66 66
9 + 13 x 1 / 4 + 7 + 12 x 6 - 5 - 11 + 2 x 3 / 8 - 10 = 66 66
9 + 13 x 1 / 4 + 7 + 12 x 6 - 5 - 11 + 3 x 2 / 8 - 10 = 66 66
9 + 13 x 2 / 8 + 7 + 12 x 6 - 5 - 11 + 1 x 3 / 4 - 10 = 66 66
9 + 13 x 2 / 8 + 7 + 12 x 6 - 5 - 11 + 3 x 1 / 4 - 10 = 66 66
9 + 13 x 4 / 1 + 5 + 12 x 2 - 7 - 11 + 3 x 8 / 6 - 10 = 66 66
9 + 13 x 4 / 8 + 5 + 12 x 6 - 7 - 11 + 3 x 1 / 2 - 10 = 66 66
9 + 13 x 5 / 3 + 1 + 12 x 4 - 2 - 11 + 8 x 7 / 6 - 10 = 66 66
9 + 13 x 6 / 4 + 3 + 12 x 5 - 8 - 11 + 7 x 1 / 2 - 10 = 66 66
9 + 13 x 8 / 6 + 2 + 12 x 4 - 1 - 11 + 5 x 7 / 3 - 10 = 66 66
9 + 13 x 8 / 6 + 2 + 12 x 4 - 1 - 11 + 7 x 5 / 3 - 10 = 66 66

*/

100,000 attempts came up with 34 different solutions.

But its slow... 58 seconds for 100,000 iterations. So optimizations, what can we do to make it more efficient?

Well the first thing that's apparent is that as the random numbers are dished out we ask for more and more that we have already have.  There's no point in the random command starting or finishing with numbers we have already issued. So lets improve that (Main loop, changes in red):

    vMin = 1.
    vMax = 9.    

    DO iY = 1 TO 9:
       
        REPEAT:

            vfValid = TRUE.

            IF vMin = vMax THEN 
                iA[iY] = vMin.
            ELSE
                iA[iY] = RANDOM(vMin,vMax).

            DO iZ = 1 TO 9:

                IF iZ = iY THEN NEXT.

                IF iA[iY] = iA[iZ] THEN DO:
                    vfValid = FALSE.
                    LEAVE.
                END.                    

            END.

            IF vfValid THEN LEAVE.

        END.

        IF iA[iY] = vMin THEN vMin = vMin + 1. 
        IF iA[iY] = vMax THEN vMax = vMax - 1.        
        

    END.

Now as the lowest random number climbs as its used and the highest descends, meaning less (not none) wasted RANDOM calls. And the result? 50 Seconds.

> 10% Gain, good stuff. What next?  Well, is randomly throwing numbers at it sensible? Probably not, there are 9! (9 Factorial) or 362,880 possible permutations. If the name of the game is to find all of the different results then feeding in all those permutations is the way to go, if we just need one answer then, with random numbers its just fate.

More speed, when we reset our guess back to 0, we are unnecessary doing it element by element, as discussed in the array article, you can clear a whole array in one hit so:

    DO iY = 1 TO 9: /* Reset to 0 */

        iA[iY] = 0.

    END.

becomes:

    iA = 0.

Performance gain? Sod all, either we have an insight into what the compiler does when we issue this statement or there are not enough iterations to gain anything.

Onwards, ah, here I've done a silly:

        ttResult.dResult =  iA[1] + 13 * iA[2] / iA[3] + iA[4] + 12 * iA[5] - iA[6] - 11 + iA[7] * iA[8] / iA[9] - 10.

    IF ( iA[1] + 13 * iA[2] / iA[3] + iA[4] + 12 * iA[5] - iA[6] - 11 + iA[7] * iA[8] / iA[9] - 10 ) = 66 THEN ttResult.fWin = TRUE.

Why put the maths in a variable and then do it all over again in order to check it. Check the dResult!

IF ttResult.dResult = 66 THEN ttResult.fWin = TRUE.

Performance gain? Sod all, again. Makes you feel better as it's tidier, but gains very little, again more iterations may prove it to be useful.

Feel free to comment with any optimisations you can find.