IMPORTANT: Please do not post solutions, hints, or other spoilers
        until at least 60 hours after the date of this message.
        Thanks.

IMPORTANT: S'il vous plaît, attendez au minimum 60 heures après la
        date de ce message avant de poster solutions, indices ou autres
        révélations. Merci.

BELANGRIJK: Stuur aub geen oplossingen, hints of andere tips in de
        eerste 60 uur na het verzendingstijdstip van dit
        bericht. Waarvoor dank.

Qing3 Zhu4Yi4: Qing3 Ning2 Deng3Dao4 Jie1Dao4 Ben3 Xin4Xi2 Zhi1Hou4 60
        Xiao3Shi2, Zai4 Fa1Biao3 Jie3Da2, Ti2Shi4, Huo4 Qi2Ta1 Hui4
        Xie4Lou4 Da2An4 De5 Jian4Yi4.  Xie4Xie4.

----------------------------------------------------------------

Write a program, 'wordladder', which gets two arguments, which are
words of the same length, and which constructs and prints a "word
ladder" from the first word to the second word.

A word ladder from word AAA to word BBB is a sequence of dictionary
words such that:

1. the first word in the sequence is word AAA
2. each word in the sequence after the first differs from the previous
   word in exactly one letter position
3. the last word in the sequence is word BBB

For example, given the two words "love" and "hate", the program might
print the word ladder:

        love
        hove
        have
        hate

Or it might print:

        love
        lave
        have
        hate

It might also print a longer word ladder, such as

        love
        lore
        lobe
        robe
        role
        rose
        lose
        lost
        most
        mosh
        moth
        math
        hath
        hate

If the program is unable to find a word ladder, it should print an
appropriate error message to the standard error, and exit with a
failure status.

The program should also accept an optional third argument, which, if
specified, is the name of a dictionary file which contains the
permissible words.  If the third argument is omitted, the program
should use a default dictionary.

Sample word lists are available from
        [URL=http://perl.plover.com/qotw/words/]http://perl.plover.com/qotw/words/[/URL]

#!perl

use strict;
use warnings;

++$|;

################################################################################

my $wl_standard = 'englisch2.wl';

################################################################################

my ($wort_start,$wort_ziel,$wl) = @ARGV;
$wort_start = ($wort_start ne '') ? lc $wort_start : die 'Es muss ein Startwort übergeben werden!';
$wort_ziel  = ($wort_ziel ne '')  ? lc $wort_ziel  : die 'Es muss ein Zielwort übergeben werden!';
die 'Start und Zielwort müssen die selbe Länge haben!' if length $wort_start != length $wort_ziel;
$wl ||= $wl_standard;

print "
Startwort:   $wort_start
Zielwort:    $wort_ziel
Wörterliste: $wl

";

################################################################################

print "Wörterliste einlesen...";
open (DATEI,$wl) || die 'Wörterbuchdatei konnte nicht geöffnet werden!';
 chomp (my @w = <DATEI>);
close (DATEI);
my $l = length $wort_start;
my %w = map { lc($_) => 1 } grep { length $_ == $l } @w;
print " fertig\n";

################################################################################

die 'Das Startwort kommt im Wörterbuch nicht vor!' unless $w{$wort_start};
die 'Das Zielwort kommt im Wörterbuch nicht vor!'  unless $w{$wort_ziel};

################################################################################

my @zw = (([]) x length $wort_start);
$zw[0] = [$wort_start];

my %von;

print "Suche starten...";
while (1) {
 my $wort;
 foreach (0..$#zw) {
  next unless @{$zw[$_]};
  $wort = shift @{$zw[$_]};
  last;
 }
 unless ( defined $wort ) {
  print " fertig\n\n";
  print "Keine Lösung möglich!\n";
  exit;
 }
 foreach my $foo (&foo($wort)) {
  $von{$foo} = $wort;
  my $u = &bar($foo);
  if ( $u == 0 ) {
   print " fertig\n\n";
   my @weg = ($foo);
   while ( $foo ne $wort_start ) {
    $foo = $von{$foo};
    unshift @weg, $foo;
   }
   print (join(' -> ',@weg), "\n");
   exit;
  }
  push @{$zw[$u]}, $foo;
 }
}

################################################################################
################################################################################
################################################################################

sub foo {
 my $wort = shift;
 my @m;
 foreach my $i (0..length($wort)-1) {
  foreach my $v ('a'..'z') {
   next if substr($wort,$i,1) eq $v;
   my $m = substr($wort,0,$i).$v.substr($wort,$i+1);
   next unless $w{$m};
   next if $von{$m};
   push @m, $m;
  }
 }
 return @m;
}

sub bar {
 my $wort = shift;
 my $unterschied = length($wort);
 foreach my $i (0..length($wort)-1) {
  --$unterschied if substr($wort,$i,1) eq substr($wort_ziel,$i,1);
 }
 return $unterschied;
}