Stories
Slash Boxes
Comments
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

Journal of nicholas (3034)

Saturday May 30, 2009
05:40 AM

Word ladder

[ #39052 ]

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 :-(

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.
  • 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. :-)

    • Why are you making the detour from "peck" to "pick"?
      • ... ah... emm...

        that will show me to try to perform any type of mental activity before my first mug of coffee. :-)

  • Using my /usr/share/words/dict I found 3 different 5 word "solutions". However I disagreed with the dictionary on whether pino and penk are really English words. (Or piro for that matter, but that was in the same line that used pino.) That left just one solution:

    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:

    #! /usr/bin/perl
    use strict;
    use warnings;

    open(DICT, "/usr/share/dict/words") or die "Can't open words: $!";
    m

    • >

      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/~wdr/x/wesun/WESun.html [std.com] .
      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

      --
      Bill
      # I had a sig when sigs were cool
      use Sig;
      • 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.

        • 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

          --
          Bill
          # I had a sig when sigs were cool
          use Sig;
  • 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 [pic-upload.de]

    Get DejaVu Sans Mono [sf.net], which I like to call a real fucking font [diveintomark.org].

  • See http://perlmonks.org/?node_id=558342 [perlmonks.org]

    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 ...