Freigeben über

A JScript entry to the Phaser chanllenge

  • Artikel

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);

Comments

  • Anonymous
    April 06, 2004
    "for (word in words) if (words [word] != "") add (trie, words [word]);"
    Admitted, it's very short. But by using these kind of constructs, it's no surprise it's short ;).

    Still, a clever solution.
  • Anonymous
    April 07, 2004
    Yeah, I'm not particular happy about that. Unfortunately in JS an array iterator returns the array indices and not the array values. I asked Brendan Eich about why that is and he said it was because object iteration was originally intended just for debugging. So it's not as usable as in other languages where it can produce gorgeous code.

    Fortunately in C# and Java it will be possible to define sensible iterators for foreach if you don't like the system ones.

    Alternatively you can replace that with a use of Array.prototype.apply which is probably the solution any functional programmer would have tried first :)