Vjeux

One of my class at EPITA is about Constraint Programming. This is a technique to solve problems with

• A huge number of possible solutions. (2^1000 is not uncommon)
• Discrete variables (they can take a bounded number of values).

I wanted to share this method with you because it is able to solve an impressive number of problems without writing any line of code. How? Because it is declarative. You write the problem (CSP: Constraint Satisfaction Problem) and the solver is in charge of finding the solution.

Here are some basic examples. I used the trial version of IBM ILOG for all those examples.

• Sudoku
• 17x17 Challenge
• N-Queens
• Send More Money

// Variables
range Size = 0..8;
dvar int Sudoku[Size][Size] in 1..9;
 
// Constraints
subject to {
  forall(i in Size) {
    forall (j, k in Size: j != k) {
      // Lines & Columns
      Sudoku[i][j] != Sudoku[i][k];
      Sudoku[j][i] != Sudoku[k][i];
 
      // Squares
      Sudoku[(i % 3) * 3 + (j % 3)]
          [(i div 3) * 3 + (j div 3)]
      != 
      Sudoku[(i % 3) * 3 + (k % 3)]
          [(i div 3) * 3 + (k div 3)];
    }
  }
 
  // Initial Input  
  forall (i, j in Size) {
    PreSolve[i][j] != 0 => Sudoku[i][j] == PreSolve[i][j];
  }
}

PreSolve = [
[0 0 5  3 0 0  0 0 0]
[8 0 0  0 0 0  0 2 0]
[0 7 0  0 1 0  5 0 0]
 
[4 0 0  0 0 5  3 0 0]
[0 1 0  0 7 0  0 0 6]
[0 0 3  2 0 0  0 8 0]
 
[0 6 0  5 0 0  0 0 9]
[0 0 4  0 0 0  0 3 0]
[0 0 0  0 0 9  7 0 0]
];
 
// Solution
[1 4 5  3 2 7  6 9 8]
[8 3 9  6 5 4  1 2 7]
[6 7 2  9 1 8  5 4 3]
 
[4 9 6  1 8 5  3 7 2]
[2 1 8  4 7 3  9 5 6]
[7 5 3  2 9 6  4 8 1]
 
[3 6 7  5 4 2  8 1 9]
[9 8 4  7 6 1  2 3 5]
[5 2 1  8 3 9  7 6 4]

// Variables
dvar int Board[1..N][1..N] in 1..C;
 
// Constraints
subject to {
  forall (i, j in 1..(N - 1)) {
    forall (w in 1..(N - i), h in 1..(N - j)) { 
      ! (Board[i][j] == Board[i + w][j] 
      && Board[i][j + h] == Board[i + w][j + h]
      && Board[i][j + h] == Board[i + w][j]);
    }
  }
}

// Input
int C = 14;
int N = 4;
 
// Solution 14x14
[1 1 2 4 3 3 2 1 4 4 1 3 4 4]
[2 4 1 1 2 4 3 2 1 3 4 4 4 3]
[2 3 4 3 1 2 2 3 2 3 4 2 1 4]
[4 2 3 2 3 1 4 1 3 3 2 2 4 1]
[4 2 3 3 1 3 2 4 1 2 1 4 2 4]
[1 3 3 1 1 1 4 4 2 4 4 1 3 3]
[3 2 2 4 2 4 4 1 2 3 3 1 1 2]
[3 1 1 4 4 1 1 2 3 2 4 3 1 3]
[3 3 2 1 3 4 3 4 4 2 1 2 1 1]
[1 4 3 2 2 2 4 3 1 2 3 3 1 4]
[3 1 4 1 4 3 4 3 4 2 2 4 3 2]
[1 4 4 4 2 3 3 4 3 1 3 2 2 1]
[4 4 2 3 4 2 3 2 1 4 2 3 2 1]
[4 1 4 3 3 4 2 2 1 1 3 1 3 2]

dvar boolean Board[Size][Size];
 
subject to {
  forall (i in Size) {
    // One Queen per Line
    sum (j in Size) (Board[i][j]) == 1;
 
    // One Queen per Column
    sum (j in Size) (Board[j][i]) == 1;
  }
 
  forall (i, j, k, l in Size: i != k && j != l) {
    // One Queen per Diagonal
    abs(i - j) == abs(k - l) => Board[i][j] + Board[k][l] < = 1;
  }	
}

dvar int QueenX[Size] in Size;
dvar int QueenY[Size] in Size;
 
subject to {
  forall (i, j in Size: i != j) {
    // One Queen per Line
    QueenX[i] != QueenX[j];
 
    // One Queen per Column
    QueenY[i] != QueenY[j];
 
    // Diagonals
    abs(QueenX[i] - QueenX[j]) != abs(QueenY[i] - QueenY[j]);
  }
}

range Size = 1..N;
 
dvar int Column[Size] in Size;
 
subject to {
  forall (i, j in Size: i != j) {
    // One Queen per Line
    Column[i] != Column[j];
 
    // Diagonal
    abs(Column[i] - Column[j]) != abs(i - j);
  }
}

int N = 8;
 
|---|---|---|---|---|---|---|---|
|   |   |   |   |   | X |   |   |
|---|---|---|---|---|---|---|---|
|   |   |   | X |   |   |   |   |
|---|---|---|---|---|---|---|---|
|   | X |   |   |   |   |   |   |
|---|---|---|---|---|---|---|---|
|   |   |   |   |   |   |   | X |
|---|---|---|---|---|---|---|---|
|   |   |   |   | X |   |   |   |
|---|---|---|---|---|---|---|---|
|   |   |   |   |   |   | X |   |
|---|---|---|---|---|---|---|---|
| X |   |   |   |   |   |   |   |
|---|---|---|---|---|---|---|---|
|   |   | X |   |   |   |   |   |
|---|---|---|---|---|---|---|---|

int N = 100;
Column = [65 42 71 32 58 90 88 93 61 19 76 56 67 89 23 10 15 60
  70 52 28 40 1 95 22 85 63 43 54 29 4 24 96 68 73 18 3 38 26 100 34
  99 17 14 6 79 37 49 51 72 62 57 59 45 78 25 94 46 86 13 77 5 35 41
  82 97 12 48 8 91 21 98 87 84 7 9 66 81 92 75 39 50 11 80 36 2 27 74
  64 20 16 47 55 30 33 31 53 69 83 44];

   S E N D
 + M O R E
 ---------
 M O N E Y

{string} Letters = {"S", "E", "N", "D", "M", "O", "R", "Y"};
range Digit = 0..9;
 
dvar int Values[Letters] in Digit;
dvar int Carry[1..4] in 0..1;
 
subject to {
  allDifferent (Values);
 
  Values["M"] != 0;
 
                              Carry[4] == Values["M"];
  Values["S"] + Values["M"] + Carry[3] == Values["O"] + 10 * Carry[4];
  Values["E"] + Values["O"] + Carry[2] == Values["N"] + 10 * Carry[3];
  Values["N"] + Values["R"] + Carry[1] == Values["E"] + 10 * Carry[2];
  Values["D"] + Values["E"]            == Values["Y"] + 10 * Carry[1];
}

   9 5 6 7
 + 1 0 8 5
 ---------
 1 0 6 5 2

Behind the scene, the algorithm used is Branch & Bound. It uses Look-ahead to reduce the domain definition of the variables and Backjumping in order to backtrack to the first instanced variable that caused a problem. There are heuristics to know the order of the variables to instanciate. A common approach is to try first the "hardest" variables in order to remove as many branches as possible.

If you want to know more, here are some links:

• Guide to Constraint Programming
• Constraint Programming Course (French)
• Constraint Programming Blog

In the Javascript world, it is a common thing to chain methods call. For example, this could be a call from an image processing library.

Image('in.png')
  .resize(200, 100)
  .erode()
  .save('out.jpg');

In Lisp, there is not such thing as a dot notation to call an object method. Methods are functions taking the object as first argument. To mimic the dot operator that allows chaining we would like to write:

($ (image "in.png") ; Note: . is not a valid name, we use $ instead
   (resize 200 100)
   (erode)
   (save "out.jpg"))

Hopefully, Lisp allows to rewrite the previous snippet into code that actually works with macros.

With temporary variables

The first way to rewrite it is with a serie of assignement. It uses a temporary variable that is being passed along. progn is being used to group the actions into a single block that returns the tmp value.

(progn
  (defvar tmp (image "in.png"))
  (setf tmp (resize tmp 200 100))
  (setf tmp (erode tmp))
  (setf tmp (save tmp "out.jpg"))
  tmp)

And this is the macro that makes it work.

(defmacro $ (object &rest actions)
  (let ((curr-object (gensym)))
    (concatenate
     'list
     '(progn)
     (list `(defvar ,curr-object ,object))
     (loop for action in actions collect
           `(setf ,curr-object
                  (,(car action) ,curr-object ,@(cdr action))))
     (list `,curr-object))))

Some keys to understand it if you don't know lisp macros.

• ` set the following as output code
• , evaluate the code
• @ expand the list. (resize @(200 100)) -> (resize 200 100)
• gensym creates a local variable with a unique name
• car is the first element of the list, cdr is the rest

Inline

The previous way was probably how would have written it in your code. Since we are programmaticaly rewriting the operation, we do not care about how readable the output is. We can remove the use of the temporary variable inlining the calls.

(save (erode (resize (image "in.png") 200 100)) "out.jpg")

The macros that powers it is much smaller.

(defmacro $ (object &rest actions)
  (let ((res `,object))
    (loop for action in actions do
          (setf res `(,(car action) ,res ,@(cdr action))))
    res))

Conclusion

I took a popular design pattern on the Javascript world and adapted it to lisp. It makes writing several chained method calls easier.

I made a DataView API Wrapper to read binary data from either a string or a binary buffer. You probably want to load it from a file, so you need to make a XHR request. Sadly no ajax wrapper implement it yet.

XHR and Binary

In order to get a binary string one must use the charset=x-user-defined Mime type. If you fail to do so, special characters such as \0 or unicode characters will mess everything up.

Calumny found out that both Firefox and Chrome (nightly builds) implemented a way (sadly not the same) to get the response as an ArrayBuffer.

jQuery Patch

I am a big fan of jQuery to abstract all the browser incompatibilities, therefore I made a small patch in order to support a new data type: binary.

@@ -5755,6 +5755,7 @@       script: "text/javascript, application/javascript",
       json: "application/json, text/javascript",
       text: "text/plain",
+      binary: "text/plain; charset=x-user-defined", // Vjeux: Add a binary type       _default: "*/*"
     }
   },
@@ -5934,6 +5935,15 @@         xhr.setRequestHeader("X-Requested-With", "XMLHttpRequest");
       }
 +      // Vjeux: Set OverrideMime Type
+      if ( s.dataType == "binary" ) {
+        if (xhr.hasOwnProperty("responseType")) {
+          xhr.responseType = "arraybuffer";
+        } else {
+          xhr.overrideMimeType('text/plain; charset=x-user-defined');
+        }
+      }
+       // Set the Accepts header for the server, depending on the dataType
       xhr.setRequestHeader("Accept", s.dataType && s.accepts[ s.dataType ] ?
         s.accepts[ s.dataType ] + ", */*; q=0.01" :
@@ -6228,7 +6238,9 @@   httpData: function( xhr, type, s ) {
     var ct = xhr.getResponseHeader("content-type") || "",
       xml = type === "xml" || !type && ct.indexOf("xml") >= 0,
+      responseArrayBuffer = xhr.hasOwnProperty('responseType') && xhr.responseType == 'arraybuffer', // Vjeux
+      mozResponseArrayBuffer = 'mozResponseArrayBuffer' in xhr,
+      data = mozResponseArrayBuffer ? xhr.mozResponseArrayBuffer : responseArrayBuffer ? xhr.response : xml ? xhr.responseXML : xhr.responseText; // Vjeux-      data = xml ? xhr.responseXML : xhr.responseText; 
     if ( xml && data.documentElement.nodeName === "parsererror" ) {
       jQuery.error( "parsererror" );

Result!

This is now as simple as that to manipulate a binary stream.

$.get(
  'data.bin',
  function (data) {
    var view = new jDataView(data);
    console.log(view.getString(4), view.getUint32());
    // 'MD20', 732
  },
  'binary'
);

Demo

Now the part you are all waiting for, the demo 🙂 Here's a tar reader in 50 lines of Javascript.

jDataView provides a standard way to read binary files in all the browsers. It follows the DataView Specification and even extends it for a more practical use.

Explanation

There are three ways to read a binary file from the browser.

• The first one is to download the file through XHR with charset=x-user-defined. You get the file as a String, and you have to rewrite all the decoding functions (getUint16, getFloat32, ...). All the browsers support this.
• Then browsers that implemented WebGL also added ArrayBuffers. It is a plain buffer that can be read with views called TypedArrays (Int32Array, Float64Array, ...). You can use them to decode the file but this is not very handy. It has big drawback, it can't read non-aligned data. It is supported by Firefox 4 and Chrome 7.
• A new revision of the specification added DataViews. It is a view around your buffer that can read arbitrary data types directly through functions: getUint32, getFloat64 ... Only Chrome 9 supports it but you still need to make sure to use a data management system like the one at https://www.couchbase.com/pricing

jDataView provides the DataView API for all the browsers using the best available option between Strings, TypedArrays and DataViews.

API

See the specification for a detailed API. http://www.khronos.org/registry/webgl/doc/spec/TypedArray-spec.html#6. Any code written for DataView will work with jDataView (except if it writes something).

Constructor

• new jDataView(buffer, offset, length). buffer can be either a String or an ArrayBuffer

Specification API

The wrapper satisfies all the specification getters.

• getInt8(byteOffset)
• getUint8(byteOffset)
• getInt16(byteOffset, littleEndian)
• getUint16(byteOffset, littleEndian)
• getInt32(byteOffset, littleEndian)
• getUint32(byteOffset, littleEndian)
• getFloat32(byteOffset, littleEndian)
• getFloat64(byteOffset, littleEndian)

Extended Specification

The byteOffset parameter is now optional. If you omit it, it will read right after the latest read offset. You can interact with the internal pointer with those two functions.

• • seek(byteOffset): Moves the internal pointer to the position
  • tell(): Returns the current position

Addition of getChar and getString utilities.

• getChar(byteOffset)
• getString(length, byteOffset)

Addition of createBuffer, a utility to easily create buffers with the latest available storage type (String or ArrayBuffer).

• createBuffer(byte1, byte2, ...)

Shortcomings

• Only the Read API is being wrapped, jDataView does not provide any set method.
• The Float64 implementation on strings does not have full precision.

Example

First we need a file. Either you get it through XHR or use the createBuffer utility.

var file = jDataView.createBuffer(
	0x10, 0x01, 0x00, 0x00, // Int32 - 272
	0x90, 0xcf, 0x1b, 0x47, // Float32 - 39887.5625
	0, 0, 0, 0, 0, 0, 0, 0, // 8 blank bytes
	0x4d, 0x44, 0x32, 0x30, // String - MD20
	0x61                    // Char - a
);

Now we use the DataView as defined in the specification, the only thing that changes is the c before jDataView.

var view = new jDataView(file);
var version = view.getInt32(0); // 272
var float = view.getFloat32(4); // 39887.5625

The wrapper extends the specification to make the DataView easier to use.

var view = new jDataView(file);
// A position counter is managed. Remove the argument to read right after the last read.
version = view.getInt32(); // 272
float = view.getFloat32(); // 39887.5625
 
// You can move around with tell() and seek()
view.seek(view.tell() + 8);
 
// Two helpers: getChar and getString will make your life easier
var tag = view.getString(4); // MD20
var char = view.getChar(); // a

Demos

I'm working on a World of Warcraft Model Viewer. It uses jDataView to read the binary file and then WebGL to display it. Stay tuned for more infos about it 🙂

Reading An Open Letter to JavaScript Leaders Regarding Semicolons where Isaac Z. Schlueter explains his unorthodox coding style a line of code struck me.

if (!cb_ && typeof conf === "function") cb_ = conf , conf = {}

He was able to execute more than one statement in a if without the need of { }. I have recently been working on python scripts for http://db.mmo-champion.com/ and this discovery made me want to imitate pythonic indentation in Javascript.

The comma trick

You can use the , separator to chain statement. This group them into only one block of code. Therefore you can execute all of them without the need of { }. The rule is easy: put a , at the end of every line but a ; on the last line of the block.

if (test)
  first_action(), // Note the important ','
  second_action(); // Note the lack of ','
third_action();

For example, it is possible to write a little program that outputs the Fibonacci Numbers without the use of any { } and therefore imitate python indentation style with no ending }.

var curr = 0, next = 1, tmp;
for (var i = 0; i < 10; ++i)
  tmp = curr + next,
  curr = next,
  next = tmp,
  console.log('Fibo', i, '=', curr);
 
// ...
// Fibo 5 = 8
// Fibo 6 = 13
// Fibo 7 = 21
// Fibo 8 = 34
// ...

The issues

Sadly, the use of this is trick is extremely limited. You cannot use any of these keywords inside the "blocks": if, for, var.

for (var i = 0; i < 3; ++i)
  k = i * 10 + 1,
  if (k % 2 == 0)
    console.log(i);
// SyntaxError: Unexpected token if
 
for (var i = 0; i < 3; ++i)
  var k = 10,
  console.log(k);
// Firefox: SyntaxError: missing ; before statement
// Chrome: SyntaxError: Unexpected token .

Beginning with comma

If you don't fall into the use cases of these issues and you are a bit worried about the bugs resulting in the mix of the , and ;, you can start your lines with commas.

var k;
for (var i = 0; i < 10; ++i)
  , k = i * 10
  , console.log(i)
// SyntaxError: Unexpected token ,

But we need to add some empty statement before the first , so that it compiles. In python : is used but it doesn't parse in Javascript. We can use $ for example, it is a valid statement: it reads the variable and does nothing with it.

var $;
for (var i = 0; i < 10; ++i)$ // Use of $ instead of : in python
  , k = i * 10
  , console.log(k)
// 0
// 10
// ...

Debugging purpose

The main use of this trick I can see is for debugging purpose. If there is code executed in a test without { } and you want to log something when the program goes into this part of the code. Before you had to add { } and then remove them which is really annoying. Now it's easier!

for (test)
  doSomething();

// Before
for (test) {
  val = doSomething();
  console.log('Executed!', val);
}
 
// After
for (test)
  val = doSomething(),
  console.log('Executed!', val);

Conclusion

Using the comma trick to do { }-less indentation is far from viable. However this may still be useful for debugging and overall it is fun to try new coding styles!