Roger Burton West <roger-UvLOT2mcgw/NLxjTenLetw@xxxxxxxxxxxxxxxx> writes:
> The only "clever bit" that I've included is the adding of the end word
> to the dictionary, to make sure that it is reachable; and the use of a
> list as a pipeline rather than recursing, since this saves a great deal
> of memory.
Indeed. My approach, with two workqueues, does much the same. A few
observations on your program:
Your program doesn't stop when it finds the endword - it keeps going
until everything is exhausted. For instance, with your program doing
"herpes" to "seated" takes as long as doing "herpes" to "zounds",
despite the fact that the first path takes 8 words and the second
36. (with Web2)
This can be remedied by adding
last MAINLOOP if ($ww eq $endword);
right before the "push @candidate, $ww" statement, and adding a
MAINLOOP label above while(@candidates). If you do that, it may be
tempting to also remove the "if ($w ne $endword)" condition, but if so
you'll want to handle the special case where startword and endword are
the same.
Also, this if condition is always true because of the order in which
words get added to @candidates:
> if ($chain >= scalar @{$wordinfo{$ww}}) {
the code cleanups/efficiencies this allows should be obvious.
Finally, I found in doing my solution that instead of:
> my $ww=$w;
> substr($ww,$pos,1)=$letter;
it is faster (by 20% or so) to do instead:
my $ww = $pre . $letter . $post;
where "$pre" and "$post" are figured out at the same time as "$o".
--
@;=map[/./g],qw;.h:nJ yapou cets krht ele: r:ra;;map{y;y:;
;+print}map{pop@$_}@;for@;
|
