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 console6 when something depends on a class/object within a project, but this is an independent enough chunk that you could use ammonite7 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] Loading settings for project simplecalc-build from metals.sbt ...
[info] Loading project definition from /home/agam/code/simplecalc/project
[info] Loading settings for project simplecalc from build.sbt ...
[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] Loading project definition from /home/agam/code/caves/caves/project
[info] Loading settings for project caves from build.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)

A simple Sudoku solver- Haskell to Scala

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

Comments on the original

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: May 2020

Monthly Curations: April 2020

Monthly Curations: March 2020

Monthly Curations: February 2020

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.