#!/usr/bin/perl


our ($Top, $Bottom, $DictFile) = @ARGV;
$Top      ||= 'love';
$Bottom   ||= 'hate';
$DictFile ||= 'words';

our $Length = length($Top);

$BotNext{$Bottom} = "-SELF-";
$TopPrev{$Top}    = "-SELF-";

my $TopDist = GetDistFunc($Top);
my $BotDist = GetDistFunc($Bottom);

#print "Loading $DictFile...\n";
open DICT, $DictFile;
while (<DICT>) {
  chomp;
  next unless length == $Length;
  next unless /^[A-Za-z]+$/;
  $_ = lc;

  my $dTop = $TopDist->($_);
  push @{$TopWords[$dTop]}, $_;
  if ($dTop == 1) {
    $TopPrev{$_} = $Top;
  }

  my $dBot = $BotDist->($_);
  push @{$BotWords[$dBot]}, $_;
  if ($dBot == 1) {
    $BotNext{$_} = $Bottom;
  }
 
  if ($dTop == 1 && $dBot == 1) {
    PrintList($Top, $_);
  }
}

#print "Scanning...\n";
my $tdistance = 2;
my $bdistance = 2;
while (1) {
  if (@{$TopWords[$tdistance]} <= @{$BotWords[$bdistance]}) {

    # Test all the words at minimum distance from top, to see if the stay.
    my @words = @{$TopWords[$tdistance]};
    @{$TopWords[$tdistance]} = ();
    for my $word (@words) {
      my $DistFunc = GetDistFunc($word);
  
      my $mindist = $Length+1;
      for my $altword (@{$TopWords[$tdistance -1]}) {
      # Test to see if $word is one step away from any word of less distance.
    my $dist = $DistFunc->($altword);
    $mindist = $dist if $dist < $mindist;
    if ($dist == 1) {
      push @{$TopWords[$tdistance]}, $word;
      $TopPrev{$word} = $altword;
      PrintList($word,$BotNext{$word}) if $BotNext{$word};
      last;
    }
      }
     
      unless ($mindist == 1) {
    # Make the minimum distance at least one higher.
    push @{$TopWords[$tdistance+$mindist-1]}, $word;
      }
    }
    unless (@{$TopWords[$tdistance]}) {
      # No new words were found to connect to a previous word.
      print "\nNo Path Found\n";
      exit 1;
    }

    if (@{$TopWords[$tdistance++]}/@words < 0.10) {
      last;
    }

  } else {

    my @words =  @{$BotWords[$bdistance]};
    @{$BotWords[$bdistance]} = ();
    for my $word (@words) {
      my $DistFunc = GetDistFunc($word);
   
      my $mindist = $Length+1;
      for my $altword (@{$BotWords[$bdistance -1]}) {
    my $dist = $DistFunc->($altword);
    $mindist = $dist if $dist < $mindist;
    if ($dist == 1) {
      push @{$BotWords[$bdistance]}, $word;
      $BotNext{$word} = $altword;
      PrintList($TopPrev{$word},$word) if $TopPrev{$word};
      last;
    }
      }

      unless ($mindist == 1) {
    push @{$BotWords[$bdistance+$mindist-1]}, $word;
      }
    }

    unless (@{$BotWords[$bdistance]}) {
      print "\nNo Path Found\n";
      exit 1;
    }

    if (@{$BotWords[$bdistance++]}/@words < 0.10) {
      last;
    }
  }
}


# If we got here, the potential word list exploded...
# time to build a connection mapping.

#print "Switching Search Modes....\n";
my %words = ();
for my $x ($tdistance .. $#TopWords) {
  for my $word (@{$TopWords[$x]}) {
    $words{$word} = 1;
  }
}
$#TopWords = --$tdistance;

for my $x ($bdistance .. $#BotWords) {
  for my $word (@{$BotWords[$x]}) {
    $words{$word} = 1;
  }
}
$#BotWords = --$bdistance;

my %maps = ();
for my $word (keys %words) {
  for my $x (0..$Length-1) {
    my $str = $word;
    substr($str, $x, 1, '?');
    push @{$maps{$str}}, $word;
  }
}

while (1) {
  if (@{$TopWords[$tdistance]} <= @{$BotWords[$bdistance]}) {

    my %newwords = ();
    for my $word (@{$TopWords[$tdistance]}) {
      for my $x (0..$Length-1) {
    my $str = $word;
    substr($str,$x,1,'?');
    for my $altword (@{$maps{$str}}) {
      next if $TopPrev{$altword};
      $TopPrev{$altword} = $word;
      $newwords{$altword} = 1;
      PrintList($word,$altword) if $BotNext{$altword};
    }
      }
    }
    $TopWords[++$tdistance] = [keys %newwords];

    unless (@{$TopWords[$tdistance]}) {
      print "\nNo Path Found\n";
      exit 1;
    }

  } else {

    my %newwords = ();
    for my $word (@{$BotWords[$bdistance]}) {
      for my $x (0..$Length-1) {
    my $str = $word;
    substr($str,$x,1,'?');
    for my $altword (@{$maps{$str}}) {
      next if $BotNext{$altword};
      $BotNext{$altword} = $word;
      PrintList($altword,$word) if $TopPrev{$altword};
      $newwords{$altword} = 1;
    }
      }
    }
    $BotWords[++$bdistance] = [keys %newwords];

    unless (@{$BotWords[$bdistance]}) {
      print "\nNo Path Found\n";
      exit 1;
    }
  }
}
   


sub GetDistFunc {
  my $code = 'sub { 0 ';
  for (my $x = 0 ; $x < $Length ; ++$x) {
    $code .= " + (substr(\$_[0], $x, 1) ne '" . substr($_[0], $x, 1) . "')";
  }
  $code .= '};';
  return eval $code;
}


sub PrintList {
  my @x = @_;
  while ($x[0]  ne $Top   ) { unshift @x, $TopPrev{$x[0] }; }
  while ($x[-1] ne $Bottom) { push    @x, $BotNext{$x[-1]}; }
  print join("\n", @x, '');
  exit;
}
