Not for XSLT? More Fun with Project Euler

 

Here is another Project Euler problem that seems exactly what XSLT was not intended for:

 

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.

  

131

673

234

103

18

201

96

342

965

150

630

803

746

422

111

537

699

497

121

956

805

732

524

37

331

  

 

Find the minimal path sum, in matrix.txt (right click and ‘Save Link/Target As…’), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by only moving right and down.

My solution:

 

<xsl:stylesheet version="2.0"

 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"

 xmlns:xs="http://www.w3.org/2001/XMLSchema"

 xmlns:saxon="http://saxon.sf.net/"

 xmlns:mx="my:my" exclude-result-prefixes="xs saxon mx"

 >

 <xsl:output omit-xml-declaration="yes" indent="yes"/>

 

 <xsl:variable name="vMatrix" as="element()*">

  <xsl:variable name="vLines" as="xs:string*"

   select="tokenize(unparsed-text(‘matrix.txt’),’\s+’)[.]"/>

   <xsl:for-each select="$vLines">

     <line>

      <xsl:for-each select="tokenize(.,’,’)">

        <v><xsl:value-of select="."/></v>

      </xsl:for-each>

     </line>

   </xsl:for-each>

 </xsl:variable>

 

 <xsl:variable name="vDimension" as="xs:integer"

  select="count($vMatrix)"/>

 

 <xsl:template match="/">

  <xsl:sequence select="mx:path-minSum(1,1,0)"/>

 </xsl:template>

 

 <xsl:function name="mx:path-minSum" as="xs:integer"

  saxon:memo-function="yes">

  <xsl:param name="pX" as="xs:integer"/>

  <xsl:param name="pY" as="xs:integer"/>

  <xsl:param name="pcurSum" as="xs:integer"/>

 

  <xsl:variable name="curVal" as="xs:integer"

   select="mx:mtx($pX, $pY)"/>

 

  <xsl:sequence select=

   "if($pX eq $vDimension and $pY eq $vDimension)

      then $curVal

      else

        for $nextX in min(($vDimension, $pX+1)),

            $nextY in min(($vDimension, $pY+1)),

            $s1 in if($nextY gt $pY)

                    then

                     $pcurSum + $curVal

                     + mx:path-minSum($pX, $nextY, $pcurSum)

                    else 999999999999,

            $s2 in if($nextX gt $pX)

                    then

                     $pcurSum + $curVal

                     + mx:path-minSum($nextX, $pY, $pcurSum)

                    else 999999999999

          return

            min(($s1,$s2))

   "/>

 </xsl:function>

 

 <xsl:function name="mx:mtx" as="xs:integer"

  saxon:memo-function="yes">

  <xsl:param name="pX" as="xs:integer"/>

  <xsl:param name="pY" as="xs:integer"/>

 

  <xsl:sequence select="$vMatrix[$pY]/*[$pX]"/>

 </xsl:function>

</xsl:stylesheet>

 

 

Properties:

  • LOC:                                         65 – well-formatted code for readability.
  • Execution time:                  078 ms.
  • Time to write the code:  ~ 10 minutes.
Advertisements
This entry was posted in Project Euler. 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