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.

Arrays

Arrays are great.

In a lot of languages they form the only temporary repository of related information you have access to and so are used and abused regularly.

Perhaps because Progress has such quick and easy access to the database and temp-tables its array handling has been somewhat neglected. Oh and they start at 1, which to many programmers is a unforgivably bad form.

So what can you and cant you do?

You can define fixed length and indeterminate length arrays.

Fixed:

DEF VAR MyArray AS INTEGER EXTENT 10.

Indeterminate:

DEF VAR MyArray AS INTEGER EXTENT.

Slightly weird syntax but there it is, once we have our indeterminate length array we can tell it how long it is.

EXTENT(MyArray) = 4.

But don't be fooled, our array is now permanently stuck at 4, so:

EXTENT(MyArray) = 4.
EXTENT(MyArray) = 5.

Will get you an error, it is in no way a dynamic or variable length array.

Initialising.

Like most languages you can define that values as you start:

DEF VAR MyArray AS INTEGER EXTENT 5 INIT [1,2,3,4,5].

And you can clear out the whole array with a single line of code:

DEF VAR MyArray AS INT EXTENT 5 INIT [1,2,3,4,5].

DISPLAY myArray.

MyArray = 0.

DISPLAY myArray.

Comparisons.

Consider the following code snipit.

DEF VAR MyArray AS INTEGER EXTENT 5 INIT [1,2,3,4,5].
DEF VAR YourArray AS INTEGER EXTENT 5 INIT [1,2,4,4,5].

MESSAGE MyArray = YourArray.

You might hope it would say "No" as the two arrays are different, no such luck...
---------------------------
Error
---------------------------
** Only individual array elements allowed in expressions. (361)
**  Could not understand line 5. (196)
---------------------------
OK  
---------------------------

To be fair Javascript would give a similar if rather less helpful, result.

<script>
var cars = [1,2,3,4,5];
var cars2 = [1,2,3,4,5];

alert (cars == cars2);

</script>

You get a "False" alert box, but its really asking if they are the same object, which of course they are not.

C, now that's were it's at, just two lumps of memory that are either the same or they aren't (ok, the same for the length of MyArray):

int MyArray[] = {1,2,3,4,5};
int YourArray[] = {1,2,4,4,5};

if(memcmp(MyArray,YourArray,sizeof(MyArray)) == 0)

I miss those days. Given how the Javascript result could lead you up the garden path its perhaps best that Progress at least gives a syntax error.

So you're left with the step by step:

DEF VAR MyArray AS INTEGER EXTENT 5 INIT [1,2,3,4,5].
DEF VAR YourArray AS INTEGER EXTENT 5 INIT [1,2,4,4,5].
DEF VAR vi AS INTEGER NO-UNDO.

DO vi = 1 TO EXTENT(MyArray):

    IF MyArray[vi] <> YourArray[vi] THEN DO:
        Message "Different".
        LEAVE.
    END.

END.

Sorting.

So here Progress wins, with most languages you're writing sorts like mama used to make, bubble sorts from high school computer class, with Progress we make use of the simple and close at hand database (or in this case TEMP-TABLE) connection.

Get your whole array, bung it in an indexed temp temp-table and let progress take the strain:

DEF TEMP-TABLE ttMyTable
    FIELD iValue AS INTEGER.
   
DEF VAR MyArray AS INTEGER EXTENT 13 INIT [1,2,3,4,5,2,4,65,654,7,43,3,12].
DEF VAR vi AS INTEGER NO-UNDO.

DO vi = 1 TO EXTENT(MyArray):

    CREATE ttMyTable.
    ASSIGN
        ttMyTable.iValue = MyArray[vi].
    RELEASE ttMyTable.

END.

FOR EACH ttMyTable BY iValue:
    DISPLAY ttMyTable.iValue.
END.

Sorted.

2 and 3 dimensional arrays.

Er... no. You'd have to work around this with a a temp-table, so to express:

/*

1,2,3

4,5,6

7,8,9

*/

/* Definition */

DEFINE VARIABLE viX AS INTEGER     NO-UNDO.

DEFINE VARIABLE viY AS INTEGER     NO-UNDO.

DEF TEMP-TABLE ttMy2dArray

    FIELD ix AS INTEGER

    FIELD iy AS INTEGER

    FIELD ivalue AS INTEGER.

/* Populate */

DO viY = 1 TO 3:

    DO viX = 1 TO 3:

        CREATE ttMy2dArray.

        ASSIGN

            ttMy2dArray.iX = viX

            ttMy2dArray.iY = viY

            ttMy2dArray.iValue = INT(SUBSTRING("123456789",vix + ((viy - 1 )* 3), 1)).

        RELEASE ttMy2dArray.

    END.

END.

/* Whats the center number, 2 dwon 2 accross*/

FIND FIRST ttMy2dArray WHERE ttMy2dArray.iX = 2 

                         AND ttMy2dArray.iY = 2 NO-ERROR.

IF AVAIL ttMy2dArray THEN

    DISPLAY ttMy2dArray.iValue.

Ta, da, note; we'll stick with Progress's idea of starting at array position 1.

Arrays of objects.

That a TEMP-TABLE record, so no need.

Conclusion

So that's the Progress take on arrays, a lack of some of the pre written functions that a PHP programmer would take for granted, but nothing a little lateral thinking a does of TEMP-TABLES cant sort out.

Welcome to the Bledge

Progress isn't the language it was when I started out in 4GL land back in 1996. Progress 6 running on a green screen CTOS terminal was in use as a character based bug logging and customer details system as I started in a support role.

As Unisys killed off CTOS we moved to Windows, paralleling Progress concentrating their GUI development with the dominant power from Redmond.

I progressed (boom boom!) to developer and as the years passed developed with progress 7,8,9,10 and now open edge 11.

There have been some great and powerful improvements and additions over time such as AppServer. Some pointless development dead ends like smart-objects. Some things still not included in the language that should have been in since day one like strict prototyping, but mainly there is more than enough to write about and that's where this blog comes in.

As well as being a cathartic release from some of the frustration of being a Progress (sorry... Open Edge) developer there will be some hopefully useful information for fellow development old and new.

Use and abuse the comments and welcome on board.