[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] Re: Word Ladders as an example of a "Find shortest pat
On Tue, Nov 27, 2012 at 3:47 AM, Sean B. Durkin <sean@xxxxxxxxxxxxxxxxx> wrote: > Dimitre, > > In relation to the XPath 3.0 implementation of *my:HammingDistance*, here > are two alternatives. > > _Alternative 1:__ > _ > fn:fold-left( > 0, > function($distance, $code-diff) > { > if ($code-diff) then $distance + 1 > else $distance > }, > let $c1 := string-to-codepoints($pStr1), > $c2 := string-to-codepoints($pStr1) return > for $i in 1 .. min(count($c1),count($c2)) return > $c1[$i] - $c2[$i] > ) > > __Alternative_ 2:__ > > _count( > let $c1 := string-to-codepoints($pStr1), > $c2 := string-to-codepoints($pStr1) return > for $i in 1 .. min(count($c1),count($c2)) return > 1[$c1[$i] eq $c2[$i]] > ) > > The count() function in alternative 2 could equally well be sum(). > > I'm not making any claims about the relative merits of these alternatives -- > just providing some food for thought. Sean, Why do you think these are better than: <xsl:sequence select= bcount(map-pairs(f:eq#2, string-to-codepoints($pStr1), string-to-codepoints($pStr2) ) [not(.)] ) b/> ? I am planning on what I hope will be significantly optimized Hamming distance implementation -- probably in a next post. Cheers, Dimitre > > Faithfully, > Sean B. Durkin > > > > On 27/11/2012 4:08 PM, Dimitre Novatchev wrote: >> >> Dear XSLT professionals, >> >> In case you are interested in solving the Word Ladders problem first >> formulated by Lewis Carroll, or just in an XSLT solution of the "Find >> shortest path in graph" problem, you might be interested to have a >> look at the implementation in my latest blog post: >> >> >> http://dnovatchev.wordpress.com/2012/11/26/word-ladders-or-how-to-go-from-ang ry-to-happy-in-20-steps/ >> >> Any feedback about this implementation and suggestions for further >> optimization are welcome. > -- Cheers, Dimitre Novatchev --------------------------------------- Truly great madness cannot be achieved without significant intelligence. --------------------------------------- To invent, you need a good imagination and a pile of junk ------------------------------------- Never fight an inanimate object ------------------------------------- To avoid situations in which you might make mistakes may be the biggest mistake of all ------------------------------------ Quality means doing it right when no one is looking. ------------------------------------- You've achieved success in your field when you don't know whether what you're doing is work or play ------------------------------------- Facts do not cease to exist because they are ignored. ------------------------------------- Typing monkeys will write all Shakespeare's works in 200yrs.Will they write all patents, too? :) ------------------------------------- I finally figured out the only reason to be alive is to enjoy it.
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|