forfeit game - ALGOL 60 solution from 1964

by Christian Harms on Mon, 11/15/2010 - 14:51

I found two ALGOL sniplets for the forfeit game contest. My ALGOL 60 programming book (happy birthday for the ALGOL programming language) offer for every problem the question, a problem analysis, a code structure chart, the code solution and the executing time for the ZUSE 23 computer (see a very similar Z22 on wikipedia). I converted the fast solution for the game of forfeit from ALGOL to javascript without optimizations and benchmarked it.

Opera 10.63 vs. Chrome 7/8 vs. Firefox 3.6.12/4b7

I will start with the results from the converted ALGOL solution. The new javascript engine Jägermonkey with the firefox 4b7 is a real competitor for other fast javascript engines! And the ALGOL version is (mostly) better than the clean code version. The absolute numbers are generated on my own mini-pc and used for comparing with the clean code solution.

The 1:1 conversion of the ALGOL code runs on my Intel Atom N270 3.5 million times faster than on the original ZUSE Z23.

get ALGOL working on your box

How can I start ALGOL code on my local ubuntu? And not the more popular ALGOL 68? There is only one working interpreter: the NASE A60 interpreter from Erik Schoenfelder. Extract the archive, run ./configure and start your algol code directly.

More background to the z23 on egge.net:

The 1961 Zuse Z-23 was his eighth model, being a transistorised version of the 1956 valve based Z22. His previous computers had used relays! A typical Z22 had 14 words of 38-bit core RAM, 8192 word (38 KB) magnetic drum, punched card I/O, it ran at just 3 KiloHz!! And - oh wonders - by 1958 there was an ALGOL 58 compiler for it !!!

fastest solution

This solution from H.Lehr was the fastest solution. Its not working for all number ranges and there is no defined break. It needs 6 minuts and 17 seconds for calculating and printing on the original hardware. If you are not familiar with ALGOL 60 some tips:

ENTIER function rounds down a floating number to an integer
all keywords are wrapped by single quotes, variable names not
code blocks start with BEGIN and end with END instead of { and }
A: is a label and you can direct jump to the line with the GOTO keyword.

Simple and fast solution

The usage of multiple for-loops to check each digit of the number with 7, instead of generating a string, is a limited but a creative solution. And the sum of all digits is directly accessable! The next interessting point: The maximal value for the sum of digits for example n=1.000.000 is 54 - we dont need complex checks for this number. In the ALGOL example only X1 to X4 are used for these checks.

Converting ALGOL to javascript

This works fine and I converted it to javascript (without changes), but it doesn't perform like excepted. But this code can be an inspiration to get better performance boost for the solution of the forfeits game contest.

function forfeits(n) {
        var k=6, x1, x2, x3, x4, q, z=-1, s, t, result=[];
        for (var a9=0; a9<10; a9++)
        for (var a8=0; a8<10; a8++)
        for (var a7=0; a7<10; a7++)
        for (var a6=0; a6<10; a6++)
        for (var a5=0; a5<10; a5++)
        for (var a4=0; a4<10; a4++)
        for (var a3=0; a3<10; a3++)
        for (var a2=0; a2<10; a2++)
        for (var a1=0; a1<10; a1++) {
            z++; 
            k++;
            x1 = 7 * entier(k/7);
            k = k - x1;
            q = (a1+a2+a3+a4+a5+a6+a7+a8+a9);
            s = q/7;
            x2 = 7+sign(s-entier(s));
            t = q/10;
            x3 = entier(t);
            x4 = q-10*entier(t);
            if (x1!==7 && x2!==7 && x3!==7 && x4!==7 && 
                a1!==7 && a2!==7 && a3!==7 && a4!==7 && a5!==7 &&
                a6!==7 && a7!==7 && a8!==7 && a9!==7) result.push(z);
 
            if (z === n) return result;
        }
 
        //transfers an expression of real type to one of integer type, and assigns 
        //to it the value which is the largest integer not greater than the value of E
        function entier(e) {
            return Math.floor(e);
        }
        //the sign of the value of E (+1 for E < 0, 0 for E=0, -1 for E < 0).
        function sign(e) {
            return (e<0)?1:(e>0)?-1:0;
        }
    }

Simple test it in your browser:

elegant solution

The second solution printed in the book is from R. Wagner and the calculating/printing time was 7 minuts and 53 seconds.

Elegant solution for the forfeit puzzle in algol 60
This doen' t work with the a60 interpreter and I have no idea what's is wrong. Feel free to get it running in the a60 interpreter or use the exmaple for a javascript version.

Attachment	Size
forfeit_fast.a60.txt	1.01 KB
forfeit_fine.a60.txt	371 bytes
forfeits.js.txt	10.01 KB

Comments

Pingback
GreeFilesolution All solution for site &raquo; forfeit g (not verified) - Tue, 11/16/2010 - 00:43

[...] the original post here: forfeit game – ALGOL 60 solution from 1964 | united-coders.com Tags: algol, fast, fast-javascript, new-javascript, the-clean, the-converted, the-firefox, [...]

Pingback
GreeFilesolution All solution for site &raquo; forfeit g (not verified) - Tue, 11/16/2010 - 00:43

[...] reading here: forfeit game – ALGOL 60 solution from 1964 | united-coders.com Tags: algol, clean, fast, fast-javascript, firefox, from-the-converted, new-javascript, [...]