Scala, Maven, jOOQ, Scalatra

This post is about sharing some wonderful experience: using Scala, Scalatra, jOOQ altogether makes me a happy developer.
Now, there is nothing sexy about this post - it is not cutting edge, there is no big data involved, no AI, just simple tools that I think make a software engineer's life happier and fun.
I have embraced some parts of functional programming in Java 8 - sometimes it is quite difficult to read and debug - but it is clear and concise - less error prone - you know the usual shebang.
I still think that Scala has an edge over Java 8 - but I must say that I cannot wait for Scala 2.12 - as the binary compatibility and compilation speed are big issues.
The Scala IDE is great - but not there yet if you ask me, and I would hate to go and use IntelliJ - just not the tool for me.

This post is about using Scala with Maven, and some really cool stuff using Scalatra and jOOQ to build a simple RESTful server.

pom.xml

All you need for dependencies in one epic pom.xml

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <groupId>Pento</groupId>
    <artifactId>PentoPay</artifactId>
    <version>1.0</version>

    <build>
        <pluginManagement>
            <plugins>
                <plugin>
                    <groupId>net.alchim31.maven</groupId>
                    <artifactId>scala-maven-plugin</artifactId>
                    <version>3.2.1</version>
                </plugin>
                <plugin>
                    <groupId>org.apache.maven.plugins</groupId>
                    <artifactId>maven-compiler-plugin</artifactId>
                    <version>2.0.2</version>
                </plugin>
            </plugins>
        </pluginManagement>
        <plugins>
            <plugin>
                <groupId>net.alchim31.maven</groupId>
                <artifactId>scala-maven-plugin</artifactId>
                <executions>
                    <execution>
                        <id>scala-compile-first</id>
                        <phase>process-resources</phase>
                        <goals>
                            <goal>add-source</goal>
                            <goal>compile</goal>
                        </goals>
                    </execution>
                    <execution>
                        <id>scala-test-compile</id>
                        <phase>process-test-resources</phase>
                        <goals>
                            <goal>testCompile</goal>
                        </goals>
                    </execution>
                </executions>
            </plugin>
            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-compiler-plugin</artifactId>
                <executions>
                    <execution>
                        <phase>compile</phase>
                        <goals>
                            <goal>compile</goal>
                        </goals>
                    </execution>
                </executions>
            </plugin>
        </plugins>
    </build>

    <dependencies>
        <dependency>
            <groupId>org.jooq</groupId>
            <artifactId>jooq</artifactId>
            <version>3.7.3</version>
        </dependency>

        <dependency>
            <groupId>org.jooq</groupId>
            <artifactId>jooq-meta</artifactId>
            <version>3.7.3</version>
        </dependency>

        <dependency>
            <groupId>org.jooq</groupId>
            <artifactId>jooq-codegen</artifactId>
            <version>3.7.3</version>
        </dependency>

        <dependency>
            <groupId>org.jooq</groupId>
            <artifactId>jooq-scala</artifactId>
            <version>3.7.3</version>
        </dependency>

        <dependency>
            <groupId>org.scalatra</groupId>
            <artifactId>scalatra_2.11</artifactId>
            <version>2.4.0</version>
        </dependency>

        <dependency>
            <groupId>com.google.inject</groupId>
            <artifactId>guice</artifactId>
            <version>4.0</version>
        </dependency>

        <dependency>
            <groupId>javax.servlet</groupId>
            <artifactId>javax.servlet-api</artifactId>
            <version>3.1.0</version>
        </dependency>

        <dependency>
            <groupId>org.eclipse.jetty</groupId>
            <artifactId>jetty-server</artifactId>
            <version>9.3.8.v20160314</version>
        </dependency>

        <dependency>
            <groupId>org.eclipse.jetty</groupId>
            <artifactId>jetty-webapp</artifactId>
            <version>9.3.8.v20160314</version>
        </dependency>

        <dependency>
            <groupId>org.slf4j</groupId>
            <artifactId>slf4j-simple</artifactId>
            <version>1.7.21</version>
        </dependency>

        <dependency>
            <groupId>org.apache.derby</groupId>
            <artifactId>derby</artifactId>
            <version>10.12.1.1</version>
        </dependency>

        <dependency>
            <groupId>org.apache.derby</groupId>
            <artifactId>derbyclient</artifactId>
            <version>10.12.1.1</version>
        </dependency>

        <dependency>
            <groupId>com.zaxxer</groupId>
            <artifactId>HikariCP</artifactId>
            <version>2.4.5</version>
        </dependency>

    </dependencies>
    
</project>

Scalatra

Using Scalatra, the bootstrap class (with Guice Module for DI), the servlet definition and the launcher

import javax.servlet.ServletContext

import com.google.inject.Guice
import org.pento.services.{PingModule, PingService}
import org.scalatra.LifeCycle

class ScalatraBootstrap extends LifeCycle {
  private lazy val injector = Guice.createInjector(new PingModule())

  override def init(context: ServletContext): Unit = {
    context mount (injector.getInstance(classOf[PingService]), "/main-service/")
  }
}

package org.pento.services

import java.time.Clock

import com.google.inject.{AbstractModule, Provides, Singleton}

class PingModule extends AbstractModule {
  override def configure(): Unit = {
    bind(classOf[PingService]).asEagerSingleton()
  }

  @Provides @Singleton
  def provideClock() = Clock.systemUTC()
}

package org.pento.services

import java.time.Clock
import javax.inject.Inject

import org.scalatra.ScalatraServlet

class PingService @Inject() (val clock: Clock) extends ScalatraServlet {
  get ("/ping") {
    clock.millis()
  }
}

package org.pento.services

import org.eclipse.jetty.server.Server
import org.eclipse.jetty.servlet.DefaultServlet
import org.eclipse.jetty.webapp.WebAppContext
import org.scalatra.servlet.ScalatraListener

object PentoServer {
  val server = new Server(5899)
  val context = new WebAppContext()
  context.setContextPath("/")
  context.setResourceBase("src/main/scala")
  context.addEventListener(new ScalatraListener)
  context.addServlet(classOf[DefaultServlet], "/")
  server.setHandler(context)

  server.start()
  server.join()

  def main(args: Array[String]) {

  }
}

Neat. Simple.

Now to the database and jooq code generation

Who writes SQL those days? Well we have to.. but not in the code. jOOQ is probably one of the best libs I have used from Java and SCALA. Here is a simple jOOQ config that generates code from a given existing schema

<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
<configuration>
    <!-- Configure the database connection here -->
    <jdbc>
        <driver>org.apache.derby.jdbc.ClientDriver</driver>
        <url>jdbc:derby://localhost:1527/C:/Users/tj/Google Drive/IT-Projects/PentoPay/derby/PentoDb;create=true</url>
        <user>APP</user>
        <password>*</password>
    </jdbc>

    <generator>
        <name>org.jooq.util.DefaultGenerator</name>

        <database>
            <name>org.jooq.util.derby.DerbyDatabase</name>
            <inputSchema>APP</inputSchema>
            <includes>.*</includes>
        </database>

        <generate>
            <relations>true</relations>
            <deprecated>false</deprecated>
            <generateAnnotation>true</generateAnnotation>
            <records>true</records>
            <immutablePojos>true</immutablePojos>
            <globalObjectReferences>true</globalObjectReferences>
            <fluentSetters>false</fluentSetters>
        </generate>

        <target>
            <packageName>jooq.pento.db</packageName>
            <directory>C:/Users/tj/Google Drive/IT-Projects/PentoPay/src/main/java</directory>
        </target>
    </generator>
</configuration>

Some very nice utility classes to manage AutoCloseable and some fancy resource management (take back the jdbc connection to the pool post request). The code below allows automatically call close on an AutoCloseable

  def using[T <: AutoCloseable, R](resource: T)(block: T => R): R = {
    try {
      block(resource)
    } finally {
      if (resource != null) resource.close()
    }
  }

The one below deals specifically with jOOQ DSL Context:

  override def withSession[R](block: (DSLContext) => R): Option[R] = {
    import org.pento.utils.PentoUtils.using
    using(ds.getConnection) {connection =>
      try {
        Some(block(DSL.using(connection, sqlDialect, jooqSettings)))
      } catch  {
        case t: Throwable => None
      }
    }
  } // withSession

All in one, how to do a simple query. This is quite neat.

package org.pento.db

import com.google.inject.Inject
import com.zaxxer.hikari.HikariDataSource
import jooq.pento.db.tables.records.LastaccessRecord
import org.jooq.conf.Settings
import org.jooq.impl.DSL
import org.jooq.{DSLContext, SQLDialect}
import org.pento.utils.LastAccess

trait DataSource {
  def withSession[R](block: DSLContext => R): Option[R]
}

class DataSourceImpl @Inject() () extends DataSource {
  val ds = {
    val hds = new HikariDataSource()
    hds.setDriverClassName("")
    hds.setJdbcUrl("")
    hds.setUsername("")
    hds.setPassword("")
    hds
  }
  val sqlDialect = SQLDialect.valueOf("DERBY")
  val jooqSettings = new Settings()

  override def withSession[R](block: (DSLContext) => R): Option[R] = {
    import org.pento.utils.PentoUtils.using
    using(ds.getConnection) {connection =>
      try {
        Some(block(DSL.using(connection, sqlDialect, jooqSettings)))
      } catch  {
        case t: Throwable => None
      }
    }
  } // withSession
}

trait DB {
  def allAccesses: Option[List[LastAccess]]
}

class DBImpl @Inject() (val ds: DataSource) extends DB {
  override def allAccesses: Option[List[LastAccess]] = {
    import jooq.pento.db.tables.Lastaccess.LASTACCESS

    import scala.collection.JavaConversions._

    ds.withSession{ctx => {
      val rs = ctx.select(LASTACCESS.TS)
                  .from(LASTACCESS)
                  .fetchInto(classOf[LastaccessRecord])
      (for{r <- rs} yield LastAccess(r.value1())).toList
    }}
  }
}

Mutual SSL with HTTPClient in Scala

Follows a Scala code snippet to use mutual SSL when talking to a server. This code uses Apache HC

package org.tj.mssl

import org.apache.http.impl.client.CloseableHttpClient
import org.apache.http.impl.client.HttpClientBuilder
import java.security.KeyStore
import java.io.FileInputStream
import java.io.File
import org.apache.http.conn.ssl.TrustStrategy
import java.security.cert.X509Certificate
import org.apache.http.ssl.SSLContexts
import org.apache.http.conn.ssl.SSLConnectionSocketFactory
import org.apache.http.impl.client.HttpClients

object MutualSSL {

  def buildHTTPClient(useSSL: Boolean): CloseableHttpClient = {
    if (!useSSL) {
      HttpClientBuilder.create().build()
    } else {
      val keyStorePassword = "[your keystore password]".toCharArray()
      val importedKeyPassword = "[your imported key password]".toCharArray()
      val keyStore = KeyStore.getInstance(KeyStore.getDefaultType)
      val keyStorePath = new FileInputStream(new File("[your key store path .jks]"))
      keyStore.load(keyStorePath, keyStorePassword)
      keyStorePath.close()
      
      val trustStrategy = new TrustStrategy() {
        override def isTrusted(x509Certs: Array[X509Certificate], s: String): Boolean = true
      }
      
      val sslContext = SSLContexts.custom()
                                  .loadKeyMaterial(keyStore, importedKeyPassword)
                                  .build()
                                  
      val sslSocketFactory = new SSLConnectionSocketFactory(sslContext)
      
      HttpClients.custom().setSSLSocketFactory(sslSocketFactory).build()
    }  
  }
  
  def main(args: Array[String]): Unit = {
    
  }
}

Group By Sum Scala 2.11 vs Java 8

I had to recently implement an aggregate function in Scala 2.11 and Java 8... Which one do you prefer?

Scala 2.11

case class Datum(val id: String, val count: Int)

object GroupBySumScalaDemo {
  val list = List(Datum("a", 1), Datum("a", 2), Datum("a", 3),
                  Datum("b", 4), Datum("b", 5),
                  Datum("c", 6))
                  
  // Want to group by 'id' and sum all values
  val map = list.groupBy(_.id).mapValues(_.map(_.count).sum)   
  
  println(map)
  
  def main(args: Array[String]): Unit = {
  }
}

Java 8

class MyDatum {
  private final String id;
  private final int count;
 
  public MyDatum(final String id, final int count) {
    this.id = id;
    this.count = count;
    }

  public String getId() {
    return id;
  }

  public int getCount() {
    return count;
  }
}

public class GroupBySumJava8Demo {
  public GroupBySumJava8Demo() {
    final List list = Arrays.asList(
      new MyDatum("a", 1), new MyDatum("a", 2), new MyDatum("a", 3),
      new MyDatum("b", 4), new MyDatum("b", 5),
      new MyDatum("c", 6));
    final Map map = list.stream()
      .collect(Collectors.groupingBy(MyDatum::getId, Collectors.summingInt(MyDatum::getCount)));
    System.out.println(map);
  }

  public static void main(String[] args) {
    new GroupBySumJava8Demo();
  }
}

I know which one I like ;-)

Monadic behaviour

Today, home-sick, read and found a bunch of nice links on Scala and Monads. For future reference, I paste those links here.
Monads in Scala I
Haskell Monads
Category Theory
Monads are elephant I, Monads are elephant II, Monads are elephant III, Monads are elephant IV
Scalaz Monads

RPC, Protobuf, Scala

Seen too many custom frameworks for RPC, asynchronous callbacks, custom serialization, etc...... There are great frameworks out there to handle this. Let's have a look at a simple Search service, asynchronous request, using protobuf and Scala. Some *.proto def where the services are defined, and the data to marshall in and out.

syntax = "proto2";

package myprotocol;

message SearchRequest {
 required int32 requestid = 1;
}

message SearchResponse {
 required int32 requestid = 1;
 required int32 responseid = 2;
}

A simple RPC call definition:

syntax = "proto2";
option java_generic_services = true;

package myprotocol;

import "Search.proto";

service SearchService {
  rpc Search (SearchRequest) returns (SearchResponse);
}

Then you define two classes...the one that implements your RpcChannel is the one where you plugin your underlying messaging system, such as JMS, Solace, Tibco RV, or sockets...

package demo

import java.util.logging.Logger

import com.google.protobuf.Descriptors.MethodDescriptor
import com.google.protobuf.Message
import com.google.protobuf.RpcCallback
import com.google.protobuf.RpcChannel
import com.google.protobuf.RpcController

import myprotocol.Search.SearchRequest
import myprotocol.Search.SearchResponse

class SChannel extends RpcChannel {
  val logger = Logger.getLogger("SChannel")
  
  override def callMethod(methodDescriptor: MethodDescriptor , 
                          rpcController: RpcController , 
                          m1: Message, 
                          m2: Message, 
                          rpcCallback: RpcCallback[Message] ) {
    m1 match {
      case sr: SearchRequest => {
        val response = SearchResponse.newBuilder.setRequestid(sr.getRequestid).setResponseid(2).build
        rpcCallback.run(response)
      }
      case _ => logger.warning(s"Not handling message type $m1 yet")
    }
  } //  override def callMethod
}

class SController extends RpcController {
  val logger = Logger.getLogger("SController")
  
  override def reset() {
    logger.info("reset()")
  }

  override def failed(): Boolean = {
    logger.info("failed()")
    false
  }

  override def errorText(): String = {
    logger.info("errorText()")
    null
  }

  override def startCancel() {
    logger.info("startCancel()")
  }

  override def setFailed(s: String) {
    logger.info(s"setFailed($s")
  }

  override def isCanceled():Boolean = {
    logger.info("isCanceled()")
    false
  }

  override def notifyOnCancel(rpccallback: RpcCallback[Object]) {
    logger.info(s"notifyOnCancel($rpccallback)")
  }
}

Edited I Forgot the code to actually use those classes :-)

package demo

import java.util.logging.Logger

import com.google.protobuf.RpcCallback

import myprotocol.Search.SearchRequest
import myprotocol.Search.SearchResponse
import myprotocol.Services

object RPCDemo {
  val logger = Logger.getLogger("RPCDemo")
  
  def main(args: Array[String]): Unit = {
    val channel = new SChannel
    val controller = new SController
    val services = Services.SearchService.newStub(channel)
    val request = SearchRequest.newBuilder().setRequestid(1).build
    val callback = new RpcCallback[SearchResponse] {
      override def run(obj: SearchResponse) = logger.info(s"Received on RpcCallback $obj")
    }
    services.search(controller, request, callback)
    
    logger.info("Sleeping 5 seconds")
    Thread.sleep(5000)
    logger.info("Ciao")
  }
}

For example, if you are looking for a pre-built TCP/IP socket implementation on top of protobuf, check out protobuf-socket-rpc A detailed view of a custom channel can be seen there: RpcChannelImpl.java

Edited II You can obviously define an implict instead of this callback a la Java:

  import scala.language.implicitConversions
  implicit def f2cb(f: (SearchResponse) => Unit) = new RpcCallback[SearchResponse] {
    override def run(sr: SearchResponse) = f(sr)
  }

  services.search(controller, request, (resp: SearchResponse) => {
    logger.info(s"Received on RpcCallback $resp")
  })

... Voila.

So much fun recently

Had lots of fun recently: played with Scalatra, RESTful APIs, Slick, all the web services security aspects like HMAC, etc... Really fun. I am quite amazed that I never had to work on web services until now... but hey, there is always a first time.
Special Kudos to Scalatra -- just love this framework, although the integration with Swagger can be a real pain.

Private Key for Digital Signature, KeyStore, PKCS#12

The following demonstrates the use of the Java security API to digitally sign a document.
Before we get to the Scala code, we must first use Java's keytool to create a self-signed certificate.
In real-life, you'd probably buy one from Verisign for example. The archive file format chosen is PKCS12.

keytool -genkey
        -alias tj
        -keystore mykeystore
        -storepass storepass
        -validity 365
        -keyalg RSA
        -keysize 2048
        -storetype pkcs12

Once you have answered the questions, you can list the aliases using the following command:

keytool -keystore mykeystore 
        -storepass storepass 
        -list 
        -storetype pkcs12

Should output:

Keystore type: PKCS12
Keystore provider: SunJSSE

Your keystore contains 1 entry

tj, Oct 12, 2014, PrivateKeyEntry,
Certificate fingerprint (SHA1): 52:6B:0D:05:9E:CE:5A:CA:5E:EF:74:C9:51:FE:46:8D:E6:CE:4F:11

Let's get to the coding part. We will extract the private key from the store to digitally sign a document. I usually first create a digest from the initial document and store this digest as base 64. But there is no need for this step.

  def createDigest(legalDocument: String): Array[Byte] = {
    val md = MessageDigest.getInstance("SHA-256")
    md.update(legalDocument.getBytes)
    md.digest()
  }

to be called like this:

val alias = "tj"
val password = "storepass".toCharArray
val legalDoc = createDigest("This is a legal document I must digitally sign")

legalDoc is an array of bytes - it contains a SHA-256 digest from the initial document.

The code to list the keystore entries, just to make sure we are on the right path:

  def listStoreEntries(password: Array[Char]): KeyStore = {
    val keyStoreDefaultType = KeyStore.getDefaultType
    val keyStore = KeyStore.getInstance("pkcs12")
    keyStore.load(new FileInputStream("mykeystore"), password)

    val aliases = keyStore.aliases()
    while(aliases.hasMoreElements) {
      val alias = aliases.nextElement()
      log(s" Alias: $alias")
    }

    keyStore
  }

listStoreEntries returns the initialized keystore. Let's now sign the legal document and return a base 64 encoded digital signature:

  def signLegalDocument(keystore: KeyStore, alias: String, password: Array[Char], legalDoc: Array[Byte]): String = {
    val privateKey = keystore.getKey(alias, password)
    val dsig = Signature.getInstance("MD5withRSA")
    dsig.initSign(privateKey.asInstanceOf[PrivateKey])
    dsig.update(legalDoc)
    val signature = dsig.sign()
    Base64.getEncoder.encodeToString(signature)
  }

And the code to verify the signature:

  def verifyDigitalSignature(keystore: KeyStore, alias: String, legalDoc: Array[Byte], signature: String): Unit = {
    val certificate = keystore.getCertificate(alias)
    val x509Certificate = certificate.asInstanceOf[X509Certificate]
    val publicKey = x509Certificate.getPublicKey
    val dsig = Signature.getInstance("MD5withRSA")
    dsig.initVerify(publicKey)

    val sig = Base64.getDecoder.decode(signature)
    dsig.update(legalDoc)
    val verifiedSig = dsig.verify(sig)
    log(s"Has the legal document signature successfully been verified? $verifiedSig")
    require(verifiedSig == true)
  }

The whole main method:

  def main(args: Array[String]) {
    val alias = "tj"
    val password = "storepass".toCharArray
    val legalDoc = createDigest("This is a legal document I must digitally sign")
    val keyStore = listStoreEntries(password)

    val signature = signLegalDocument(keyStore, alias, password, legalDoc)
    verifyDigitalSignature(keyStore, alias, legalDoc, signature)
  }

  def log(ref: Any) = println(ref)

How do I import my self-signed certificate into Windows cert manager?
Just rename the keystore from mykeystore to mykeystore.pfx On Windows, simple double-click on it and follow the instructions.
Open certmgr.msc via the run command or from a DOS console - under Certificates - Currrent User, Personal, Certificates you should see your previously create certificate using Java's keytool.

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

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

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.

SOM (2D Grid)

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

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

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

Palindromes in Scala... there is always a better way

What does one do while having dessert? Write some Scala code to find out the longest palindrome in a string. Some piece of code that makes you humble... :-) I came up with this (based on a double array in O(N^2))

  def longestPalindrome(in: String): Option[String] = {
    val inLength = in.length
    val arr = Array.ofDim[Boolean](inLength, inLength)
    for(i <- 0 until in.length) {
      arr(i)(i) = true
      if (i < inLength - 1 && in(i) == in(i+1)) arr(i)(i+1) = true
    }
    
    def helper(k: Int, i: Int, pal: Option[String]): Option[String] = {
      val j = i + k - 1
      if (in(i) == in(j)) {
         arr(i)(j) = arr(i+1)(j-1)
         if (arr(i)(j)) {
           val npal = in.substring(i, j+1)
           pal match {
             case None => Some(npal)
             case Some(s: String) => if (npal.size > s.size) Some(npal) else pal
           }
         } else pal
      } else {
        arr(i)(j) = false
        pal
      }
    }
    
    val allPals = for(k <- 3 to inLength; i <- 0 until inLength - k) yield helper(k, i, None)
    val validPals = allPals.filter(o => o.isDefined).map(o => o.get)
    if (validPals.isEmpty)
      None
    else
      Some(validPals.maxBy(s => s.size))
  }                                               //> longestPalindrome: (in: String)Option[String]
  
  val str = "sdfsdfbbbgggbbggthierryjjyrreihtjdfdscdcdvdv"
                                                  //> str  : String = sdfsdfbbbgggbbggthierryjjyrreihtjdfdscdcdvdv
  longestPalindrome(str)                          //> res0: Option[String] = Some(thierryjjyrreiht)
  

But then I found out on StackOverFlow, a much better way of doing this..... I was LOL when I saw this piece of code:

  (for{i <- 2 to str.size; s <- str.sliding(i) if (s == s.reverse)} yield s).maxBy(s => s.size)
                                                  //> res1: String = thierryjjyrreiht

;-) There is always a better way

Parsing XML data without vars

Another code snippet - was trying to parse a XML document in Scala without vars... Here is the XML:

<apm>
  <entry>
    <service>GOOGLE</service>
    <id>G-ID</id>
    <pwd>G-PWD</pwd>
    <url>www.google.com</url>
  </entry>
  
  <entry>
    <service>AMAZON</service>
    <id>A-ID</id>
    <pwd>A-PWD</pwd>
    <url>www.amazon.com</url>
  </entry>
</apm>

In the scala code that uses pattern matching and recursion.

package scala.fun

import scala.io.Source
import scala.xml.pull.XMLEventReader
import scala.xml.pull.XMLEvent
import scala.xml.pull.EvElemStart
import scala.xml.pull.EvText
import scala.xml.pull.EvElemEnd
case class Label(val lbl: String)

case class Service(val svr: String)
case class Id(val id: String)
case class Pwd(pwd: String)
case class URL(url: String)

case class Entry(val svr: Service, val id: Id, val pwd: Pwd, val url: URL)

object XmlP {
  def parse(xmlf: String): List[Entry] = {
    def ip(xmlr: XMLEventReader, xmle: XMLEvent, start: Boolean = true, label: Label = Label(""),
           service: Service = Service(""), id: Id = Id(""), pwd: Pwd = Pwd(""), url: URL = URL(""),
           entries: List[Entry] = List()): List[Entry] = {
      xmle match {
        case EvElemStart(pre, lbl, attrs, scope) => ip(xmlr, xmlr.next, true, Label(lbl), service, id, pwd, url, entries)
        case EvText(txt) =>
          if (start)
            label.lbl match {
              case "service" => ip(xmlr, xmlr.next, true, label, Service(txt.trim), id, pwd, url, entries)
              case "id" => ip(xmlr, xmlr.next, true, label, service, Id(txt.trim), pwd, url, entries)
              case "pwd" => ip(xmlr, xmlr.next, true, label, service, id, Pwd(txt.trim), url, entries)
              case "url" => ip(xmlr, xmlr.next, true, label, service, id, pwd, URL(txt.trim), entries)
              case _ => ip(xmlr, xmlr.next, false, label, service, id, pwd, url, entries)
            }
          else ip(xmlr, xmlr.next, false, label, service, id, pwd, url, entries)
        case EvElemEnd(pre, lbl) => {
          val newEntries = if ("entry".equals(lbl)) Entry(service, id, pwd, url) +: entries else entries
          if (xmlr.hasNext) ip(xmlr, xmlr.next, false, label, service, id, pwd, url, newEntries) else entries
        }
        case _ => if (xmlr.hasNext) ip(xmlr, xmlr.next, false, label, service, id, pwd, url, entries) else entries
      } // xmle match
    } //ip
    
    val xml = new XMLEventReader(Source.fromFile(xmlf))
    ip(xml, xml.next)
  }
  
  val result = parse("apm.xml")
  println(s"result: $result")

  def main(args: Array[String]): Unit = {}
}

A neat Scala code snippet for depth aggregation

case class Price(val value: Double) extends AnyVal
case class Qty(val value: Int) extends AnyVal
case class Depth(price: Price, qty: Qty)

object Agg {
  def aggregate(in: List[Depth]) = in.foldLeft(List[Depth]())((l, c) => {
    if (l.isEmpty) List(c)
    else if (l.head.price == c.price) l updated (0, Depth(l.head.price, Qty(l.head.qty.value+c.qty.value)))
    else c +: l
  }).reverse
}

GAs speed x10

For the astute observer, you will notice that in my previous post, there is a slight performance problem if the evaluation function is expensive. This line of code:

val sortedChromos = population.sortBy(w => evaluate(decode(w), target))

Actually, it should not be even coded like this, the evaluation should happen once, and then we should sort. That's one thing. The other thing, is that we could simply parallelise this... First time I have actually found a good usage for .par ;-) With this in mind, here is a new implementation of the above:

def parSort(population: Population): Population = {
  val parPopulation = population.par
  val evaledParPopulation = parPopulation.map(e => (e, evaluate(decode(e), target))).toList
  val sortedParPopulation = evaledParPopulation.sortBy(e => e._2).map(e => e._1)
  sortedParPopulation
}

val sortedChromos = parSort(population)

The third problem with a maximum of 2,000 iterations with the first sort/eval takes 51 seconds, with the par/sort/eval, 5 seconds :-)

GAs in Scala

For tonight, what about a small, generic algorithm Scala lib? Let's start with some basic definition:

case class NbChromos(val nb: Int) extends AnyVal
case class NbGenes(val nb: Int) extends AnyVal

Then the core lib, an abstract class that will be implemented for specific solutions. T is the type of the underlying gene, U, the type of the target (solution) You can see the implementations for the methods cross, mutates for a gene, and the whole chromosome. The 3 methods that must be implemented for a specific problem are (1) the basic gene mutation ~~(), (2) the decoder to decode the chromosome def decoder and (3) the evaluator function def evaluator.

abstract class GA[T, U] {
  import scala.language.implicitConversions
  implicit def nbgenes2int(obj: NbGenes): Int = obj.nb
  implicit def nbchromos2int(obj: NbChromos): Int = obj.nb
  
  protected val rnd = new scala.util.Random
  protected def nextInt(upper: Int) = rnd.nextInt(upper)
  
  type Gene = T
  type Chromo = Seq[Gene]
  type Population = Seq[Chromo]
  
  def ~~(): Gene // Generates a random gene
  def ~~(gene: Gene): Gene = ~~() // Mutates a given gene
  def xx(c1: Chromo, c2: Chromo): (Chromo, Chromo) = { // Crosses two chromosomes
    require(c1.length == c2.length, s"Crossing chromos of different lengths ${c1.length} != ${c2.length}")
    val idx = nextInt(c1.length)
    val rmi = c1.length - idx
    (c1.take(idx) ++ c2.takeRight(rmi), c2.take(idx) ++ c1.takeRight(rmi))
  }
  def ~~(c: Chromo): Chromo = { // Mutates a chromosome
    val idx = nextInt(c.length)
    val mc = ~~(c(idx))
    c.take(idx) ++ List(mc) ++ c.takeRight(c.length - 1 - idx)
  }
  def ~#(nbGenes: NbGenes): Chromo = // Generates a random chromosome 
    (for(i <- 0 until nbGenes) yield ~~())
  def ~#(nbChromos: NbChromos, nbGenes: NbGenes): Population = { // Generates a random population
    val nbc = if (nbChromos%2 == 0) nbChromos.nb else 1 + nbChromos.nb // Makes sure we have an even number
    for(i <- 0 until nbc) yield ~#(nbGenes)
  }
  
  // The algorithm uses a 'decoder' (to decoded a chromo into the target),
  // an 'evaluator' to evaluate a solution towards its target
  // and a generic 'solve' method
  def decoder(chromo: Chromo): U
  def evaluator(solution: U, target: Option[U]): Double // The higher the number the worst, 0 is the best
  
  def solve(decode: Chromo => U)(evaluate: (U, Option[U]) => Double)
    (nbChromos: NbChromos, nbGenes: NbGenes, target: Option[U], crossOverRate:Double = 0.7, mutationRate:Double = 0.2, maxIterations:Double = 10000): (Chromo, U, Double) = {
    val nbBests = 2
    val initialPopulation = ~#(nbChromos, nbGenes)
    
    def ~!#(in: Population, out: Population = Seq()): Population = {
      val rndDouble = rnd.nextDouble
      
      if (in.isEmpty) out else {
        val c1h = in.head
        val rcs = in.tail
        val c2h = rcs.head
        if (rndDouble < mutationRate) { // Let's mutate
          val mc1 = ~~(c1h)
          val mc2 = ~~(c2h)
          ~!#(rcs.tail, List(mc1, mc2) ++ out)
        } else if (rndDouble < crossOverRate) {
          val cxs = xx(c1h, c2h)
          ~!#(rcs.tail, List(cxs._1, cxs._2) ++ out)
        } else
          ~!#(rcs.tail, List(c1h, c2h) ++ out)
      }
    } // crosses, mutates, or copies the population into a new population
    
    def solve(population: Population, iter: Int = 0): Chromo = {
      val sortedChromos = population.sortBy(w => evaluate(decode(w), target))
      
      if (iter > maxIterations) {
        sortedChromos(0)
      } else {
        val bests = sortedChromos.slice(0, nbBests)
        val best = bests(0)
        val bestDecoded = decode(best)
        val evaled = evaluator(bestDecoded, target)
        if (iter%1000 == 0) println(s"Current iter $iter, found $bestDecoded")
        if (evaled == 0) {
          println(s"Found a solution in $iter iterations")
          best
        } else {
          val shuffledChromos = rnd.shuffle(sortedChromos.take(sortedChromos.length-nbBests))
          val nextChromos = ~!#(shuffledChromos)
          val newPopulation = bests ++ nextChromos
          solve(newPopulation, iter+1)
        }
      }
    } // solves the problem
    
    val best = solve(initialPopulation)
    val bestDecoded = decode(best)
    val bestScore = evaluate(bestDecoded, target)
    (best, bestDecoded, bestScore)
  } // def solve
}

That is it for the "core" lib. Let's try this on 3 problems: a word finder, a formula finder and a circle fitter (like the one at the bottom of this page) Problem one: Word finder Given a random set of characters, find a target string.

package org.jts.ga

class PhraseGA extends GA[Char, String] {
  private val from = 'a'; val to = 'z'
  private def rndChar: Char = (rnd.nextInt(to-from+1)+from).toChar
  
  override def ~~(): Gene = rndChar
  override def decoder(chromo: Chromo) = chromo.map(g => g.toString).mkString
  override def evaluator(sol: String, tgt: Option[String]): Double =
    if (sol.length() != tgt.get.length()) Double.MaxValue else
      (for(i <- 0 until sol.length) yield if (sol(i).equals(tgt.get(i))) 0 else 100).sum
}

object WordFinder {
  def main(args: Array[String]): Unit = {
    val sga = new PhraseGA
    val target = "abcdefghijklmnopqrstuvwxyz"
    val targetLength = target.length
    val result = sga.solve(sga.decoder)(sga.evaluator)(NbChromos(100), NbGenes(targetLength), Some(target))
    println(s"result: $result")
  }
}

Problem two: Formula finder Given a sets of digits and operands, find a formula that results into a given number.

package org.jts.ga

import org.mvel2.MVEL

class FormulaFinder extends GA[Char, String] {
  private val digits = List('0', '1', '2', '3', '4', '5', '6', '7', '8', '9')
  private val operands = List('+', '-', '/', '*')
  private val domain = digits ++ operands
  private def rndElem = domain(rnd.nextInt(domain.length))
  
  override def ~~(): Gene = rndElem
  override def decoder(chromo: Chromo) = chromo.map(g => g.toString()).mkString
  override def evaluator(sol: String, tgt: Option[String]): Double = {
    try {
      val eval = MVEL.eval(sol+"+0.0")
      val tgtSol = eval.asInstanceOf[Double]
      val tgtAsD = tgt.get.toDouble
      Math.abs(tgtSol-tgtAsD)
    } catch {
      case t: Throwable => Double.MaxValue
    }
  }
}

object FormulaFinder {
  def main(args: Array[String]): Unit = {
    val sga = new FormulaFinder
    val target = "123456"
    val result = sga.solve(sga.decoder)(sga.evaluator)(NbChromos(100), NbGenes(9), Some(target))
    println(s"result: $result")
  }
}

Problem three: Circle Fitter Fits the bigger circle possible in an area full of circles. This problem is the one at the bottom of this page.

package org.jts.ga

case class Circle(val x: Int, val y: Int, val radius: Int) {
  val dxy = (x - radius, y - radius)
  val dwh = (radius * 2, radius * 2)
  val surface = Math.PI * radius.toDouble * radius.toDouble
  
  def dist(other: Circle) = Math.sqrt((x - other.x) * (x - other.x) + (y - other.y) * (y - other.y))
  def intersect(other: Circle) = (radius + other.radius) > dist(other)
  
  def draw(g2d: java.awt.Graphics2D) = g2d.drawOval(dxy._1, dxy._2, dwh._1, dwh._2)
  override def toString = s"C($x, $y, $radius)"
}

case class Area(val w: Int, val h: Int, val max: Int) {
  val maxVal = Math.max(w, h)
  val rnd = new scala.util.Random
  val circles = for(i <- 0 until max) yield Circle(ni(w), ni(h), ni((w*.2).toInt))
  val nbCircles = circles.length
  
  def ni(i: Int) = rnd.nextInt(i)
  def persist2file(best: Circle) {
    val image = new java.awt.image.BufferedImage(w, h, java.awt.image.BufferedImage.TYPE_INT_ARGB)
    val g2d = image.createGraphics
    g2d.setColor(java.awt.Color.BLACK)
    circles.foreach(c => {
      c.draw(g2d)
      g2d.drawString(c.toString, c.x, c.y)
    })
    g2d.setColor(java.awt.Color.RED)
    best.draw(g2d)
    g2d.drawString(best.toString, best.x, best.y)
    javax.imageio.ImageIO.write(image, "png", new java.io.File("area.png"))
    println("Drawn circles")
  }
}

class CircleFitter(val area: Area) extends GA[Int, Circle] {
  private def rndVal = rnd.nextInt(area.maxVal)
  private val maxRadius = Math.min(area.h/2, area.w/2)
  private val maxSurface = Math.PI * maxRadius * maxRadius
  
   override def ~~(): Gene = rndVal
   override def decoder(chromo: Chromo) = Circle(chromo(0), chromo(1), chromo(2))
   override def evaluator(sol: Circle, tgt: Option[Circle]): Double = {
    // bigger the surface, the better
    val surfaceScore = Math.abs(1.0 - sol.surface / maxSurface)
    // fewer number of intersections, the better
    val nbIntersects = (for(c <- area.circles) yield if (sol.intersect(c)) 1.0 else 0.0).sum
    val interesectScore = nbIntersects / area.nbCircles
    // the solution must be strongly inside
    val insideScore = if ((sol.x-sol.radius < 0) || (sol.x+sol.radius > area.w) ||
                          (sol.y-sol.radius < 0) || (sol.y+sol.radius > area.h)) 10.0 else 0.0
    surfaceScore + interesectScore * 3.0 + insideScore
  }
}

object CircleFitter {
  def main(args: Array[String]): Unit = {
    val area = Area(800, 600, 25)
    val circleFitter = new CircleFitter(area)
    val best = circleFitter.solve(circleFitter.decoder)(circleFitter.evaluator)(NbChromos(1000), NbGenes(3), None, .7, .2, 1000)
    area.persist2file(best._2)
  }
}

Have fun.

Dijkstra meets Scala meets ScalaFX

A quick post for an naive implementation of Dijkstra in Scala and a visual representation of the solution using FXML and ScalaFX.
I have first defined a graph and a vertex class as follows:

case class Coordinates(val x: Int, val y: Int)

class Vertex(val id: String, val coords: Coordinates) {
  def dist(v: Vertex):Double = dist(v.coords.x, v.coords.y)
  def dist(x: Int, y: Int):Double = Math.sqrt(
    Math.pow(coords.x - x, 2) + Math.pow(coords.y - y, 2))
  override def toString = s"V($id)@$coords"
}

class Graph(val vertices: Seq[Vertex], val neighbours: Map[Vertex, Seq[Vertex]]) {
  def +(v: Vertex):Graph = new Graph(v +: vertices, neighbours) // adds a vertex to the graph
  def ~(v: Vertex, n: Vertex):Graph = { // sets a neighbour relationship between two vertices
    val g = new Graph(vertices, neighbours + (v -> (neighbours(v) :+ n)))
    new Graph(g.vertices, g.neighbours + (n -> (g.neighbours(n) :+ v)))
  }
  def closest(x: Int, y: Int): Vertex = vertices.minBy( v => v.dist(x, y))
  override def toString = s"G(Vertices: $vertices, Neighbours: $neighbours)"
}

Then comes my Scala version of Dijkstra (would be nice to share your version...)

object Dijkstra {
  def run(graph: Graph, source: Vertex, target: Vertex):Seq[Vertex] = {
    val neighbours = graph.neighbours

    def dj2(u: Vertex, vs: Seq[Vertex], distances: Map[Vertex, Double], queue: Seq[Vertex],
            visited: Seq[Vertex], previous: Map[Vertex, Vertex]):
    (Map[Vertex, Double], Seq[Vertex], Seq[Vertex], Map[Vertex, Vertex]) = {
      if (!vs.isEmpty) {
        val v = vs.head
        val alt = distances(u) + u.dist(v)
        if (alt < distances(v) && !visited.contains(v)) {
          dj2(u, vs.tail, distances + (v -> alt), v +: queue, visited, previous + (v -> u))
        } else if (!vs.tail.isEmpty) {
          dj2(u, vs.tail, distances, queue, visited, previous)
        } else (distances, queue, visited, previous)
      } else (distances, queue, visited, previous)
    } // dj2

    def dj1(distances: Map[Vertex, Double], queue: Seq[Vertex], visited: Seq[Vertex], previous: Map[Vertex, Vertex]):Seq[Vertex] = {
      if (!queue.isEmpty) {
        val u:Vertex = queue.filter(v => {!visited.contains(v)}).min(Ordering.by((v:Vertex) => distances(v)))
        if (u == target) {
          sequenceSol(previous, target)
        } else {
          val res = dj2(u, neighbours(u), distances, queue.filterNot(v => v.id == u.id), u +: visited, previous)
          dj1(res._1, res._2, res._3, res._4)
        }
      } else Seq()
    } // dj1

    dj1(Map(source -> 0.0) withDefaultValue Double.MaxValue, Seq(source), Seq(), Map())
  } // dijkstra

  def sequenceSol(previous: Map[Vertex, Vertex], to: Vertex): Seq[Vertex] = {
    def helper(seq: Seq[Vertex], current: Vertex): Seq[Vertex] =
      if (previous.contains(current)) helper(previous(current) +: seq, previous(current)) else seq
    helper(Seq(to), to)
  }
}

I would like to find a simpler version.. really. The FXML is a simple file like this:

<?xml version="1.0" encoding="UTF-8"?>

<?import java.lang.*?>
<?import java.util.*?>
<?import javafx.scene.control.*?>
<?import javafx.scene.layout.*?>
<?import javafx.scene.paint.*?>

<AnchorPane id="AnchorPane" fx:id="masterAnchorPane" maxHeight="-Infinity" maxWidth="-Infinity" minHeight="-Infinity" minWidth="-Infinity" prefHeight="400.0" prefWidth="600.0" xmlns:fx="http://javafx.com/fxml/1" xmlns="http://javafx.com/javafx/2.2" fx:controller="org.jts.dijkstra.DijkstraController">
  <children>
    <BorderPane fx:id="borderPane" prefHeight="400.0" prefWidth="600.0" style="-fx-background-color: #CCFF99" AnchorPane.bottomAnchor="0.0" AnchorPane.leftAnchor="0.0" AnchorPane.rightAnchor="0.0" AnchorPane.topAnchor="0.0">
      <top>
        <FlowPane minHeight="21.0" prefHeight="21.0" prefWidth="600.0">
          <children>
            <TextField fx:id="nbNodes" alignment="CENTER_RIGHT" prefWidth="50.0" promptText="# nodes" text="100" />
            <Button fx:id="applyButton" mnemonicParsing="false" onAction="#handleApply" text="Apply" />
          </children>
        </FlowPane>
      </top>
    </BorderPane>
  </children>
</AnchorPane>

And finally the controller:

package org.jts.dijkstra

import javafx.fxml.{Initializable, FXML}
import javafx.scene.{control => jfxctrl}
import javafx.scene.{layout => jfxlyt}
import javafx.{event => jfxe}
import scalafx.scene.effect.Bloom
import scalafx.scene.paint.Color
import scalafx.scene.{layout => scxlyt}
import scalafx.scene.{control => scxctrl}
import java.net.URL
import javafx.event.EventHandler
import javafx.scene.input.MouseEvent

object Constants {
  val nodeSize = 16
  val width = 1500
  val height = 800
}

class DijkstraController extends Initializable {
  @FXML private var nbNodes: jfxctrl.TextField = null
  @FXML private var applyButton: jfxctrl.Button = null
  @FXML private var borderPane: jfxlyt.BorderPane = null
  @FXML private var masterAnchorPane: jfxlyt.AnchorPane = null

  private var scxMasterPane: scxlyt.AnchorPane = null
  private var scxPane: scxlyt.BorderPane = null
  private var scxNbNodes: scxctrl.TextField = null
  private var scxApplyButton: scxctrl.Button = null
  private var scxCanvas: scalafx.scene.canvas.Canvas = null

  private var fromVertex: Option[Vertex] = None
  private var toVertex: Option[Vertex] = None

  override def initialize(url: URL, rb: java.util.ResourceBundle) {
    require(masterAnchorPane != null, "masterAnchorPane must not be null")
    scxMasterPane = new scxlyt.AnchorPane(masterAnchorPane)

    require(nbNodes != null, "nbNodes must not be null")
    scxNbNodes = new scxctrl.TextField(nbNodes)

    require(applyButton != null, "applyButton must not be null")
    scxApplyButton  = new scxctrl.Button(applyButton)

    require(borderPane != null, "centerPane must not be null")
    scxPane = new scxlyt.BorderPane(borderPane)

    scxCanvas = new scalafx.scene.canvas.Canvas(Constants.width, Constants.height)
    scxPane.setCenter(scxCanvas)
  }

  @FXML private def handleApply(event: jfxe.ActionEvent) {
    // TODO In Future not in EDT
    val maxNodes:Integer = scxNbNodes.getText.toInt
    val width = scxCanvas.width.toInt
    val height = scxCanvas.height.toInt
    println(s"Generating random graph with $maxNodes in ($width, $height)")

    val random = new java.util.Random
    val vertices = for(i <- 0 until maxNodes) yield {
      val x = random.nextInt(width)
      val y = random.nextInt(height)
      val vertex = new Vertex(s"v-$i", Coordinates(x, y))
      vertex
    }
    println(s"Generated vertices $vertices")

    def generateNeighbours(neighbours: Map[Vertex, Seq[Vertex]], nbTimes: Int): Map[Vertex, Seq[Vertex]] = {
      if (nbTimes >= maxNodes) neighbours
      else {
        val v1 = vertices(random.nextInt(maxNodes))
        val v2 = vertices(random.nextInt(maxNodes))
        val n1 = neighbours + (v1 -> (neighbours(v1) :+ v2))
        val n2 = n1 + (v2 -> (n1(v2) :+ v1))
        generateNeighbours(n2, nbTimes + 1)
      }
    }

    val neighbours = generateNeighbours(Map() withDefaultValue Seq(), 0)
    println(s"Generated neighbours $neighbours")

    val graph = new Graph(vertices, neighbours)
    drawGraph(graph)
    addMouseEventHandler(graph)
  }

  private def drawGraph(g: Graph, sol: Seq[Vertex] = Seq()) {
    val gc = scxCanvas.getGraphicsContext2D
    gc.clearRect(0, 0, Constants.width, Constants.height)
    gc.setFill(Color.BLACK)
    gc.fillRect(0, 0, Constants.width, Constants.height)

    gc.setFill(Color.LIGHTYELLOW)
    gc.setEffect(new Bloom())
    g.vertices.foreach(v => {
      gc.fillOval(v.coords.x, v.coords.y, Constants.nodeSize, Constants.nodeSize)
    })

    gc.setEffect(null)
    val offset = Constants.nodeSize / 2
    gc.setStroke(Color.LIGHTBLUE)
    g.neighbours.foreach(t => {
      val from = t._1
      t._2.foreach(to => {
        gc.strokeLine(from.coords.x + offset, from.coords.y + offset, to.coords.x + offset, to.coords.y + offset)
        gc.setLineWidth(1.0)
      })
    })

    if (!sol.isEmpty) {
      gc.setFill(Color.RED)
      gc.setStroke(Color.GREEN)
      gc.setEffect(new Bloom())
      val from = sol(0)
      val to = sol.last
      gc.fillOval(from.coords.x, from.coords.y, Constants.nodeSize, Constants.nodeSize)
      gc.fillOval(to.coords.x, to.coords.y, Constants.nodeSize, Constants.nodeSize)
      val path = sol.sliding(2, 1)

      gc.setLineWidth(5.0)
      while(path.hasNext) {
        val subPath = path.next
        if (subPath.size == 2) {
          val f = subPath(0)
          val t = subPath(1)
          gc.strokeLine(f.coords.x + offset, f.coords.y + offset, t.coords.x + offset, t.coords.y + offset)
        }
      }
    }
  }

  private def addMouseEventHandler(g: Graph) {
    scxCanvas.addEventHandler(MouseEvent.MOUSE_CLICKED, new EventHandler[MouseEvent]() {
      override def handle(me: MouseEvent) = {
        val closestVertex = g.closest(me.getX.toInt, me.getY.toInt)
        //println(s"Original vertex: $closestVertex")
        fromVertex = Some(closestVertex)
      }
    })

    scxCanvas.addEventHandler(MouseEvent.MOUSE_MOVED, new EventHandler[MouseEvent]() {
      override def handle(me: MouseEvent) = {
        val closestVertex = g.closest(me.getX.toInt, me.getY.toInt)
        //println(s"Closest vertex: $closestVertex")
        val oldToVertex = toVertex
        toVertex = Some(closestVertex)
        if (!oldToVertex.equals(toVertex)) runDijkstra(g)
      }
    })
  }

  private def runDijkstra(g: Graph) {
    (fromVertex, toVertex) match {
      case (Some(f), Some(t)) => {
        val sol = Dijkstra.run(g, f, t)
        drawGraph(g, sol)
        println(s"Sol from $f to $t is $sol")
      }
      case _ =>
    }
  }
}

I am still trying to grasp ScalaFX - but looks ok so far. Full source code available on request. Just email me.