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(.), ‘�xA0; ‘“/>
</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: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
Photo Via: aboutpetlife.com
XSLT: Riding the challenge 