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 🙂

Journalling flow

I’ve been doing this for perhaps four years now, so … it’s something I can write about. Here’s a rough outline:

  • I use Day One1
  • Every day, I write one entry on what happened that day
  • Optionally (this is something I only started doing in the last couple months, but I like it a lot already), I add a few pictures from the day
  • Once every week2, I go through the daily entries, and summarize what happened that week
  • Once every month, I go through the weekly entries, and summarize what happened that month
  • I share3 this monthly entry in a blog post
  • Once a quarter, I go through the monthly entries, and summarize what happened that quarter
  • Once a year4, I go through the quarterly entries, and get the “big events” for the year.
  • I also share the yearly update in a blog post.


  1. An app that lives on both my phone and laptop ↩︎
  2. usually Saturday night, i.e. right now ↩︎
  3. I think this started as a way to make up for not being on Facebook, more on which later… ↩︎
  4. yup, this one is the most satisfying 🙂 ↩︎

The Highlight Zone

One of my favorite shows for Tara is Peg Cat. There is a glut of “kid-oriented shows”, and this is very refreshing.

The “drawing quality” is similar to Pete the Cat (crayon-cartoon-ish), with grid paper in the background. I came for the “oh, a show that tries to make Math fun”, and stayed for the whacky characters.

It is not without … references for cough … discerning adults … cough, as I realized when watching ”The Highlight Zone1, where everything turns black and white, and Peg and the eponymous Cat must find things out of whack to return to “the normal world” (or do they? Lol).

Anyway, all round good fun, easily recommend.


  1. link to video here ↩︎

My daughter’s first horror movie :-|

We recently finished all three seasons of the “new” 2002-2006 Scooby Doo series1, and while browsing Netflix, we came across a full-length Scooby Doo movie.

Great. In the spirit of watching a “family movie” this weekend (previously: Kung Fu Panda, Kung Fu Panda: 2, My Little Pony), we ended up watching it 2 and … damn, it was a bit unexpected.

Every regular episode follows the same plot line: some random ghost/monster is introduced, the gang investigates, a musical chase scene results, an unmasking results, the mystery is solved.

The premise of the monsters not being “real” is … ignored by this movie. And instead of a comedy, it’s actually … a comic horror movie.

In that (spoiler alert) the zombies and … er, ”cat creatures ?” … are real. Yes, a twist on the ol’ Scooby-Doo formula!

Must’ve been fun to write, and I thought it was a genuinely fun movie in that way … except that I should’ve cursorily skimmed the plot overview on Wikipedia 3, and … let my daughter know it was gonna be a bit on the scary side.

A collection of notes on nature and order

I found these notes I’d copy-pasted from somewhere from about five years ago. I decided to track down their sources, as best I could.

From “QED: The Strange Theory of Light and Matter” By Richard P. Feynman

My physics students don’t understand it either. That is because I don’t understand it. Nobody does …. The theory of quantum electrodynamics describes Nature as absurd from the point of view of common sense. And it agrees fully with experiment. So I hope you can accept Nature as she is—absurd. In short, there is no way to visualize what is going on. The theory of quantum mechanics explains it perfectly, to unbelievable mathematical accuracy. And that is all you need to know.

From “The Nature of Order” by Christopher Alexander

According to this view, the evolving system of the genetic material ITSELF causes evolution to follow certain pathways, not only because of selective pressure from outside, but also by virtue of its own internal dynamical ordering tendencies. The results of evolution are then to be understood [as being] mainly formed not by Darwinian selective pressure acting from outside, but by pressures created by the geometry and dynamics of the evolving genetic system itself

From “An Essay on the Art of Building and the Nature of the Universe” by Christopher Alexander

There are…two worlds in our minds. One is the scientific world which has been pictured through a highly complex system of mechanisms. The other is the world we actually experience. These two worlds, so far, have not been connected in a meaningful fashion. Alfred North Whitehead, writing about 1920, was one of the first philosophers to draw attention to this modern problem, which he called the bifurcation of nature. Whitehead believed that we will not have a proper grasp of the universe and our place in it, until the self, which we experience in ourselves, and the machinelike character of matter we see outside ourselves can be united in a single picture.

When I am part of the making of a building and examine my process, what is happening in me when I do it, myself, in my effort, is that I find that I am always reaching for the same thing. In some form, it is the personal nature of existence, revealed in the building, that I am searching for. It is “I,” the I-myself, lying within all things. It is that shining something which draws me on, which I feel in the bones of the world, which comes out of the earth and makes our existence luminous.

What must I do to put this self-like quality into the house, the room, the roof, the path, the tile? Often I can feel the possibility of this in a thing before I start to think, or design, or plan, or build, or before I start to paint. It is the sublime interior, the right thing. I first feel existence shimmering in reality, and I then feel it deep enough in the thing I am looking at and trying to ake, to know that it is worth capturing in concrete and wood and tile and paint. I can feel it, nearly always, almost before I start. Or, rather, I do not let myself start until I can feel this thing.

This thing, this something, is not God, it is not nature, it is not feeling. It is some ultimate, beyond experience. When I reach for it, I try to find—I can partly feel—the illumination of existence, a glimpse of that ultimate. It is always the same thing at root. Yet, of course, it takes an infinite variety of different forms

From “The Luminous Ground” by Christopher Alexander

I believe it is in the nature of matter, that it is soaked through with self or “I.” The essence of the argument … is that the thing we call “the self,” which lies at the core of our experience, is a real thing, existing in all matter, beyond ourselves, and that in the end we must understand it, in order to make living structure in buildings. But it is also my argument that this is the nature of matter. It is not only necessary to understand it when we wish to make living structure in buildings. It is also necessary if we wish to grasp our place in the universe, our relationship to nature.

From “Life and Mind in the Universe” by George Wald

It takes no great imagination to conceive of other possible universes, each stable and workable in itself, yet lifeless. How is it that, with so many other apparent options, we are in a universe that possesses just that peculiar nexus of properties that breeds life? It has occurred to me lately—I must confess with some shock at first to my scientific sensibilities—that both questions might be brought into some degree of congruence. This is with the assumption that mind, rather than emerging as a late outgrowth in the evolution of life, has existed always as the matrix, the source and condition of physical reality—that the stuff of which physical reality is composed is mind-stuff.

From “The Luminous Ground” by Christopher Alexander

Why is unity the same as tears? … Unity ties everything together—including joy, happiness, and laughter, but also including loss, death, and betrayal. A thing which truly has unity partakes of everything. And through that everything, there must be sadness. The making of this sadness, then, must come through a process where land, details, rooms, form an individual whole. Always trying to tie it together, to unify it, to make it disappear.

Addendum: I was curious where I got this from, and then … found it! An amazing composition of words and pictures and more, by Dick Gabriel (for some of you, yes, of worse is better …)