<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=US-ASCII">
<META NAME="Generator" CONTENT="MS Exchange Server version 5.5.2657.73">
<TITLE>Solutions and Discussion for Perl Quiz of the Week #22 (Expert Edition)</TITLE>
</HEAD>
<BODY>
<P><FONT SIZE=2>Sample solutions and discussion</FONT>
<BR><FONT SIZE=2>Perl Quiz of The Week #22 (20040825)</FONT>
</P>
<P><FONT SIZE=2> Write a program, 'wordladder', which gets two arguments, which are</FONT>
<BR><FONT SIZE=2> words of the same length, and which constructs and prints a "word</FONT>
<BR><FONT SIZE=2> ladder" from the first word to the second word.</FONT>
<BR><FONT SIZE=2> </FONT>
<BR><FONT SIZE=2> A word ladder from word AAA to word BBB is a sequence of dictionary</FONT>
<BR><FONT SIZE=2> words such that:</FONT>
<BR><FONT SIZE=2> </FONT>
<BR><FONT SIZE=2> 1. the first word in the sequence is word AAA</FONT>
<BR><FONT SIZE=2> 2. each word in the sequence after the first differs from the previous</FONT>
<BR><FONT SIZE=2> word in exactly one letter position</FONT>
<BR><FONT SIZE=2> 3. the last word in the sequence is word BBB</FONT>
<BR><FONT SIZE=2> </FONT>
<BR><FONT SIZE=2> For example, given the two words "love" and "hate", the program might</FONT>
<BR><FONT SIZE=2> print the word ladder:</FONT>
<BR><FONT SIZE=2> </FONT>
<BR><FONT SIZE=2> love</FONT>
<BR><FONT SIZE=2> hove</FONT>
<BR><FONT SIZE=2> have</FONT>
<BR><FONT SIZE=2> hate</FONT>
<BR><FONT SIZE=2> </FONT>
<BR><FONT SIZE=2> Or it might print:</FONT>
<BR><FONT SIZE=2> </FONT>
<BR><FONT SIZE=2> love</FONT>
<BR><FONT SIZE=2> lave</FONT>
<BR><FONT SIZE=2> have</FONT>
<BR><FONT SIZE=2> hate</FONT>
<BR><FONT SIZE=2> </FONT>
<BR><FONT SIZE=2> It might also print a longer word ladder, such as</FONT>
<BR><FONT SIZE=2> </FONT>
<BR><FONT SIZE=2> love</FONT>
<BR><FONT SIZE=2> lore</FONT>
<BR><FONT SIZE=2> lobe</FONT>
<BR><FONT SIZE=2> robe</FONT>
<BR><FONT SIZE=2> role</FONT>
<BR><FONT SIZE=2> rose</FONT>
<BR><FONT SIZE=2> lose</FONT>
<BR><FONT SIZE=2> lost</FONT>
<BR><FONT SIZE=2> most</FONT>
<BR><FONT SIZE=2> mosh</FONT>
<BR><FONT SIZE=2> moth</FONT>
<BR><FONT SIZE=2> math</FONT>
<BR><FONT SIZE=2> hath</FONT>
<BR><FONT SIZE=2> hate</FONT>
<BR><FONT SIZE=2> </FONT>
<BR><FONT SIZE=2> If the program is unable to find a word ladder, it should print an</FONT>
<BR><FONT SIZE=2> appropriate error message to the standard error, and exit with a</FONT>
<BR><FONT SIZE=2> failure status.</FONT>
<BR><FONT SIZE=2> </FONT>
<BR><FONT SIZE=2> The program should also accept an optional third argument, which, if</FONT>
<BR><FONT SIZE=2> specified, is the name of a dictionary file which contains the</FONT>
<BR><FONT SIZE=2> permissible words. If the third argument is omitted, the program</FONT>
<BR><FONT SIZE=2> should use a default dictionary.</FONT>
<BR><FONT SIZE=2> </FONT>
<BR><FONT SIZE=2> Sample word lists are available from</FONT>
<BR><FONT SIZE=2> <A HREF="http://perl.plover.com/qotw/words/" TARGET="_blank">http://perl.plover.com/qotw/words/</A></FONT>
<BR><FONT SIZE=2> </FONT>
<BR><FONT SIZE=2>---------------------------------------------------</FONT>
</P>
<P><FONT SIZE=2>[ MJD: This week's report is a collaboration between three people.</FONT>
<BR><FONT SIZE=2> Ron Isaacson tested and timed the many solutions and wrote up a</FONT>
<BR><FONT SIZE=2> timing report. Daniel Martin read over the solutions and</FONT>
<BR><FONT SIZE=2> analyzed the algorithms used. I selected one sample solution</FONT>
<BR><FONT SIZE=2> and wrote up an explanation of how it works. My very grateful</FONT>
<BR><FONT SIZE=2> thanks to Prs. Isaacson and Martin for bailing me out of this</FONT>
<BR><FONT SIZE=2> one when I bit of far more than I could chew. I now turn you</FONT>
<BR><FONT SIZE=2> over to Pr. Martin. ]</FONT>
</P>
<P><FONT SIZE=2>[Daniel Martin]</FONT>
</P>
<P><FONT SIZE=2>This was a popular quiz, judging by the number of solutions. 23 solutions were submitted from 21 different people. Three solutions weren't tested for one reason or another, leaving 21 solutions to be tested and timed. Many thanks to Ron Isaacson for doing the time-testing.</FONT></P>
<P><FONT SIZE=2>The overall algorithm used by each solution can be classified as</FONT>
<BR><FONT SIZE=2>follows:</FONT>
</P>
<P><FONT SIZE=2>- "Expanding circles":</FONT>
</P>
<P><FONT SIZE=2> 1) Start with just the word AAA as your working set. </FONT>
</P>
<P><FONT SIZE=2> 2) Find every word which is only one letter different from something</FONT>
<BR><FONT SIZE=2> in the working set and that hasn't been seen before and make that</FONT>
<BR><FONT SIZE=2> your new working set.</FONT>
</P>
<P><FONT SIZE=2> 3) Repeat (2) until BBB is in the working set.</FONT>
</P>
<P><FONT SIZE=2> This solution can be viewed as Dijkstra's shortest-path algorithm</FONT>
<BR><FONT SIZE=2> applied to the specifics of this problem.</FONT>
<BR><FONT SIZE=2> (see <A HREF="http://en.wikipedia.org/wiki/Dijkstra's_algorithm" TARGET="_blank">http://en.wikipedia.org/wiki/Dijkstra's_algorithm</A>)</FONT>
</P>
<P><FONT SIZE=2> A variant of this has the circles expanding from both AAA and BBB,</FONT>
<BR><FONT SIZE=2> and stopping when the two sets intersect.</FONT>
</P>
<P><FONT SIZE=2> One solution, from Rod Adams, computed each subsequent expanding</FONT>
<BR><FONT SIZE=2> circle by gathering the words that might be in the next working set</FONT>
<BR><FONT SIZE=2> and then eliminating those that were not adjacent to something in</FONT>
<BR><FONT SIZE=2> the previous working set. (It then switched to the more standard</FONT>
<BR><FONT SIZE=2> version based on an estimate as to which method would be faster)</FONT>
</P>
<P><FONT SIZE=2>- "workqueue":</FONT>
<BR><FONT SIZE=2> 1) Place AAA in a queue.</FONT>
<BR><FONT SIZE=2> 2) Pull a word from the queue and push onto the queue all the</FONT>
<BR><FONT SIZE=2> adjacent words we haven't seen before.</FONT>
<BR><FONT SIZE=2> 3) Repeat (2) until BBB is pulled from the queue. (Variation:</FONT>
<BR><FONT SIZE=2> until BBB is about to be pushed onto the queue)</FONT>
</P>
<P><FONT SIZE=2> This solution can be viewed as the A* algorithm applied to</FONT>
<BR><FONT SIZE=2> the specifics of this problem with no estimate of future</FONT>
<BR><FONT SIZE=2> path length. (see</FONT>
<BR><FONT SIZE=2> <A HREF="http://en.wikipedia.org/wiki/A-star_search_algorithm" TARGET="_blank">http://en.wikipedia.org/wiki/A-star_search_algorithm</A>)</FONT>
</P>
<P><FONT SIZE=2> A few people extended this by using a full-blown priority</FONT>
<BR><FONT SIZE=2> queue, with the priority of a word being</FONT>
<BR><FONT SIZE=2> (distance from w to BBB) + (length of path to w from AAA)</FONT>
</P>
<P><FONT SIZE=2> This is the A* algorithm with a distance estimate.</FONT>
</P>
<P><FONT SIZE=2> As before, there were also bi-directional variants that attacked</FONT>
<BR><FONT SIZE=2> the path from both ends, stopping when the words seen intersected.</FONT>
</P>
<P><FONT SIZE=2> Yes, sometimes the classification between "workqueue" and "expanding</FONT>
<BR><FONT SIZE=2> circles" was a bit of a judgement call about how the code was</FONT>
<BR><FONT SIZE=2> organized overall. In general if </FONT>
</P>
<P><FONT SIZE=2>- "depth first":</FONT>
<BR><FONT SIZE=2> 1) Start at AAA.</FONT>
<BR><FONT SIZE=2> 2) Pick an adjacent word that hasn't been visited yet.</FONT>
<BR><FONT SIZE=2> 3) Repeat (2) until you reach BBB or visit everything.</FONT>
<BR><FONT SIZE=2> If there are no available adjacent words, backtrack.</FONT>
</P>
<P><FONT SIZE=2> Only two solutions attempted this. Both also sorted the</FONT>
<BR><FONT SIZE=2> adjacent words so as to first try words closer to BBB.</FONT>
</P>
<P><FONT SIZE=2>After overall algorithm choice, there were still several other design decisions that could be made. A common source of variation was in how the dictionary was stored. Most solutions used a variation on this</FONT></P>
<P><FONT SIZE=2>design: (code adapted from Colin Meyer's solution)</FONT>
</P>
<P><FONT SIZE=2> open DICT, '<', $DICT or die "can't open $DICT: $!";</FONT>
<BR><FONT SIZE=2> @words = grep length( $_ ) == $SIZE,</FONT>
<BR><FONT SIZE=2> map { chomp; lc } <DICT>;</FONT>
<BR><FONT SIZE=2> close DICT;</FONT>
</P>
<P><FONT SIZE=2> for my $w ( @words ) {</FONT>
<BR><FONT SIZE=2> my @rungs = map { my $c = $w; </FONT>
<BR><FONT SIZE=2> substr( $c, $_, 1 ) = '_';</FONT>
<BR><FONT SIZE=2> $c } 0..($SIZE-1);;</FONT>
<BR><FONT SIZE=2> push @{ $rung2word{ $_ } }, $w for @rungs;</FONT>
<BR><FONT SIZE=2> }</FONT>
</P>
<P><FONT SIZE=2>That is, stored the dictionary as a hash of pattern => wordlist, where "pattern" is the word in question with one character replaced by an '_' (or '?' or '.' or '\0') and "wordlist" is a reference to all words with that pattern. Occasionally, the map word => patternlist would also be recorded.</FONT></P>
<P><FONT SIZE=2>Storing the words in a hash that mapped each word to 1 (or some other</FONT>
<BR><FONT SIZE=2>value) was also popular. (So that keys %words was used whenever the full list of words was needed)</FONT>
</P>
<P><FONT SIZE=2>A few stored the dictionary in a single giant array, searching through it with regexps or with Inline::C functions when finding adjacent words.</FONT></P>
<P><FONT SIZE=2>There were also some non-perl solutions submitted: 1 in PIR (Parrot Intermediate Representation - assembly language for Perl 6, sort of),</FONT></P>
<P><FONT SIZE=2>2 in python, and 1 in scheme. Unfortunately, I have no PIR interpreter and neither of my scheme interpreters was able to handle the submitted scheme solution (guile chokes on the variable name with asterisks in it and mzscheme doesn't know about 'sort'). The python solutions were tested along with the others.</FONT></P>
<P><FONT SIZE=2>Several of the solutions failed to check for certain edge cases. For example, if AAA == BBB, 4 solutions found no path. 3 more solutions found a path only if AAA was adjacent to something (so testing on "transubstantiationalist transubstantiationalist" showed no path for those, but testing "love love" did find a path) Also, some solutions had trouble with very large dictionaries or with long paths.</FONT></P>
<P><FONT SIZE=2>At least one solution made the erroneous assumption that if AAA and BBB differ only in positions 1, 3, and 5, then all the words along the path from AAA to BBB will differ from each other only in positions 1, 3, and 5. This is shown false by the path from "axal" to "utah" in the Web2 dictionary, which among other words passes through "itch".</FONT></P>
<P><FONT SIZE=2>Because of the large number of solutions, I won't go through each one and list the classification. Instead, this chart might be useful:</FONT></P>
<P><FONT SIZE=2> dictionary ->|sig>wordlist|word>1|@DICT</FONT>
<BR><FONT SIZE=2> search method | | |</FONT>
<BR><FONT SIZE=2> ==================================================</FONT>
<BR><FONT SIZE=2> Expanding circles| 0 | 1 | 2</FONT>
<BR><FONT SIZE=2> 2-dir version | 5 | 0 | 1</FONT>
<BR><FONT SIZE=2> --------------------------------------------------</FONT>
<BR><FONT SIZE=2> workqueue | 3 | 2 | 0</FONT>
<BR><FONT SIZE=2> + distance ver | 2 | 0 | 0</FONT>
<BR><FONT SIZE=2> 2-dir version | 0 | 1 | 0</FONT>
<BR><FONT SIZE=2> --------------------------------------------------</FONT>
<BR><FONT SIZE=2> depth first | 0 | 2 | 1</FONT>
</P>
<P><FONT SIZE=2>I didn't classify the scheme solution from Greg Bacon, nor the PIR solution from Ingo Blechschmidt. I also did not classify the perl solution sent in by David B., since I was unable to puzzle it out. (I was also unable to test it - it's doing something that eats memory like crazy.)</FONT></P>
<P><FONT SIZE=2>I will note that in general, the depth first solutions all performed very poorly on this quiz, despite two of them coding crucial parts in C. The overall fastest solution was mine, the 2-direction workqueue, though not by much.</FONT></P>
<P><FONT SIZE=2>Ron Isaacson's beautifully-formatted timing report is available at:</FONT>
</P>
<P><FONT SIZE=2> <A HREF="http://perl.plover.com/qotw/misc/e022/report.html" TARGET="_blank">http://perl.plover.com/qotw/misc/e022/report.html</A></FONT>
</P>
<P><FONT SIZE=2>The raw timing data, and the submitted programs, are available at</FONT>
</P>
<P><FONT SIZE=2> <A HREF="http://perl.plover.com/qotw/misc/e022/" TARGET="_blank">http://perl.plover.com/qotw/misc/e022/</A></FONT>
</P>
<P><FONT SIZE=2>Although the problem merely specified _a_ path from AAA to BBB, many solutions found the shortest path. Therefore, some people speculated on what the "longest shortest path" might be for different word lengths in the different dictionaries. The results can be found in the thread starting here:</FONT></P>
<P><FONT SIZE=2> <A HREF="http://perl.plover.com/~alias/list.cgi?1:mss:2054" TARGET="_blank">http://perl.plover.com/~alias/list.cgi?1:mss:2054</A></FONT>
</P>
<P><FONT SIZE=2>----------------------------------------------------------------</FONT>
</P>
<P><FONT SIZE=2>[Mark Dominus]</FONT>
</P>
<P><FONT SIZE=2>I've decided to use Zed Lopez's program as this week's sample solution. According to Ron Isaacson's report, it's consistently one of the very fastest sumbissions, and it's much shorter than the other comparably fast solutions.</FONT></P>
<P><FONT SIZE=2>Part of that may be due to Zed's use of the Tree::Simple module, which provides functions that manage tree structures:</FONT>
</P>
<P><FONT SIZE=2> #!/usr/bin/perl</FONT>
<BR><FONT SIZE=2> use strict;</FONT>
<BR><FONT SIZE=2> use warnings;</FONT>
<BR><FONT SIZE=2> use Tree::Simple;</FONT>
</P>
<P><FONT SIZE=2>And part of it may be due to a somewhat excessively terse coding style, as seen here:</FONT>
</P>
<P><FONT SIZE=2> my ($start_word, $destination_word, $dictionary_file) = @ARGV;</FONT>
<BR><FONT SIZE=2> die "You must specify two words of equal length" unless defined</FONT>
<BR><FONT SIZE=2> $start_word and defined $destination_word and length $start_word ==</FONT>
<BR><FONT SIZE=2> length $destination_word;</FONT>
</P>
<P><FONT SIZE=2>But on the whole I found the program straightforward and easy to understand.</FONT>
</P>
<P><FONT SIZE=2>In Daniel Martin's classification, this was an "expanding circles"</FONT>
<BR><FONT SIZE=2>solution, of the "two directions at once variety". Pr. Lopez's program maintains two working sets of words, and operates on them alternately. On each pass, it finds all the words that are one step removed from the words in the current working set, and replaces the current working set with this new set of words. When it finds a word that is already in the *other* working set, it knows it has found a complete path.</FONT></P>
<P><FONT SIZE=2> $dictionary_file ||= "/usr/share/dict/web2";</FONT>
<BR><FONT SIZE=2> open (FH, $dictionary_file) or die "Couldn't open $dictionary_file: $!";</FONT>
</P>
<P><FONT SIZE=2> $start_word = lc $start_word;</FONT>
<BR><FONT SIZE=2> $destination_word = lc $destination_word;</FONT>
</P>
<P><FONT SIZE=2> my %dict;</FONT>
<BR><FONT SIZE=2> while (<FH>) {</FONT>
<BR><FONT SIZE=2> chomp;</FONT>
<BR><FONT SIZE=2> $dict{lc $_} = 1 if length $_ == length $start_word and $_ !~ /[^a-zA-Z]/;</FONT>
<BR><FONT SIZE=2> }</FONT>
<BR><FONT SIZE=2> close(FH);</FONT>
<BR><FONT SIZE=2> die "$start_word is not in dictionary" unless exists $dict{$start_word};</FONT>
<BR><FONT SIZE=2> die "$destination_word is not in dictionary" unless exists</FONT>
<BR><FONT SIZE=2> $dict{$destination_word};</FONT>
</P>
<P><FONT SIZE=2>The dictionary is the usual Perl implementation of a set, with words as keys, and the values always 1. </FONT>
</P>
<P><FONT SIZE=2>This code handles the special case if the start word and the end word being the same. Had I thought about it in advance, I might have ruled this out when I posed the problem:</FONT></P>
<P><FONT SIZE=2> print "$start_word\n" and exit if $start_word eq $destination_word;</FONT>
</P>
<P><FONT SIZE=2>$list and $next_nodes are the main data structures of the program:</FONT>
</P>
<P><FONT SIZE=2> my ($list, $next_nodes);</FONT>
<BR><FONT SIZE=2> {</FONT>
<BR><FONT SIZE=2> my $top = Tree::Simple->new($start_word);</FONT>
<BR><FONT SIZE=2> my $bottom = Tree::Simple->new($destination_word);</FONT>
</P>
<P><FONT SIZE=2> $list = [{$start_word => $top}, {$destination_word => $bottom}];</FONT>
<BR><FONT SIZE=2> $next_nodes = [[$top],[$bottom]];</FONT>
<BR><FONT SIZE=2> }</FONT>
</P>
<P><FONT SIZE=2>The Tree::Simple objects keep track of tree structures whose roots are labeled with the start and end words; each tree node is labeled with another word. If BBB is in the start-word tree, then a word ladder from the start word to BBB can be found by tracing the path from BBB back to the root. The program's wordchain() function does this:</FONT></P>
<P><FONT SIZE=2> sub word_chain {</FONT>
<BR><FONT SIZE=2> my $node = shift;</FONT>
<BR><FONT SIZE=2> my @words;</FONT>
<BR><FONT SIZE=2> while (1) {</FONT>
<BR><FONT SIZE=2> push @words, $node->getNodeValue();</FONT>
<BR><FONT SIZE=2> last if $node->isRoot;</FONT>
<BR><FONT SIZE=2> $node = $node->getParent;</FONT>
<BR><FONT SIZE=2> }</FONT>
<BR><FONT SIZE=2> return @words;</FONT>
<BR><FONT SIZE=2> }</FONT>
</P>
<P><FONT SIZE=2>(->getNodeValue returns the word with which the node is labeled.)</FONT>
</P>
<P><FONT SIZE=2>$list contains exactly two hashes, one working 'down' from the source word and the other working 'up' from the destination word. Each hash maps words to the Tree::Simple objects that represent them.</FONT></P>
<P><FONT SIZE=2>$next_nodes contains the two 'working sets'.</FONT>
</P>
<P><FONT SIZE=2>The main loop of the program is:</FONT>
</P>
<P><FONT SIZE=2> for (my $x = 0; ; $x = !$x) {</FONT>
<BR><FONT SIZE=2> $next_nodes->[$x] = find_next_nodes($next_nodes->[$x], $x);</FONT>
<BR><FONT SIZE=2> }</FONT>
</P>
<P><FONT SIZE=2>The '$x = !$x' is a little obscure; he really means '$x = 1 - $x'</FONT>
<BR><FONT SIZE=2>here. The main loop alternates between the two working sets, replacing the old working set with the set of words adjacent to it.</FONT></P>
<P><FONT SIZE=2>Calculating this new set of words is the job of find_next_nodes():</FONT>
</P>
<P><FONT SIZE=2> sub find_next_nodes {</FONT>
<BR><FONT SIZE=2> my ($nodes, $x) = @_;</FONT>
<BR><FONT SIZE=2> my @next_nodes;</FONT>
<BR><FONT SIZE=2> for my $node (@$nodes) {</FONT>
<BR><FONT SIZE=2> my $orig_word = $node->getNodeValue();</FONT>
<BR><FONT SIZE=2> for (my $i = 0; $i < length $orig_word; $i++) {</FONT>
<BR><FONT SIZE=2> my $word = $orig_word;</FONT>
<BR><FONT SIZE=2> for my $char ('a'..'z') {</FONT>
<BR><FONT SIZE=2> next if $char eq substr $orig_word, $i, 1;</FONT>
<BR><FONT SIZE=2> substr $word, $i, 1, $char;</FONT>
</P>
<P><FONT SIZE=2>This last line uses the four-argument form of substr(), which is newish. It was introduced by analogy with the four-argument form of splice(). substr($word, $i, 1, $char) locates the length-1 substring of $word at position $i, just like substr($word, $i, 1), but then replaces this substring with the contents of $char. It is just like</FONT></P>
<P><FONT SIZE=2>>MJD> substr($word, $i, 1) = $char;</FONT>
</P>
<P><FONT SIZE=2>only faster.</FONT>
</P>
<P><FONT SIZE=2>The program has just calculated a new word, $word, that is one step removed from some word $orig_word that was in the working set. If this new word is already in the *other* working set, then a complete path has been found:</FONT></P>
<BR>
<P><FONT SIZE=2> # if word is in other list, we're done</FONT>
</P>
<P><FONT SIZE=2> success($x ? ($list->[!$x]->{$word}, $node) : ($node,</FONT>
<BR><FONT SIZE=2> $list->[!$x]->{$word})) if exists $list->[!$x]->{$word};</FONT>
</P>
<P><FONT SIZE=2>I would have formatted this differently. I think it's clearer like</FONT>
<BR><FONT SIZE=2>this:</FONT>
</P>
<P><FONT SIZE=2>>MJD> success($x ? ($list->[1-$x]->{$word}, $node) </FONT>
<BR><FONT SIZE=2>>MJD> : ($node, $list->[1-$x]->{$word}))</FONT>
<BR><FONT SIZE=2>>MJD> if exists $list->[1-$x]->{$word};</FONT>
</P>
<P><FONT SIZE=2>The success() function, which we'll see shortly, is responsible for tracing the paths from the common word back to the roots of the two trees, and generating the resulting word ladder. Its arguments are the nodes of the two trees that have the same label, with the node from the top-down tree first. If $x is true (that is, 1) then the current working set is the bottom-up one, so needs to be put second in the argument list of success().</FONT></P>
<P><FONT SIZE=2>If the program hasn't been succesful, it extends the current tree structure and the new working set:</FONT>
</P>
<P><FONT SIZE=2> if (exists $dict{$word} and !exists $list->[$x]->{$word}) {</FONT>
<BR><FONT SIZE=2> my $child = Tree::Simple->new($word);</FONT>
<BR><FONT SIZE=2> $node->addChild($child); </FONT>
<BR><FONT SIZE=2> push @next_nodes, $child;</FONT>
<BR><FONT SIZE=2> $list->[$x]->{$word} = $child;</FONT>
<BR><FONT SIZE=2> }</FONT>
<BR><FONT SIZE=2> }</FONT>
<BR><FONT SIZE=2> }</FONT>
</P>
<P><FONT SIZE=2>If there were no new words that could be reached from the current node, it is a dead end and is deleted from the tree structure to save</FONT></P>
<P><FONT SIZE=2>memory:</FONT>
</P>
<P><FONT SIZE=2> prune($node) if $node->isLeaf;</FONT>
<BR><FONT SIZE=2> }</FONT>
<BR><FONT SIZE=2> return \@next_nodes;</FONT>
<BR><FONT SIZE=2> }</FONT>
</P>
<BR>
<P><FONT SIZE=2>Here's prune(), which deletes the dead end. After the dead-end node is deleted, prune() checks to see if its parent is now a dead end also:</FONT></P>
<P><FONT SIZE=2> sub prune {</FONT>
<BR><FONT SIZE=2> my $node = shift;</FONT>
<BR><FONT SIZE=2> while ($node->isLeaf) {</FONT>
<BR><FONT SIZE=2> die "No path exists" if $node->isRoot;</FONT>
<BR><FONT SIZE=2> my $parent = $node->getParent;</FONT>
<BR><FONT SIZE=2> $parent->removeChild($node);</FONT>
<BR><FONT SIZE=2> $node = $parent;</FONT>
<BR><FONT SIZE=2> }</FONT>
<BR><FONT SIZE=2> }</FONT>
</P>
<BR>
<P><FONT SIZE=2>The success() function was called when two nodes were found with the same label, one in each of thee trees. It uses word_chain() to find the word ladders from the common word up to the source word (at $node1) and down to the destination word (at $node2) and appends the two ladders together:</FONT></P>
<P><FONT SIZE=2> sub success {</FONT>
<BR><FONT SIZE=2> my ($node1, $node2) = @_;</FONT>
<BR><FONT SIZE=2> print join "\n", (reverse word_chain($node1)), word_chain($node2), '';</FONT>
<BR><FONT SIZE=2> exit;</FONT>
<BR><FONT SIZE=2> }</FONT>
</P>
<P><FONT SIZE=2>The function avoids listing the common word twice because the common word is never added to the second tree. One of the arguments to</FONT></P>
<P><FONT SIZE=2>success() is the node containing the common word; the other is the node in the other tree that would have been adjacent to the common-word node.</FONT></P>
<P><FONT SIZE=2>Once again, thanks to everyone who participated by sending a solution or adding to the discusion, and thanks also to everyone who participated *without* sending a solution or adding to the discussion.</FONT></P>
<P><FONT SIZE=2>Thanks especially to Ron Isaacson and Daniel Martin.</FONT>
</P>
<P><FONT SIZE=2>John Trammell is working hard on the writeup of last week's parenthesis-generating quiz; I will send that along when it is ready.</FONT></P>
<P><FONT SIZE=2>I hope to send out the new quiz tonight.</FONT>
</P>
</BODY>
</HTML>