Facebook Hackers Cup eliminations

Last weekend I was participating in the elimination part of Facebook Hacker Cup. There were three problems to solve and it was obligatory to finish at least one. Since it was last weekend before Mozilla GameOn 2010 deadline, I had no time for solving academical, non-real life, algorithmic problems I was always poor in. So I just took a look to the first one [mirror]. It looked quite easy, and in couple of minutes I had kind of prototype algorithm implemented in pure Javascript. Main idea of the problem was that the biggest number which square could be part of the input, cannot be bigger than square root of the input divided by two. So I simply iterate from 1 to that max, and in each iteration I checked square root of input number reduced by square of 'i'. If it was integer, we have sum of two squares. If float, we haven't. Piece of cake:). My Javascript implemetation in Rhino (as I described before):

var check = function(input) {
    var result = 0,
        max = Math.sqrt(input/2);

    if(Math.sqrt(input)%1==0) {
        result++;
    }

    for(i=1;i <= max;i++) {
        if(Math.sqrt((input-Math.pow(i, 2)))%1==0) {
            result++;
        }
    }
    return result;
}

var MainFunction = function(args) {
    var a = readFile(args).split("\n");

    for (var i=1, j=a.length;i < j ;i++) {
        print(check(a[i]));
    }
}(arguments);

JavaScript from command line - standard input & output

As you could already know from Mr. C's lectures from YUI Theater or FrontTrends - standard I/O is the worst thing programming languages could ever implement. Fortunately - Javascript has no input at all. And in most cases it doesn't need any - it was designed as script language for web pages. But nowadays we use Javascript in any other aspects of our programming life - we can build for desktops using XUL, server-side tools like node.js (for example with announced last week JSPP) or any other Server-side Javascript implemenation provide JS backend for the web, native mobile apps could be created using frameworks like Phonegap. So what about executing JS scripts from command line? And why do we need it?
The reason I've refreshed my experiences with JS scripts executing was Hacker Cup organized by Facebook - there are no language restrictions in there, your scripts just has to know how to analyze given input and write the answers on the standard output. It is quite unpopular way of using & writing Javascript, so I will show few tips of command line in here.

Engines
There is such a JavaScript engine called Rhino. It is completely written in Java, open source, and very easy to use. It is managed by Mozilla, so you can find a lot of docs and tutorials on Mozilla's page.
Rhino has few additional functions eg for working with files (readFile()) or serializing objects (serialize()), which makes it useful in solving algorithmic problems in competitions like FBHC. Full list of all shell function can be found on Mozilla's page.
Each time you run Javascript scripts from command line, all the arguments you provide will be stored in global variable called 'arguments'. Enriched with this knowledge we can begin with some examples. This is my implementation of binarySearch algorithm:

Array.prototype.binSearch = function(element) {
    var element = parseInt(element, 10), 
        left = 0,  
        right = this.length-1,
        middle = ~~((left+right)/2),
        lastMiddle;

    while (parseInt(this[middle], 10) !== element) {
    
        if (lastMiddle === middle) {
            return null; //nothing found, break
        }
        
        if (parseInt(this[middle], 10) < element)
            left = middle++;
        else 
            right = middle--;
        
        lastMiddle = middle;
        middle = Math.round((left+right)/2); 
    }        
    return middle; //index of found element 
}


var MainFunction = function(args) {

    var a = readFile(args).split("\n"),
        arrayElement = a[0].split(" "),
        result;
    
   
    print("Array: "+arrayElement);
    
    for (var i=1, j=a.length;i < j;i++) {
        result = arrayElement.binSearch(a[i]);
        if (result) 
            print("Element "+parseInt(a[i], 10)+" in on position nr "+result);
        else 
            print("Element "+parseInt(a[i], 10)+" cannot be found in the array");
    }

}(arguments)

As an input it takes filename with the elements of an array in first row and elements to find in that array in next rows, like this:

4 10 12 19 25 34 41 50 52 61 66 68 76 81 82 85 94 97 105 112 115 124 128 138 139 230 321 432 456 540 
61
82
94
2
10
4
24
432

Assuming that script file is called binSearch.js, data.txt is the file with input data, and both are in the same directory as Rhino, to run the script simply type

java -jar js.jar binSearch.js data.txt

Ideone You can simply achieve the same effect using online tools\, without installing anything on your computer. Ideone, online IDE & debugging tool allows you to run your scripts using Rhino or SpiderMonkey, another Mozilla's JS engine, this one written in C. You can edit your scripts in realtime and provide different inputs on every run. Good luck in FBHC!

iPad etc.

Today I had my first touch with most hated mobile device ever - Apple iPad. I won internal contest organized by my employer, GG Network. It was all about creating application using new API of GG social site. If someone is interested - public edition of the competition end on 31 of December and you can win 30.000PLN (about 10000$). In week, maybe two I will write something more about the API and publishing apps on GG.pl (it has more than 10 millions of users and just about 50 apps so far - best way for promoting your apps).

There were thousands of iPad's reviews all over the web, so I want to write one single sentence from gamedeveloper's point of view. Porting one of my Javascript game to run on the device took me about 7 minutes - I add simple code for screen size detection, now it is possible to run 'Zombie Eliminator' in any browser, without resolution issues. It is the biggest advantage of Javascript programming - it will run on different platforms out of the box. When I will finish my Game On entry I will try to write something more about iPad gamedev.

Oh, and my new game is available in SamsungApps since yesterday - tetris-like logic puzzle with jewels - try it here.

Using css3 transformations for sprite animation

Inspired by Kamil Trebunia's speech on FrontTrends so as "Practical HTML5" presentation by Jeremy Orlow & Malte Ubl on Google Developer Day in Munich two days ago, I decide to test if using transformations provided by CSS3 really improves performance of JavaScript games for mobile devices. Kamil said about fastest page redrawing using translate instead of position absolute & top/left attributes. Google guys presented css3 transformations with hardware acceleration. It looks nice so I made a little performance test.
I create simple 'Frames per seconds' counter and run it with 100 animated sprites, each with 4 frames (actually every sprite has 8 frames, but I used only 4 of them) and random movement. The sprites were penguins drawn by me some time ago, based on Antarctic Adventures for NES (one of my favorite games back in '90). I made three tests on my Samsung bada - one using canvas for rendering everything, second one with 'Div with overflow:hidden' method I described in one of the latest posts, and the third one similar to 2nd, but with css3 translation instead of top/left changes. The result was quite surprising - classical DOM manipulation animation had 11-12fps, Css3 transition method reached 10-13fps, and canvas rendering about 27fps. I know that there is wrong way of thinking somewhere, but I have no idea what exactly goes wrong. Any suggestions? You can find the source on my github account: [michalbe]