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 🙂

On syntax, in Haskell and Lisp

Yes, but not so much simplicity of syntax. I’m misled here by a superficial resemblance between the cultures of Haskell and Lisp. Both cultures are obsessed with mechanically processing code, and therefore want the language core to be as simple as possible. Since a minimal core is impractical to program in, both expect a larger, more useful language to be defined by translation to the core, so its complexity can be mechanically eliminated. And both consider the representation of code as text to be separate, at least in principle, from the core. So at first glance, it seems as if they should have the same attitude to syntactic complexity.

But they treat it quite differently. Lisp’s culture considers syntax unimportant, and therefore tries to make it as simple and transparent as possible, so it won’t prevent humans from seeing through it — because code is much more interesting than its textual representation. But Haskell’s culture considers syntax safely separate from the language core, and is therefore willing to tolerate complexity in it. Since it goes away without inflicting any complexity on the core, why shouldn’t it include whatever features are convenient?

Nit-picking languages

It’s that (too frequent) time again … when I anxiously (and full of fickleness) wonder what language to increase familiarity with.

The last year, I learnt quite a bit of common lisp, or atleast enough to write a lot of exploratory code in, working with libraries, timing, profiling, improving, and so on.

I had a rude shock when I learnt from one of my Scheme heroes that he really just prefers…

View On WordPress

Nit-picking languages

It’s that (too frequent) time again … when I anxiously (and full of fickleness) wonder what language to increase familiarity with.

The last year, I learnt quite a bit of common lisp, or atleast enough to write a lot of exploratory code in, working with libraries, timing, profiling, improving, and so on.

I had a rude shock when I learnt from one of my Scheme heroes that he really just prefers Haskell now. WTF? But seriously, he makes good points, chief among which is the lack of confidence in refactoring existing lisp code.

But both have the same “lack of libraries” barrier (sure, you’d say, why don’t you build your own — but that’s not the point).

So I’ve been moving around among these, toying with some web-development style languages (and always recoiling from JS), when I suddenly realized that I have absolutely zero experience with any of the .Net languages.

So, (just thinking out loud here) why not learn me some F#, and kill two birds with one stone?

Calculating, Scheming, and Paul Graham

Calculating, Scheming, and Paul Graham

I came across [this paper] recently, and it challenged some of the thoughts/assumptions that had been building in my mind for a while (it discusses Scheme vs Miranda, but you can imagine Lisp vs Haskell instead).

It also mirrors a short email exchange I had with someone who I expected to be a Scheme/Lisp “champion”, but who gently led me down from my gas balloon of hype.

Yes, S-expressions are…

View On WordPress

Calculating, Scheming, and Paul Graham

I came across [this paper] recently, and it challenged some of the thoughts/assumptions that had been building in my mind for a while (it discusses Scheme vs Miranda, but you can imagine Lisp vs Haskell instead).

It also mirrors a short email exchange I had with someone who I expected to be a Scheme/Lisp “champion”, but who gently led me down from my gas balloon of hype.

Yes, S-expressions are great, and one can fall in love with them, and the notion of “building material” for a language to build an application or solve a problem, but there’s no point being dogmatic about them.

Also, another tangential perspective: people consider Paul Graham a big advocate of Lisp, but in my opinion there is no one who has harmed the cause of Common Lisp more than Paul Graham.

Instead of praising the language that allowed him to build his own “killer app”, or teaching the specific details of his implementation, or his own work with the language, what did he proceed to do instead? Ask everyone to wait for his “perfect language” (i.e. stop using Common Lisp!!), and write inflated, abstract articles attracting only language lawyers and the my-language-is-longer-than-yours crowd. Sheesh.

If you want to learn Common Lisp, read The Land of Lisp or PAIP or PCL instead, or browse the sources of Hunchentoot or gendl (or some of the other well-used open-source libraries out there).

Trying out Haskell again

Because, you know, every once in a while …

Clear out existing stuff

rm ~/.ghc ~/.cabal

Get basic stuff

sudo apt-get update
sudo apt-get install ghc cabal-install

Set up cabal

cabal update
cabal install cabal-install

Set up misc recommended packages

cabal install happy alex
cabal install ghc-mod structured-haskell-mode stylish-haskell

Some half dozen persons have written technically on combinatory logic, and most of these, including ourselves, have published something erroneous.

Since some of our fellow sinners are among the most careful and competent logicians on the contemporary scene, we regard this as evidence that the subject is refractory.

Thus fullness of exposition is necessary for accuracy; and excessive condensation would be false economy here, even more than it is ordinarily.

Haskell B. Curry and Robert Feys, Preface to “Combinatory Logic”

State machines are difficult to program and debug. Almost every consideration about the goto statement applies to the event handling mechanisms that manage state transitions. The event handlers do not share variable scopes, so, like in the case of the goto, the code relies on global variables, or in global session variables, when they are created dynamically. There is no top-level structure in the code to make the main sequence evident. For the maintainer, it is very difficult to know what it is trying to achieve.