Most useless skills ever aka how to implement sqrt() in javascript.

Couple of day ago, Dominic Szablewski, author of Impact Engine tweets about interesting job interview:

Seriously, WTF? Why Javascript developer, even working for such a big company as Facebook, needs to know how to re-implement build-in language elements? Knowing everything about everything was bane of elementary education - we have all been trained (at least here, in Eastern Europe), that when we need to know something we shouldn't use 'outside' sources such as books then and Internet now. Why? Personally, I didn't know any developer who didn't sometimes read the documentation, especially if it takes less than 3s if you know what you are looking for.
In case that 'implementing sqrt()' task will ever occurs again, here are two of my JS implementations:) :

//in this way calculators implements square roots:
var ownSqrt = function(number) {
    return Math.exp(Math.log(number)/2);
}

But if it is forbidden to use Javascript Math object constants at all, the best way is to use approximation like this:

var ownSqrt2 = function(number) {
    var x = number;
    while (Math.abs(x*x-number) > 0.001) x = (x*x+number)/(2*x);
    return x;
}

There are a lot of different algorithms on Wiki, and their implementations all over the Web.

Mozilla Game On 2010

During last Thursday it was possible to send your entry to the Mozilla GameOn 2010 Competition. There were more than 160 games submitted, but some of them was disqualified because of using 'non open' technologies like flash or Unity. Finally, there are 124 chosen titles in the gallery. Checking almost every game I found couple of technologies, libraries, plugins, frameworks or engines I've never heard of before, or just forgot about. Some of them are worth describing in here. First of all I totally forgot about HTML5 Boilerplate, an "HTML/CSS/JS template for a fast, robust and future-proof site", used in Snake game [MGO2010]. Another technically interesting entry was Black Obelisk [MGO2010], written completely in haXe, opensource programming language with ability to compile to Javascript, Flash, NekoVM bytecode, PHP, C++ and C# or Java in the near future. Couple of games was written in Java with cross-compiled JavaScript presentation layer using GWT, eg SVG-EDU [MGO2010] or Zulu [MGO2010]. Main reason people used Flash in their games was enabling sound effects (like Sinuous [MGO2010], the winner of 10kApart). But Wizard Wars [MGO2010] used SoundManager2 to achieve same effect. Mad Tanks TD [MGO2010], one of my personal favorites in the competition, uses LESS, which "extends CSS with variables, mixins, operations and nested rules". Looks cool! (both, the game and the compiler:) ). I was impressed with amount of WebGL based games. In Red shooting Hood [MGO2010], made by Tymon Zgaiński from Poland, member of polish gameDev community Warsztat, I found Sylvester, "Vector and Matrix math for JavaScript". Open web implementation of simple and well known Frogger [MGO2010] was compiled to Javascript & canvas using Ristretto Mobile, "a Web-based Compiler for Running Interactive Games and Simulations". My own entry, OpenOdyssey [MGO2010]was made simultaneous with Mibbu framework and is based on it. I'm not satisfied with the final result, but I will develop both after the competition. If I will find some free time during the weekend I will write few words about OO & Mibbu.

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!