So Richard mailed this to p5p, and it made me wonder, what's the shortest word ladder to get from ping to perl. i.e.
+-+-+-+-+ |p|e|r|l| +-+-+-+-+ | | | | | +-+-+-+-+ ... +-+-+-+-+ | | | | | +-+-+-+-+ |p|i|n|g| +-+-+-+-+
Well, the theoretically optimal word ladder would only change 1 letter at a time, so would have to be
+-+-+-+-+ |p|e|r|l| +-+-+-+-+ |p| | | | +-+-+-+-+ |p| | | | +-+-+-+-+ |p|i|n|g| +-+-+-+-+
but I don't think that that's doable. (in English, at least).
So, suggestions for short but amusing ladders?
I found all these really nice Unicode box drawing characters but they don't seem to work on my Firefox. Fixed width fonts don't seem to be fixed width :-(
Got one in 11 steps:
perl peal peel peed peek peck pack pock pick pink ping
Found using a little Perl script, it goes without saying.
Re:in 11 steps
bart on 2009-05-31T00:09:38
Why are you making the detour from "peck" to "pick"?Re:in 11 steps
Yanick on 2009-05-31T02:15:25
... ah... emm...
that will show me to try to perform any type of mental activity before my first mug of coffee.
:-)
Using my
ping
pint
pent
pert
perl
I didn't bother to go through 6 word solutions - there are a lot of them.
Here is the program that I wrote to find this:
#!
use strict;
use warnings;
open(DICT, "/usr/share/dict/words") or die "Can't open words: $!";
my %is_word;
while () {
chomp();
$is_word{lc($_)}++;
}
delete $is_word{pino};
delete $is_word{penk};
my %prev_word;
my @list = "perl";
WORD: while (@list) {
my $word = shift @list;
my @c = split
for my $pos (0..$#c) {
for my $char ("a".."z") {
local $c[$pos] = $char;
my $new_word = join "", @c;
if ($is_word{$new_word}) {
$prev_word{$new_word} ||= $word;
push @list, $new_word;
last WORD if $new_word eq "ping";
}
}
}
}
my $word = "ping";
print "$word\n";
until ($word eq "perl") {
$word = $prev_word{$word};
print "$word\n";
}
dictionary Re:5 is the shortest
n1vux on 2009-06-01T18:12:10
>
The original Unix* usr/dict/words file was always skewed by Bell Labs terminology. The crossword fanciers' online dict files are usually better for word puzzles. Links to such at foot of my Boston.PM talk on Cheating at Word Puzzles with Perl http://world.std.com/user/wdr/x/wesun/WESun.html .
I remember liking thzweb2 file, with web2a good for common phrase puzzles.Not that the larger dict matters for this puzzle since there is such a short ladder already, but 'words' having only qw(peal peel perk) as perl adjacencies, the NI2/web2 having more might have been expected to help
$ perl ladder.pl perl web2.txt | fmt
.erl|p.rl|pe.l|per.
herl jerl merl peal peel pell peri perk perm pern pert pirl purlbut of course the bigger the wordbase thzslower it runs.
The offered program is sensitive to reversal of ping and perl.
Re:dictionary Re:5 is the shortest
btilly on 2009-06-01T18:26:37
Sensitive how? If perl is not in your dictionary, then reversing the two will result in your never finding perl. If there are multiple paths, reversing can change which path you find. Otherwise it should run forwards as well as backwards.
It admittedly lacks when it comes to efficiency. However given that most of the time on my machine was scanning the file, I didn't care to optimize.
Re:dictionary Re:5 is the shortest
n1vux on 2009-06-01T19:45:55
Even if Perl is in dict, starting at perl is faster since it has fewer adjacent ladder words, so search tree starts less bushy (and on average will reamain so), and more next-move-win states since ping has more adjacency.
Most of the time shouldn't be in file scan unless your machine has no disk cache or the program ran correctly the first and only time! With cache, I am seeing 124ms on building %is_word with a small dict, twice as much loading half dozen dicts including moby. Oh wait, I made one small tweak to achieve that
... my $n = length($start ); # add
...
while () {
chomp();
next unless length() == $n; # add
$is_word{lc($_)}++;
}the cost of rebalancing the much smaller hash is much less. To build a full dict is more like 5000ms, so yes, tha would be dominating. Don't hash what you don't need!
maybe tonight or weekend i can bench some otheralgos, eg the meet in the middle / alternate ends strategy and the grep f($word), keys tactic. Need something better to try to answer if there is ANY connection from
ladder
ramrodstarting from ping, with a gob of dicts loaded, I still don't to theoretical 3-move 4-ladder, but this is cute -
perl
pern
penn
peng
pingnot that I'd allow many of those in a game of Scr@bbl3* either.
but [characters] don't seem to work on my Firefox. Fixed width fonts don't seem to be fixed width
:-(
That's hardly the fault of the web browser. http://www3.pic-upload.de/30.05.09/97zl.png
Get DejaVu Sans Mono, which I like to call a real fucking font.
See http://perlmonks.org/?node_id=558342
Perhaps I am misremembering but I believe at least one of the solutions in that thread (or the one it references) gives all possible "best" solutions.
Of course that thread was about optimizing for runtime speed and not fun ladders/bridges but it was fun anyway.
Hmmm, I seem to've got lost somewhere along the way and taken a few detours:
Perl
purl
pure
pube
rube
Ruby
rubs
pubs
puns
pins
ping
Those Ruby folks can get to pubs a lot quicker than us ...
