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 …)

On “effects” in moving images

See this opening for Vertigo

and then realize this:

However, what if CGI in films went back even further, to 1957 1958? I heard about this possibility through a video presented by John Hess on some film special effects history. He mentioned that a computer was used in creating the opening sequence for Alfred Hitchcock’s movie Vertigo. I watched it, and was amazed! Yes! These look like computer graphics!

An article in Rhizome describes it, saying that John Whitney programmed these graphics using a computer that was originally designed to aim artillery during WW II. A pendulum (which contained pressurized paint) was placed above a drawing surface that was attached to a platform. The platform was moved by the computer according to mathematical equations as the pendulum swung back and forth across it. This created precise spiral designs. There’s a part of the opening sequence where you can see these spiral designs change shape. These changes were created by altering the formulas for each frame that was drawn by the computer/pendulum combination. In my mind, this is similar to how computers interacted with oscilloscopes in the earliest visual computer displays, though it sounds like the computer could not turn the paint on and off.

Original source: Were the first movie computer graphics in a Hitchcock film?