Alice, Bob, and Mallory

CoffeeScript is inspired by Ruby and Python but what's most peculiar with it is that it compiles to JavaScript. The generated JavaScript isn't all that bad and it even passes JavaScript lint without warnings.

"Underneath all of those embarrassing braces and semicolons, JavaScript has always had a gorgeous object model at its heart." - Jeremy Ashkenas

About a week ago I stumbled on the very clever Sudoku solver by Peter Norvig. I have nothing (or at least not much) against Python but I pretty soon checked out the Ruby translations of the solver. I then refactored one of the solutions to get a chance to get to know the algorithm better.

Now that I finally installed CoffeeScript the Sudoku solver came to mind. I dived in head first and got in trouble pretty soon. It turns out that Array Comprehensions in CoffeeScript differs some from the List Comprehensions in Python.

1
2
3

def cross(A, B):
       "Cross product of elements in A and elements in B."
       return [a+b for a in A for b in B]

returns an one-dimensional array if you call it with two arrays (or strings).

But in CoffeeScript

cross = (A, B) -> (a+b for a in A for b in B)

returns a two-dimensional array.

The jury is still out on if this is intended or not but either way the array comprehensions in CoffeeScript are still very useful.

For the cross-function I ended up with

1
2
3
4
5
6

cross = (A, B) ->
  results = []
  for a in A
    for b in B
      results.push a + b
  results

1
2

cross = (cols, rows) ->
  [].concat (cols.map (x) -> rows.map (y) -> y+x)...

You can find the CoffeScript Sudoku solver as a Gist. Compile it with
coffee -c sudoku.coffee
and then run it with
node sudoku.js

I don't know how I missed it but as Trevor pointed out below all you have to do is
coffee sudoku.coffee

    1 2 3 4 5 6 7 8 9
  |------+-----+-----|
A | 4 8 3|9 2 1|6 5 7|
B | 9 6 7|3 4 5|8 2 1|
C | 2 5 1|8 7 6|4 9 3|
  |------+-----+-----|
D | 5 4 8|1 3 2|9 7 6|
E | 7 2 9|5 6 4|1 3 8|
F | 1 3 6|7 9 8|2 4 5|
  |------+-----+-----|
G | 3 7 2|6 8 9|5 1 4|
H | 8 1 4|2 5 3|7 6 9|
I | 6 9 5|4 1 7|3 8 2|
  |------+-----+-----|

Here's the generated sudoku.js.

This is the only CoffeeScript I've ever written but I already like it (more than JavaScript). Please correct me if I strayed from the CoffeeScript way.

In browsers that supports the HTML5 canvas it's possible to read the raw image data. I figured that this makes it possible to encrypt images on the client. Why would one ever want to encrypt images client-side? One use case could be to send images to a server that only those who know the password can decrypt (host-proof hosting).

I used Crypto-JS to encrypt with AES and Rabbit.

First I get the CanvasPixelArray from the ImageData object.

1
2
3
4

var ctx = document.getElementById('leif')
                  .getContext('2d');
var imgd = ctx.getImageData(0,0,width,height);
var pixelArray = imgd.data;

1
2
3
4
5
6
7
8
9
10

function canvasArrToString(a) {
  var s="";
  // Removes alpha to save space.
  for (var i=0; i<pix.length; i+=4) {
    s+=(String.fromCharCode(pix[i])
        + String.fromCharCode(pix[i+1])
        + String.fromCharCode(pix[i+2]));
  }
  return s;
}

var encrypted = Crypto.Rabbit.encrypt(imageString, password);

1
2
3
4
5
6
7
8
9
10

function canvasStringToArr(s) {
  var arr=[];
  for (var i=0; i<s.length; i+=3) {
    for (var j=0; j<3; j++) {
      arr.push(s.substring(i+j,i+j+1).charCodeAt());
    }
    arr.push(255); // Hardcodes alpha to 255.
  }
  return arr;
}

1
2
3
4

var arr=canvasStringToArr(
              Crypto.Rabbit.decrypt(encryptedString, password));
imgd.data=arr;
ctx.putImageData(imgd,0,0);

A demo can be found here.

EDIT 2010-10-17

Warning I've noticed that the encrypted strings aren't compatible between browsers. At least not in between Google Chrome and Firefox. I don't know why.

I also tried to add deflate/inflate and that compresses my test image to a third of the raw size and in Google Chrome it also halved the execution time. In Firefox Rabbit got about 50% slower and AES about 50% faster with deflate/inflate.

Here's a demo of this.

EDIT 2010-10-21

Added a preprocessing filter of the raw image data inspired by PNG type 1 sub filter. Presented my idea to Fredrik and he returned a formula. Thanks!
The result wasn't what I had hoped for, a measly 6% smaller. I also tried to save the image as real PNG and that one is 20480 bytes. 20480*1.37=28057 bytes (Base64 overhead) and my homemade format is 38336 bytes. Not a fantastic result but not that horrible either.

Here's a demo of this.

In JavaScript you can add properties to objects dynamically. You can access those properties both by object.foo and object['foo']. The later is commonly used to use JavaScript objects as hash tables (associative arrays).

While implementing a simplistic unique random number generator I happened to use keys(obj). Unfortunately keys(obj) is part of ECMAScript 5. See chapter 15.2.3.14 in ECMA-262. The web browsers of today mostly implements ECMAScript 3.

Here's an implementation of keys(obj) for ECMAScript 3 browsers (tested in Google Chrome, IE8 and Firefox 3.5). If the browser already has a keys function then nothing will be done.

1
2
3
4
5
6
7
8
9

if (typeof keys == "undefined") 
{ 
  var keys = function(ob) 
  {
    props=[];
    for (k in ob) if (ob.hasOwnProperty(k)) props.push(k);
    return props;
  }
}

The simplistic unique random number generator looks like this

1
2
3
4
5
6

function uniqueRndNumbers(min, max, quantity) {
  var ht={}, i=quantity;
  while ( i>0 || keys(ht).length<quantity) 
    ht[Math.floor(Math.random()*(max-min+1))+min]=i--;
  return keys(ht);
}

This function has not undergone any serious testing. Also if the quantity is more than a fraction of (max-min) then another algorithm like the Fisher–Yates shuffle might be a better choice.