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

[Michel Hendriksen <michel.hendriksen@xxxxx>]

Cool, thnx for the links!

On Tue, Nov 27, 2012 at 1:58 PM, Sean B. Durkin <sean@xxxxxxxxxxxxxxxxx>
wrote:
> Dimitre,
>
> I'm not making any claims about any alternatives being better or worse. I
am
> just offering food for thought.
>
> Faithfully,
> Sean.
>
>
> On 27/11/2012 11:50 PM, Dimitre Novatchev wrote:
>>
>> 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=
>>        count(map-pairs(f:eq#2,
>>                                    string-to-codepoints($pStr1),
>>                                    string-to-codepoints($pStr2)
>>                                    )
>>                                    [not(.)]
>>                       )
>>      />
>>
>>
>> ?
>>
>>
>> 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.