scala-logo-small

Scala for-loop that can select a sub-area from two-dimensional space


val smallBox = for {
	gridPosition = topCorner to bottomCorner
	} yield valueOf(gridPosition)

The thing I’ve had the most fun with in Scala is hacking the language to add my own syntax. Recently while doing a code kata I came across a prime use case for hacking in some new syntax. I’ll walk you through it.

Problem Statement

Given a Sudoku puzzle that’s been filled in, I wanted to grab all values from the box I’m currently checking so I could see if it has duplicates.

On the face of it this is a pretty common scenario. It’s no different than selecting an area on the screen with a mouse or drawing a box around an area in a map.

gridview-rows-selection-rectangle001

The usual high-level way I think about this is in terms of selecting everything between the top-left point and the bottom-right point. It’d be nice to have code expressed in this same manner:


val smallBox = for {
	gridPosition = topCorner to bottomCorner
	} yield valueOf(gridPosition)

Out-of-the-box Java

If you use an ordinary C-like language and represent the Sudoku puzzle as a two-dimensional array then it’s painful to pull out a sub-area from that array.

For example, look at the grid again and think about how to select the values of the middle box, highlighted in yellow here.

grid2

The code for this would start at the yellow area’s top left position (3,3) and copy the nine squares left to right and top to bottom through position (5,5). Code for that in Java would look like:


for(int x = 0, i = 3; x < 3, i < 6; x++, i++) {
	for(int y = 0, j = 3; y < 3, j < 6; y++, j++) {
		smallBox[x][y] = grid[i][j];
	}
}

That's just to grab one specific known box out. While checking if a Sudoku puzzle is solved, we'll be dynamically selecting the box based on variables constructed from our current location at any given point. This adds even more variables than {x,y,i,j} and starts to get pretty ugly.

Hacking Scala: A better approach

Java doesn't give me an obvious way to simplify the box grabbing. As I described above my ideal syntax for grabbing the values from a specific sub-area would look like this:


val smallBox = for {
	gridPosition = topCorner to bottomCorner
	} yield valueOf(gridPosition)

Scala actually allows this if we combine a couple features, starting with a value class for each cell position.

A value class for each cell position

First, I need to define each location as something other than two int's. It'd be nice to call the upper right position of a box "topCorner" rather than grid[0][3]. In Java that might seem like "over-engineering" the problem because you'd have to make a whole new class for this one purpose which would sit in a whole new file somewhere in your code.

Thankfully, in Scala, it's just one line and it can go anywhere in scope:


case class GridPosition(val x: Int, val y: Int)

With this value representation, I can define the top corner of the second box in the top row of the grid like this:


val topCorner = GridPosition(0,3)

And I can likewise define the bottomCorner:


val bottomCorner = GridPosition(2, 5)

Now I have a way to refer to whole boxes by two values representing their upper-leftmost point and their lower-rightmost point. Just as I do when selecting an area on the screen with a mouse.

Now to make my value class iterable in a for loop

Second, in Scala you would generally execute a for loop with this more readable syntax:


for(i <- 0 to 8) {
  println(i)
}

This is equivalent to the Java:


for(int i = 0; i < 9; i++) {
    System.out.println(i);
}

To iterate over a multi-dimensional array, Scala also provides a readable syntax called "for yield." It basically collapses nested for loops down into one.


val smallBox = for {
    i <- 0 to 2
    j <- 3 to 5
    } yield grid(i)(j)

This code would produce a sequence (which is like a list) of the values in the small 3x3 box and assign it to the "smallBox" variable. It is equivalent to the Java code shown earlier:


for(int x = 0, i = 3; x < 3, i < 6; x++, i++) {
	for(int y = 0, j = 3; y < 3, j < 6; y++, j++) {
		smallBox[i][j] = grid[i][j];
	}
}

The out-of-the-box Scala is pretty readable compared to that ugly mess but why not go all the way and get the version I really want?


val smallBox = for {
	gridPosition = topCorner to bottomCorner
	} yield valueOf(gridPosition)

Scala lets you skip dot-notation when it can be inferred. The above line that says "topCorner to bottomCorner" can be inferred by Scala's compiler to mean "topCorner.to(bottomCorner)".

So you see that means all I have to do is add a "to" method to my GridPosition class.


case class GridLocation(val x: Int, val y: Int) {

      def to(o: GridLocation): Seq[GridLocation] = {
        for {
          x <- x to o.x
          y <- y to o.y
        } yield GridLocation(x, y)
      }

    }

There. All finished!

Now the following code is legit Scala syntax:


val smallBox = for {
	gridPosition = topCorner to bottomCorner
	} yield valueOf(gridPosition)

The "topCorner to bottomCorner" bit will be translated as "topCorner.to(bottomCorner)" behind the scenes, and the loop will produce a "Seq" (sequence) of GridPositions that represent the nine cells inside that particular 3x3 box. The "yield" portion will pass those nine cells in turn to the "valueOf" method I will write that looks like this:

def valueOf(cell: GridLocation): Int = {
    grid(cell.x)(cell.y)
}

The overall result here is that I will get a Seq[Int] containing the nine values inside that particular box. Pretty nice if I do say so myself.

Leave a Reply

Your email address will not be published. Required fields are marked *