As with most things I blog about, this starts with Twitter. I follow a lot of people on Twitter, and I use Lists. I want to be able to group people more-or-less on community, because there's the community where they talk about programming, for example, and the community where they talk about music, or the town I live in.
I can begin to break things up myself, but curation is a hard thing, so I wanted to do it automatically. And I spent a long time not knowing what to do. I imagined myself traversing trees in what looks like linked lists reimagined by Cthulhu, and that doesn't sound like much fun at all.
Eventually, I decided to search on "graphs and Perl". Of course, I probably should've done it earlier, but oh well. I found Graph. I had used GD::Graph before, which is a plotting library. (There has to be some index of how overloaded words are.) And once I installed it, I figured it out: As a programmer, all you're dealing with are arrays and hashes. Nothing scary.
Word Ladder
We'll take a problem invented by Lewis Carroll called a "word ladder", where you find your way from one word (for example, "cold") to another ("warm") by changing one letter at a time:
cold
coRd
cArd
Ward
warM
Clearly, this can and is often done by hand, but if you're looking to automate it, there are three basic problems: what are the available words, how do you determine when words are one change away, and how do you do this to get the provable shortest path?
First, I went to CERIAS years ago and downloaded word lists. Computer security researchers use them because real words are bad passwords, so, lists of real words can be used to create rainbow tables and the like. My lists are years old, so there may be new words I don't account for, but unlike Lewis Carroll, I can get from APE to MAN in five words, not six.
ape
apS
aAs
Mas
maN
Not sure that Lewis Carroll would've accepted AAS, but there you go
There is a term for the number of changes it takes to go from one word to another, and it's called the Levenshtein Distance. I first learned about this from perlbrew, which is how, if you type "perlbrew isntall", it guesses that you meant to type "perlbrew install". It's hardcoded there because perlbrew can't assume you have anything but perl and core modules. I use the function from perlbrew instead of Text::Levenshtein but it is a module worth looking into.
And the final answer is "Put it into a graph and use Dijkstra's Algorithm!"
Perhaps not with the exclamation point.
Showing Code
Here's making a graph of it:
#!/usr/bin/env perl
use feature qw{say} ;
use strict ;
use warnings ;
use Data::Dumper ;
use Graph ;
use List::Util qw{min} ;
use Storable ;
for my $l ( 3 .. 16 ) {
create_word_graph($l) ;
}
exit ;
# -------------------------------------------------------------------
# we're creating a word graph of all words that are of length $length
# where the nodes are all words and the edges are unweighted, because
# they're all weighted 1. No connection between "foo" and "bar" because
# the distance is "3".
sub create_word_graph {
my $length = shift ;
my %dict = get_words($length) ;
my @dict = sort keys %dict ; # sorting probably is unnecessary
my $g = Graph->new() ;
# compare each word to each word. If the distance is 1, put it
# into the graph. This implementation is O(N**2) but probably
# could be redone as O(NlogN), but I didn't care to.
for my $i ( @dict ) {
for my $j ( @dict ) {
my $dist = editdist( $i, $j ) ;
if ( $dist == 1 ) {
$g->add_edge( $i, $j ) ;
}
}
}
# Because I'm using Storable to store the Graph object for use
# later, I only use this once. But, I found there's an endian
# issue if you try to open Linux-generated Storable files in
# Strawberry Perl.
store $g , "/home/jacoby/.word_$length.store" ;
}
# -------------------------------------------------------------------
# this is where we get the words and only get words of the correct
# length. I have a number of dictionary files, and I put them in
# a hash to de-duplicate them.
sub get_words {
my $length = shift ;
my %output ;
for my $d ( glob( '/home/jacoby/bin/Toys/Dict/*' ) ) {
if ( open my $fh, '<', $d ) {
for my $l ( <$fh> ) {
chomp $l ;
$l =~ s/\s//g ;
next if length $l != $length ;
next if $l =~ /\W/ ;
next if $l =~ /\d/ ;
$output{ uc $l }++ ;
}
}
}
return %output ;
}
# -------------------------------------------------------------------
# straight copy of Wikipedia's "Levenshtein Distance", straight taken
# from perlbrew. If I didn't have this, I'd probably use
# Text::Levenshtein.
sub editdist {
my ( $f, $g ) = @_ ;
my @a = split //, $f ;
my @b = split //, $g ;
# There is an extra row and column in the matrix. This is the
# distance from the empty string to a substring of the target.
my @d ;
$d[ $_ ][ 0 ] = $_ for ( 0 .. @a ) ;
$d[ 0 ][ $_ ] = $_ for ( 0 .. @b ) ;
for my $i ( 1 .. @a ) {
for my $j ( 1 .. @b ) {
$d[ $i ][ $j ] = (
$a[ $i - 1 ] eq $b[ $j - 1 ]
? $d[ $i - 1 ][ $j - 1 ]
: 1 + min( $d[ $i - 1 ][ $j ], $d[ $i ][ $j - 1 ], $d[ $i - 1 ][ $j - 1 ] )
) ;
}
}
return $d[ @a ][ @b ] ;
}
Following are what my wordlists can do. Something tells me that, when we get to 16-letter words, it's more a bunch of disconnected nodes than a graph.
1718 3-letter words
6404 4-letter words
13409 5-letter words
20490 6-letter words
24483 7-letter words
24295 8-letter words
19594 9-letter words
13781 10-letter words
8792 11-letter words
5622 12-letter words
3349 13-letter words
1851 14-letter words
999 15-letter words
514 16-letter words
My solver isn't perfect, and the first thing I'd want to add is ensuring that both the starting and ending words are actually in the word list. Without that, your code goes on forever.
So, I won't show off the whole program below, but it does use Storable, Graph and feature qw{say}.
dijkstra( $graph , 'foo' , 'bar' ) ;
# -------------------------------------------------------------------
# context-specific perl implementation of Dijkstra's Algorithm for
# shortest-path
sub dijkstra {
my ( $graph, $source, $target, ) = @_ ;
# the graph pre-exists and is passed in
# $source is 'foo', the word we're starting from
# $target is 'bar', the word we're trying to get to
my @q ; # will be the list of all words
my %dist ; # distance from source. $dist{$source} will be zero
my %prev ; # this holds our work being every edge of the tree
# we're pulling from the graph.
# we set the the distance for every node to basically infinite, then
# for the starting point to zero
for my $v ( $graph->unique_vertices ) {
$dist{$v} = 1_000_000_000 ; # per Wikipeia, infinity
push @q, $v ;
}
$dist{$source} = 0 ;
LOOP: while (@q) {
# resort, putting words with short distances first
# first pass being $source , LONG WAY AWAY
@q = sort { $dist{$a} <=> $dist{$b} } @q ;
my $u = shift @q ;
# say STDERR join "\t", $u, $dist{$u} ;
# here, we end the first time we see the target.
# we COULD get a list of every path that's the shortest length,
# but that's not what we're doing here
last LOOP if $u eq $target ;
# this is a complex and unreadable way of ensuring that
# we're only getting edges that contain $u, which is the
# word we're working on right now
for my $e (
grep {
my @a = @$_ ;
grep {/^${u}$/} @a
} $graph->unique_edges
) {
# $v is the word on the other end of the edge
# $w is the distance, which is 1 because of the problem
# $alt is the new distance between $source and $v,
# replacing the absurdly high number set before
my ($v) = grep { $_ ne $u } @$e ;
my $w = 1 ;
my $alt = $dist{$u} + $w ;
if ( $alt < $dist{$v} ) {
$dist{$v} = $alt ;
$prev{$v} = $u ;
}
}
}
my @nodes = $graph->unique_vertices ;
my @edges = $graph->unique_edges ;
return {
distances => \%dist,
previous => \%prev,
nodes => \@nodes,
edges => \@edges,
} ;
}
I return lots of stuff, but the part really necessary is %prev, because that, $source and $target are everything you need. Assuming we're trying to go from FOR to FAR, a number of words will satisfy
$prev{FOR}, but it's the one we're wanting. In the expanded case of FOO to BAR, $prev->{BAR} = 'FAR', $prev->{FAR} is 'FOR', and $prev->{FOR} is 'FOO'.And nothing in there is complex. It's all really hashes or arrays or values. Nothing a programmer should have any problem with.
CPAN has a number of other modules of use: Graph::Dijkstra has that algorithm already written, and Graph::D3 allows you to create a graph in such a way that you can use it in D3.js. Plus, there are a number of modules in Algorithm::* that do good and useful things. So go in, start playing with it. It's deep, there are weeds, but it isn't scary.
