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

[Wolfgang Laun <wolfgang.laun@xxxxxxxxx>]

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.