use strict;
use warnings;

use List::Compare;
use Benchmark qw( cmpthese );

my $lword = shift || 'love';
my $rword = shift || 'hate';

die unless length($rword) == length($lword);
my $length = length($lword);

my $wordlist;
open(FH,'word.list') or die;
while(<FH>) {
    chomp;
    undef($wordlist->{lc $_}) if length($_) == $length;
}

print solo($lword,$rword);

#cmpthese( ... );

sub solo {
    my ( $rdepth,$ldepth,$rex,$lex ) = (0,0,1,1);
    my $left   = { $_[0] => [$_[0]] };
    my $right  = { $_[1] => [$_[1]] };

    while ( 1 ) {
        # compare the intersection of the leaf nodes
        my $lc = List::Compare->new( {
            lists    => [ [keys %$left], [keys %$right] ],
            accelerated => 1,
            unsorted => 1,
        } );
        my @int = $lc->get_intersection();
        if ( @int ) {
            my $solve = shift @int;
            pop @{$right->{$solve}};
            return join("\n", @{$left->{$solve}}, reverse @{$right->{$solve}}) . "\n";
        }

        # pick a side to expand the search in
        if ( $lex && $rdepth > $ldepth ) {
            $lex = expandTree($left,++$ldepth);
        }
        elsif ( $rex ) {
            $rex = expandTree($right,++$rdepth);
        }
        else {
            return "No solution.";
        }
    
    }
}

sub expandTree {
    my ($tree, $depth) = @_;
    my ($word, $path, $expanded);
    while ( ($word, $path) = each %$tree ) {
        if ( @$path == $depth ) {
            for my $i (0..(length($word)-1) ) {
                for my $letter ( 'a'..'z' ) {
                    my $try = $word;
                    substr($try,$i,1) = $letter;
                    next if exists $tree->{$try};
                    if ( exists $wordlist->{$try} ) {
                        $tree->{$try} = [ @{$tree->{$word}}, $try ];
                        $expanded = 1;
                    }
                }
            }
        }
    }
    return $expanded;
}