Simple web programming (in Common Lisp)

It can be really simple.

Stumbled across this …

… and (yes, questionable aesthetics aside) decided to recreate it:

Really does work as advertised:

One-time stuff I had to run:

(ql:quickload 'lass)
(ql:quickload 'spinneret)
(ql:quickload 'hunchentoot)

That’s it. Out of the box. Didn’t start any project, or any framework. Scales up and down, and starts small.

This was less than 10 minutes.

Advent-of-code 2021

Using Wolfram Mathematica for this is more satisfying than it should be

https://www.wolframcloud.com/obj/agam.brahmawolfram/Published/AOC%202021.nb

It was shockingly easy to do all this.

  • REPL/Notebook glory with fast-n-quick editing and modification
  • easy switching between text and code cells
  • easy prototyping
  • easy plotting

I’m sure anything that requires “running systems” would be a bad fit, but most cases where you’d think “I need a real programming language here”, Wolfram Language is more than adequate.

The state of scheme

The “Larceny” benchmarks

I check out the “Scheme universe” every couple years or so, and it’s a big and varied place now!

I was aware of “Guile and Chicken” a decade ago.

Since then:

  • Chez was open-sourced
  • Racket (re-)built itself on top of Chez
  • R7Rs became a reality
  • Gambit has been around for a while, I was simply ignorant
  • Guile got a lot of upgrades (including a JIT) and is the basis for Guix
  • Gerbil scheme got built on top of Gambit

If someone’s looking to dip their toes in this universe today, they’re really spoilt for choice, between very high-performant implementations (Chez and Gambit/Gerbil), pretty well-supported ones (Racket & Guile).

Prime Palindromes

Came across this on the “Programming Praxis” blog

I thought I’d use something other than a “typical” programming language, by which I mean not “an esoteric language”, but rather something that’s not thought of as a programming language: Mathematica.

This is the entirety of the solution, a one-liner that (using Timing), also shows how long it took.

The above is an image, but an online (read-only) notebook containing this evaluation is here at Wolfram Cloud.

Ten years ago, I’d be on the side of the fence saying “but that’s cheating“, or “hey, that’s not really programming“, but today my attitude is more of “use the right tool for the job“.

And Mathematica is a mighty fine tool !!

Simple calculator in Rust

Sometime last year, I had tried writing a parser for basic arithmetic to drive a simple calculator in Scala.

To follow-up, I decided to try writing this in Rust.

I looked at some parser crates, settled on peg (it seemed simpler than … pest).

The code is here.

The core of it is this parser section:

peg::parser!(
grammar calc_parser() for str {
    rule number() -> i64
    = n:$(['0'..='9']+) {
        ? n.parse().or(Err("bad num"))
    }

    rule whitespace() = quiet!{[' ']*}

    rule operator() -> Operator
    = op:$(['*' | '/' | '+' | '-']) { Operator(op.chars().next().unwrap()) }

    rule paren() -> i64
    = "(" whitespace() n:calculate() whitespace() ")" { n }

    rule factor() -> i64
    =
    n:number() { n }
    /
    n:paren() { n }

    rule term() -> i64
    =
    n1:factor() whitespace() op:operator() whitespace() n2:factor() {
        eval(&op, n1, n2)
    }
    /
    n:factor() { n }

    pub rule calculate() -> i64
    =
    n1:term() whitespace() op:operator() whitespace() n2:term() {
        eval(&op, n1, n2)
    }
    /
    n:term() { n }
}
);

Here’s what a sample session looks like:

Enter an expression, or 'END' to quit:
45
Answer: 45
Enter an expression, or 'END' to quit:
8 * (7 + (9 / 3))
Answer: 80
Enter an expression, or 'END' to quit:
4 * ( 5
Calculation error: ParseError { location: LineCol { line: 1, column: 8, offset: 7 }, expected: ExpectedSet { expected: {"['0' ..= '9']", "['*' | '/' | '+' | '-']", "\")\""} } }
Enter an expression, or 'END' to quit:
END

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)