I’m excited at the speed of the computer’s moves. Almost all moves take less than a second on my MacBook Air (1.86 GHz Intel Core 2 Duo) – the times when a move requires about 3 seconds is when the computer analyses how to play a joker. Did I already mention this is pure JavaScript running on the browser ?

Its amazing how far JavaScript has come, from being considered a toy language for running some checks on form inputs to being recognized as the powerful (though sometimes quirky) language that powers the Internet today.

New features

After making a small change, I’ve managed to improve the algorithm so that the computer will make a move in under a second every turn. Considering this is all written in pure JavaScript and runs on the browser, I’m starting to wonder whether the algorithm I wrote is the fastest existing scrabble algorithm out there…

The nice thing about having a blog site that no one knows about is that if you’re creating a project and you don’t want potential competitors to know what you are up to, you can freely shout all your new ideas and features to the void… 🙂

The English JavaScript is working nicely so I’ve added a Russian version too, just to see how fast I can add support for other languages. The answer: very fast. It will take less than an hour to add localization and play support for any new language (RTL excluded for now, but will be handled later).

An example below:

Support for Russian

Making progress with the Scrabble clone. Also made changes so it will even work on IE6. There is still the 10% of polishing work that takes 90% of the time, but its fun so I’m not complaining. Its great to see that the number of words in the dictionary have no noticeable effect on the speed of the search.

Current look – still under construction

It took me almost two weeks but I’m nearing completion of an implementation of a fast Scrabble game against the computer written in pure JavaScript. It is both fast (less than 3 seconds per move) and unbeatable.

Here you can see the browser (playing in Red) giving me a humility lesson (playing in Green)…

First Scrabble prototype

I’m in the process of developing a CPU intensive Javascript game. I found the profilers of the different browsers lacking and needed some higher resolution probing of CPU hogger sections in the code. To this effect I created the timers manager below. Basically at any point in the code where you want to start measuring something, say data sorting, you add the line g_timers.begin("my data sort"); and at the end of where the code does its thing you add the line g_timers.pause("my data sort");. You can add as many checkpoints as you see fit for different part of the code – just make sure the string timer identifier passed to the g_timers.begin method is identical to the one passed to the corresponding g_timers.pause method.

Finally, whenever you want to see a report of the accumulated times of all the timers you’ve planted, simply call g_timers.show(). You might probably also want to call g_timers.reset() after that to zero all the accumulated time measurements.

var timers = {};
timers.new = function()
{
    var self = {}
    var t1,total;

    self.begin = function(id) {
        t1[id] = +new Date();
        if (!(id in total))
            total[id] = 0;
    }

    self.pause = function(id) {
        if (id in t1) {
            var t2 = +new Date();
            total[id] += t2-t1[id];
            t1[id] = t2;
        }
    }

    self.show = function() {
        console.log( "Total times:")
        for (id in total)
            console.log( id+": "+total[id]+" ms." );
    }

    self.reset = function() {
        t1    = {};
        total = {};
    }

    self.reset();
    return self;
}

var g_timers = timers.new();

I think IE6 does not like the above method of creating the JavaScript object – if you have problems, just use your own flavor.

I’ve been looking at some JavaScript libraries to be used for data visualization – there are quite a few, from impressive heavy duty data visualization frameworks like D3 (which requires modern browsers that support SVG) through powerful vector rendering libraries like Raphaël that work across almost all browsers and versions using SVG or VML for older versions of IE.

The following is a sample from yet another library (JSDraw2DX) that works on both IE and non-IE browsers. View frame source to see the simplicity with which these libraries can create useful presentations (click and drag the yellow dots).

While comparing the efficiency of my iterative method for generating combinations vs. the recursive method shown at the Rosetta Code site I picked up on a pattern that at first glance is not obvious so I’m still looking into it. It seems that the ratio of the efficiency between the algorithms seems to approach the natural logarithm base (2.71828182…)

Here’s the code – I’ll do some more research before attempting to explain what is going on here

------------------------------------------------------------------------------
-- Lua recursive code for generating combinations from Rosetta Code
function map(f, a, ...)
    c1=c1+1
    if a then return f(a), map(f, ...) end
end

function incr(k)
    return function(a) return k > a and a or a+1 end
end

function combs1(m, n)
    if m * n == 0 then return {{}} end
    local ret, old = {}, combs1(m-1, n-1)
    for i = 1, n do
        for k, v in ipairs(old) do
            ret[#ret+1] = {i, map(incr(i), unpack(v))}
        end
    end
    return ret
end

--for k, v in ipairs(combs(3, 5)) do print(unpack(v)) end

-----------------------------------------------------------------------------
-- My Lua iterative code for generating combinations
-- input a, b (a number of slots, b number of symbols)
function combs2(a,b)
    if a==0 then return end
    local taken = {}
    local slots = {}
    for i=1,a do slots[i]=0 end
    for i=1,b do taken[i]=false end
    local index = 1
    while index > 0 do repeat

        repeat
            c2=c2+1
            slots[index] = slots[index] + 1
        until slots[index] > b or not taken[slots[index]]

        if slots[index] > b then
            slots[index] = 0
            index = index - 1
            if index > 0 then
                taken[slots[index]] = false
            end
            break
        else
            taken[slots[index]] = true
        end

        if index == a then
            -- for i=1,a do
            --     io.write( slots[i] )
            --     io.write( " " )
            -- end
            -- io.write( "n")
            taken[slots[index]] = false
            break
        end

        index = index + 1
    until true end
end

------------------------------------------------------
-- A comparison of the number of operations required
-- by recursive and non-recursive method. Tests show
-- that as the number of slots and symbols rise, the
-- ratio of the efficiency shows an interesting pattern
-- and has to do with the base of the natural logarithm
-------------------------------------------------------

function compare(sl,sy)
    c1=0
    c2=0
    combs1(sl, sy)
    combs2(sl, sy)
    print( "slots:"..sl..", symbols:"..sy.." => iterative/recursive ratio:"..c2/c1)
end

for n=2,11 do
    compare(n,n)
end

For some experiment I’m conducting, I needed to generate all permutations given a number of slots and a number of symbols. I also didn’t want to use built-in libraries like Python or other languages have to generate them, so I picked Lua to avoid being tempted to do so (and because its a cool language).

Now there are Lua implementations to do this, for example on Rosetta Code but the all examples I’ve seen either use recursion or appeared oversized.

I wrote the following non-recursive function in Lua to generate permutations given as input a number of slots and a number of symbols.

-- generate permutations
-- input a, b (a number of slots, b number of symbols)
function permutations(a,b)
    if a==0 then return end
    local taken = {}
    local slots = {}
    for i=1,a do slots[i]=0 end
    for i=1,b do taken[i]=false end
    local index = 1
    while index > 0 do repeat

        repeat
            slots[index] = slots[index] + 1
        until slots[index] > b or not taken[slots[index]]

        if slots[index] > b then
            slots[index] = 0
            index = index - 1
            if index > 0 then
                taken[slots[index]] = false
            end
            break
        else
            taken[slots[index]] = true
        end

        if index == a then
            for i=1,a do
                io.write( slots[i] )
                io.write( " " )
            end
            io.write( "n")
            taken[slots[index]] = false
            break
        end

        index = index + 1
    until true end
end

The following is in generator form:

function perm( sl, sy )
    local permutations = function( a,b )
        if a==0 then return end
        local taken = {}
        local slots = {}
        for i=1,a do slots[i]=0 end
        for i=1,b do taken[i]=false end
        local index = 1
        while index > 0 do repeat
            repeat
                slots[index] = slots[index] + 1
            until slots[index] > b or not taken[slots[index]]
            if slots[index] > b then
                slots[index] = 0
                index = index - 1
                if index > 0 then
                    taken[slots[index]] = false
                end
                break
            else
                taken[slots[index]] = true
            end
            if index == a then
                coroutine.yield(slots)
                taken[slots[index]] = false
                break
            end
            index = index + 1
        until true end
    end

    return coroutine.wrap(function () permutations(sl, sy) end)
end

function test(a,b)
    ci = perm(a,b)
    a = ci()
    while a~=nil do
        for i=1,#a do
            io.write( a[i] )
            io.write( " " )
        end
        io.write( "n")
        a = ci()
    end
end

This method can probably be improved since it goes over all possible combinations (both repeating and non-repeating) and in the process filters out the repeating ones.