Subject: Re: [xsl] Word Ladders as an example of a "Find shortest path between two nodes in a graph" problem From: Wolfgang Laun <wolfgang.laun@xxxxxxxxx> Date: Tue, 27 Nov 2012 09:17:21 +0100 |
Below is a variation on the stage that creates the graph, a little shorter and faster. Output is identical for a comprehensive list of 4 letter words. Cheers Wolfgang <xsl:stylesheet version="2.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:my="my:my" xmlns:xs="http://www.w3.org/2001/XMLSchema" exclude-result-prefixes="my xs"> <xsl:output omit-xml-declaration="yes" indent="yes"/> <xsl:function name="my:key-set" as="xs:string+"> <xsl:param name="word" as="xs:string"/> <xsl:for-each select="1 to string-length($word)"> <xsl:variable name="pos" select="."/> <xsl:sequence select="concat(substring($word, 1, $pos -1),'.', substring($word, $pos +1, string-length($word) -$pos))"/> </xsl:for-each> </xsl:function> <xsl:key name="kFindWord" match="w/text()" use="my:key-set(.)"/> <xsl:variable name="vDict" select="/"/> <xsl:template match="/"> <words> <xsl:apply-templates select="*"/> </words> </xsl:template> <xsl:template match="w"> <xsl:variable name="w" select="."/> <word> <xsl:sequence select="$w"/> <xsl:for-each select="my:key-set($w)"> <xsl:variable name="key" select="."/> <xsl:for-each select="key('kFindWord', $key, $vDict)"> <xsl:if test=". != $w"> <nb><xsl:sequence select="."/></nb> </xsl:if> </xsl:for-each> </xsl:for-each> </word> </xsl:template> </xsl:stylesheet> On 27/11/2012, Dimitre Novatchev <dnovatchev@xxxxxxxxx> 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. > > -- > 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.
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
[xsl] Word Ladders as an example of, Dimitre Novatchev | Thread | Re: [xsl] Word Ladders as an exampl, Michel Hendriksen |
[xsl] Word Ladders as an example of, Dimitre Novatchev | Date | Re: [xsl] Word Ladders as an exampl, Michel Hendriksen |
Month |