JavaScript with Xgrid

JavaScript is implemented very efficiently on a variety of platforms, so it looks like an interesting choice for developing jobs to be run under Xgrid.

This page describes how to develop a JavaScript program to search for all the possible 4 x 4 word squares.

Complete listing

Running JavaScript from the Mac Terminal

JavaScript isn't limited to Web browsers. On the Mac there's a command-line version of JavaScript called jsc (JavaScriptCore)[1]. It's located at:

/System/Library/Frameworks/JavaScriptCore.framework/Versions/A/Resources/jsc

You can make it available as a direct command from the Terminal by defining a link to it with the command:

sudo ln /System/Library/Frameworks/JavaScriptCore.framework/Versions/A/Resources/jsc /bin/jsc

You can display help about the command in the usual way:

jsc -h

Arguments can be accessed in the JavaScript by the array arguments[], and print() prints to the Terminal. For example, if you create a text file called test.js containing:

print('Hello ' + arguments[0]);

you can run it from the Terminal like this:

jsc test.js -- World!

The output will be:

Hello World!

Word squares in JavaScript

The following program is a pretty direct translation of the Lisp version. The program first defines an array of four-letter words which starts:

var words4=new Array("abed", "abet", "able", "ably", "abut", "aces" ... );

The function makeWord constructs a four-letter string from specified characters of four other words:

function makeWord4 (w0,c0,w1,c1,w2,c2,w3,c3)
{
    return w0.substr(c0,1) + w1.substr(c1,1) + w2.substr(c2,1) + w3.substr(c3,1);
};

The function lookupPrefix looks up a two-letter prefix in the hash table and returns the list of words starting with that prefix:

function lookupPrefix(w0,c0,w1,c1,table)
{
    return table[ w0.substr(c0,1) + w1.substr(c1,1) ];
};

Finally checkDistinct checks that all the words in an array are distinct:

function checkDistinct (array)
{
    var sorted = array.sort();
    var distinct = true;
    for ( var i=0, len=sorted.length; i<len-1; ++i )
        {
        if ( sorted[i] == sorted[i+1] )
            { 
            distinct = false;
            };
        };
};

Then we define the main function findsquares:

function findsquares (from,to)
{
 
// Initialise hash tables
 
// words['fred'] is true if 'fred' is a valid word
 
var words = new Array();
 
for ( var i=0, len=words4.length; i<len; ++i )
    {
        words[ words4[i] ] = true;
    };
 
// twins['fr'] is an array of words beginning with 'fr'
var twins = new Array();
 
for ( var i=0, len=words4.length; i<len; ++i )
    {
        var word = words4[i];
        var prefix = word.substring(0,2);
        if (twins[ prefix ] == undefined) 
            {
                twins[prefix] = new Array();
            };
        twins[prefix].push(word);
    };
 
for ( var i=from, leni=Math.min(words4.length, to); i<leni; ++i )
    {
    var v0 = words4[i];
    /* print(v0 + ', '); */
 
    for ( var j=0, lenj=words4.length; j<lenj; ++j )
        {
        var v1 = words4[j];
        var l0 = lookupPrefix(v0,0,v1,0,twins);
        var l1 = lookupPrefix(v0,1,v1,1,twins);
        var l2 = lookupPrefix(v0,2,v1,2,twins);
        var l3 = lookupPrefix(v0,3,v1,3,twins);
        // Diagonals
        var ld0 = lookupPrefix(v0,0,v1,1,twins);
        var ld1 = lookupPrefix(v0,3,v1,2,twins);
        if ( l0 != undefined && l1 != undefined && l2 != undefined
            && l3 != undefined && ld0 != undefined && ld1 != undefined)
            {
            for ( var k=0, lenk=l0.length; k<lenk; ++k )
                {
                var h0 = l0[k];
                for ( var l=0, lenl=l1.length; l<lenl; ++l )
                    {
                    var h1 = l1[l];
 
                    // Check first two letters of v2 and v3 are OK - divides time by 3
                    var ll2 = lookupPrefix(h0,2,h1,2,twins);
                    var ll3 = lookupPrefix(h0,3,h1,3,twins);
                    if ( ll2 != undefined && ll3 != undefined )
                        {
                        for ( var m=0, lenm=l2.length; m<lenm; ++m )
                            {
                            var h2 = l2[m];
                            for ( var n=0, lenn=l3.length; n<lenn; ++n )
                                {
                                var h3 = l3[n];
                                var v2 = makeWord4(h0,2,h1,2,h2,2,h3,2);
                                var v3 = makeWord4(h0,3,h1,3,h2,3,h3,3);
                                var d0 = makeWord4(h0,0,h1,1,h2,2,h3,3);
                                var d1 = makeWord4(h3,0,h2,1,h1,2,h0,3);
 
                                // Test we've got a valid square
                                if ( words[v2] != undefined && words[v3] != undefined &&
                                     words[d0] != undefined && words[d1] != undefined )
                                    {
                                    // Check all the words are distinct
                                    var final = new Array();
                                    final.push(v0,v1,v2,v3,h0,h1,h2,h3,d0,d1);
                                    if ( checkDistinct(final) )
                                        {
                                        print('\n\n'+h0+'\n'+h1+'\n'+h2+'\n'+h3+'\n\n');
                                        };
 
                                    };
                                };
                            };
                        };
                    };
                };
            };
        };
    };
};

Finally we call the function with the command-line arguments:

findsquares(arguments[0],arguments[1])

To run the program from the Terminal for the complete list of words give the command:

jsc squares4.js -- 0 2360

  1. ^ Thanks to Stoyan Stefanov at www.phpied.com for this tip.

blog comments powered by Disqus