A JScript entry to the Phaser chanllenge

You probably have got tired of me, and my phone number phraser chanllenge, but you should check this one out.

Today I got a JavaScript (!) program that solves the phraser problem from Nicholas Allen. This one is surprisingly short, and fairly clear too. I have to study JScript sometimes.

Note that JScript is not statically typed, which means many type errors will not be detected until run time. This is a major drawback to me. I strongly prefer to work in a type safe language that is statically typed. Actually, many times when you get rid of all type errors in a Haskell program, it just works – a good type system allows you to express so much!

Nicholas used a trie from letters to words. I would use a trie from digits to sets of words. Since more than one letters map to one digit, this change will result in a much smaller trie (there are much fewer keys) and a much faster algorithm (we look up a whole set of words, instead of a single word, at one time).

Here’s Nicholas’ message:

“I was reading over the solutions today and found the variety interesting. The Haskell method was very well done and really showed off the language well. Some of the great features of functional languages like lambda and apply are starting to appear in C-like languages so maybe one day everyone will be able to solve problems like this so pithily :)

Since I had a JavaScript solution written previously I thought I'd share it. It's amazing how many languages JS borrowed from in addition to Java. My solution uses a trie which I think was done fairly simply. It's a bit shorter than even the Haskell.

Note: to actually run this you'll need a JS interpreter that can handle files, such as Rhino.”

var number = "6423946369";

var letters = [,,{A:1,B:2,C:3},{D:1,E:2,F:3},{G:1,H:2,I:3},{J:1,K:2,L:3},

               {M:1,N:2,O:3},{P:1,Q:2,R:3,S:4},{T:1,U:2,V:3},{W:1,X:2,Y:3,Z:4}];

var trie = [];

var words = readFile ("dict").toUpperCase ().split ("\n");

function add (node, word) {

   if (!node [word [0]]) node [word [0]] = [];

   if (word == "") node.isWord = true;

   else add (node [word [0]], word.substr (1));

}

function find (node, word, number) {

   if (number == "") {

      if (node == trie || node.isWord) print (word);

      return;

   }

   for (letter in letters [number [0]])

      if (node [letter]) find (node [letter], word + letter, number.substr (1));

   if (node.isWord) find (trie, word, number);

   if (node == trie) find (trie, word + number [0], number.substr (1));

}

for (word in words) if (words [word] != "") add (trie, words [word]);

find (trie, "", number);