Word Ladders, or How to go from “angry” to “happy” in 20 steps

Acknowledgement: To Brandon, the person who attracted my attention to this problem.

From Wikipedia, the free encyclopedia:

A word ladder (also known as a doublets, word-links, or Word golf) is a word game invented by Lewis Carroll. A word ladder puzzle begins with two given words, and to solve the puzzle one must find the shortest chain of other words to link the two given words, in which chain every two adjacent words (that is, words in successive steps) differ by exactly by one letter.

As with the original game of Lewis Carroll, each step consists of a single letter substitution.

My struggle to find a solution to this problem processed into these stages:

1.   Total lack of understanding and trying to apply brute force approaches, only to realize what astronomical effort was involved and that “brute force” wasn’t readily definable.

2.   “Discovering” the idea that when playing with four-letter words we only need the 4-letter words part of a dictionary.

3.   Thinking hard how to pre-process an N-letter projection of a dictionary into a structure that would be more suitable for solving word-ladders.

4.   Finally being told that the structure I was trying to invent is called a graph

So, the main idea is that the set of N-letter words from an English dictionary is represented as a graph, where every node is a word from the dictionary, and there is an arc between two nodes exactly when the two words in these nodes differ only in a single letter.

Obviously, any such graph is undirected – if there is an arc between node N1 and N2, then there is also an arc between N2 and N1.

Finding the shortest chain of words is finding the shortest path in this graph that connects the two nodes. This problem has a well-known solution, called BFS (Breadth-First Search).

What may be new here is that the solution we have here is implemented in XSLT.

There were a number of subtasks:

ST1: Split a dictionary into a set of dictionaries, each containing only words of the same size N, where N = 1, 2, 3, 4, …

This one is quite natural and easy:

MakeLength-SizedDicts.xsl:

<xsl:stylesheet version=”2.0” xmlns:xsl=”http://www.w3.org/1999/XSL/Transform“>
 <xsl:output omit-xml-declaration=”yes” indent=”yes“/><xsl:template match=”/*“>
        <xsl:for-each-group select=”w” group-by=”string-length()“>
<xsl:sort select=”string-length()“/>
       <xsl:sort select=”lower-case(.)“/>       <xsl:result-document href=
           “file:///c:/temp/delete/dictSize{string-length()}.txt”>
             <xsl:for-each select=”current-group()“>
                 <xsl:value-of select=”lower-case(.), ‘&#0xA0; ‘“/>
             </xsl:for-each>
          </xsl:result-document>           <xsl:result-document href=
          “file:///c:/temp/delete/dictSize{string-length()}.xml”>
           <words>
            <xsl:for-each select=”current-group()“>
              <w><xsl:value-of select=”lower-case(.)“/></w>
            </xsl:for-each>
           </words>
          </xsl:result-document>
        </xsl:for-each-group>
 </xsl:template>
</xsl:stylesheet>

Thus we have produced the following separate dictionaries: dictSize1.xml, dictSize2.xml, …, dictSize24.xml .

ST2: For a given dictionary dictSizeN, produce a dictionary – graph:

AddNeighborsNaive.xsl:

<xsl:stylesheet version=”2.0
xmlns:xsl=”http://www.w3.org/1999/XSL/Transform&#8221;
   xmlns:my=”my:my
xmlns:xs=”http://www.w3.org/2001/XMLSchema&#8221;
  exclude-result-prefixes=”my xs“>
<xsl:output omit-xml-declaration=”yes” indent=”yes“/> 

 <xsl:key name=”kFindWord” match=”w” use=”.“/>

 <xsl:variable name=”vACode” as=”xs:integer
select=”string-to-codepoints(‘a’)“/>

 <xsl:variable name=”vDict” select=”/“/>

 <xsl:template match=”/*“>
   <xsl:variable name=”vPass1“>
       <words>
           <xsl:for-each select=
               “w[generate-id()=generate-id(key(‘kFindWord’, .)[1])]”>
           <word>
             <xsl:sequence select=”.“/>
             <xsl:sequence select=”my:neighbors(.)“/>
           </word>
        </xsl:for-each>
      </words>
   </xsl:variable>

  <xsl:apply-templates select=”$vPass1” mode=”pass2“/>
</xsl:template>

 <xsl:template match=”node()|@*” mode=”pass2“>
   <xsl:copy>
       <xsl:apply-templates select=”node()|@*” mode=”#current“/>
</
xsl:copy>
 </xsl:template> 

 <xsl:template match=”word” mode=”pass2“>
   <word>
      <xsl:sequence select=”w“/>
      <xsl:apply-templates select=”nb” mode=”pass2“/>
   </word>
 </xsl:template>

 <xsl:function name=”my:neighbors“>
    <xsl:param name=”pCurrentWord” as=”xs:string“/> 

    <xsl:variable name=”vWordCodes” select=”string-to-codepoints($pCurrentWord)“/> 

  <xsl:for-each select=”1 to count($vWordCodes)“>
    <xsl:variable name=”vPos” select=”.“/>
    <xsl:variable name=”vLetterCode” select=”$vWordCodes[$vPos]“/> 

    <xsl:for-each select=”(1 to 26)[. ne $vLetterCode – $vACode+1]“>
        <xsl:variable name=”vNewCode” select=”. -1 +$vACode“/>
        <xsl:variable name=”vNewWordCodes” select=
         “subsequence($vWordCodes, 1, $vPos -1),
          $vNewCode,
          subsequence($vWordCodes,$vPos +1)
         “/>

        <xsl:variable name=”vNewWord” select=”codepoints-to-string($vNewWordCodes)“/> 

        <xsl:if test=”key(‘kFindWord’, $vNewWord, $vDict)“>
         <nb><xsl:sequence select=”$vNewWord“/></nb>
      </xsl:if>
    </xsl:for-each>
  </xsl:for-each>
 </xsl:function>
</xsl:stylesheet>

This transformation is applied on an N-letter words dictionary which in the case of N = 5 looks like:

<words>

   <w>aalii</w>

   <w>aaron</w>

   <w>abaca</w>

   <w>aback</w>

   <w>abaff</w>

   <w>abaft</w>

   <w>abama</w>

   <w>abase</w>

   <w>abash</w>

   <w>abask</w>

   <w>abate</w>

   <w>abave</w>

   <w>abaze</w>

   <w>abbas</w>

   <w>abbey</w>

   <w>abbie</w>

   <w>abbot</w>

   <w>abdal</w>

   <w>abdat</w>

   <w>abeam</w>

       .   .   .   .   .   .

</words>

And produces our desired dictionary-graph, which looks like this:

<words>

   <word>

      <w>aalii</w>

   </word>

   <word>

      <w>aaron</w>

      <nb>baron</nb>

      <nb>saron</nb>

      <nb>acron</nb>

      <nb>apron</nb>

   </word>

   <word>

      <w>abaca</w>

      <nb>araca</nb>

      <nb>abama</nb>

      <nb>aback</nb>

   </word>

       .   .   .   .   .   .

</words>

ST3: Now that we have the graph, we are ready to implement the “Find Shortest Path” BFS algorithm:

findChainOfWords.xsl:

<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 method=”text“/>

<xsl:key name=”kFindWord” match=”w” use=”.“/>  <xsl:param name=”pStartWord  select=”‘nice’” as=”xs:string“/>
    <xsl:param name=”pTargetWord” select=”‘evil’” as=”xs:string“/>     <xsl:variable name=”vDictGraph” select=”/“/>      <xsl:template match=”/*“>
        <xsl:sequence select=”my:chainOfWords($pStartWord,
$pTargetWord)
“/>
    </xsl:template>        <xsl:function name=”my:chainOfWords” as=”xs:string*“>
     <xsl:param name=”pStartWord” as=”xs:string“/>
     <xsl:param name=”pEndWord” as=”xs:string“/>        <xsl:sequence select=
         “if(not(key(‘kFindWord’, $pStartWord, $vDictGraph))
           or
               not(key(‘kFindWord’, $pEndWord, $vDictGraph))
               )
               then error((), ‘A word-argument isn`t found in the dictionary.’)
               else ()
   “/> 

  <xsl:variable name=”vStartWord” as=”xs:string
select=key(‘kFindWord’, $pStartWord, $vDictGraph)
                       [count(../*)  lt  count(key(‘kFindWord’, $pEndWord,
$vDictGraph)/../* )
]
  |
     key(‘kFindWord’, $pEndWord, $vDictGraph)
                [count(../*) le count(key(‘kFindWord’, $pStartWord,
$vDictGraph)/../*)
]
  “/> 

   <xsl:variable name=”vEndWord” as=”xs:string
       select=”($pStartWord, $pEndWord)[not(. eq $vStartWord)]“/>

   <xsl:variable name=”vStartNode” as=”element()“>
    <node>
        <value><xsl:value-of select=”$vStartWord“/></value>
    </node>
   </xsl:variable> 

   <xsl:sequence
select=”my:processQueue($vStartNode, $vEndWord, $vStartWord)“/>
 </xsl:function> 

 <xsl:function name=”my:processQueue  as=”xs:string*“>
     <xsl:param name=”pQueue” as=”element()*“/>
     <xsl:param name=”pTarget” as=”xs:string“/>
     <xsl:param name=”pExcluded” as=”xs:string*“/> 

    <xsl:sequence select=
     “if(not($pQueue))
         then ()
         else
for $vTop in $pQueue[1],
                  $vResult in my:processNode($vTop, $pTarget, $pExcluded)[1]
             return
               if($vResult/self::result)
                 then string-join($vResult/*, ‘ ==> ‘)
                 else my:processQueue((subsequence($pQueue, 2), $vResult/*),
                                                                $pTarget,
                                                                ($pExcluded, $vResult/*/value)
                                                               )“/>
 </xsl:function> 

 <xsl:function name=”my:processNode” as=”element()“>
     <xsl:param name=”pNode” as=”element()“/>
     <xsl:param name=”pTarget” as=”xs:string“/>
     <xsl:param name=”pExcluded” as=”xs:string*“/> 

     <xsl:variable name=”vCurWord
           select=”key(‘kFindWord’, $pNode/value, $vDictGraph)“/> 

     <xsl:variable name=”vNeighbors
select=”$vCurWord/following-sibling::*“/>
     <xsl:choose>
         <xsl:when test=”$pTarget = $vNeighbors“>
              <xsl:variable name=”vResult  as=”element()“>
                <result>
                  <xsl:sequence select=”my:enumerate($pNode)“/>
                  <w><xsl:sequence select=”$pTarget“/></w>
                </result>
              </xsl:variable>

               <xsl:sequence select=”$vResult“/>
         </xsl:when>
         <xsl:otherwise>
            <xsl:variable name=”vMustAdd” as=”element()“>
               <add>
                 <xsl:for-each select=”$vNeighbors[not(. = $pExcluded)]“>
                   <node>
                    <parent><xsl:sequence select=”$pNode“/></parent>
                    <value><xsl:value-of select=”.“/></value>
                   </node>
                 </xsl:for-each>
               </add>
         </xsl:variable> 

        <xsl:sequence select=”$vMustAdd“/>
      </xsl:otherwise>
   </xsl:choose>
 </xsl:function> 

 <xsl:function name=”my:enumerate” as=”element()*“>
     <xsl:param name=”pNode” as=”element()?“/> 

      <xsl:sequence select=
        “if($pNode)
            then (my:enumerate($pNode/parent/node), $pNode/value)
            else ()“/>
  </xsl:function>
</xsl:stylesheet>

And sure enough, we get this result:

 

evil ==> emil ==> emir ==> amir ==> abir ==> abie ==> able ==> aile ==> nile ==> nice

The first variant of this solution seems encouraging. But it takes a while – especially on my 9-year old Pc, which has 2GB of RAM, and a tiny cache. For example, the 8-parts chain connecting thus to else took 118 seconds (26 seconds on my newer, 2-year old PC).

Therefore, we are clearly in need of:

ST3: Optimizations:

Optimization1: Order the arc-words in increasing number of their own arcs. This means that we will first try the neighbor-node with the fewest number of neighbors.

To implement this optimization, we modify this part of the AddNeighborsNaive.xsl:

<xsl:template   match=”word”   mode=”pass2“>
<word>
<xsl:sequence select=”w“/>
<xsl:apply-templates   select=”nb”   mode=”pass2“/>
</word>
</xsl:template>

To:

<xsl:template match=”word” mode=”pass2“>
  <word>
     <xsl:sequence select=”w“/>
     <xsl:apply-templates select=”nb” mode=”pass2“>
        <xsl:sort select=”count(key(‘kFindWord’, .)/../nb)
              data-type=”number“/>
      </xsl:apply-templates>
   </word>
 </xsl:template>

Now the time for producing the 8-parts chain connecting thus to else falls from 118 sec. to 107 sec. –  10% faster.

Optimization2: When adding new words/nodes in the queue, always add them by increasing Hamming Distance to the target word:

To implement this, I added to the transformation the following function:

<xsl:function name=”my:HammingDistance” as=”xs:integer“>
    <xsl:param name=”pStr1” as=”xs:string“/>
    <xsl:param name=”pStr2” as=”xs:string“/> 

    <xsl:sequence select=
     “count(f:zipWith(f:eq(),
                                        f:string-to-codepoints($pStr1),
                                        f:string-to-codepoints($pStr2)
                                        )
                                        [not(.)]
                   )
   “/>
 </xsl:function>

Here I am using FXSL – the f:zipWith() function, as well as the function implementing the Xpath eq operator and the FXSL HOF analogue of the standard Xpath function  string-to-codepoints().

In order for this to compile, one must add the following (or similar) imports:

 <xsl:import href=”../../../CVS-DDN/fxsl-xslt2/f/func-zipWith.xsl“/>
  <xsl:import href=”../../../CVS-DDN/fxsl-xslt2/f/func-Operators.xsl“/>
  <xsl:import href=”../../../CVS-DDN/fxsl-xslt2/f/func-standardStringXpathFunctions.xsl“/>

This will not be needed if you were using XSLT 3.0 – then the above function would be:

<xsl:function name=”my:HammingDistance” as=”xs:integer“>
    <xsl:param name=”pStr1” as=”xs:string“/>
    <xsl:param name=”pStr2” as=”xs:string“/> 

  <xsl:sequence select=
     “count(map-pairs(f:eq#2,
                                          string-to-codepoints($pStr1),
                                          string-to-codepoints($pStr2)
                                         )
                                     [not(.)]
                    )
   “/>
 </xsl:function>

 But one would still need to write the f:eq() function.

The new function is used to change this code in my:processNode():

    <xsl:variable name=”vMustAdd” as=”element()“>
           <add>
                <xsl:for-each select=”$vNeighbors[not(. = $pExcluded)]“>
                   <node>
                     <parent><xsl:sequence select=”$pNode“/></parent>
                     <value><xsl:value-of select=”.“/></value>
                  </node>
               </xsl:for-each>
           </add>
    </xsl:variable>
    <xsl:sequence select=”$vMustAdd“/>

 To this new code:

    <xsl:variable name=”vMustAdd” as=”element()“>
           <add>
                <xsl:for-each select=”$vNeighbors[not(. = $pExcluded)]“>
                   <xsl:sort select=”my:HammingDistance(., $pTarget)
                                  data-type=”number“/>
                   <node>
                      <parent><xsl:sequence select=”$pNode“/></parent>
                      <value><xsl:value-of select=”.“/></value>
                   </node>
             </xsl:for-each>
           </add>
    </xsl:variable>
    <xsl:sequence select=”$vMustAdd“/>

The complete code of the transformation after this optimization becomes:

<xsl:stylesheet   version=”2.0
xmlns:xsl=”http://www.w3.org/1999/XSL/Transform
xmlns:xs=”http://www.w3.org/2001/XMLSchema
xmlns:f=”http://fxsl.sf.net/”   xmlns:my=”my:my
exclude-result-prefixes=”my   f xs“>
<xsl:import href=”../../../CVS-DDN/fxsl-xslt2/f/func-zipWith.xsl“/>
<xsl:import href=”../../../CVS-DDN/fxsl-xslt2/f/func-Operators.xsl“/>
<xsl:import href=”../../../CVS-DDN/fxsl-xslt2/f/func-standardStringXpathFunctions.xsl“/>
<xsl:output   method=”text“/>

<xsl:key   name=”kFindWord”   match=”w”   use=”.“/>

<xsl:param   name=”pStartWord”  select=”‘point’”   as=”xs:string“/>
<xsl:param   name=”pTargetWord”   select=”‘given’”   as=”xs:string“/>

<xsl:variable   name=”vDictGraph”   select=”/“/>

<xsl:template   match=”/*“>
<xsl:sequence   select=”my:chainOfWords($pStartWord,   $pTargetWord)“/>
</xsl:template>

<xsl:function   name=”my:chainOfWords”   as=”xs:string*“>
<xsl:param name=”pStartWord”   as=”xs:string“/>
<xsl:param name=”pEndWord”   as=”xs:string“/>

<xsl:sequence select=
if(not(key(‘kFindWord’,   $pStartWord, $vDictGraph))
        or
         not(key(‘kFindWord’, $pEndWord,   $vDictGraph))
        )
        then error((), ‘A word-argument isn`t   found in the dictionary.’)
        else ()
    “/>

<xsl:variable name=”vStartWord”   as=”xs:string”   select=
key(‘kFindWord’,   $pStartWord, $vDictGraph)
            [count(../*) lt count(key(‘kFindWord’, $pEndWord,
$vDictGraph)/../* )
]
  |
   key(‘kFindWord’, $pEndWord, $vDictGraph)
        [count(../*) le count(key(‘kFindWord’, $pStartWord,  $vDictGraph)/../*)]
  “/>

<xsl:variable name=”vEndWord”   as=”xs:string
select=”($pStartWord,   $pEndWord)[not(. eq $vStartWord)]“/>

<xsl:variable   name=”vStartNode”   as=”element()“>
<node>
<value><xsl:value-of   select=”$vStartWord“/></value>
</node>
</xsl:variable>

<xsl:sequence   select=
my:processQueue($vStartNode,   $vEndWord, $vStartWord)“/>
</xsl:function>

<xsl:function name=”my:processQueue”  as=”xs:string*“>
<xsl:param name=”pQueue”   as=”element()*“/>
<xsl:param name=”pTarget”   as=”xs:string“/>
<xsl:param name=”pExcluded”   as=”xs:string*“/>

<xsl:sequence select=
if(not($pQueue))
      then ()
      else
for $vTop in $pQueue[1],
         $vResult in   my:processNode($vTop, $pTarget, $pExcluded)[1]
            return
               if($vResult/self::result)
                 then string-join($vResult/*, ‘ ==>   ‘)
                 else   my:processQueue((subsequence($pQueue, 2),
$vResult/*),
                                                                    $pTarget,
                                                                    ($pExcluded,   $vResult/*/value)
                                                                   )“/>
</xsl:function>

<xsl:function name=”my:processNode”   as=”element()“>
<xsl:param name=”pNode”   as=”element()“/>
<xsl:param name=”pTarget”   as=”xs:string“/>
<xsl:param name=”pExcluded”   as=”xs:string*“/>

<xsl:variable name=”vCurWord
select=”key(‘kFindWord’,   $pNode/value, $vDictGraph)“/>

<xsl:variable name=”vNeighbors
select=”$vCurWord/following-sibling::*“/>

<xsl:choose>
<xsl:when test=”$pTarget   = $vNeighbors“>
<xsl:variable   name=”vResult”  as=”element()“>
<result>
<xsl:sequence   select=”my:enumerate($pNode)“/>
<w><xsl:sequence   select=”$pTarget“/></w>
</result>
</xsl:variable>

<xsl:sequence select=”$vResult“/>
</xsl:when>
<xsl:otherwise>
<xsl:variable name=”vMustAdd”   as=”element()“>
<add>
<xsl:for-each select=”$vNeighbors[not(.   = $pExcluded)]“>
<xsl:sort select=”my:HammingDistance(.,   $pTarget)
data-type=”number“/>
<node>
<parent><xsl:sequence   select=”$pNode“/></parent>
<value><xsl:value-of   select=”.“/></value>
</node>
</xsl:for-each>
</add>
</xsl:variable>

<xsl:sequence select=”$vMustAdd“/>
</xsl:otherwise>
</xsl:choose>
</xsl:function>

<xsl:function name=”my:enumerate”   as=”element()*“>
<xsl:param name=”pNode”   as=”element()?“/>

<xsl:sequence select=
if($pNode)
         then (my:enumerate($pNode/parent/node),   $pNode/value)
         else ()“/>
</xsl:function>

<xsl:function name=”my:HammingDistance”   as=”xs:integer“>
<xsl:param name=”pStr1”   as=”xs:string“/>
<xsl:param name=”pStr2”   as=”xs:string“/>

<xsl:sequence select=
count(f:zipWith(f:eq(),
                     f:string-to-codepoints($pStr1),
                     f:string-to-codepoints($pStr2)
                   )
                    [not(.)]
        )
  “/>
</xsl:function>
</xsl:stylesheet>

 The effect of this:

“point” to “given” (13-parts chain): 137 sec. before the optimization, 118 seconds after the optimization.

That is: another 14% increase of efficiency.  The combined effect of the two optimizations is speeding up the initial transformation with about 23%.

As I mentioned, my newer PC is about 4 times faster, which means that the maximum time for discovering a 5-letters shortest chain with Saxon 9.1.05 on a modern PC would be less than 35 seconds.

Another interesting fact is that these transformations take approximately 50% less time when run with XQSharp (XmlPrime), which lowers the maximum transformation time to 15 – 16 seconds.

Finally, here is the longest word chain I have found so far between 5-letter words (angry to happy):

angry ==> anury ==> anura ==> abura ==> abuta ==> aluta ==> alula ==> alala ==> alada ==> alida ==> alima ==> clima ==> clime ==> slime ==> slimy ==> saimy ==> saily ==> haily ==> haply ==> happy

And a few more interesting word chains:

story ==> novel :

novel ==> nevel ==> newel ==> tewel ==> tewer ==> teaer ==>
teaey ==> teary ==> seary ==> stary ==> story

fudge ==> cream:

cream ==> creat ==> crept ==> crepe ==> crape ==> grape ==>
gripe ==> gride ==> guide ==> guige ==> gudge ==> fudge

small ==> sized

sized ==> sizer ==> siver ==> saver ==> sayer ==> shyer ==>
shier ==> shiel ==> shill ==> shall ==> small

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s