## A simple calculator in Scala

Here1 (credits to Ben Lynn2) is a simple calculator in Haskell.

I decided to try porting it over3 to Scala. The original example also makes this work in Javascript using `Haste`; I’ve left this out for now (though I might come back and get this to work under `Scala.js` later).

The underlying basis is the same, using the awesome `fastparse` library to stand-in for `Parsec`/`Megaparsec` from Haskell, and the code feels quite concise and readable to me4.

This is the entirety of the parsing code we need:

```  def numParser[_: P] = P( ("-".? ~ CharIn("0-9").rep ~ ".".? ~ CharIn("0-9").rep).!.map(_.toDouble) )
def parenParser[_: P]: P[Double] = P( "(" ~/ exprParser ~ ")"  )  // needs explicit type because it's recursive.
def factorParser[_: P] = P( parenParser | numParser )
def termParser[_: P] = P( factorParser ~ (CharIn("*/").! ~/ factorParser).rep ).map(eval)
def exprParser[_: P] = P( termParser ~ (CharIn(" \\-").! ~/ termParser).rep ).map(eval)

```

… along with a tiny bit of evaluation:

```  def eval(ast: (Double, Seq[(String, Double)])): Double = {
val (base, ops) = ast
ops.foldLeft(base) {
case (n1, (op, n2)) =>
op match {
case "*" => n1 * n2
case "/" => n1 / n2
case " " => n1   n2
case "-" => n1 - n2
}
}
}

```

That’s it.

That’s all you need to take in a `String` and convert it to a `Double`.

What Ben says about the evolution of parsing-as-it-used is true: it was completely normal to resort to lex/yacc and then flex/bison for these earlier, but Parser Combinators and PEGs take it to a whole other level, and once you’ve become comfortable with them, there’s no going back to the verbose old days.

Just to break down the parsing code a bit:

This parses a number: `def numParser[_: P] = P( ("-".? ~ CharIn("0-9").rep ~ ".".? ~ CharIn("0-9").rep).!.map(_.toDouble) )`. Or rather, it returns a function that can parse a number.

It’s possible to play5 with this within a repl; I use `sbt console`6 when something depends on a class/object within a project, but this is an independent enough chunk that you could use `ammonite`7 instead too.

```agam-agam@ import fastparse._
import fastparse._

agam-agam@ import NoWhitespace._
import NoWhitespace._

agam-agam@ def numParser[_: P] = P( ("-".? ~ CharIn("0-9").rep ~ ".".? ~ CharIn("0-9").rep).!.map(_.toDouble) )
defined function numParser

agam-agam@ parse("45", numParser(_))
res263: Parsed[Double] = Success(45.0, 2)

agam-agam@ parse("4.5", numParser(_))
res264: Parsed[Double] = Success(4.5, 3)

```

Where it gets interesting is composing these parsing functions.

Given a function to parse a `factor` (a number, or sub-expression within parentheses), we can define a function to parse combinations of multiplying/dividing these as:

```def termParser[_: P] = P( factorParser ~ (CharIn("*/").! ~/ factorParser).rep ).map(eval)

```

… which reads very “regex-like”, imo!

Anyway, I added a basic I/o driver around this, so it can be “run” as:

```➜ sbt run
[info] Set current project to hello-world (in build file:/home/agam/code/simplecalc/)
[info] Compiling 1 Scala source to /home/agam/code/simplecalc/target/scala-2.13/classes ...
[warn] there was one deprecation warning (since 2.11.0); re-run with -deprecation for details
[warn] one warning found
[info] running Main
Simple calculator

Enter an expression, or 'END' to quit: 5   6
Result: 11.0

Enter an expression, or 'END' to quit: 2 - 5.2 * 1.5
Result: -5.800000000000001

Enter an expression, or 'END' to quit: 1.8   2.3 / 4.5
Result: 2.311111111111111

Enter an expression, or 'END' to quit: 42   1 - 5
Result: 38.0

Enter an expression, or 'END' to quit: END
[success] Total time: 55 s, completed Aug 6, 2020, 11:36:47 PM

```

(Yeah, the weird decimal point behavior is just `Double` being a double; that is beyond the scope of this example 😐)

1. ”Parser Combinators” ↩︎
2. Indeed, Ben has a bunch of other awesome stuff like this, and I might just go Scala-ize more of them 🙂 ↩︎
3. Repo (with this core code, as well as a `Main` driver and tests) is here ↩︎
4. My subjective opinion is that Scala is a sweet spot between ↩︎
5. I’ve taken a “shortcut” with my `map(_.toDouble)` bit there, so it doesn’t fail properly right now and you get `java.lang.NumberFormatException: empty String`, but normally you’d get a `Parsed.Failure` back ↩︎
6. Console ↩︎
7. Ammonite ↩︎

## Cave generation

I came across this brief overview1 of generating ASCII representations of dungeons, and decided to take a stab at a Scala version of the same.

The basic idea is (1) generate some random walls, and then (2) apply some rules to transform this into a reasonable-looking closed cave over a few iterations.

I ended up tweaking a couple of parameters (wall-wall distance, number of iterations) a bit differently, here’s how it looks:

```➜ sbt
[info] Set current project to hello-world (in build file:/home/agam/code/caves/caves/)
[info] sbt server started at local:///home/agam/.sbt/1.0/server/4e9ac60073a7ab62e5f4/sock
sbt:hello-world> run

```

Iteration zero: random walls

```######################################################################
#...####..#.#..#.#......#...#.#..#..#...#.####....##...#.##.##....##.#
#..#####.###.#..##..#....#.##.#...#.###..#.#...##.....###..#..##.....#
#....#......##..#.#....###..##....#....#....#.....##...##.#..###....##
#...#....#...####.#.###.###.#.#.#...#..##..##......#..####.#..#...####
#.......#.#..#...#....###.#.###.#...####.#..#.####..###.#..#####.#...#
##.#.....#.....###.#.#....#.....###.#..##..##.........#.#....#.#..#..#
##...#####..#####.#...#...#..#.#.....##.....#.#.....#......###.#....##
#..###..#..#...##.#..##..#.#..#..###...#.#...#...##..#...#.#...#...#.#
#...#.#####...#....######..###..#..#..####.###.#..#..##....#.##.#...##
###..###........#.#.#...###...###.#.#.##.....#.##.#.###.#.#.##..#..#.#
#....#.##.....#.#.##..##.#..#.##...#.#.##...#.###...##..##........####
#...#.#.......###..##.#####...#.##...#####.##.##.##.#..#...#.##..#####
#.#..##..###..##.......###..###...##..#.#...#...###..#.####..##.##.#.#
#.#.###.#..###.#........#.#..#.##.##..##.#.#.#..#.###.##.##.#####....#
##..#.....####.#.#.##...#.#...###.##..#...#...#.###..#..#...#.#.....##
####...###.#..#.##.#.#.........##.###.#.#..#.#...#...#.#..#..##..##.##
##.#...#..#...#.##......###.###.......#.#.#......#.#..#.#.##..#...##.#
###....#..#......#.......##....###..##..##.#..#..#.#....##..#..#.#..##
##..##.....####.####.###.##...#..#..#..##.......##.##.....#.###..##..#
#.......##....#......#........#...####.##..#.##.#.#...#...#.##.#..#..#
##...........#....###...#.##...#........#..##..#.........##.......####
#....##.##..##..#...#...##......#...####....##..#..#....#..####....###
#....#.#.....#...#..#..#.#####....#.........#.#..#..#.#.###......#...#
#.#.#..#..##.#..##.#..#...###...#.#.##.###...#..###.#.##.#...##.##.#.#
#....................................................................#
#..##.##.#.#.##..#..###.#.#.....###.#.#.#....#...#...#.....#....#.##.#
#..##..#.#.....#..####..#.#...##.##..#.###.##..#......#....#.#.#...###
#..#####.#..###..##.##..#....#..........#.#.#...#....#..##.#....####.#
#.#.##....#.#.##.#.#.#.##.....#....###..##.#..#.......#.##...##..#####
#..#........###.####.....##....##..#.#.##..#.##..##...##.#.##.#......#
#.....###.#.##.#..#####...##..............###.######......##......##.#
#..###...#..#####..##....##.#.##...##.....#.#.#..##...##.........#.#.#
#...#..##.#..##.##.........#..#.....#.#..#.#.###......##...#.#...#.###
#.....#.##..###.#...#.....#...##.#...#.#.#..#...#...###..#.###..##.###
#...#..#.#..##.##...#....#....##.##..#.#..#........###.#..##...##....#
#...##...#.#.#...#...#...##...#.#.###.....##.#.##.#.#.#..#.#.#...#...#
#.#........##.#...##..##...##.....###..###.....#.........#.#.#.###...#
#.#.##.....#..#..#....#.###.###..##.#.#....##..#.#..##..#.#.#####....#
##...#..##..#.###.##.##.###..#.#......#.#.####.#.####.##...###...#...#
#.###.###.#....#.##..#.#.#.##.#.#...#...##..#...#.###...#..##..#.##.##
#.#..##.....#...#....#.#.#.#.###.####.##........###.#...##.##..##.#.##
#..##..#..#..#........#....####.#..##.#........#...#.#..#....#.#...#.#
#.#.##.#..#.#####.#..##.##..##..#......#..#.#..##....##.##.###.#...###
#...#...#....##.#..#.#.##.####.#.#..#.#.....#.#.#...#...#.##.####....#
#...##.######.##..###.#.###..#.......###.#.###..#.#.#.##.##....#####.#
#....##.###......#.....#..#...##.#.#....#......#.#.##...#...##.#####.#
#.#.#..#..#..###...######.#.####..#.#..#...####.##....#....#..#...##.#
###.##.##.##......####..#..##.#..#.....###.##.#...#....#####....#.#..#
######################################################################

```

Iterations 1-4: Coalesce larger islands

```######################################################################
######################..############################..################
#####################...#######..###################..###########...##
##..##......##########.#######........########....##..##########...###
#....#.......##################..#....########.......###########....##
#..##..#.##....###############...#....########.####..###########.##..#
##......##..#.##########.####......##.###..###.#..##.......#####.##..#
##......##..###########...###.##............###......#..#..#####..#.##
#..##..####...##########...####...#.#....#..###...#...#.#...####....##
##....####.##....########..#####.#.#.....##.####..#..###....####.#..##
##....###..##....#########...####............####...#####..........###
#..#####...#......########....###...#..##....####...#####.##......####
#...###...#....#...#######.#.####..#...##..#..####....######.....#####
##..###.......###......###..########...##..##..####...################
##..##..#..######..#....##...#######...........#####..###########...##
#####...###############...##..######..#..##.##..###....#########....##
####....####.##########.......######..##....##...##..#.########...####
####..##.##.....###.........#..####........#..#...#..#..#######...####
###..##.........###...#..####..###...#...###..#.....##...######....###
##..##..##.###...##..##......#......#...#........#..####..#####.#...##
##.##...#.#...##......##...#.##..##....##.....##.##...##..####..##..##
##.#.....#.....#...##.........####..#..##.##......##.......###..#..###
#.....#..##.##..##..#...#.................###..#....#......###..#...##
#..##.##..####..##..####...#####.#####..#....##.##...#.##.#.....##..##
#..#...#..........#....##..##.#.....#...###..#...###..#####..##...#..#
#........##..##..#.........#.........#....#..##..##.#.....#..##..#...#
#.........#...#.....##...###..#..##..##.......#...#..##.............##
#.....#...#......#####...##..##.###........#...####..##.#..##..##..###
#....#####.......#####......##.......#..#..#......#....###..#...######
#.###............####..##...#..##...##..#.....#....#...###...#...#####
#..#...#..#......#####.#...#...####..#.##....######.#.......####..####
#........#........####.#..##......#...##...#.#######.#...###..##..####
##.###....#........##.##...#..#..#.#......#.#######...#.#.........####
#..##....#...#..##....##..##..#.....#...#....#####...###....##....####
#..#...##...#####..#..##...#..##.....##.#...........###....##..##..###
#...#.#.#...#####..##....#....##......#...###....#.####..####.......##
#....##.##..####...##......#...#...#......##..##.#......#####....##..#
##.#....#....##........#...##....###..#.#................##########..#
###........#.###..#.....######....#..###...##........##...########...#
####.....##...#####..#..######..#..........##.##...####....#######...#
####..#..#.#...###..#...#########.......###..#....####..#..#######..##
######.#....#.....##......########.##..###..##.....##...#...#####...##
#######..#...#....#..#.....######..##..##...#..##...........####..####
######...#...###...........######..#.....#.....##.#..#.....#####...###
##.###..###..###..##...#..######..#..##..##..#.......##...#######...##
#...########..#..###.........###..#...#..#...#.....####.##..##########
#....######..............#...###..##.#..........#...........##########
##....#####...##...###......####.................#...............#####
############..###########..#######.....########..##.#..#####....######
######################################################################

```
```######################################################################
######################.###############################################
###############################..################################..###
##..###.....###################......##########...##############...###
#...##.......##################.##....#########.....############....##
#..##...##.#..################..####..##########..#..#############...#
##..##..##...#################......#..##..#####.##.......########...#
##..#...##...##################..#..##......###..##..#.....######...##
##..#..####...#################..##.###.##..###...#...#.##..#####...##
##....######....##################...#...##.####..#..####....###....##
##...####.#####..##########..####..##.....#..####...#####..#..#....###
#...####...#..#...#########..####..##..#..#..####....#######......####
#...###..##....#...########..#######..###..#..####....#######....#####
##..###.......###......###...#######...#...#...####...################
######.....#########....##...#######..#..##....####.#.###########..###
#####....#############...###..######..#..#...#..###...##########...###
####....################......######..###...##...##....########...####
####..#..##....#####...#.......####..##....#..##....#...#######..#####
###..##.........###.....#####...##..##....##..##....##...######....###
######.....###...#...##..#####......#...#..#..###....##...#####..#..##
#####..##..#..#...#...#......##...###..##........##...###.####..##..##
####...........#...#...###......##....##...##.....##...#...###......##
####..#..#..#...#...#..##.#.....###...#....##..#....#......##..##...##
####..##...###.#.#.#...##..###...###.#..##.....##......####......##.##
###.###.#.....#..##.#..#...##.##....#...##..#....##.#...###..##..##..#
##..##..##.#..##.....#.#..##...#.....##..#.###...###.#.......##..#...#
#..#......###.##....##...###.....##..##.#.....#####..##...##........##
#..#..#....##.#...####.......#...##.....#..##..####..####..#...#...###
#.....####..###..#####.###..##......#...#.###.......#.####..#.....####
#..##.###..#.##..########...#..##...##...#.............##....#....####
#..#......##..##.#######...#...###....##..#...#####.#.....#...##..####
#.....##..##..##..######..#.#.#...##..##..##.#######.#...###..##..####
#....##...#........#####...#.....###......#.#######...#.##........####
#.##.....##..........###..##..#.##..##..##...#####...###.....###..####
#..#.....#...###.#....#.###..###.#...#.##...........###....##..##..###
#..#.##..#..#####.##.#...#....##..#...#....##.#..##..#...####.......##
#....##..#..####...####........#..##.....#.#..######..#..#####...#...#
##..##.##...####.......#...##..#..##..#.##............#..#########..##
###....#.....#####..#...######....##.##.....#..##....##...########...#
####..#..##...####..##..########.....##........##..####.#..#######...#
#######..###...###...##..########.......###.#......###..##.#######..##
#######.....#.....#..##...#######..##..###..##..#......###..#####..###
#######.....##...##..####..######..##...#...#..#####..#.#...####...###
######.......##........##..######....#....##......#........#####...###
###########..##...###..#....####..#..##..##.####..#..#..#..######..###
##..#######..#..####.######..###..##..####..##.##..#######..##########
##...######..#......###..##..###..##..#.........#...#........#########
###..######...##...#####....#####...............................######
############.############..#######..#..########..####..#####...#######
######################################################################

```
```######################################################################
######################################################################
#################################################################.####
##.####.....#######################..###########..##############...###
#..###.......######################...##########...##############...##
#..###..#.##.######################...##########.....#############...#
##..##..##...#####################.....##..#####..#.......#########..#
##......##...#####################..........###..###.......#######..##
##.##..####...####################..###..#..###...#......#..#####...##
##....######...###################..##.#.#..####...#.####....###....##
##...########....################..##.....#..####.#.#######....#...###
#...########.#....###################..#..#..#####...#######......####
#...#######........########.########...##..#..####....#######....#####
##.####.......###......###...#######..##...##..####...################
######.....#########....###..#######......#....####...###########.####
#####..#.#############...###..######....##...#..###.#.##########..####
####....###############.......######...##...#....#..#..########...####
####..#..##....#####...#.......####...##...#.....#..#...#######...####
######..........###.......###...##...#....##..##....##...######....###
######.##..####..#...##....###......#...##...###.#...##..######.##..##
#####..##.##..#...##..#......##....##..##........##...##..####...#..##
####.....#.....#...#...##.#..#.........#...##..#..###..#...###..#...##
####..#...#.#...#...#..###......###..##....##.##....#......##..#....##
####.###...#.#...#..#..##....#...##..#...#.....#.....#...##.......#.##
#########.....#..##.........###.........##..#........##.##...##..##..#
######...#....##.#....##..##..##..#..#......##...##..##......##.##...#
#####......#..##....##....#...#..##..##.#.......###..###..##..#.#...##
####.........##...####...#...#...##..#.#...#.##..#...####..#...##..###
####...##...###..########...##......#...#..####...#...###..##...#.####
####...##....##..########..##...#...#....#.........#...#.....#....####
###.#.....#...##.#######...#...#...#..##..#...#######.#...#...##..####
##...##...##..##..######.....##...##..##...#.#######.....###...#..####
##...###..##...#...#####..#..#...###......#.#######.....#.#.......####
###..................###.##...#.###..#..##...#####...###......##..####
###.....##...###.##...#.###...####...###.#...........##....#..##...###
##...#...##.#####.####...#.##.#####...#....##....##.......###....#..##
##..###.....####...###..#......#####.....#.##.#..###..##.#####..##..##
##.....##...#####......#...##....###....##..#..#......#..#########..##
###.....#....#####......######....#..##..#..#..##....##...########...#
####.....##...####..##..########..#..##.....#..##.#####...########...#
######..###....###...##..########.......##..#......###..##########..##
#######.##..#....##..###..#######..##...##..##.........###.######..###
#######.....##....#...###..######..##..#.......##.##.#.....#####...###
########.....###.......##..######.....#...........#..#.....#####...###
##########...##...##..####..####.........##.###.....#####..######.####
###########......##########..###..###.#.###..#.###..######..##########
###########........#######...###...#.##.........##...........#########
###########...##..#######...#####..............................#######
##################################.....########..####..#####..########
######################################################################

```
```######################################################################
######################################################################
######################################################################
#######.....##########################################################
######......########################.############..###################
######..#....######################...##########.....#################
#####...##...#####################..#..##..#####..#.......############
#####...##...#####################..##......###..###.#.....#######.###
####...####...####################..###.##..###...#.........#####...##
###...######...###################..##..##..####.....####....###....##
##...########.#..####################........####..########.....#..###
#...########.##...###################..#..#..#####...#######......####
#...#######........#################..##..##..####....#######....#####
#######.......###......#############..##...#...####...################
######.....#########....############.#....#.#..####...################
#####...##############...###.#######.....#..##..###...##########.#####
####..#.################......######..###...##...#..#..########...####
######...##....#####...##......####...##...#.......##...#######...####
######..........###.....##.##...##...#....##..##....##...######....###
######.#...#.##..##..##.....##..#..##....##...#..#...##..######.##..##
#####..##.#.#.#...#..##...#..##.#..##..##........##...##..####..##..##
####.....#.....##..#...####..#.........##..##..#...#...##..###..#...##
####......#.#...#..##..###..#...###..##....##.###.###......##..##...##
########..####.....##........#...##.##..##.....#.........#..........##
########.#.......##...##..#...#.........##..##....#.....###..#...##..#
######..###....##.....##..##..##.....#...#..##...##..........#...##..#
#####....##...##....##....#...#..##..##..##......##.####...#..#.....##
####..#...#..##...#####..#...##..##...##.....###.....####.##...##..###
####..##..#..##..########...##..##..#...#...###.......###...##..#.####
####...##.#..##..########..##...#...#....###...........#.....#....####
###...........##.#######..#....#......##..#...#########...#...##..####
##..###...##..##..######..#..##...#...##.....#######.....####..#..####
##..####..###......#####....##...##.#....#...######.....#..##.....####
###....#.............#####......###.##..###...####..#####.....##..####
###.....##...###.....######....####..##....#.........##.......##...###
##..##...##.####..########..#######..##....##.#...##......###.......##
##..##......####...######......#####....#..###.#..##...#.#####..#...##
##..##.##...#####......######....###....##..#...#.....#..#########..##
###....##....#####.#....######....#..##..#.....##....##...########...#
####....##.#..####..#...########.....##....##..##...###..#########...#
######..###....###...##..########.#......#..##..#.......##########..##
#######..#..#....##..###..#######..##..####..#..#.##....#########..###
#######...#.......##..###..######..##.##..#....#..##..#...######...###
########..#..###......###..######.....#......#.......###...#####...###
##########..####..##.#####..####..#......#..###..#..#####..###########
###########.#.....########...###..##.##.####....##...#####..##########
###########.......########...###..#..##.......#..#..#........#########
############..##.################.............................########
##################################..#..########..####..#####.#########
######################################################################

```

Iterations 5-7: Coalescing smaller islands

```######################################################################
######################################################################
######################################################################
#######....###########################################################
######......#####################################..###################
######.......###################################.....#################
#####........############################..#####..........############
#####...##...############################...###...#........###########
####...####...############################..###...#.........#####..###
###...######...#######################..#...####.....####....###...###
##...########....####################........####....######........###
#...########......###################........#####...#######......####
##.########........#################...#......####....#######....#####
#######.......###......#############...#.......####...################
######.....#########....############...........####...################
#####....#############...###########.....#......###...################
######...##############.......######.........#.........#########.#####
######.........#####...........####...##................#######...####
######..........###.....#.......##.........#...#.........######....###
######...........##.................#......#..#...#......######.....##
#####...#...#.................#.....#...#.................####...#..##
####...........#........##.....#....................#..#...###...#..##
#####..........#....#.......#..................#....##..............##
#######.....##...................##..#.........#.....#........##....##
#######.....#.....##...#.................................##..........#
######.....................#.............#...#...................#...#
#####.....#.....#...##....#...........#...#......##...##............##
####..............#####............#...#.....##..##...###..#.......###
####...#.........#######.....#...#..#.................###.........####
####....#..#.....#######........#.........##..........##......#...####
###..............#######..#............#...#..######...........#..####
##...##.......##..######......#..............#######........#.....####
##....#....#.......######...##...#...........######......#..#.....####
###.................######......###......#....####......##.....#..####
###......#...##..#..######.....####...#..............#.........#...###
##..........####...#######.....####...#.............#.....###.......##
##..........####....#######.....####........#......#.....#####......##
##...#......#####......######....###.....#...#....#......########...##
###..........#####......######........#..............#...#########...#
####..........####......########......#.........#....#...#########...#
######.....#...###.......########............#..........##########..##
#######..........##.......#######.........#........#.....########..###
#######................#...######..#..##..#....##.........######...###
########.....##.......###..######....................###...######.####
##########...##......#####..####.....................####..###########
###########........#######...###..#......#####...##..####...##########
###########.......#########.####...#..#......................#########
############..###################............................#########
##################################.....########..####..###############
######################################################################

```
```######################################################################
######################################################################
######################################################################
#######....###########################################################
######......#####################################..###################
######..##...###################################.....#################
#####........###################################..#.......############
#####...##...##################################...##.......###########
####...####...############################.####.............#####.####
###...######...#######################......####......###....###...###
##...#######.....####################....#...####..#.######........###
##..########.#....###################..#.##..#####...#######......####
###########........#################......#...####....#######....#####
#######.......###......#############..##...#...####...################
######.....#########....############..#...#.#..####...################
######....############...###########.....#...#..##..#.################
######..#..###########........######..#..#...#.....##..###############
######..#......#####...##..#...####...#..#......#...#...########..####
######..#.#.....###....#..###...##....#....#...#.#...#...######....###
######.....###...#..##.......#......#..#...##.#...#..##..######.....##
#####..##...........#...#.....#..#.##..##..#...#.#........####..##..##
#####..##.#....##..#...#.###...#.......#..#............##..##....#..##
######....#.....#....##.....#.#......#...##.##..##..#..#............##
#######..#...#...........#...#...##.##..........##..#.....#..###.#..##
#######.#...###...##...##...#.#.##.....##...#.......#....##..#...#...#
######...#.....#...........#...#..........#...#..............#...#...#
#####....##.#..#....##...##...#...##..#...#...#...#........#..##....##
####..#.....##....#####..#...#........##......#..###...#..##...#...###
####..#.......#..#######....#...#..#..................##..#.......####
####....###......#######..##...##.###..#..##.............#...#.#..####
###......#..#....#######..#...........##..#...#####.##..#...#..#..####
##...##.....#..#..######.....#......#..#.....#######.#.........#..####
##...#.#...#...#...######...##......#...#.#..######.......#.#.....####
###.....#.#.........######..#...##.......##...####...#..#......#..####
###.##...#...##..#..######..#..####..##...#..........#.#.......##..###
##...#..#...####....######.....####...##...#...#......#...###.......##
##.....##...####.....######.....####....#...#.##..##.....#####......##
##...#..#...#####..#...######....##......#........#...#..########...##
###.....##...#####.##...######.......##..##.#..#.....##..#########...#
####....#.....####..##..########..##..#.....#..##.#......#########...#
######....##...###...#...########..#..............##..#..#########..##
#######..##........#......#######.....#..##.##...........########..###
#######..........###.......######..#..#..#..#..###........#######..###
########......#..#....###..######..##.#........#......##...###########
##########...##......#####..####..................#..####..###########
###########........#######..####..#...#..#..###..##...##....##########
###########.......##############...#.#.......................#########
############..###################...........................##########
##################################.....########..####..###############
######################################################################

```
```######################################################################
######################################################################
######################################################################
#######....###########################################################
######......#####################################..###################
######...#...###################################.....#################
#####........###################################..........############
#####...##...##################################..####......###########
####...####...#################################.............##########
###...######...#######################......####......###....###..####
##...#######.....####################........####....######.......####
############..#...###################....#...#####...#######......####
###########........#################..........####....#######....#####
#######.......###......#############..##...#...####...################
######.....#########....############...........####...################
######..#..##########....###########.....#..#...##....################
######......#########.........######..#..#..##.........###############
######...#.....#####...#.......####.................#...########..####
######..........###.....#..##...##...............#.......######....###
######......##.......#..............#...#...#.#...#..##..######.....##
#####.......#.................#....#..............#.......####...#..##
#####....#.....##.##.......#...#..#...#....................##....#..##
######....#..........##..#...............##..##.....#.##............##
#######......................#......#...........##.....#............##
#######.......##..##...#........#..##..#........#...#....##..#..##...#
######...#.................#...#.........###........##...............#
#####....#..#...#...##....#...#............#..#................#....##
####...#.....#....#####......#........##.....##..##....#...##..#...###
####..#.......#..#######..........................................####
####.....#.......#######..##...##..#......##.........#..##........####
###......#..#....#######..#....##..#...#......#####.#...#...#.##..####
##....#.....#..#..######...............#.....#######...#...#......####
##.....#.......#...######....#......#........######........#......####
###.......#.........######..#...##.......#....####......#.....#...####
###..#....#..##..#..######..#..####...#...#.........#..#.......#...###
##..........####....######.....####....#...#..............###...#...##
##..#.......####.....######.....###...........##..#......#####......##
##...#...#..#####......######....#...#...#........#..#...########...##
###..........#####......######........#..#..#.........#..#########...#
####...#......####...#..########...#...#.......#...#..#..#########...#
######.....#...##....##..########..#...............#..#..#########..##
#######..####.............#######........#..#......#.....########..###
#######...........##.......######.....#..#..#...#..#......############
########......#..#....###..######..#..#..#.....#......##...###########
##########...##.#....#####..####...#.....#............##...###########
###########........#############......#..#..##.#.###....##..##########
###########.......##############...#.##..............#......##########
############..###################..........................###########
##################################.....########..####..###############
######################################################################

```

Iteration 8: prune out isolated walls

```######################################################################
######################################################################
######################################################################
#######....###########################################################
######......#####################################..###################
######.......###################################.....#################
#####........###################################..........############
#####...##...##################################............###########
####...####...#################################.............##########
###...######...#######################......####......###....###.#####
############.....####################........####....######.......####
############......###################........#####...#######......####
###########........#################..........####....#######....#####
#######.......###......#############...........####...################
######......########....############...........####...################
######......#########....###########............##....################
######.......########.........######...................###############
######.........#####...........####.....................########..####
######..........###.............##.......................######....###
######...................................................######.....##
#####.....................................................####......##
#####......................................................##.......##
######..............................................................##
#######.............................................................##
#######..............................................................#
######...............................................................#
#####...............##..............................................##
####..............#####............................................###
####.............#######..........................................####
####.............#######..........................................####
###..............#######......................#####...............####
##................######.....................######...............####
##.................######....................######...............####
###.................######......##............####................####
###..........##.....######.....####................................###
##..........####....######.....####.......................###.......##
##..........####.....######.....###......................#####......##
##..........#####......######............................########...##
###..........#####......######...........................#########...#
####..........####......########.........................#########...#
######.........##........########........................#########..##
#######...................#######........................#############
#######....................######.........................############
########..............###..######..........................###########
##########...........###########...........................###########
###########........#############............................##########
###########.......##############............................##########
############..###################..........................###########
##################################.....########..####..###############
######################################################################

```

This was my first “procedural generation” of any kind, so … I’m quite pleased 🙂. The repository is here2 at Bitbucket.

#topublish

## Optimized Sudoku solver- Haskell to Scala

### Context

As hinted at in the first post, I found Abhinav’s posts to be a great source material for learning and (over this weekend) recreation 🙂

I picked the second post, where the pruning process is tweaked to be faster.

### Pruning changes

I pretty much stuck to the original code, just Scala-ized it, most of the action happens here:

```  def exclusivePossibilities(row: Row): List[List[Int]] = {
def foldHelper1(m: Map[Int, List[Int]], entry: (Cell, Int)): Map[Int, List[Int]] =  entry match {
case (Possible(nums), idx) =>
nums.foldLeft(m) {  (m,n) =>
m.updatedWith(n)( (optList) => optList match {
case None => Some(List(idx))
case Some(list) => Some(list.appended(idx))
})
}
}

def foldHelper2(m: Map[List[Int], List[Int]], entry: (Int, List[Int])): Map[List[Int], List[Int]] = entry match {
case (idx, nums) =>
m.updatedWith(nums)( (optList) => optList match {
case None => Some(List(idx))
case Some(list) => Some(list.appended(idx))
})
}

// Get map of indices to values.
val interim = row.
zip(Range(1,10).toList).
filter {
case (c, _) => isPossible(c)
}.
foldLeft(Map(): Map[Int, List[Int]])(foldHelper1(_, _)).
filter(_._2.length < 4)

// Flip map and extract list of indices.
interim.
foldLeft(Map(): Map[List[Int], List[Int]])(foldHelper2(_, _)).
filter { case (k, v) => k.length == v.length }.
values.
toList
}

def makeCell(nums: List[Int]): Option[Cell] = nums match {
case List() => None
case List(x) => Some(Fixed(x))
case xs => Some(Possible(xs))
}

```

… which is then used by the pruning functions (the first largely kept from before, the second one something new) …

```  def pruneCellsByFixed(cells: List[Cell]): Option[List[Cell]] = {
val fixeds = cells.collect { case Fixed(x) => x }

def pruneCell(c: Cell): Option[Cell] = c match {
case f @ Fixed(_) => Some(f)
case Possible(nums) => makeCell(nums.filterNot(fixeds.toSet))
}

traverser(cells)(pruneCell)
}

def pruneCellsByExclusives(cells: List[Cell]): Option[List[Cell]] = {
val exclusives = exclusivePossibilities(cells)
val allExclusives = exclusives.flatten

def pruneCell(c: Cell): Option[Cell] = c match {
case f @ Fixed(_) => Some(f)
case p @ Possible(nums) => {
val intersection = nums.intersect(allExclusives)

if (exclusives.contains(intersection)) {
makeCell(intersection)
} else {
Some(p)
}
}
}

exclusives match {
case List() => Some(cells)
case _ => traverser(cells)(pruneCell)
}
}

```

… and the replacement for the old `pruneCells` is:

```
def pruneCells(cells: List[Cell]): Option[List[Cell]] = {
for {
step1 <- fixM[List[Cell]](pruneCellsByFixed, cells)
step2 <- fixM[List[Cell]](pruneCellsByExclusives, step1)
} yield step2
}

```

View source here.

(Note: I had a bug where I had forgotten to filter out keys/values of identical length within `exclusivePossibilities`, which led to a few rounds of debugging … once again, I elected to leave that commit history instead of cleaning it up)

### Results

```sbt:sudoku> run "/home/agam/tmp/sudoku17-top-100.txt"
…
Total time: 2 s,

```

I found a massive speedup too (100x! … two seconds to solve the sample set of a hundred problems, instead of two hundred seconds earlier)

## Context

I found this excellent blog post by Abhinav Sarkar that lays out, step-by-step, writing a simple Sudoku solver in Haskell, and … it seemed a good idea to translate it, step-by-corresponding-step, into Scala.

## Finding equivalents

I tried to stick to the spirit of the code as much as possible.

Some translations were obvious, such as `Option` for `Maybe`, or `grouped` for `Data.List.Split.chunksOf`, but others (e.g. how `unlines` were replaced by their stdlib equivalents, in that case, `scala.io.Source.getLines`)

I thought it was okay to just use `print...()` for showing the Grid:

```  def showGridWithPossibilities(grid: Grid) = {
def printPossibilities(nums: List[Int]) = {
print("[ ")
Range(0,10).map { n =>
nums.contains(n) match {
case true => print(n)
case false => print(" ")
}
}
print(" ]")
}

def showRow(row: Row) = {
for (cell <- row) {
cell match {
case Fixed(fv) => print(s"      \$fv       ")
case Possible(pv) => printPossibilities(pv)
}
}
println()
}
for (row <- grid) showRow(row)
}

```

For `traverse` and `sequence`, I could have used portions from `cats`, but decided to just “roll my own” to keep it simple:

```  def traverser[A, B](list: List[A])(f: A => Option[B]): Option[List[B]] = {
def inner[A](elem: Option[A], list: Option[List[A]]): Option[List[A]] = {
for { l <- list; e <- elem } yield e :: l
}

list.foldRight[Option[List[B]]](Some(Nil))( (elem, list) => inner(f(elem), list) )
}

def sequencer[A](list: List[Option[A]]) = traverser(list)(identity)

```

The `data` ADT was replaced by `sealed trait` `case class … extends …`.

The solve method itself doesn’t look too different:

```
def solve(grid: Grid): Option[Grid] = {
for {
pg <- fixPoint(grid)

nextGrid <- solveHelper(pg)
} yield nextGrid
}

def solveHelper(grid: Grid): Option[Grid] = {
if (isGridInvalid(grid)) {
None
} else if (isGridFilled(grid)) {
Some(grid)
} else {
val (g1, g2) = nextGrids(grid)
val solvedG1 = solve(g1)
solvedG1 match {
case None => solve(g2)
case _ => solvedG1
}
}
}

```

The way the original blog post lays out the solution to the problem is brilliant from a pedagogical point of view, and I wish there were more like it. Personally, I feel “seeing the work” teaches me way more than viewing some sort of final polished product.

## Code cleanup

While developing, I basically had one long file, with the test code left in, mostly because I liked having this `runTests()` helper around while I was making additions.

Some of the helper functions could be consolidated into other methods, I might get to that later.

In general, I elected to leave it as a “work in progress” state.

## Performance

Tested it on the first 100 entries from the same problem set,
Running it within SBT .
``` sbt:sudoku> run "/home/agam/tmp/sudoku17-top-100.txt" ```

… showed a similar result:

```[success] Total time: 205 s (03:25)

```

… although this is (1) a cold JVM, running (2) on a small DO droplet, so I suppose it’s possible to do an amortized, longer test later on to get better timings.

## tl;dr

The source code for all this is here

… and I see there’s a follow-on post, so … I’ll try that some time 🙂

## Monthly Curations: December 2019

Note: Many parts of this post are true or at least plausible, but I did not actually install Emacs in my car. Neither should you.