A web developer specialising in Laravel and AngularJS.

Raga Man - Scala Anagram Finder

Anagram Finder

There is only so far you can go with Hello World, so my next task was to solve a problem a friend of mine was given in an interview. How would you write an anagram solver in scala.

Don't expect a nice pithy solution, this will be a journey trying out various constructs along the way. I will be writing tests for everything, but things may get messy. For a start - I am too lazy/eager to start a new project so I am just hacking it on to my hello world app. Once I have a working tool I will look at refactoring and creating some sort of restful api.

The rules:

I'm unsure what constraints the interview question set, but mine are as follows:

  • Given a word and a list of valid words, find all potential anagrams of that word.
  • Any potential anagram must consist of one or more valid words that are, obviously, not the same word.

The code.

I have added the source code to my github account, feel free to check it out. I will include code snippets inline, but if you want to know what goes where in the file system, please browse the various tags I have created an linked to github.

So, to get started - I created a class called AnagramFinder and wrote a spec for that class.

import org.specs2.Specification

class AnagramFinderSpec extends Specification { def is = s2"""
  I can get an instance of an AnagramFinder
    valid instance          $anagramFinder1
    should contain the word that we are looking for anagrams of $hasword
  I can check that a word is entirely contained within another word
    hell is contained in hello $hello_contains_hell
    help is not contained in hello  $hello_does_not_contains_help
  """
  def anagramFinder1 = new AnagramFinder("hello") must beAnInstanceOf[AnagramFinder]
  def hasword = new AnagramFinder("hello").word must be_==("hello")
  def hello_contains_hell = new AnagramFinder("hello").contains("hell") must be_==(true)
  def hello_does_not_contains_help = new AnagramFinder("hello").contains("help") must be_==(false)
}

The code required to pass these tests is here:

class AnagramFinder(myword: String ) {
  var word: String = myword
  def contains(str: String) = {
    word.contains(str)
  }
}

so far so good, but nowhere near complete, for instance this wont work when asked if hello contains "leo", which it clearly does.

So lets add a test

leo is contained in hello  $hello_contains_leo
...
def hello_contains_leo = new AnagramFinder("hello").contains("leo") must be_==(true)

see here for code

Now this doesn't pass

[info] AnagramFinderSpec
[info]   I can get an instance of an AnagramFinder
[info]     + valid instance
[info]     + should contain the word that we are looking for anagrams of
[info] 
[info]   I can check that a word is entirely contained within another word
[info]     + hell is contained in hello
[info]     + help is not contained in hello
[error]     x leo is contained in hello
[error]  the value is not equal to 'true' (AnagramFinderSpec.scala:17)

So I tried a couple of ways of doing this, and to cut a long story short, word.toList.contains(str.toList) didn't work; and word.toCharArray.contains(str.toCharArray) didn't either

but thanks to StackOverflow I found this sugestion that did.

class AnagramFinder(myword: String ) {
  var word: String = myword

  def contains(str: String) = {
    str.toSet.subsetOf(word.toSet)
  }
}

running my tests again:

[info] AnagramFinderSpec
[info]   I can get an instance of an AnagramFinder
[info]     + valid instance
[info]     + should contain the word that we are looking for anagrams of
[info] 
[info]   I can check that a word is entirely contained within another word
[info]     + hell is contained in hello
[info]     + help is not contained in hello
[info]     + leo is contained in hello
[info] 
[info] Total for specification AnagramFinderSpec
[info] Finished in 39 ms
[info] 5 examples, 0 failure, 0 error

This is the point where I start to see the elegance of scala as a language

Fisher-Price: My first Scala test

Once I managed to get hello world working (see Getting Started With Scala) I wanted to find out how to write a simple test. A friend recommended specs2 so that is what I'm going with.

Create a build definition

Following this guide I created a build.sbt file in my projects root

mark@sister:~/src/scala/hello$ ls -la
total 24
drwxr-xr-x 4 mark mark 4096 Nov  6 07:49 .
drwxr-xr-x 6 mark mark 4096 Nov  4 07:56 ..
-rw-r--r-- 1 mark mark   65 Nov  6 07:49 build.sbt
-rw-r--r-- 1 mark mark   78 Nov  4 08:04 helloWorld.scala
drwxr-xr-x 3 mark mark 4096 Nov  6 07:46 project
drwxr-xr-x 5 mark mark 4096 Nov  4 08:07 target
mark@sister:~/src/scala/hello$ 

In the .sbt file, the blank lines are significant*, see the scala-sbt docs, so my initial file looks like this:

* apparently no longer significant with recent versions of sbt ymmv

name := "hello mark"

version := "1.0"

scalaVersion := "2.10.5"

Testing that this file is valid I run

sbt run
mark@sister:~/src/scala/hello$ sbt run
[info] Set current project to hello mark (in build file:/home/mark/src/scala/hello/)
[info] Running HelloWorld 
Hello World!
[success] Total time: 1 s, completed 06-Nov-2015 07:56:12
mark@sister:~/src/scala/hello$ 

Note the subtle change in the name, now reported as hello mark

Now to add a test

Yes I know, the tests should have come first, but not testing is simpler and I always like to start with the simplest task first.

Following Eric Torreborre's Quickstart I added the following to my build.sbt:

libraryDependencies ++= Seq("org.specs2" %% "specs2-core" % "3.6.5" % "test")

scalacOptions in Test ++= Seq("-Yrangepos")

and I created a new file HelloWorldSpec.scala

mark@sister:~/src/scala/hello$ cat HelloWorldSpec.scala

import org.specs2_
class HelloWorldSpec extends Specification { def is = s2"""

This is my first specification
  it is working                 $ok
  really working!               $ok
                                """
}

I then ran sbt compile

[info] Set current project to hello mark (in build file:/home/mark/src/scala/hello/)
[info] Compiling 1 Scala source to /home/mark/src/scala/hello/target/scala-2.10/classes...
[error] /home/mark/src/scala/hello/HelloWorldSpec.scala:1: object specs2_ is not a member of package org
[error] import org.specs2_
[error]        ^
[error] /home/mark/src/scala/hello/HelloWorldSpec.scala:2: not found: type Specification
[error] class HelloWorldSpec extends Specification { def is = s2"""
[error]                              ^
[error] /home/mark/src/scala/hello/HelloWorldSpec.scala:2: value s2 is not a member of StringContext
[error] class HelloWorldSpec extends Specification { def is = s2"""
[error]                                                       ^
[error] three errors found
[error] (compile:compileIncremental) Compilation failed
[error] Total time: 1 s, completed 07-Nov-2015 08:30:23

Ok so that didn't work. It appears that the compiler isn't finding org.specs2!

So here's my file layout, note that project and target directories have been created by the build tool.

mark@sister:~/src/scala/hello$ ls -la
total 28
drwxr-xr-x 4 mark mark 4096 Nov  7 08:34 .
drwxr-xr-x 6 mark mark 4096 Nov  4 07:56 ..
-rw-r--r-- 1 mark mark  185 Nov  7 08:33 build.sbt
-rw-r--r-- 1 mark mark   78 Nov  6 08:15 HelloWorld.scala
-rw-r--r-- 1 mark mark  229 Nov  6 08:11 HelloWorldSpec.scala
drwxr-xr-x 3 mark mark 4096 Nov  7 08:33 project
drwxr-xr-x 5 mark mark 4096 Nov  7 08:34 target

My build layout is non-statndard so I set up a structure as suggested on the sbt man pages

mark@sister:~/src/scala/hello$ mkdir -p src/main/scala
mark@sister:~/src/scala/hello$ mkdir -p src/test/scala
mark@sister:~/src/scala/hello$ mv HelloWorld.scala src/main/scala/
mark@sister:~/src/scala/hello$ mv HelloWorldSpec.scala src/test/scala/
mark@sister:~/src/scala/hello$ sbt clean
mark@sister:~/src/scala/hello$ sbt compile

This now works fine for compilation

[info] Set current project to hello (in build file:/home/mark/src/scala/hello/)
[info] Updating {file:/home/mark/src/scala/hello/}hello...
[info] Resolving org.fusesource.jansi#jansi;1.4 ...
[info] Done updating.
[info] Compiling 1 Scala source to /home/mark/src/scala/hello/target/scala-2.10/classes...
[success] Total time: 3 s, completed 07-Nov-2015 08:39:02

but running sbt test still causes the same compile error, so it wasn't my directory structure.

mark@sister:~/src/scala/hello$ sbt test
[info] Set current project to hello (in build file:/home/mark/src/scala/hello/)
[info] Compiling 1 Scala source to /home/mark/src/scala/hello/target/scala-2.10/test-classes...
[error] /home/mark/src/scala/hello/src/test/scala/HelloWorldSpec.scala:1: object specs2_ is not a member of package org
[error] import org.specs2_
[error]        ^
[error] /home/mark/src/scala/hello/src/test/scala/HelloWorldSpec.scala:2: not found: type Specification
[error] class HelloWorldSpec extends Specification { def is = s2"""
[error]                              ^
[error] /home/mark/src/scala/hello/src/test/scala/HelloWorldSpec.scala:2: value s2 is not a member of StringContext
[error] class HelloWorldSpec extends Specification { def is = s2"""
[error]                                                       ^
[error] three errors found
[error] (test:compileIncremental) Compilation failed
[error] Total time: 2 s, completed 07-Nov-2015 08:41:51
mark@sister:~/src/scala/hello$ sbt compile

Maybe time to stop guessing and try a bit of research... watch this space

After a bit of hackery and some trial and error, it appears that the solution is to import the Specification class explicitly, replacing import org.specs2 with import.specs2.Specification. This resulted in success.

mark@sister:~/src/scala/hello$ git diff src/test/scala/HelloWorldSpec.scala
--- a/src/test/scala/HelloWorldSpec.scala
+++ b/src/test/scala/HelloWorldSpec.scala
-import org.specs2_
+import org.specs2.Specification

mark@sister:~/src/scala/hello$ sbt test
[info] Loading project definition from /home/mark/src/scala/hello/project
[info] Set current project to hello (in build file:/home/mark/src/scala/hello/)
[info] Updating {file:/home/mark/src/scala/hello/}hello...
[info] Resolving org.fusesource.jansi#jansi;1.4 ...
[info] Done updating.
[info] HelloWorldSpec
[info] 
[info]   This is my first specification
[info]     + it is working
[info]     + really working!
[info] 
[info] Total for specification HelloWorldSpec
[info] Finished in 26 ms
[info] 2 examples, 0 failure, 0 error
[info] 
[info] Passed: Total 2, Failed 0, Errors 0, Passed 2
[success] Total time: 2 s, completed 07-Nov-2015 09:51:29

Great, so we have a scala app that runs and a test that asserts that true is true. It's a start I suppose, nothing wrong with baby steps.

Getting Started With Scala

This is not a tutorial*

* Well it kind of is. I wanted to learn how to program in scala, with pretty much zero knowledge. I wanted to use test driven development from the start. I know how to program, just not scala. This isn't a how to code scala guide, just a how to get started. I'll talk you through getting a build tool and setting up an ide, and getting some tests working. Once you get started, go soewhere else to learn how to do it well! These are just my ramblings as to how to get started.

I'm using Linux Mint 17 to do this, but any flavour of Ubuntu should be similar.

Hello World

A cliche, but what respectable programmer doesn't start with this.

Get the scala build tool.

echo "deb https://dl.bintray.com/sbt/debian /" | sudo tee -a /etc/apt/sources.list.d/sbt.list
sudo apt-key adv --keyserver hkp://keyserver.ubuntu.com:80 --recv 642AC823
sudo apt-get update
sudo apt-get install sbt

Now create a folder to work in

Frm this point I pretty much followed this tutorial but here's a summary of what's involved.

mkdir -p src/scala/hello
cd src/scala/hello
echo 'object HelloWorld { def main(args: Array[String]) = println("Hello World!") }' > helloWorld.scala
sbt run

The sbt will download the a bunch of required packages the first time you run this command, which may take a while, these will be cached in the ~/.sbt folder. Subsequent runs should be instantaneous.

Getting org.scala-sbt sbt 0.13.9 ...
downloading https://repo.typesafe.com/typesafe/ivy-releases/org.scala-sbt/sbt/0.13.9/jars/sbt.jar ...
[SUCCESSFUL ] org.scala-sbt#sbt;0.13.9!sbt.jar (1896ms)
downloading https://jcenter.bintray.com/org/scala-lang/scala-library/2.10.5/scala-library-2.10.5.jar ...
[SUCCESSFUL ] org.scala-lang#scala-library;2.10.5!scala-library.jar (4631ms)

... etc

and you should then see the reults of your labour.

Hello World

amazing! Now you can go on to writing some tests

What to write about.

For some years now I have owned the domain markfee.com. It's good to own it, it's my name and it's easy to remember. The only problem is that, apart from a whole load of geekery, I have no idea what to do with it.

Geekery: obsessive interest in or enthusiasm for a subject, typically one of specialist or minority interest:


Mk 1. A self written CMS.

Back in the day, before kids, we went on lots of holidays and lots of bike rides and took lots of photos. So I taught myself php and wrote a sort of CMS that loaded my photos dynamically based on folder names passed through the url (eek).

I posted a link on a synth geek forum I frequented at the time. Soon after someone on the forum posted back a link which exposed the contents of my servers root directory. I have to confess that there are better ways to learn about HTML injection.


Mk2. Self hosted Wordpress site.

After a few iterations of markfee.com mk1 (with added protection) I was writing php professionally and was frankly ashamed of my early efforts, so I replaced markfee.com with a self hosted wordpress blog. This was fine but I didn't have much to say and most of my posts were just a bunch of photos, only it was much more of a hassle to upload and layout my pics than before, so the site just stagnated. Besides facebook is a much better forum for sharing a picture of my kids dressed like the Peaky Blinders.

**featured-image**


Mk3. Ghost.

Lots of forums were singing the praises of Ghost so I thought I'd jump on the bandwagon. I can confirm that it is very easy to install, it has taken me longer to write this post than it did to get started.


How I set it up.

For the record it went roughly like this (on a debian box).

Install node js
sudo curl -sL https://deb.nodesource.com/setup | bash -
sudo apt-get install -y nodejs
Install ghost
cd /var/www/
curl -L https://ghost.org/zip/ghost-latest.zip -o ghost.zip
unzip -uo ghost.zip -d ghost
cd ghost/
npm install --production
Run as a service
sudo curl https://raw.githubusercontent.com/TryGhost/Ghost-Config/master/init.d/ghost   -o /etc/init.d/ghost
sudo useradd -r ghost -U
sudo chown -R ghost:ghost /var/www/ghost
sudo chmod 755 /etc/init.d/ghost
sudo update-rc.d ghost defaults
sudo update-rc.d ghost enable
sudo /etc/init.d/ghost/start
Finally configure apache to reverse proxy

This is covered quite nicely on allaboutghost.com