[XSL-LIST Mailing List Archive Home] [By Thread] [By Date]

Re: [xsl] Word Ladders as an example of a "Find shortest path between two nodes in a graph" problem


Subject: Re: [xsl] Word Ladders as an example of a "Find shortest path between two nodes in a graph" problem
From: "Sean B. Durkin" <sean@xxxxxxxxxxxxxxxxx>
Date: Tue, 27 Nov 2012 22:47:11 +1100

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.

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-angry-to-happy-in-20-steps/

Any feedback about this implementation and suggestions for further
optimization are welcome.


Current Thread
Keywords