Rosetta Code

So I signed up at rosetta code the other day (guess I get a little bored on vacations…). For those of you who are not familiar with the site (visit it), it basically a collection of problems with solutions written in all sort of languages. So I glanced at the open problems for my favourite language, and saw a few Fibonacci related tasks that are just ripe for the taking. The first few problems were too simple to write about, but one of these problems (Fibonacci word fractal) caught my attention, and made a good experience to share here.

Well, in short, the Fibonacci word \(f(n)\) is constructed by concatenating \(f(n-1)\) with \(f(n-2)\), where \(f(0)=“1”\) and \(f(1)=“0”\):

word	value
\(f(0)\)	\(“1”\)
\(f(1)\)	\(“0”\)
\(f(n)\)	\(_f(n-1) \cdot f(n-2)\)

The fractal is defined by the word \(f(n)\) where \(n \rightarrow \infty\), and the rules for constructing the fractal from the word are:

For i = 0 to f(n).length
  Draw a segment forward 
  If current Character is '0'
    If i is even turn left
    Else if i is odd turn right

When I saw it, it reminded me SVG paths, so I thought, why not create a SVG image instead of ascii art? Turning right or left relatively with drawing of only straight lines fits perfectly to SVG path lineTo command. So, the idea is to convert a fibonacci word into a seqeunce of commands.

First thing I had to do, was to get the Fibonacci word. this can be easily achieved with an Iterator, note that I’m gonna show here a more complicated with better performance variant of the code I submitted to rosetta code.

val it = Iterator.iterate((Seq('1'),Seq('0'))){
  case (f1,f2) => (f2,f2++f1)
}.map(_._1)
//let's take f(20) as our word
val word = it.drop(20).next

well, now I needed to translate the left and right turns into absolute Up/Left/Down/Right movements. ok, that’s simple too. Since a direction is based on a preceding direction, we need “turning functions”:

val leftTo: PartialFunction[Char,Char] = 
  Map('R' -> 'U', 'U' -> 'L', 'L' -> 'D', 'D' -> 'R')
val rightTo: PartialFunction[Char,Char] = 
  Map('R' -> 'D', 'D' -> 'L', 'L' -> 'U', 'U' -> 'R')

and with these in hand, a simple(?) fold would do the trick:

/* The fold should result with a tuple of (Vector[Char],Boolean)
 * The Boolean value signifies if the char index is even (true) 
 * or odd (false), and is not needed after the fold.
 */
word.foldLeft((Vector('R'),true)){
  case ((v,parity),'1') => (v :+ v.last, !parity)
  case ((v,true),'0')   => (v :+ leftTo(v.last), false)
  case ((v,false),'0')  => (v :+ rightTo(v.last), true)
}._1

But since we’re interested in an efficient solution, and the resulting sequence from the fold still needs to be traversed again to generate the suitable commands, I’ll rewrite the turning functions & the fold to be less clear, but the fold will result in (almost) exactly what we need.

type SVGCommand = (Char,Int) // now you see where I'm getting at... right?
val leftTo: PartialFunction[SVGCommand,SVGCommand] = {
  case ('h',i) if i > 0 => ('v',-1)
  case ('h',i) if i < 0 => ('v',1)
  case ('v',i) if i > 0 => ('h',1)
  case ('v',i) if i < 0 => ('h',-1)
}
val rightTo: PartialFunction[SVGCommand,SVGCommand] = {
  case ('h',i) if i > 0 => ('v',1)
  case ('h',i) if i < 0 => ('v',-1)
  case ('v',i) if i > 0 => ('h',-1)
  case ('v',i) if i < 0 => ('h',1)
}

and the fold will now look like:

val commands = word.foldLeft(Vector('h' -> 1),true){
  case ((v,parity),'1') if v.last._2 > 0 => 
    (v.init :+ (v.last._1, v.last._2 + 1), !parity) 
  case ((v,parity),'1') if v.last._2 < 0 => 
    (v.init :+ (v.last._1, v.last._2 - 1), !parity)
  case ((v,true), '0') => (v :+ leftTo(v.last), false)
  case ((v,false),'0') => (v :+ rightTo(v.last), true)
}._1

OK, so the “hard work” is done. All we need now, is to create the SVG:

//just trust me with the width, height and starting position... it works. 
val buff = new StringBuilder("""<svg height="172" width="411">""" + 
"""<path style="stroke:#000;stroke-width:1" """ + 
"""stroke-linejoin="miter" fill="none" d="M 2 170 """)
commands.foreach{case (c,i) => buff.append(s" $c $i")}
buff.append("\"/></svg>")
println(buff.mkString) //or write to a file, or whatever...

and here’s the output:

Final version of the code, optimized a bit more (exploiting the fold to populate the handler instead of creating an entire unneeded collection), which takes arguments to generate the image to your liking is given here:

  /**
   * @param n                - The Fibonacci word to draw f(n)
   * @param                  - height image height
   * @param                  - width  image width
   * @param xStart           - X coordinate to start the path from
   * @param yStart           - Y coordinate to start the path from
   * @param color            - path's color
   * @param lengthMultiplier - control how long segments are
   * @param stringHandler    - input function to handle appends
   * @return the SVG string
   */
  def drawFibonacciFractal(n: Int, height: Int, width: Int, xStart: Int, yStart: Int, 
      color: String, lengthMultiplier: Int)(stringHandler: String => Unit): Unit = {

    type SVGCommand = (Char,Int)

    val leftTo: PartialFunction[SVGCommand,SVGCommand] = {
      case ('h',i) if i > 0 => ('v',-1)
      case ('h',i) if i < 0 => ('v',1)
      case ('v',i) if i > 0 => ('h',1)
      case ('v',i) if i < 0 => ('h',-1)
    }

    val rightTo: PartialFunction[SVGCommand,SVGCommand] = {
      case ('h',i) if i > 0 => ('v',1)
      case ('h',i) if i < 0 => ('v',-1)
      case ('v',i) if i > 0 => ('h',-1)
      case ('v',i) if i < 0 => ('h',1)
    }

    stringHandler(s"""<svg height="${height}" width="${width}">""" + 
s"""<path style="stroke:${color};stroke-width:1" """ + 
s"""stroke-linejoin="miter" fill="none" d="M ${xStart} ${yStart}""")

    val last = Iterator.iterate((Seq('1'),Seq('0'))){
      case (f1,f2) => (f2,f2++f1)
    }.map(_._1).drop(n).next.foldLeft(('h' -> 1),true){
      case ((t,parity),'1') if t._2 > 0 => ((t._1, t._2 + 1), !parity)
      case ((t,parity),'1') if t._2 < 0 => ((t._1, t._2 - 1), !parity)
      case ((t,true), '0') => {
        stringHandler(s" ${t._1} ${t._2 * lengthMultiplier}")
        (leftTo(t) -> false)
      }
      case ((t,false),'0') => {
        stringHandler(s" ${t._1} ${t._2 * lengthMultiplier}")
        (rightTo(t) -> true)
      }
    }._1

    stringHandler(s""" ${last._1} ${last._2 * lengthMultiplier}\"/></svg>""")
  }

to get the example above (colored), in a file, one should execute:

val buff = new java.io.BufferedWriter(new java.io.FileWriter("/path/to/output/image.svg"))

buff.write("""<?xml version="1.0" encoding="utf-8"?>""" + 
"""<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/""" +
"""SVG/1.1/DTD/svg11.dtd">""")

drawFibonacciFractal(20, 172, 411, 2, 170, "#ffb01c", 1){
  s => buff.append(s)
}

buff.flush
buff.close

Blog.init();

Ok, first post. WOOHOOO! Just finished setting up everything: syntax highlighting & markdown. a little example (taken from here which I pimped up a bit) shows it:

Syntax highlighting is fun!

HTML

    <h1>HTML code</h1>
    <div class="some">This is an example</div>

Python

    def func():
      for i in [1, 2, 3]:
        print "%s" % i

Scala

    def fib(a: Int, b: Int): Stream[Int] = a #:: fib(b,a+b)
    fib(1,1).filter(_ % 2 == 0).take(10).toList

Java (deprecated)

    class HelloWorldApp {
      public static void main(String[] args) {
        System.out.println("Hello World!"); // Print the string to the console.
      }
    }

highlighting is done with highlight.js & markdown with pagedown extra

So, I’ll probably babble here about all kind of things I find interesting. Also, as the name says, I’m open to suggestions (So my wife just came up with a cool name… IM KEEPING IT!). apparently, coming up with a name for your blog, is quite hard…

anyway, hope to have some fun. see ya’ :)