What words cannot describe

Lillies in my garden:

Is this the best?

Or maybe this?

Posted in Flowers, Photos | Leave a comment

Migrating to WordPress: https://dnovatchev.wordpress.com

As part of a global migration of spaces.live com to WordPress, I am migrating my blog to: https://dnovatchev.wordpress.com
 
Please, update your links, and sorry for the inconvenience.
 
From now on all my current and future posts will only be available at: https://dnovatchev.wordpress.com
Posted in Uncategorized | Leave a comment

The first Fibonacci Number that is zeroless-pandigital at both ends

Here is another Project Euler problem – this time a little-bit more challenging:

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn1 + Fn2 , where F1 = 1 and F2 = 1.

It turns out that F541  , which contains 113 digits, is the first Fibonacci number for which the last nine digits are 1-9 pandigital (contain all the digits 1 to 9, but not necessarily in order). And F2749  , which contains 575 digits, is the first Fibonacci number for which the first nine digits are 1-9 pandigital.

Given that Fk is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find k.”

Does this sound XSLT-ish? No, not at all.

This solution:

<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/">

 <xsl:import href="../../../f/func-Fibonacci.xsl"/>

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

 

 <xsl:template match="/">

  <xsl:sequence select=

  "f:getFiboBothEndingsPan9(3,2,1)

  "/>

 </xsl:template>

 

 <xsl:function name="f:getFiboBothEndingsPan9" as="xs:integer">

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

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

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

 

  <xsl:sequence select=

   "for $current in ($pPrev1 + $pPrev2) mod 1000000000

        return

           if(f:isPandigital19($current)

             and

              f:isPandigital19Head(f:fibo($pcurrentInd))

              )

             then $pcurrentInd

             else

               f:getFiboBothEndingsPan9($pcurrentInd+1, $current, $pPrev1)

   "/>

 </xsl:function>

 

 <xsl:function name="f:isPandigital19" as="xs:boolean">

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

 

  <xsl:sequence select=

  "for $s in xs:string($pN)

    return

          not(translate(‘123456789’, $s, ”))

  "/>

 </xsl:function>

 

 <xsl:function name="f:isPandigital19Head" as="xs:boolean">

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

 

   <xsl:sequence select="f:isPandigital19(f:head9($pN))"/>

 </xsl:function>

 

  <xsl:function name="f:head9" as="xs:integer">

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

 

   <xsl:sequence select=

    "xs:integer(substring(string($arg1), 1, 9))"/>

  </xsl:function>

</xsl:stylesheet>

has the following properties:

  • Execution time:                 34.6 sec.
  • LOC:                                       54 (~ 40 express the solution)
  • Time to write the code:  ~15 min.
  • Uses library:                       FXSL (the f:fibo() function for generating Fibonacci numbers)

The index of the first Fibonacci number with the required properties is more than 300 thousand and the number itself has more than 68 thousand digits.

Not satisfied with the speed of this solution? Want even faster? Then here’s something you may consider:

<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/">

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

 

 <xsl:template match="/">

  <xsl:sequence select=

  "f:getFiboBothEndingsPan9(3,2,1,2,1)

  "/>

 </xsl:template>

 

 <xsl:function name="f:getFiboBothEndingsPan9" as="xs:integer">

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

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

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

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

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

 

  <xsl:sequence select=

   "for $currentTail in ($pPrevTail1 + $pPrevTail2) mod 1000000000,

        $newHead1 in $pPrevHead1 + $pPrevHead2,

        $newHead2 in $pPrevHead1,

        $currentHead1 in if($newHead1 ge 10000000000000000)

                           then $newHead1 idiv 10

                           else $newHead1,

        $currentHead2 in if($newHead1 ge 10000000000000000)

                            then $newHead2 idiv 10

                            else $newHead2

        return

           if($currentHead1 ge 100000000

             and

              f:isPandigital19($currentTail)

             and

              f:isPandigital19

                    (xs:integer(substring(string($currentHead1),1,9))))

             then $pcurrentInd

             else

               f:getFiboBothEndingsPan9($pcurrentInd+1,

                                        $currentTail, $pPrevTail1,

                                        $currentHead1, $currentHead2

                                        )

   "/>

 </xsl:function>

 

 <xsl:function name="f:isPandigital19" as="xs:boolean">

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

 

  <xsl:sequence select=

  "for $s in xs:string($pN)

    return

          not(translate(‘123456789’, $s, ”))

  "/>

 </xsl:function>

</xsl:stylesheet>

We have added a a couple of lines of code and look what we have now:

  • Execution time:                     0.555 sec.
  • LOC:                                        55 (~ 43 express the solution)
  • Time to write the code:  ~10 min.

As witnessed in the Project Euler thread for this problem (one must have provided the correct answer in order to access this thread), many solutions took longer: from 3.3 seconds, to 30-40 minutes, to couple of hours.

One Python programmer even waited for the end of his brute-force solution … 12 days

Posted in Project Euler | 8 Comments

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.
Posted in Project Euler | Leave a comment

Fun with Project Euler

I have been having fun solving some Project Euler problems. Most of my 76 solutions were done in XSLT 2.0 last year.

For those who are busy arguing whether or not  XSLT is a programming language, here is one easy problem:

The 5-digit number, 16807=75, is also a fifth power. Similarly, the 9-digit number, 134217728=89, is a ninth power.

How many n-digit positive integers exist which are also an nth power?

Below is the solution, and it takes 20ms to run with Saxon 9.1.07:

<xsl:stylesheet version="2.0"
xmlns:xsl=http://www.w3.org/1999/XSL/Transform
xmlns:f=http://fxsl.sf.net/>

<xsl:import href="../../../f/func-exp.xsl"/>

<xsl:output method="text"/>

<xsl:template match="/">
  <xsl:sequence select=
   "
(: count( :)
       for $k in 1 to 9,
           $n in 1 to 23,
           $k-pwr-n in f:intppow($k,$n),
           $low in f:intppow(10,$n -1) -1,
           $high in f:intppow(10,$n)
        return
          if($k-pwr-n gt $low and $k-pwr-n lt $high)
           then ($k, $n, $k-pwr-n, ‘
‘)
           else()
   (: ) :)
   "/>
</xsl:template>
</
xsl:stylesheet>

 

f:intppow(k, n)  is an FXSL 2.x function with positive integer arguments that calculates kn.

And if all this is possible even now, imagine yourself working with XSLT 2.1 in the near future…

Posted in Project Euler | Leave a comment

Should XPath have virtual axes?

In his recent blog-article: “XPath needs virtual axes. Making XPath more XPathy?Rick Jelliffe sais:

I really like XPath2. I would never recommend anyone start with XPath1, unless you were doing very basic transformations with no text processing or data formatting.

But the niggle I have with XPath2 is that it is less XPath-y than XPath1. It does not significantly improve the central syntactical feature of XPaths: the location steps. (The only improvement that springs to mind is that XPath2 did improve the use of parentheses in location steps.) Instead, XPath2 provided much more conventional features like a for iterator. I think these significantly decrease the comprehensibility of an XPath, are anonymous and therefore require may comments to explain them, and fracture the line. To an extent, once you start to use nested syntaxes and iterators, why both using XPath at all?”

Rick gives this example:

find-rep( find-client(//manager/clients/client-ref)/rep-ref)/name

and proposes to improve the expression above by introducing “virtual axes” so that it could be written as:

//manager/clients/client-ref/find-client::rep-ref/find-rep::rep/name

So, curious reader, pause for a while, don’t read below, and think: has Rick uncovered a hole in XPath? 

Here is my answer:

What you are asking for can be expressed almost exactly in the same form (actually I prefer the current XPath 2.0 form of expression).

You are asking for:

//manager/clients/client-ref/find-client::rep-ref/find-rep::rep/name

One can write this in XPath 2.0 as:

//manager/clients/client-ref/find-client(.)/rep-ref/find-rep(.)/name

The current XPath way of expressing this is cleaner — no need for virtual axes.

This is a feature of XPath 2.0 that is not widely used and known: any function can be used as the current location step. The syntax rules that resolve its use are (at http://www.w3.org/TR/2007/REC-xpath20-20070123/#id-grammar):

[27] StepExpr ==> [38] FilterExpr ==> [41] PrimaryExpr

and the fact that a FunctionCall is a PrimaryExpr:

[41]   PrimaryExpr   ::=   Literal | VarRef | ParenthesizedExpr | ContextItemExpr | FunctionCall

 

Also, consider that the axes in XPath have been useful so far mainly because there are just a few of them. Imagine having to deal with zillions of axes and struggling to remember what they mean. And if everyone can introduce their own axes, then why bother with them at all?

Dear reader, it’s up to you to decide… as I have already done.

Posted in Uncategorized | 2 Comments

Optimized Repetitive Prepends, Part III: Understanding the Solution

 

In Part II of this post a solution was given to the problem presented in Part I:

"Can we implement an algorithm for repetitive prepends that will be run by P1 in linear time, in addition to its excellent linear performance of repetitive appends?"

The solution is implemented within the function my:prepend-iter() that is defined in the following way:

      <xsl:function name="my:prepend-iter">

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

        <xsl:param name="pstartSeq" as="element()*"/>

        <xsl:param name="pInserts" as="element()*"/>

 

          <xsl:sequence select=

           "if($pNumTimes gt 0)

               then

                 my:prepend-iter

                        ($pNumTimes -1,

                         $pstartSeq,

                         ($pInserts, reverse($vPrepends) )

                         )

               else

                 (reverse($pInserts), $pstartSeq)

            "/>

      </xsl:function>

The first argument passed to this function, pNumTimes, is the number of times to perform the prepend operation on the initial sequence pstartSeq, which is passed as the second argument.

The third argument has an auxiliary purpose. As its name, pInserts suggests, it contains the accumulation of all sequences that are to be prepended to pstartSeq.

The idea is to produce the final result only when pNumTimes  is zero, using at this time the accumulated prepends in pInserts and the initial sequence pstartSeq.

The idea of the algorithm is to replace the repetitive prepend operations with repetitive append operations, which are carried out by the xslt processor with linear complexity.

We notice that:

y2s ++ y1s ++ xs   =

reverse(  reverse(y1s) ++ reverse(y2s) ) ++ xs       (1)

Or in general, if we have N sequences:

y1s, y2s, …, yNs 

to be prepended to an initial sequence xs in that order,

yNs ++ yN-1s ++ … y2s ++ y1s ++ xs =

reverse(reverse(y1s)++reverse(y2s) ++ …

        …    ++ reverse(yNs) )     ++xs                 (2)

 

Remarkably, the argument of the outermost reverse() is a repetitive appends operation and it has only linear complexity with P1!

We have added N+1 reverse() operations, but each of them is of linear complexity, so the total complexity of implementing (2) is O(N).

Certainly, the function my:prepend-iter() we have demonstrated is a simplified case of the many different real world scenarios we may encounter that will require repetitive prepends. Nevertheless its use is sufficient to prove and demonstrate how such an O(N) algorithm can be constructed.

We could use essentially the same algorithm, with a modification that accepts as argument a function
next-prepend(), which produces the next sequence to be prepended. To signal the end of the repetitive prepend operation, we can use a convention that next-prepend() will indicate this by producing some special sequence, such as the empty sequence.

In case you may be wondering how can a function be passed as an argument to another function in XSLT, do read about FXSL.

Posted in Performance Optimization | Leave a comment