Re: [SPOILER] Solution to Perl 'Expert' Quiz-of-the-Week #22

On Sun, Aug 29, 2004 at 12:08:31PM -0400, Daniel Martin wrote:
> 
> Is there some reason you used this:
> 
> >    sub _rungs {
> >       my $w = shift;
> >       return map { my $c = $w; substr( $c, $_, 1 ) = ''; $c } 0..($SIZE-1);
> >    }
> 
> Instead of this?
> 
> sub _rungs {
>    my $w = shift;
>    return map { my $c = $w; substr( $c, $_, 1 ) = '_'; $c } 0..($SIZE-1);
> }
> 
> Then, you wouldn't have to keep track of what position each rung came
> from, and your %rung2word hash could have a much simpler structure
> (since it could just be $rung2word{$rung} = [$word1, $word2, ...];).

Primarily because it didn't occur to me! If I get a moment in the next
day or so, I'll try this out and see how much of a difference it makes.
It certainly makes sense, as it removes two loops from my algorithm.

> 
> I'm not quite clear how the rest of your code is working yet - I'm
> finding the data structures a bit convoluted.  I'm not sure, for
> example, that you need both the "beenseen" and "visited" keys, for
> example.  I'm not sure that:
>       next WORD if $h->{ paths }{ $word }{ beenseen }++;
> ever jumps to the next word, for example.  

I thought that there might be a case where a path from the start might a
path of a different generation from the end, so I just saved all paths
from all generations. 'beenseen' makes sure that each path is only
expanded once, and yes, it does jump to the next word.

visited is used so that each word is only used in one path. On second
thought, I just could have used the keys from the paths hash, as they
would match visited.

Again, I'll revise this if I get a chance. I've already spent some time
on this fun little puzzle. :)

-Colin.