Word ladder: Difference between revisions
→{{header|Phix}}
m (Swift - simplified code) |
|||
Line 398:
white → whine → chine → chink → clink → clank → blank → black
bubble → babble → gabble → garble → gargle → gaggle → waggle → wangle → tangle → tingle → tinkle → tickle</pre>
=={{header|Perl}}==
{{trans|C++}}
<lang perl>use strict;
use warnings;
my %dict;
open my $handle, '<', 'unixdict.txt';
while (my $word = <$handle>) {
chomp($word);
my $len = length $word;
if (exists $dict{$len}) {
push @{ $dict{ $len } }, $word;
} else {
my @words = ( $word );
$dict{$len} = \@words;
}
}
close $handle;
sub distance {
my $w1 = shift;
my $w2 = shift;
my $dist = 0;
for my $i (0 .. length($w1) - 1) {
my $c1 = substr($w1, $i, 1);
my $c2 = substr($w2, $i, 1);
if (not ($c1 eq $c2)) {
$dist++;
}
}
return $dist;
}
sub contains {
my $aref = shift;
my $needle = shift;
for my $v (@$aref) {
if ($v eq $needle) {
return 1;
}
}
return 0;
}
sub word_ladder {
my $fw = shift;
my $tw = shift;
if (exists $dict{length $fw}) {
my @poss = @{ $dict{length $fw} };
my @queue = ([$fw]);
while (scalar @queue > 0) {
my $curr_ref = shift @queue;
my $last = $curr_ref->[-1];
my @next;
for my $word (@poss) {
if (distance($last, $word) == 1) {
push @next, $word;
}
}
if (contains(\@next, $tw)) {
push @$curr_ref, $tw;
print join (' -> ', @$curr_ref), "\n";
return;
}
for my $word (@next) {
for my $i (0 .. scalar @poss - 1) {
if ($word eq $poss[$i]) {
splice @poss, $i, 1;
last;
}
}
}
for my $word (@next) {
my @temp = @$curr_ref;
push @temp, $word;
push @queue, \@temp;
}
}
}
print STDERR "Cannot change $fw into $tw\n";
}
word_ladder('boy', 'man');
word_ladder('girl', 'lady');
word_ladder('john', 'jane');
word_ladder('child', 'adult');
word_ladder('cat', 'dog');
word_ladder('lead', 'gold');
word_ladder('white', 'black');
word_ladder('bubble', 'tickle');</lang>
{{out}}
<pre>boy -> bay -> ban -> man
girl -> gill -> gall -> gale -> gaze -> laze -> lazy -> lady
john -> cohn -> conn -> cone -> cane -> jane
Cannot change child into adult
cat -> cot -> cog -> dog
lead -> load -> goad -> gold
white -> whine -> chine -> chink -> clink -> blink -> blank -> black
bubble -> babble -> gabble -> garble -> gargle -> gaggle -> giggle -> jiggle -> jingle -> tingle -> tinkle -> tickle</pre>
=={{header|Phix}}==
Line 436 ⟶ 547:
child into adult cannot be done
</pre>
=={{header|Python}}==
| |||