#!/usr/bin/perl

use strict;
use warnings;

my ($A, $B, $DICT) = @ARGV;
$DICT = "/usr/share/dict/words" if !$DICT;
die "$A and $B have different length.\n" if length($A) != length($B);

# Read in the dictionary
my %words = ();
my %holes = ();
open DICT, $DICT or die "Cannot open dictionary $DICT: $!\n";
#print STDERR "Reading in $DICT";
while (<DICT>) {
   #print STDERR "." if $. % 10000 == 0;
   chomp;
   $_ = lc;
   next if length($_) != length($A);
   next if exists $words{$_};
   while (/./g) {
     push @{$holes{"$`.$'"}}, $_;
     push @{$words{$_}}, "$`.$'";
   }
}
#print STDERR "\n";
close DICT;

# Find a shortest ladder (breadth-first)
my @queue = ([$A]);
my %seen = ();
while (@queue) {
   my (@ladder) = @{shift @queue};
   my $w = $ladder[-1];
   if ($w eq $B) {
     #print "@ladder\n";
     print "$_\n" for @ladder;
     exit;
   } else {
     next if $seen{$w}++;
     for (grep { $_ ne $w } map { @{$holes{$_}} } @{$words{$w}}) {
       push @queue, [@ladder, $_];
     }
   }
}
die "Could not find word ladder between $A and $B.\n"
