perlquestion Limbic~Region All, <br /> In [id://558123|this thread], [Ieronim] posted a cool script. It finds the shortest bridge between two words where all the words in the bridge can be found in <i>a dictionary</i> and each word differs from its adjacent partners by only one character. <p> I posted what I believe to be a very fast elegant solution: <READMORE> <CODE> #!/usr/bin/perl use strict; use warnings; use Storable; my ($src, $tgt) = @ARGV; die "Usage: $0 <src> <tgt>" if ! defined $src || ! defined $tgt; die "The <src> and <tgt> must be same length" if length($src) != length($tgt); my $db = retrieve('dictionary.db'); my $path = find_path($src, $tgt, $db->{length($tgt)}); print "$path\n"; sub find_path { my ($src, $tgt, $list, $seen, $work) = @_; @$work = map {key => $_ => path => "$src->$_"}, @{$list->{$src}} if ! defined $work; my $next = []; for (@$work) { my ($word, $path) = @{$_}{qw/key path/}; next if $seen->{$word}++; return $path if $word eq $tgt; push @$next, map {key => $_, path => "$path->$_"}, @{$list->{$word}}; } return find_path($src, $tgt, $list, $seen, $next) if @$next; return 'path not found'; } </CODE> </READMORE> </p> <p> The algorithm is simple. First, create a datastructure that relates all words of a given length to all other words of the same length with a [wp://Levenshtein Distance] of 1. This is a one time up-front cost. Next, simply perform a [wp://Breadth-first_search|breadth first search] starting from one end and stopping when the other end is encountered. </p> <p> With the hard work done up front, the task can be accomplished in about 20 lines of code. Is anyone aware of a more efficient (faster run-time) algorithm? As usual, this is just one of my "I want to learn" questions and there is no real-world speed barrier I am trying to break. It just seemed to me that there should be some way to eliminate some paths during the BFS. I think an evolutionary algorithm technique might work. Paths that increase the Levenshtein Distance to the target word would not be allowed to survive. Even if this does work, I am not sure that the reduction in search space is worth the added distance calculation. </p> <p> I appreciate any ideas on this. </p> <small> <small> * The original did allow for the endpoints not to be dictionary words. </small> </small> <div class="pmsig"><div class="pmsig-180961"> <p> Cheers - [Limbic~Region|L~R] </p> </div></div>