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...

# oogifu

## Friday, 5 September 2014

## 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 ;-)

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)].

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:

Time to put this to the test:

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 = 3The 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 =To avoid calling the filter method with the same predicate, another cool variant is this one, using lazy val and _: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)

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 thereimplicit 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.nextThen 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

## 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 latticeSome 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)) }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.jsdef 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") } }

Labels:
javafx,
Kohonen,
Scala,
Self Organizing Map,
SOM

## 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") } }

Subscribe to:
Posts (Atom)