Re: Solutions and Discussion for Perl Quiz of the Week #22 (Expert Edition)

Mark Jason Dominus <[email protected]> writes:

> On Sep 9, 2004, at 12:51 PM, Ronald J Kimball wrote:
>
>> On Wed, Sep 08, 2004 at 10:06:47PM -0400, Daniel Martin wrote:
>>
>>>   Yes, sometimes the classification between "workqueue" and "expanding
>>>   circles" was a bit of a judgement call about how the code was
>>>   organized overall.  In general if
>>
>> This paragraph was cut off.  I'm curious to know more about how this
>> distinction was made.
>>
>
> Me too.  I thought that Zed Lopez's solution was clearly of the
> "expanding circles" type, but
> Daniel Martin's table seemed to categorize it as something else:

It was expanding circles, but I'd misread the code and had it listed
as a 1-directional in my notes, when it is clearly two-directional (as
shown by its performance, among other things).  I blame the position
of his name in the alphabet, which affected how tired I was when I got
to his program.

Sorry about the cut sentence; you may notice that I tend to do that
sort of thing.  (See my network protocol message)

The sentence which was cut off should have been:

  In general, if a program was aware each time it worked through
  that it had found all words at that distance, then it was
  classified as expanding circles, even if the structures used
  were called "workqueue", "queue", or something similar.

The canonical example of this was the expanding circles version sent
by Ronald J Kimball, whose workqueue had an explicit 'break' in it to
possibly switch directions each time a complete new circle was
finished.  (Jurgen Pletinckx's solution almost hit this rule too, but
his stack only had a break in it if the optional VERBOSE flag was
given)

Another thing I should have done in the summary is hilighted Dan
Schmidt's solution, which I thought was exceptionally well-written and
readable, despite being in a foreign language.

For the record, here's the breakdown, pulled from my notes:

andrew_dalke.py
  Python
  Dictionary accumulated in sig>wordlist map
             then word>adjwordlist map is formed 
             by processing sig>wordlist map
  Search is straight 0-estimate A* (One way)

colin_meyer.pl
  Dictionary loaded through sig>wordlist map
  (Actually several complicated maps, since sig is formed by deleting
   letters) 
  Search is expanding circles.  (Two way, simultaneously)

colin_meyer_2.pl
  Dictionary loaded through sig>wordlist map
  (with word>siglist also stored as a map at dictionary load time)
  Search is expanding circles.  (Two way, simultaneously)

daniel_martin.pl
  Dictionary loaded to word>1 map.  Neighbors found during search
  by exhaustive a-z substitution.
  Search by two d(goal,word)-estimate A* queues
  (at each step, pull next word from smaller queue)

dan_schmidt.py
  Dictionary uses sig>wordlist.
  Classic d(goal,word)-estimate A* using python's standard heapq
  module.
  Searches with a word class that uses __cmp__, etc.
  Very clean.  (If you want a reference implementation of A*, this
  would be a good choice)

david_b.pl_bad
  Uses the perl module Grah::Directed to find shortest path via
  Djikstra algorithm.
  Computes word adjacency in a method I can't decipher.

greg_bacon.scheme:
  Guile chokes on the first line, could it be asterisks in the var
  name?  MzScheme doesn't understand 'sort'.

ingo_blechschmidt.pir:
  I'll assume this is the .pl translated into .pir

ingo_blechschmidt.pl:
  Dictionary loaded into sig>wordlist map.
  (with word>siglist also stored as a map at dictionary load time)
  Search is 0-estimate A*.

james_e_tilley.pl:
  Straight dist(a,end)-estimate A*.
  Dictionary stored as sig>wordlist map

jereme_corrado.pl:
  Depth-first recursive search with final compression phase
  where the ladder is hopefully compressed.
  Dictionary stored as list, regexps built for each 
  computation of neighbors()

john_j_trammell.pl:
  Search is 1-way expanding circles.  
  Dictionary as list, neighbors by grep(off_by_one($w,$_), @DICT)

julien_quint.pl:
  Dictionary loaded through sig>wordlist map
  (with word>siglist also stored as a map at dictionary load time)
  Uses regexps (with $' and $`) to load dictionary.
  Search is 0-estimate A*.

jurgen_pletinckx.pl:
  Straight 0-estimate A*.
  Dictionary stored as word>1 map.  Neighbors found by using
  String::Approx and doing a grep with 'amatch' on keys %dict.

rod_adams.pl:
  Reads words in, arranges them in rings around $AAA and $BBB.
  Expands out pushing words to further-out rings if they aren't
  reachable that fast.  Switches from eliminating based on unreachable
  to adding in based on reachable (which is like everyone else's
  expanding circles) if "pushing out" eliminates > 90% of a ring.

  Note that one ring is expanded at a time - the smaller ring each
  time.

  In the secod phase, dictionary is stored as sig>word hash.

roger_burton_west.pl:
  Search is 0-estimate A*, but a bug prevents stopping until wordlist
  is exhausted no matter what's found.
  Dictionary done as word>1 hash.
  No subs.

ronald_j_kimball.pl:
  Two-way expanding circles. (Smaller circle expanded each time)
  Dictionary stored as list, next as regexp on list.

ron_isaacson.pl:
  Dictionary stored as list, next as regexp on list.
  One-way expanding circles.

tassilo_von_parseval.pl:
  Depth first search.
  Uses Inline::C functions to try best next jump.  (But trims next
  word too aggressively, leading to erroneous "path not found"
  errors).
  Dictionary stored as word>1 hash, neighbors by grep on keys with C
  functions

xavier_noria.pl:
  Depth first search.  Uses Inline::C functions for distance.
  Dictionary stored as word>1 hash, neighbors by grep on keys with C
  functions

yitzchak_scott_thoennes.pl:
  Two expanding circles, expanded simultaneously.
  Dictionary as pat>wordlist, patterns reproduced at search time via
  regexps, $', and $`.

zed_lopez.pl:
  Two way expanding circles.
  Dictionary as word>1, neighbors found by a-z substr replacement at
  searchtime.
  uses Tree::Simple to track paths

zsban_ambrus.pl:
  Two-way expanding circles.
  Dictionary as pat>wordlist
  One interesting feature is an attempt to minimize the amount of
  dictionary being read - only first letters around the begin and end
  words are read; if this fails, the whole dictionary is read.