[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: Dimitre Novatchev Date: Tue, 27 Nov 2012 04:50:09 -0800

```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=
bcount(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:
>>
>>
>>
ry-to-happy-in-20-steps/
>>
>> 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.

```