Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
All,
In 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 a dictionary and each word differs from its adjacent partners by only one character.

I posted what I believe to be a very fast elegant solution:

#!/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) != lengt +h($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}} i +f ! 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'; }

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 Levenshtein Distance of 1. This is a one time up-front cost. Next, simply perform a breadth first search starting from one end and stopping when the other end is encountered.

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.

I appreciate any ideas on this.

* The original did allow for the endpoints not to be dictionary words.

Cheers - L~R


In reply to A Better Word Morph Builder by Limbic~Region

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    [Corion]: Aaah - you should be able to do this with overload, but I would hit somebody really hard if they constructed objects that are true but the empty string, and you not knowing about the domain knowledge where this makes sense
    [Eily]: you could tie a variable into not having the same value each time, if you like to make people who try to debug your code facepalm
    [Corion]: perl -wle 'package o; use overload q("") => sub {warn "str"; ""}, bool => sub{warn "bool"; 1}; package main; my $o={}; bless $o => o; print "Yay" if ($o && !length($o))'
    [Corion]: But people writing such code should document the objects they construct and why it makes sense for an object to be invisible as string while being true in a boolean context
    [hippo]: That's equal parts clever and horrendous.
    [Eily]: the overload version wouldn't return true with "$x" && !length $x though, I guess
    [hippo]: The more I look at this code, the more $x is a plain old scalar and the more this condition will never be true. I'm calling it a bug at this point.
    [hippo]: Thanks for your input which has soothed my sanity (a little)
    [Corion]: Eily: Sure - if you force both things into stringy things, then you break that magic. But that would also mean that you changed the expression, as now $x = 0.00 will be true instead of false as it were before
    [Corion]: Ah no, at least in my feeble experiments that doesn't change the meaning

    How do I use this? | Other CB clients
    Other Users?
    Others drinking their drinks and smoking their pipes about the Monastery: (9)
    As of 2017-07-27 13:40 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?
      I came, I saw, I ...
























      Results (413 votes). Check out past polls.