Friday, 5 September 2014

Scalatra

Just found this neat Scala project, Scalatra.
Quite amazing I did not know it... but looks pretty cool: I love the integration with Slick and Akka...

Friday, 29 August 2014

Another neat interview question: a kind of crossword puzzle

My friend had another interview question. You have already seen the first one.
This one is about crosswords. It involves graphs obviously.
Let me start by giving a brief overview of the problem he had to solve, and my Scala take on it ;-)
Question Imagine a crossword grid of size n x n containing letters. Given a dictionary of words, find all possible paths in the grid that match the words in the dictionary.
For Example:
MBC
ARA
NMO
is a 3x3 grid of letters, if the dictionary contains the word MAN, there are two paths possible: [(0,0), (0,1), (0,2)] and [(1,2), (0,1), (0,2)].

My Scala take on it
Let's define a Coord class that represents the grid coordinates - and a bunch of methods to work out the neighbours of a given coordinate:
  val gridSize = 3                                //> gridSize  : Int = 3
  case class Coord(val x: Int, y: Int) {
    def /\ = Coord(x, y - 1)
    def \/ = Coord (x, y + 1)
    def |> = Coord(x + 1, y)
    def <| = Coord(x - 1, y)
    def -/ = Coord(x + 1, y - 1)
    def -\ = Coord(x + 1, y + 1)
    def \- = Coord(x - 1, y - 1)
    def /- = Coord(x - 1, y + 1)
    def isValid = x >= 0 && x < gridSize && y >= 0 && y < gridSize
  }
  type Path = List[Coord]
  type Paths = List[Path]
The next method works out all valid neighbours for a given coordinate:
  def /\/\ (c: Coord) = List(c /\, c \/, c |>, c <|, c -/, c -\, c \-, c /-).filter(_.isValid)
For example:
  require((/\/\(Coord(1, 1))).size == 8)
  require((/\/\(Coord(0, 0))).size == 3)
Let's define a dictionary for our tests:
  val dict = Set("MAN", "ARM", "CAR")             //> dict  : scala.collection.immutable.Set[String] = Set(MAN, ARM, CAR)
  val dictMaxLength = dict.map(w => w.size).max   //> dictMaxLength  : Int = 3
The main algorithm is the following that enumerates all the paths between two nodes in the graph. Note that I restrict the path length based on the maximum of letters defined in the dictionary. This can be improved further using the dictionary (prefix.. etc. left as an exercise).
  def allPaths(from: Coord, to: Coord): Paths = {
    def allPathsRec(currentCoord: Coord, currentPath: Path): Paths = {
      if (currentPath.size > dictMaxLength) Nil
      else if (currentCoord == to) List(currentPath)
      else /\/\(currentCoord).filter(c => !(currentPath contains c)).flatMap(c => allPathsRec(c, c :: currentPath))
    }
    allPathsRec(from, List(from)).map(_.reverse)
  }    
As an example, the following will give you the diagonal:
allPaths(Coord(0, 0), Coord(2, 2))  //WordGrid.Paths = List(List(Coord(0,0), Coord(1,1), Coord(2,2)))
Before we test it, we need one final procedure: a def to generate all pairs of cells (from one cell to another cell):
  def fromsTos: List[(Coord, Coord)] = {
    val keys = dictMap.keySet.toList
    for {
      c1 <- keys
      c2 <- keys.filter(_ != c1)
    } yield (c1, c2)
  }
dictMap is the crossword definition:
val dictMap = Map(Coord(0, 0) -> 'M', Coord(1, 0) -> 'B', Coord(2, 0) -> 'C',
                  Coord(0, 1) -> 'A', Coord(1, 1) -> 'R', Coord(2, 1) -> 'A',
                  Coord(0, 2) -> 'N', Coord(1, 2) -> 'M', Coord(2, 2) -> 'O')  
Test
Time to put this to the test:
// Generates all possible pairs path in the grid
// List(List(Coord(0,2), Coord(0,1), Coord(0,0)),  ...
val allPairsPaths = fromsTos.map(t => allPaths(t._1, t._2)).flatten 
// Generates all words from the pairs path
// List(NAM, NRM, NRC, NAR, NMR, NR, NMO ....
val words = allPairsPaths.map(p => p.map(c => dictMap(c))).map(cs => cs.mkString)
// Combine the two lists, keep only what is in the dictionary
// List((MAN,List(Coord(0,0), Coord(0,1), Coord(0,2))), (CAR,List(Coord(2,0), Coord(2,1), Coord(1,1))) ....
val wordsPath = (words, allPairsPaths).zipped.map((_, _)).filter(t => dict contains t._1)
// Pretty print
wordsPath.foreach(wp => {println(s"Word ${wp._1} has path ${wp._2}")})
//> Word MAN has path List(Coord(0,0), Coord(0,1), Coord(0,2))
//| Word CAR has path List(Coord(2,0), Coord(2,1), Coord(1,1))
//| Word ARM has path List(Coord(0,1), Coord(1,1), Coord(0,0))
//| Word ARM has path List(Coord(0,1), Coord(1,1), Coord(1,2))
//| Word MAN has path List(Coord(1,2), Coord(0,1), Coord(0,2))
//| Word ARM has path List(Coord(2,1), Coord(1,1), Coord(0,0))
//| Word ARM has path List(Coord(2,1), Coord(1,1), Coord(1,2))
There are a few optimizations to do here and there. An interview question not easy to get right on a white board!

Some Scala Interview Questions

This is not for you. It is just a brain dump on Scala interview questions.. I like this site - questions like:

What is tail recursion? A hack to transform a recursive function into a for loop :-). Like the compute method there
What is function currying in Scala? It is a technique of transforming a function that takes multiple arguments into a function that takes a single argument. mult2 is mult1 after currying.
  def mult1(d1: Double, d2: Double) = d1 * d2     //> mult1: (d1: Double, d2: Double)Double
  def mult2(d1: Double) = (d2: Double) => d1 * d2 //> mult2: (d1: Double)Double => Double
  
  mult1(3, 4)                                     //> res0: Double = 12.0
  mult2(4)(3)                                     //> res1: Double = 12.0

Above can be applied to partially applied functions:
  def filter1[T](predicate: T => Boolean)(input: List[T]): List[T] = {
    input match {
      case head::tail => if (predicate(head)) head :: filter1(predicate)(tail) else filter1(predicate)(tail)
      case Nil => Nil
    }
  }                                               //> filter1: [T](predicate: T => Boolean)(input: List[T])List[T]
  val even = (i : Int) => i % 2 == 0              //> even  : Int => Boolean = 
  val odd = (i: Int) => i % 2 != 0                //> odd  : Int => Boolean = 
  
  filter1(even)((0 until 10) toList)              //> res2: List[Int] = List(0, 2, 4, 6, 8)
  filter1(odd)((0 until 10) toList)               //> res3: List[Int] = List(1, 3, 5, 7, 9)
To avoid calling the filter method with the same predicate, another cool variant is this one, using lazy val and _:
  def filter2[T](predicate: T => Boolean)(input: List[T]): List[T] = {
    lazy val rec = filter2(predicate) _
    input match {
      case head::tail => if (predicate(head)) head :: rec(tail) else rec(tail)
      case Nil => Nil
    }
  } 
And lots of other ways with partials and co. Quite neat.
What are implicit parameters? For me they are tricky... without an IDE, ... anyway. Best definition is obviously there
  implicit def myImplicit(i: Int): Boolean = i < 3//> myImplicit: (i: Int)Boolean
  def filter3[T](input: List[T])(implicit predicate: T => Boolean): List[T] = {
    input match {
      case head::tail => if (predicate(head)) head :: filter3(tail) else filter3(tail)
      case Nil => Nil
    }
  }                                               //> filter3: [T](input: List[T])(implicit predicate: T => Boolean)List[T]
  
  filter3[Int]((0 until 10) toList)               //> res5: List[Int] = List(0, 1, 2)

How to create enum? For me, Scala enums are weird...
  object PrimaryColours extends scala.Enumeration {
    type PrimaryColours = Value
    val Red, Green, Blue = Value
    
    def asInts(c: PrimaryColours): (Int, Int, Int) = {
      c match {
        case Red => (255, 0, 0)
        case Green => (0, 255, 0)
        case Blue => (0, 0, 255)
      }
    }
  }
  import PrimaryColours._PrimaryColours.asInts(Red)   //> res6: (Int, Int, Int) = (255,0,0)PrimaryColours.asInts(Red)

Referential transparency? Given a function and a set of inputs, the results will always be the same... no side effect, can be parallelised, cached, etc....

Saturday, 16 August 2014

Snail Algo in Scala

A friend of mine just had an interview for a job at Amazon... and he had a funny algorithm to work on. Something that I would describe as a 'snail algorithm' for a matrix. A bit like this:
So, I was wondering how to implement this .. and I wrote this in Scala.. seems to work - although not entirely tested ;-) Some type def
  val numRows = 4
  val numCols = 3        
  val matrixSize = numRows * numCols 
  
  type Coord = (Int, Int)
  type Operand = (Int, Int)
  type Path = List[Coord]

  val incs = List((0, 1), (1, 0), (0, -1), (-1, 0))
incs defines directions: go right, go down, go left, go up, etc. In order to continuously iterate through those values, I used Stream.continually():
  val incsIt = (for(x <- Stream.continually(); y <- incs) yield y).iterator
  def nxtOp = incsIt.next 
Then a small recursive function to snail-walk the matrix:
  def walk(coord: Coord = (0, 0), op: Operand = nxtOp, path: Path = List()): Path = {
    if (path.size == matrixSize) path else {
      val nrc = (coord._1+op._1, coord._2+op._2)
      if (nrc._1 < 0 || nrc._1 >= numRows || nrc._2 < 0 || nrc._2 >= numCols || (path contains nrc))
        walk(coord, nxtOp, path)
      else
        walk(nrc, op, if (path.size == matrixSize-2) path :+ coord :+ nrc else path :+ coord)
    }
  }   
The result for (4, 3) shows:
  val p1 = walk()                                 

//> p1  : org.jts.z.Snail.Path = 
// List((0,0), (0,1), (0,2), (1,2), (2,2), (3,2), (3,1), (3,0), (2,0), (1,0), (1,1), (2,1))
I really have the feeling it can be done in a better way. Have not found how yet.

Thursday, 7 August 2014

SOM (2D Grid)

This time, just a Google + Video. Next time.. the 3D version :-)

Sunday, 27 July 2014

Self-Organizing Map in Scala

My Scala code of the day relates to Self-Organising Maps. The end result can be seen on this short video. Let's start with some basic definition
case class Coord(x: Int, y: Int)
case class Weight(r: Double, g: Double, b: Double) // Represents the color vector
case class Node(coord: Coord, weight: Weight) // The node in the lattice
Some utility class, wrapped in a Scala object. As you can see, Euclidean distance is used for weight proximity (r, g, b) and nodes (x, y)
object SOMUtils {
  private val rnd = new java.security.SecureRandom()
  def rndWeight = Weight(rnd.nextDouble(), rnd.nextDouble(), rnd.nextDouble())
  def squa(d: Double) = d*d
  def euclDist(w1: Weight, w2: Weight) = sqrt(squa(w1.r-w2.r)+squa(w1.g-w2.g)+squa(w1.b-w2.b)) // Euclidian distance
  def euclDist(n1: Node, n2: Node) = sqrt(squa(n1.coord.x-n2.coord.x)+squa(n1.coord.y-n2.coord.y)) // Euclidian distance
  def rndElem[T](list: List[T]):T = list(rnd.nextInt(list.size))
}
Follows the definition of the lattice
import SOMUtils._

class Lattice(val size: Int, val nodes: List[Node])
object Lattice {
  def apply(size: Int) = new Lattice(size, (for(x<-0 until size; y<-0 until size) yield Node(Coord(x, y), rndWeight)).toList)
}
And finally the core of the algorithm
class SOM(val size: Int, val numIterations: Int, val trainingSet: List[Weight]) {
  val mapRadius = size / 2.0
  val timeConstant = numIterations / log(mapRadius)
  def neighbourhoodRadius(iter: Double) = mapRadius * exp(-iter/timeConstant)
  def bmu(input: Weight, lattice: Lattice): Node = {
    val sortedNodesByDist = lattice.nodes.sortBy(n => euclDist(input, n.weight))
    sortedNodesByDist(0)
  }
  def bmuNeighbours(radius: Double, bmu: Node, lattice: Lattice): (List[(Node, Double)], List[(Node, Double)]) =
    lattice.nodes.map(n => (n, euclDist(n, bmu))).partition(n => n._2 <= radius)
  def learningRate(iter: Double) = 0.072 * exp(-iter/numIterations) // decays over time
  def theta(d2bmu: Double, radius: Double) = exp(-squa(d2bmu)/(2.0*squa(radius))) // learning proportional to distance
  def adjust(input: Weight, weight: Weight, learningRate: Double, theta: Double): Weight = {
    def adjust(iW: Double, nW: Double) = nW + learningRate * theta * (iW - nW)
    Weight(adjust(input.r, weight.r), adjust(input.g, weight.g), adjust(input.b, weight.b))
  }

  def nextLattice(iter: Int, lattice: Lattice): Lattice = {
    val randomInput = rndElem(trainingSet)
    val bmuNode = bmu(randomInput, lattice)
    val radius = neighbourhoodRadius(iter)
    val allNodes = bmuNeighbours(radius, bmuNode, lattice)
    val lrate = learningRate(iter)
    val adjustedNodes = allNodes._1.par.map(t => {
      val tTheta = theta(t._2, radius)
      val nWeight = adjust(randomInput, t._1.weight, lrate, tTheta)
      Node(t._1.coord, nWeight)
    }).toList
    new Lattice(lattice.size, adjustedNodes ++ allNodes._2.map(t => t._1))
  }

  def compute {
    @tailrec
    def helper(iter: Int, lattice: Lattice): Lattice =
      if (iter >= numIterations) lattice else helper(iter+1, nextLattice(iter, lattice))

    val endLattice = helper(0, Lattice(size))
    UIUtils.persist(endLattice, "lattice")
  }
}
That's it. Hope you enjoyed that. Check it out and learn more. Next step: to implement the 2-D grid version - still using Scala and JavaFX, develop a generic SOM-Scala lib, and finally, re-implement the 2-D version using Three.js

Wednesday, 23 July 2014

Scala Mandel

package jts.mandel

import scala.annotation.tailrec

object Mandel {
  type Pixel = (Int, Int)
  val maxIter = 255
  val size = 1024
  val palette = {
    val rnd = new java.security.SecureRandom
    ((for(n <- 0 until maxIter) yield rnd.nextInt()).toList) ++ List(0)
  }
  
  def mandel():Map[Pixel, Int] = {
    @tailrec
    def compute(p: Pixel, x: Double = 0, y: Double = 0, iter: Int = 0): Int = {
      def x2mx(lx: Int, w: Int) = -2.5 + (lx * 3.5) / w
      def y2my(ly: Int, h: Int) = 1.0 - ly * 2.0 / h
      val xmy = (x2mx(p._1, size), y2my(p._2, size))
    
      if (x*x+y*y > 4 || iter >= maxIter) 
        iter
      else
        compute(p, x*x-y*y+xmy._1, 2*x*y+xmy._2, iter+1)
    }
    
    val area = (for(x <- 0 until size; y <- 0 until size) yield (x, y))
    area.par.map(e => (e, compute(e))).toList.toMap
  }
  
  def persistToFile(pixels: Map[Pixel, Int]) {
    import java.awt.image.{BufferedImage => BI}
    val im = new BI(size, size, BI.TYPE_INT_RGB)
    pixels.par.foreach(e => {im.setRGB(e._1._1, e._1._2, palette(e._2))})
    javax.imageio.ImageIO.write(im, "jpg", new java.io.File("C:/EclipseWS/ScalaInvestigations/mandel.jpg"))
  }
  
  def main(args: Array[String]):Unit = {
    val t0 = System.currentTimeMillis()
    persistToFile(mandel())
    val tf = (System.currentTimeMillis() - t0)
    println(s"Done in $tf millis")
  }
}