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

["Sean B. Durkin" <sean@xxxxxxxxxxxxxxxxx>]

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.