First Make It Correct

Way back in December, in the spirit of the times (it seems that everyone was either solving Advent of Code or looking for a job), like an elephant in a china shop, I found myself solving a leetcode-style problem.

Before I say anything else¹, I would like to preface that I hate leetcode problems with a passion, and not only because I suck at them. The software industry needs to rise as one and banish them from any interviewing process in existence, and leave them be for the masochists that actually enjoy solving them.

Having said that, for the right level of difficulty² I do get easily nerd sniped by leetcode problems. And that's how I found myself spending way too much time solving a simple problem. Lest this time be completely wasted, I tried to conjure up a lesson for "real code" that can be learned from this sordid ordeal.

And so, paraphrasing a famous saying:

First make it correct, then make it anything you want.

Let me illustrate this point with a leetcode problem. This is going to be a wild ride from recursive solutions to procedural loops, all with a touch of property-based testing. Grab yourselves a cup of liquid and settle in for a (very) long read.

The Problem

Here's the problem I was trying to solve:

Given a two dimensional board compute a list of coordinates that form a clockwise spiral from the top-left corner to the center.

For example, given a board of dimensions 4x3, the spiral's path looks like this³:

-------------------------------------
| -[1]→  | -[2]→  | -[3]→  |  [4]↓  |
-------------------------------------
| -[10]→ | -[11]→ |  [12]  |  [5]↓  |
-------------------------------------
| ↑[9]   | ←[8]-  | ←[7]-  | ←[6]-  |
-------------------------------------

And the list of coordinates is (using 0-based indexing from left-to-right, top-to-bottom):

(0,0), (1,0), (2,0), (3,0), (3,1), (3,2), (2,2), (1,2), (0,2), (0,1), (1,1), (2,1)

Before reading on, spend some time and think about how you would approach solving this⁴.

Obviously Correct Solution

As stated above, the first step when approaching any problem is to write a correct solution. I'd even go further, ideally, I would start with an "obviously correct" solution. A solution that so closely follows the structure of the problem that you can just see it works from reading it. No nasty edge cases or convoluted logic. It's difficult to precisely define what "obviously correct" means, this is yet another one of those cases of "you know it when you see it".

Having scratched my head some, I got myself a working solution. But it wasn't an "obviously correct" solution. It had inconvenient edge cases and just wasn't obvious. Luckily, the friend who nerd sniped me⁵ gave me a better insight into a possible solution to the problem.

Generating the correct coordinates is like peeling an orange with a knife. You shave off a row, rotate, and repeat until you're done.

Let's see this with a concrete example. Suppose you fill the board with the coordinates of each cell:

---------------------------------
| (0,0) | (1,0) | (2,0) | (3,0) |
---------------------------------
| (0,1) | (1,1) | (2,1) | (3,1) |
---------------------------------
| (0,2) | (1,2) | (2,2) | (3,2) |
---------------------------------

We can peel the top row and add it to the solution:

(0,0), (1,0), (2,0), (3,0)

We are then left with a smaller board:

---------------------------------
| (0,1) | (1,1) | (2,1) | (3,1) |
---------------------------------
| (0,2) | (1,2) | (2,2) | (3,2) |
---------------------------------

Which we rotate counter-clockwise:

-----------------
| (3,1) | (3,2) |
-----------------
| (2,1) | (2,2) |
-----------------
| (1,1) | (1,2) |
-----------------
| (0,1) | (0,2) |
-----------------

Peel the top row again, and add it to the solution:

(3,1), (3,2)

With the remaining board:

-----------------
| (2,1) | (2,2) |
-----------------
| (1,1) | (1,2) |
-----------------
| (0,1) | (0,2) |
-----------------

Which we can rotate again, and repeat the process until the board reaches size 0. This solves the problem neatly, nicely following the symmetry inherent to the problem, and leading us towards what might turn out to be an obviously correct solution. All that's left is to code it up.

The solution just described is inherently recursive. We repeat the same procedure over and over again on an input that shrinks on every step, until we reach a base case. Since functional languages are very well adapted to recursion, we'll be using a functional language for this post. Specifically the Scala programming language, as it lets us do the whole functional thing with ease, but will also let us go procedural later on.

First let's lay down some basic helpers. Since we don't want to get confused by the different pieces of data we'll need. Let's define some simple types:

case class Dims(w: Int, h: Int)
case class Point(x: Int, y: Int)

Dims represents the dimensions of a board, with a width w and a height h. Point represents a two-dimensional point located at the x and y coordinates.

With this out of the way and without further ado, here's the orange peeling solution in code⁶:

def traceSpiral(dims: Dims): List[Point] = // 1
  peel(buildCoordinates(dims)) // 2

def peel(board: List[List[Point]]): List[Point] = // 3
  board match // 4
    case Nil => Nil // 5
    case topRow :: otherRows => // 6
      topRow ++ peel(rotateCCW(otherRows)) // 7

Let's go through it step by step:

• The entry point is traceSpiral (1), it takes in the dimensions of the board and produces a list of points
• We then call a utility function buildCoordinates (2) that populates a list of lists with the coordinates of each board cell
• We pass that along to the recursive peel function
• The peel function (3) operates on the board points producing a single list of points
• We do this by pattern matching on the current board (4)
• If the board has size 0 (i.e., the empty list) we reached the base case and return an empty list (5)
• If the board is non-empty, we extract its top row and the rest of the rows (6)
• We return the results by prepending the top row we just extracted to the result of calling peel again with the counter-clockwise rotated leftover board (7)

This closely follows the algorithm we just described, and has very little extraneous detail. Pattern matching makes this safe and edge case free. You can check out the definitions of buildCoordinates and rotateCCW in the repo. But since they rely on high-level list functions like tabulate and transpose they too are edge case free, and are very easy to verify with a simple unit test⁷.

And so, this is as close to an obviously correct solution as I'll ever get⁸. But is it actually correct?

I mean, I can handwave obvious correctness as much as I want, but without some kind of more concrete proof, that's all it is, handwaving. I won't try to make an actual proof in the mathematical sense, but I can at least provide some tests.

Here's an easy one:

test("Traces the correct spiral"):
    val dims = Dims(w = 4, h = 3)
    val points = traceSpiral(dims)

    val expected =
      List(
        Point(0, 0),
        Point(1, 0),
        Point(2, 0),
        Point(3, 0),
        Point(3, 1),
        Point(3, 2),
        Point(2, 2),
        Point(1, 2),
        Point(0, 2),
        Point(0, 1),
        Point(1, 1),
        Point(2, 1),
      )

    assertEquals(points, expected)

This test codifies the example we used above. And if we run it our solution passes with flying colors.

"But what about edge cases", you may wonder. And I shall answer that life's too short to look for edge cases manually. Instead we can employ property-based testing to search for edge cases for us.

For that we need to specify some properties that should hold for any valid solution of the spiral problem. Having spent a few minutes thinking about it, here are some properties I came up with that can be used as sanity checks. For all possible board dimensions it should hold that:

1. The points of a solution must be within the bounds of the board
2. The number of points in a solution should be the same as the size of the area of the board
3. There should be no duplicate points in a solution

Let's make this specification executable using property-based testing¹⁴:

property("Sanity: all points in bounds"): // 1
  forAll(dimsGen): dims => // 2
    val points = traceSpiral(dims) // 3

    points.forall(dims.inside) ==== true // 4

This corresponds to property 1:

• In (1) we define a new property
• We use dimsGen, which is a generator of Dims instances (2), that will randomly generate different dimensions for us⁹
• The property should hold for any board dimensions that we throw at it
• With the randomly generated dimensions in hand we invoke the traceSpiral function (3)
• We then assert that all the points in the generated solutions are within the bounds of the dimensions we are working with (4)

Here's property number 2:

property("Sanity: dimensions match number of points"):
  forAll(dimsGen): dims =>
    val points = traceSpiral(dims)

    points.size ==== dims.area // 1

This works similarly to the first property, we run for any instance of Dims and assert that the length of solution matches the area of the dimensions (1).

And for property number 3:

property("Sanity: no duplicate points"):
  forAll(dimsGen): dims =>
    val points = traceSpiral(dims)

    points.distinct ==== points // 1

Here we make sure that any solution that we produce does not contain duplicate points (1). Again, holding for any board size.

In aggregate, these three properties verify that any valid solution is a permutation of all the points on the board.

Actually, we could've written that as a single property, but splitting this up has the advantages that:

• It's marginally easier to write these properties than writing a function that correctly generates all the points on the board. Thus reducing the chances of the property itself being broken.
• Having separate properties makes it easier to debug if something in the solution breaks. As we can see which aspect of "being a valid permutation" fails to hold.

And now for the big benefit defining these tests as properties: the property-based machinery is going to run our code on many different dimensions of boards, thus very likely flushing out any edge cases lurking around in our code. This happens without us needing to actually come up with those edge cases ourselves (is a board of size 0 an edge case? 1x1? 2x1? who knows?..).

We can run the full suite of tests now:

+ Traces the correct spiral 0.0s
+ Sanity: all points in bounds 0.006s
+ Sanity: dimensions match number of points 0.007s
+ Sanity: no duplicate points 0.008s

We passed all the tests (denoted by +). Our solution looks correct indeed, and we can be fairly certain that we didn't miss any edge cases.

Of course these are just sanity checks that I came up with quickly, they are not specific to spirals, and they don't actually validate that the solution we got is correct. They only attempt to reject obviously invalid solutions. My claim is that in conjunction with the single unit test above, these properties are enough to give me high confidence that the "obviously correct" solution is actually correct¹⁰. If you don't believe me, I challenge you to come up with a non-contrived solution that passes the unit test along with the sanity properties and isn't a valid solution to the spiral problem. Please let me know if you do.

In case you're not satisfied with these properties, it is clear that such a nicely symmetric and recursive problem can have other properties that actually capture its rich structure. If you're so inclined, you can see an additional property that I defined here that tries to capture some of that structure. Since defining this property was more difficult than actually solving the problem, I won't be showing it here. There's only so much verification I'm willing to do for a problem I'm not being paid to solve...

Anyways, I now feel comfortable stating that the obviously correct solution is indeed correct, and we can move on.

The Reference Solution

Before we actually do move on. Let's reap another benefit of using property-based testing.

We can now treat the solution that we just created as a reference solution, so that we can use it to check any other implementation that we come up with. We can define one more property: for all board dimensions, every solution to the problem must match the reference solution.

In code:

property("Matches reference"):
  forAll(dimsGen): dims =>
    val expected = Reference.traceSpiral(dims) // 1
    val actual = traceSpiralCandidate(dims) // 2

    actual ==== expected // 3

We are defining this property (for all board dimensions) as part of a suite that will be used by all future solution candidates. First generate the reference solution (1). Then generate the candidate solution (2). Lastly, compare the two to make sure they are equal (3).

Since we trust the reference solution we can mechanically verify that every other solution matches it. This is a very powerful test. Assuming that the reference is indeed correct, such a test can act as a strong guarantee for any new code that we introduce¹¹.

Finally, with a solid reference in hand, we are ready for the second part of the statement at the beginning of this blog:

... then make it anything you want.

Recursing the "Right" Way

Astute readers may notice that our reference solution, recursively beautiful as it is, is actually flawed in several ways. The most glaring ones:

• It does recursion "the wrong way". That is, it uses recursion in a non-tail position. In a strict language like Scala this easily leads to stack overflows.
• It allocates O(w * h) memory upfront. This is actually quite bad, so much so, that I wasn't able to trigger a stack overflow even with a heap of more than 8 GB. Allocating a large enough board, such that it is worthy of a stack overflow is so heavy that I got an out of memory exception first^{12 13}.

The fact that I consider these to be flaws is of course subjective, and depends on the use case being considered. More importantly though, these are only non-functional flaws, logically our solution is doing the right thing. And so we can still use it as a reference while we fix these flaws.

We'll start by fixing the recursion issue, as this one is easier to tackle.

Lucky for us, transforming (simple) non-tail-recursive code into tail recursive code is a fairly mechanical process. Given our reference code we can mechanically turn it into a tail recursive version:

1. Make your return value into an argument to the recursive function
2. Instead of returning a result and recursing, update the new argument with the result of the current step and then recurse
3. When reaching the base case, return the accumulated result argument

Applied to our reference solution, the result is this:

def traceSpiral(dims: Dims): List[Point] =
  peel(buildCoordinates(dims), result = Nil) // 1

@tailrec // 2
def peel(board: List[List[Point]],
         result: List[Point]): List[Point] = // 3
  board match
    case Nil => result // 4
    case topRow :: otherRows =>
      peel(rotateCCW(otherRows), topRow ++ result) // 5

This code is very similar to the code we started with, but it's now tail recursive. In detail:

• The peel function now takes an extra argument result (3), we'll use that to accumulate the final result
• When making the recursive call, we prepend the current result topRow to the result argument we got (5)
• In the base case (4), we return the result argument
• peel is now tail-recursive, so we annotate it with the tailRec annotation (2), this forces the compiler to validate that the code is indeed tail recursive and can be optimized accordingly
• When making the initial call to peel we initialize result with the original base case value Nil (1)

That's it. The code is now tail recursive. But is it correct? I mean this transformation is not completely trivial, how do we know we got it right?

Easy, we have our reference solution, we can just run our property-based tests and validate that we are still returning logically correct results:

TailRecursiveSuite:
==> X TailRecursiveSuite. Traces the correct spiral // <--- 1
31:
32:    assertEquals(points, expected)
33:
values are not the same
=> Obtained
List(
  Point(
    x = 1,
    y = 1
  ),
// ... more output
)
=> Diff (- obtained, + expected)
   Point(
+    x = 0,
+    y = 0
+  ),
// ... more output
   )
  + Sanity: all points in bounds 0.069s // <--- 2
  + Sanity: dimensions match number of points 0.015s
  + Sanity: no duplicate points 0.019s
==> X TailRecursiveSuite. Matches reference
12:
13:      actual ==== expected
- TailRecursiveSuite. Matches reference: Falsified after 10 passed tests
> Dims(1,2)
> === Not Equal ===
> --- lhs ---
> List(Point(0,1), Point(0,0))
> --- rhs ---
> List(Point(0,0), Point(0,1))

... And we failed. On two tests no less. I clipped some of the output as it's a bit noisy. Let's see what happened.

We failed the unit test, that's the X TailRecursiveSuite. Traces the correct spiral (1). The output contains the diff between what we got and what was expected (clipped). It's a somewhat difficult to decipher as the hardcoded value in the unit test is a bit large. It's good to know that we are protected by the unit test, but it's not that useful for debugging.

Next we have the sanity tests (2). We did pass them, which is unfortunate, as they don't help us to narrow down the problem in this case. Oh, well, maybe next time.

Lastly, we have the reference solution test. And this one fails, and not only that, the failing values are very small. This is no coincidence, property-based testing libraries usually come with the ability to shrink their values. That is, if a test fails on some input, the library tries to shrink that input to the smallest possible value that is still failing¹⁵. In our case this means that if we fail on some random Dims instance, the library will try to reduce the size of the dimensions as close as possible to Dims(0, 0). Here we failed on the dimensions Dims(1, 2):

> === Not Equal ===
> --- lhs ---
> List(Point(0,1), Point(0,0))
> --- rhs ---
> List(Point(0,0), Point(0,1))

rhs is the expected (reference) value, while lhs is the value we got from our tail recursive solution. We see that our new solution is reversed compared to the reference solution.

Now, I'm not much into thinking, I got my test to do that for me. Since the result looks reversed, let's reverse it back:

def traceSpiral(dims: Dims): List[Point] =
  peel(buildCoordinates(dims), result = Nil).reverse // 1

@tailrec
def peel(board: List[List[Point]], result: List[Point]): List[Point] =
  board match
    case Nil => result
    case topRow :: otherRows =>
      peel(rotateCCW(otherRows), topRow ++ result)

This solution is the same as the previous one, but the final result is reversed (1). Let's run the tests again:

==> X TailRecursiveSuite. Matches reference
12:
13:      actual ==== expected
- TailRecursiveSuite. Matches reference: Falsified after 8 passed tests
> Dims(2,1)
> === Not Equal ===
> --- lhs ---
> List(Point(1,0), Point(0,0))
> --- rhs ---
> List(Point(0,0), Point(1,0))

We're still failing on the same test. The failure looks the same, the result is again reversed compared to the reference. Except that this time the dimensions are transposed, Dims(2, 1) vs. Dims(1, 2).

I guess it's not really surprising that a simple reverse wasn't good enough. The failing unit test with the bigger board wasn't failing on a simple reversal. Something trickier is going on here.

The problem is that the counterexample is so minimized that it's hard to see what the underlying issue is. We need a bigger counterexample. If we weren't using property-based testing we'd have to manually search for more problematic cases, like some plebs. Luckily, we'll be spared this gloomy fate. Instead we'll define a generator that limits the dimensions to be at least 2. And tweak our reference test to use that (temporarily, for "debugging"):

property("Matches reference"):
  forAll(dimsAboveGen(2)): dims => // 1
    val expected = Reference.traceSpiral(dims)
    val actual = traceSpiralCandidate(dims).toList

    actual ==== expected

In (1) we're using the new generator. After removing the unproductive reverse call, and we get a new, larger, counter example:

> Dims(2,2)
> --- lhs ---
> List(Point(0,1), Point(1,1), Point(0,0), Point(1,0))
> --- rhs ---
> List(Point(0,0), Point(1,0), Point(1,1), Point(0,1))

The next counterexample was right around the corner, who could've thunk...

With this larger, but still not overwhelming, example we see a glimmer of a pattern. The new result is not reversed, but rather the halves are reversed. If we split the list in two and swap the halves around, we'll match the reference. Let's confirm this pattern with dimensions above 2:

> Dims(3,3)
> === Not Equal ===
> --- lhs ---
> List(Point(1,1), Point(0,1), Point(1,2), Point(0,2), Point(2,1), Point(2,2), Point(0,0), Point(1,0), Point(2,0))
> --- rhs ---
> List(Point(0,0), Point(1,0), Point(2,0), Point(2,1), Point(2,2), Point(1,2), Point(0,2), Point(0,1), Point(1,1))

Although we probably skipped over 2x3 cases, this is good enough. Since the number of points in the result is not even, we obviously won't be splitting in two halves. But nor can we split in thirds. It seems that the pattern is more involved. Looking for segments that we can reverse, we see the following segment lengths: 2, 2, 2, 3. Weird... But recall our orange peeling algorithm. The first segment we peel off is 3. We are then left with a 3x2 board, which we rotate, peeling off a segment of length 2. Rotate again, peel off 2, and then another 2. Our segment lengths are just the orange peeling segments in reverse!

We're building up the result the wrong way:

def peel(board: List[List[Point]], result: List[Point]): List[Point] =
  board match
    case Nil => result
    case topRow :: otherRows =>
      peel(rotateCCW(otherRows), topRow ++ result) // <--

The arrow points at the problematic place where we build up the result. This was perfectly fine with the original, non-tail-recursive solution. But what I missed in my translation algorithm is that result building with tail recursion goes "the other way around" ¹⁶.

The fix is straightforward, just reverse the arguments:

def peel(board: List[List[Point]], result: List[Point]): List[Point] =
  board match
    case Nil => result
    case topRow :: otherRows =>
      peel(rotateCCW(otherRows), result ++ topRow) // <--

With the fix in place, we finally pass all the tests:

TailRecursiveSuite:
  + Traces the correct spiral 0.04s
  + Sanity: all points in bounds 0.113s
  + Sanity: dimensions match number of points 0.04s
  + Sanity: no duplicate points 0.046s
  + Matches reference 0.058s

Now we have the confidence that we didn't break the correctness of our original solution.

If you're really into asymptotics though, you might notice that our solution just turned to be quadratic. Using ++ on a List to append to the ever growing result value is not good for performance.

The fix is yet again mechanical, but leads us even further away from the reference solution. Since prepending to a List is faster than appending to it, we can do that and sprinkle in some reverse calls. I'll spare you the gory details of me trying to debug the implementation with tests. The upshot is this:

def traceSpiral(dims: Dims): List[Point] =
  peel(buildCoordinates(dims), result = Nil).reverse // 1

@tailrec
def peel(board: List[List[Point]],
         result: List[Point]): List[Point] =
  board match
    case Nil => result
    case topRow :: otherRows =>
      peel(rotateCCW(otherRows), topRow.reverse ++ result) // 2

Here we reverse the way we build up the result (2). We first reverse the current row, and the prepend it to the accumulator. Finally, we have to reverse the whole result (1). Rest assured that I messed up the different reverse calls, but the tests had my back.

So guided by the correct reference solution we managed to go quite far away to improve performance, while not losing sight of correctness.

But why stop here?

Recursion, I Hardly Know Her

Lately, I was flabbergasted to hear that there exist languages that don't support any form of tail call optimization¹⁷.

Try as we might, our tail-recursive solution doesn't help us if we're stuck using such a language. Using any form of recursion is liable to get our stack blown. How can we help our fellow programmers in need?

Easy, just as there's a mechanical way to translate simple recursion into tail recursion, so can we translate tail recursive code into an iterative loop.

The process is as follows:

1. Replace the recursive function with a while loop
2. Replace each argument to the recursive function with a var
3. Instead of making a recursive call with new values, update the variables with those new values
4. Run the loop until reaching the base case, then return the variable that stands for the accumulator

Concretely, in code:

def traceSpiral(dims: Dims): List[Point] =
  var result = List.empty[Point] // 1
  var board = buildCoordinates(dims) // 2

  while board != Nil do // 3
    val topRow = board.head // 4
    val otherRows = board.tail // 5

    result = topRow.reverse ++ result // 6

    board = rotateCCW(otherRows) // 7

  end while

  result.reverse // 8

• We no longer have a recursive function, just one big loop
• What were previously function arguments are now the (mutable) variables result and board (1, 2)
• The loop will run until we hit the base case, the empty board (3)
• While the board is not empty, we peel of the current row (4), and the rest of the rows (5)
• We then update result variable in the same way we did in the last recursive solution (6)
• And the same for the board variable (7)
• Once the loop completes, result contains the full result in reverse, which we return after reversing (8)

Look how far away from our initial, elegant, recursive solution we managed to get. But also notice how much more error-prone this code is:

• We no longer use pattern matching, instead relying on the unsafe head and tail methods¹⁸, the compiler will no longer have our back when refactoring
• If we forget to update result, everything will still compile and run, but the final result will be wrong
• If we forget to update board, everything will still compile and run, but this time we'll hit an infinite loop¹⁹

I won't disclose how many of those issues I've hit while writing this code. But all I'll say is that I'm happy that I had a robust test suite. Having a solid reference sure pays dividends...

Looking at this solution though, we might again notice some redundancy. As we are no longer in the nice functional realm, do we really need to pay the price for building an immutable list? Especially as it forces us through all the reverse shenanigans just to keep us from getting quadratic.

Might as well go all in on the procedural approach and use a more performant mutable collection:

def traceSpiral(dims: Dims): List[Point] =
  val result = ListBuffer.empty[Point] // 1
  var board = buildCoordinates(dims)

  while board != Nil do
    val topRow = board.head
    val otherRows = board.tail

    result.addAll(topRow) // 2

    board = rotateCCW(otherRows)

  end while

  result.toList // 3

result is now a mutable ListBuffer (1), which can be appended to efficiently. Which is what we do in (2), avoiding the need to reverse. At the very end we build up the final List result from the buffer (3). This way we can maintain a functional facade while utilizing mutability in the implementation. We gained performance and made the code a bit less confusing.

Guided by the reference solution we managed to accommodate the needs of our fellow procedural programmers, recursion be damned. Yay us.

Now let's move on to the real elephant in the room.

Laziness with Class

One of my biggest takeaways from dabbling in computer science is that it pays to be lazy²⁰.

Clearly the reference solution is not very lazy. It allocates a potentially large board upfront, while in reality it might not be needed at all. Maybe our clients will need only part of the solution? Or maybe they'll use it one step at a time, like with streaming? But no, we prevent any such useful use cases by allocating O(w * h) data upfront, with no way to take it back. Time to fix that.

Nostalgic aside...

Back in the olden days, in the heyday of OOP, some smart people decreed that we should all "program to interface". And so you would see programmers gather around in circles and chant "SOLID, SOLID, SOLID..." as they conjure up the latest AbstractSingletonFactoryFactoryVisitater²¹ out of the ether. Those were the days...

And although these ancient customs may seem strange to us in this day and age, there is a grain of truth to it. Programming to interface can be very useful.

It is indeed by way of us using a very concrete representation of the board, namely List[List[Point]], that we are forced to allocate memory prematurely. But is it actually necessary for the board to be a list? Is it essential to the solution?

If we could extract some kind of simple interface from the reference maybe we'll be able to implement a less memory intensive solution.

We can use the code we started with as guidance:

def traceSpiral(dims: Dims): List[Point] =
  peel(buildCoordinates(dims)) // 1

def peel(board: List[List[Point]]): List[Point] =
  board match // 2
    case Nil => Nil // 3
    case topRow :: otherRows => // 4
      topRow ++ peel(rotateCCW(otherRows)) // 5

Suppose we had some entity called Board. What kind of interface should it have? Taking inspiration from the reference solution, what we need is:

1. A way to construct a Board for given dimensions: Dims => Board (1)
2. A way to query the state of the board, pattern matching would be a nice way to do it (2)
3. A case for empty boards (3)
4. A case for non-empty boards, where we can extract the top row and the rest of the rows (4)
5. A way to rotate the board counter-clockwise (5)

Any concrete Board representation that implements this interface can be used to solve our problem. The trick is to find a representation that consumes less memory than List. If this was some real code and we wanted to make it polymorphic over different board implementations, we might actually define that interface in code. But here I'll just use this pseudo-interface as a guide and provide another concrete implementation directly.

Not using List is necessary for us to be able to solve the problem lazily, but it's not sufficient. To actually turn things lazy we'll use Iterators²². So instead of returning List[Point], we'll return Iterator[Point]. The new signature that we need to implement is:

def traceSpiral(dims: Dims): Iterator[Point]

With the goal being that we never allocate more than O(1) memory.

Let's sketch out our new Board type, we'll refine the details as we go along. First define a type:

sealed trait Board

We are using a sealed trait (sum type) as requirements 2-4 indicate that we are going to have more than one case: empty and non-empty. Let's add those:

case object Empty extends Board

case object NonEmpty extends Board

One case per requirement, and we can distinguish between them by pattern matching.

As per requirement 4 we'll also need some way of extracting data from the non-empty case, so we'll add methods:

case object NonEmpty extends Board:
  def topRow: Iterator[Point]
  def otherRows: Board

We are using methods rather than class fields as I don't yet want to commit to a specific representation of NonEmpty. topRow returns an Iterator and not a List so as to preserve our laziness goals.

Requirement 5 implies that we need a rotation method that works on any board:

sealed trait Board:
  def rotateCCW: Board

Lastly, we need a builder function for requirement 1:

def buildCoordinates(dims: Dims): Board

And this completes our pseudo-interface, we can plug it into the algorithm and get a brand new solution to the spiral problem. To wit:

def traceSpiral(dims: Dims): Iterator[Point] =
    peel(buildCoordinates(dims))

def peel(board: Board): Iterator[Point] =
  board match
    case Empty => Iterator.empty // 1
    case ps: NonEmpty => // 2
      ps.topRow ++ peel(ps.otherRows.rotateCCW) // 3

This looks eerily similar to the reference solution. We just replaced every occurrence of List with Iterator, as Iterator and List share a very similar interface²³ this change is almost seamless, ++ works for either type (3). In (1) we return an empty Iterator rather than an empty List.

The only place things look a bit different is the NonEmpty pattern match (2), where we no longer extract the rows²⁴. Instead, we get them with the appropriate method calls on the board value (3).

As a bonus, we no longer have to care about the non-tail-recursive call to peel. ++ being lazy in its right argument makes that problem go away (left as an exercise to figure out why).

All that's left is to actually implement the functions I left abstract. Once we do that, we should have a working solution, but with a very different memory footprint.

Let's start with the easy case, Empty. The empty case has no data associated with it, so we don't need to add any fields to it. All we need is to be able to rotate it, which is trivial:

case object Empty extends Board:
  def rotateCCW: Board = Empty

A rotated empty board is still an empty board. Done.

Now comes the tricky bit, how do we implement NonEmpty without populating a whole board-worth of data?

Here we can take advantage of the fact that we already have a working solution that we can use to gain some insight about the shape of the data we're dealing with. Recall the board that we start with for a 4x3 problem:

---------------------------------
| (0,0) | (1,0) | (2,0) | (3,0) |
---------------------------------
| (0,1) | (1,1) | (2,1) | (3,1) |
---------------------------------
| (0,2) | (1,2) | (2,2) | (3,2) |
---------------------------------

The first row, which is what we want to extract is not made out of arbitrary points, instead it's very structured. It's just (0, i), where i is 0 <= i < 4. We can easily represents this with an Iterator that will consume a constant amount of space:

Iterator.range(0, 4).map(Point(_, 0))

Iterator.range creates a lazy range that is equivalent to [0, 1, 2, 3], but without actually materializing all the numbers into memory. Then we use map, which is lazy on Iterator, to build up Point(i, 0).

For the actual implementation of topRow we'll need to replace the hardcoded 4 with the width of the board. And that's the first ingredient that NonEmpty needs to hold on to: the current Dims of the board. Leading to this code:

case class NonEmpty(dims: Dims) extends Board: // 1
  def topRow: Iterator[Point] =
    Iterator.range(0, dims.w).map(Point(_, 0)) // 2

We added a new field to the NonEmpty case to hold on to the dimensions that this board represents (1). Using the dims field it's now possible to create the iterator for the first row (2).

This seemingly works, but it was suspiciously easy to implement. Sure this is the correct answer on the first step of the solution, but will it work for the second step?

Recall that as we are solving the problem we keep shrinking and rotating the board. So for the second step we should be working with the following board:

-----------------
| (3,1) | (3,2) |
-----------------
| (2,1) | (2,2) |
-----------------
| (1,1) | (1,2) |
-----------------
| (0,1) | (0,2) |
-----------------

This is what's left after we remove the first row and rotate the board. The board will now have different dimensions, but we are covered, we have the dimensions as a field of NonEmpty. We can update its values as we are building up the solution.

But even with the correct dimensions in place, the code we just had:

Iterator.range(0, dims.w).map(Point(_, 0))

Won't produce the correct result. We'll get [(0, 0), (1, 0)], which is the first row of a board of dimensions 2x4, instead of the correct [(3, 1), (3, 2)]. The problem is that we are not actually working with a 2x4 board, the entries that we are looking for come from the original board of 4x3. Compared to the 2x4 board, the original board is rotated and shifted (since we removed a row). Without the information about how much we are rotated and shifted we won't be able to compute the correct first row. Let's add this information to our class:

case class NonEmpty(dims: Dims, rotation: Rotation, shift: Point) extends Board

Rotation is a type that represents the current rotation of the board relative to the original board we started with. We do it by wrapping a number that represents the number of 90 degree rotations that we have²⁵:

case class Rotation(value: Int)

E.g., Rotation(0) is no rotation, Rotation(1) is rotation by 90 degrees, and we wrap around at 4: Rotation(4) = Rotation(0). For the second step we are at Rotation(1).

The shift field represents where we need to shift the current board so that it matches the original board²⁶. Or more concretely, where the top-left corner of the current board is located on the original board. We'll be adding shift to each point in the result. For the second step the shift is (3, 1).

With these two fields we can define the following helper method:

def rotateShift(point: Point): Point

This method takes a single point, and rotates and shifts it using the rotation and shift fields. The implementation is not very difficult (you can see it in the repo), but having nonexistent spatial abilities it took me quite a few trials and errors to get it right. Figuring out the axis of rotation, mixing up signs, the order of operations, and rotation directions. But guess what had my back all along? A strong test suite backed by a correct solution.

If we keep track of the correct rotation and shift while we compute the solution (we'll see how later on), we can use them to get the right answer for the first row at every step:

def topRow: Iterator[Point] =
  val row = Iterator.range(0, dims.w).map(Point(_, 0)) // 1

  row.map(rotateShift) // 2

Now we compute the first row like we did before (1), but instead of returning it as is, we rotateShift each point in the row (2). This is still as lazy as before, but now gives the correct answer at every step (assuming that the rotate and shift fields are correct).

For example, as mentioned above, for the second step of the solution we should have: rotation = Rotation(1), shift = Point(3, 1), and row = [(0, 0), (1, 0)]. If we rotate it by 90 degrees we get:

[(0, 0), (0, 1)]

Then we shift it to get:

[(3, 1), (3, 2)]

Which is the correct result for the second step.

Before we proceed with otherRows, let's define a useful helper:

def buildCoordinateFrom(dims: Dims, // 1
                        rotation: Rotation,
                        shift: Point): Board =
  if dims.area == 0 then Empty // 2
  else NonEmpty(dims, rotation, shift) // 3

This function takes in all the ingredient that we need for a board (1) and constructs the appropriate representation for it. For dimensions that represent an empty area we return an instance of Empty (2). Otherwise we return a NonEmpty instance with all the arguments we got (3). This implementation conveniently hides away the distinction between Empty and NonEmpty when we don't care about it.

With this function we can also implement the buildCoordinates function that's part of our "interface":

def buildCoordinates(dims: Dims): Board =
  buildCoordinateFrom(dims, Rotation(0), Point(0, 0))

This is just a call to buildCoordinateFrom with the rotation and shift set to their initial values (no rotation and no shift).

Next we are ready to implement otherRows. As we are aiming for laziness here, no "actual" work should be performed by otherRows. It's topRow's job to produce actual data, otherRows needs only to keep track of the changing state of the board. That is, it needs to update dims, rotation, and shift to match the new, smaller board.

Pictorially, what's happening is this:

---------------------------------
|   x   |   x   |   x   |   x   |
---------------------------------
| (0,1) | (1,1) | (2,1) | (3,1) |
---------------------------------
| (0,2) | (1,2) | (2,2) | (3,2) |
---------------------------------

We need to remove the top row, marked by xs. We can do it like so:

def otherRows: Board =
  val newDims = dims.reduceH(1) // 1
  val newShift = rotateShift(Point(x = 0, y = 1)) // 2

  buildCoordinateFrom(newDims, rotation, newShift) // 3

In the first step we reduce the vertical (height) dimension of the board by 1 (1), the intent being to drop the top row. Next we compute the new shift. When removing the top row, the new top-left corner moves one step down, hence the shift is by (0, 1) (one step down). But we must not forget that we have the current rotation and shift to account for, so we have to rotateShift (0, 1) to cover that (2). Finally, we build up a new (smaller) board with new dimensions and shift using buildCoordinateFrom (3).

All we did here is to manipulate the parameters that represent the state of the board, and laziness is preserved.

The last ingredient to complete this lazy solution is rotateCCW. It's similar to otherRows in that it only manipulates the state parameters, but it's somewhat trickier geometrically. We need this board:

---------------------------------
| (0,1) | (1,1) | (2,1) | (3,1) |
---------------------------------
| (0,2) | (1,2) | (2,2) | (3,2) |
---------------------------------

To become this:

-----------------
| (3,1) | (3,2) |
-----------------
| (2,1) | (2,2) |
-----------------
| (1,1) | (1,2) |
-----------------
| (0,1) | (0,2) |
-----------------

Meaning that the top right corner rotates to become the top-left corner.

def rotateCCW: Board =
  val newDims = dims.transpose // 1
  val newRotation = rotation.next // 2
  val newShift = rotateShift(Point(x = dims.w - 1, y = 0)) // 3

  buildCoordinateFrom(newDims, newRotation, newShift) // 4

Step by step:

• The new dimensions are just the transpose (swapping w and h) of the old ones (1)
• The new rotation is + 1 on the old one, but we need to wrap around when we reach 4, that's what next does (2)
• The new shift is the top-right corner (w - 1, 0), which now becomes the top-left corner, appropriately rotateShifted, of course (3)²⁷
• With the full new state, we can create a new board (4)

That's it! We got a fully lazy solution to our problem. And if you're thinking to yourselves "wow, so much geometry, must have been tedious and error prone to implement", you're completely right. Lucky that I was blessed by a correct reference solution to keep me sane.

And after so many failed attempts, it was all the more satisfying to see the test suite passing on this one:

LazySuite:
  + Traces the correct spiral 0.023s
  + Sanity: all points in bounds 0.051s
  + Sanity: dimensions match number of points 0.019s
  + Sanity: no duplicate points 0.021s
  + Matches reference 0.04s

But is it actually lazy?

While this code using the reference solution throws an out-of-memory exception on my machine:

Reference.traceSpiral(Dims(w = 5000, h = 5000))
  .foreach(println)

The same code with the lazy solution happily chugs along, printing all the spiral elements:

Lazy.traceSpiral(Dims(w = 5000, h = 5000))
  .foreach(println)

Mission accomplished. By using the "interface" of the obviously correct solution as inspiration we managed to derive a functioning lazy solution. At least for me, coming up with such a solution without some concrete (and correct) reference would've been challenging²⁸.

But all these rotations and shifts, they do feel a bit painful.

Follow the Pain

There's this phenomenon that I noticed over the years, that software developers tend to build up pain tolerance to the point where they no longer feel any pain while writing code. It seems to be a protection mechanism against all the terrible code we have to deal with daily. "It gets the job done", "worse is better", "it is what it is", they say to themselves and move along the 3,000 LOC function. And that's a shame. Pain is an excellent driver for improvement. The moment you stop feeling pain, like a shark that stops moving, your creativity and drive to improve wither away.

Cultivating the appropriate pain sensitivity when writing code is a must-have when working on large and complex codebases.

With that in mind, I shall follow the pain that we felt in the previous section with all the geometry and rotations. How did we get there? Does it have to be that way?

We pretty much mechanically followed the "interface" dictated by the reference solution. One might say that we were lulled into a false sense of security by it. Maybe it's a downside of having an existing solution. But not all is lost. Now that we have the painful solution, we can use it to visualize the problem, and maybe come up with something better.

The main pain point of the lazy solution are the rotations that we have to keep track of. They contribute the biggest chunk of complication in the code, making the shifts jump all over the place in a seemingly random fashion. Let's plot the rotations and shifts on a board:

-----------------------------------------------------------------------
| a,0→ |      |      |      |      |      |      |      |      |      |
-----------------------------------------------------------------------
|      | e,0→ |      |      |      |      |      |      |      | ↓b,1 |
-----------------------------------------------------------------------
|      |      | i,0→ |      |      |      |      |      | ↓f,1 |      |
-----------------------------------------------------------------------
|      |      |      | m,0→ |      |      |      | ↓j,1 |      |      |
-----------------------------------------------------------------------
|      |      | l,3↑ |      |      | ←o,2 | ↓n,1 |      |      |      |
-----------------------------------------------------------------------
|      | h,3↑ |      |      |      |      | ←k,2 |      |      |      |
-----------------------------------------------------------------------
| d,3↑ |      |      |      |      |      |      | ←g,2 |      |      |
-----------------------------------------------------------------------
|      |      |      |      |      |      |      |      | ←c,2 |      |
-----------------------------------------------------------------------

Here the first letter (a-z) is indexing the shifts, the number is the rotation index (0-3), and the arrow is the direction of the row getting peeled.

Unsurprisingly, the shifts form a spiral-like pattern, something that was not intuitively clear from the code. Seeing this from a high-level vantage point makes the pattern very clear: all shifts of the same rotation sit on a diagonal. Better yet, the shifts with no rotation (== 0) sit on the main diagonal (i, i), for i going from 0 to the center of the board.

This reflects the not very deep insight²⁹ about 90 degree rotations: every 4 rotations we are back where we started. So each shift of the same rotation must start on the same angle of the board.

With this insight in mind we can come up with a new algorithm to solve the riddle:

• On each step, draw a frame around the board
• Remove the frame's points and add them (in clockwise order) to the solution
• Repeat until the board is empty

Notice how this algorithm does not imply any rotations. We just remove frames one by one keeping the board in place.

We can illustrate the first few steps of the algorithm with this board:

---------------------------------------------------------------------------------
| (0,0) | (1,0) | (2,0) | (3,0) | (4,0) | (5,0) | (6,0) | (7,0) | (8,0) | (9,0) |
---------------------------------------------------------------------------------
| (0,1) | (1,1) | (2,1) | (3,1) | (4,1) | (5,1) | (6,1) | (7,1) | (8,1) | (9,1) |
---------------------------------------------------------------------------------
| (0,2) | (1,2) | (2,2) | (3,2) | (4,2) | (5,2) | (6,2) | (7,2) | (8,2) | (9,2) |
---------------------------------------------------------------------------------
| (0,3) | (1,3) | (2,3) | (3,3) | (4,3) | (5,3) | (6,3) | (7,3) | (8,3) | (9,3) |
---------------------------------------------------------------------------------
| (0,4) | (1,4) | (2,4) | (3,4) | (4,4) | (5,4) | (6,4) | (7,4) | (8,4) | (9,4) |
---------------------------------------------------------------------------------
| (0,5) | (1,5) | (2,5) | (3,5) | (4,5) | (5,5) | (6,5) | (7,5) | (8,5) | (9,5) |
---------------------------------------------------------------------------------
| (0,6) | (1,6) | (2,6) | (3,6) | (4,6) | (5,6) | (6,6) | (7,6) | (8,6) | (9,6) |
---------------------------------------------------------------------------------
| (0,7) | (1,7) | (2,7) | (3,7) | (4,7) | (5,7) | (6,7) | (7,7) | (8,7) | (9,7) |
---------------------------------------------------------------------------------

The first frame will be:

---------------------------------------------------------------------------------
| (0,0) | (1,0) | (2,0) | (3,0) | (4,0) | (5,0) | (6,0) | (7,0) | (8,0) | (9,0) |
---------------------------------------------------------------------------------
| (0,1) |                                                               | (9,1) |
---------                                                               ---------
| (0,2) |                                                               | (9,2) |
---------                                                               ---------
| (0,3) |                                                               | (9,3) |
---------                                                               ---------
| (0,4) |                                                               | (9,4) |
---------                                                               ---------
| (0,5) |                                                               | (9,5) |
---------                                                               ---------
| (0,6) |                                                               | (9,6) |
---------------------------------------------------------------------------------
| (0,7) | (1,7) | (2,7) | (3,7) | (4,7) | (5,7) | (6,7) | (7,7) | (8,7) | (9,7) |
---------------------------------------------------------------------------------

We add the elements of the frame in clockwise direction to the solution. The remaining board becomes:

-----------------------------------------------------------------
| (1,1) | (2,1) | (3,1) | (4,1) | (5,1) | (6,1) | (7,1) | (8,1) |
-----------------------------------------------------------------
| (1,2) | (2,2) | (3,2) | (4,2) | (5,2) | (6,2) | (7,2) | (8,2) |
-----------------------------------------------------------------
| (1,3) | (2,3) | (3,3) | (4,3) | (5,3) | (6,3) | (7,3) | (8,3) |
-----------------------------------------------------------------
| (1,4) | (2,4) | (3,4) | (4,4) | (5,4) | (6,4) | (7,4) | (8,4) |
-----------------------------------------------------------------
| (1,5) | (2,5) | (3,5) | (4,5) | (5,5) | (6,5) | (7,5) | (8,5) |
-----------------------------------------------------------------
| (1,6) | (2,6) | (3,6) | (4,6) | (5,6) | (6,6) | (7,6) | (8,6) |
-----------------------------------------------------------------
| (1,7) | (2,7) | (3,7) | (4,7) | (5,7) | (6,7) | (7,7) | (8,7) |
-----------------------------------------------------------------

The next frame becomes:

-----------------------------------------------------------------
| (1,1) | (2,1) | (3,1) | (4,1) | (5,1) | (6,1) | (7,1) | (8,1) |
-----------------------------------------------------------------
| (1,2) |                                               | (8,2) |
---------                                               ---------
| (1,3) |                                               | (8,3) |
---------                                               ---------
| (1,4) |                                               | (8,4) |
---------                                               ---------
| (1,5) |                                               | (8,5) |
---------                                               ---------
| (1,6) |                                               | (8,6) |
-----------------------------------------------------------------
| (1,7) | (2,7) | (3,7) | (4,7) | (5,7) | (6,7) | (7,7) | (8,7) |
-----------------------------------------------------------------

We add it to the solution, and repeat until the board is empty. No rotations involved, everything seems simple³⁰.

Let's code this up (while still maintaining laziness). We'll use the description of the algorithm as an inspiration for an "interface", and solve the problem in terms of the new interface. After that we'll actually implement the interface itself.

Like before, we'll start with two cases for the board:

sealed trait Board

case object Empty extends Board

case class NonEmpty extends Board:
  def getFrame: Iterator[Point] // 1
  def dropFrame: Board // 2

def buildCoordinates(dims: Dims): Board // 3

The Empty case looks the same (1), no additional methods beyond the datatype itself. NonEmpty changes completely and now has two new methods:

• getFrame - returns an iterator for the full frame of the board (1), in clockwise order
• dropFrame- returns a new board with the outer frame of the board removed (2)

We also still use a factory function to build up a board for given dimensions (3).

This covers all the functionality we need to implement the new algorithm:

def traceSpiral(dims: Dims): Iterator[Point] =
  peel(Board.buildCoordinates(dims)) // 1

def peel(board: Board): Iterator[Point] =
  board match // 2
    case Empty => Iterator.empty // 3
    case nonEmpty: NonEmpty => // 4
      nonEmpty.getFrame ++ peel(nonEmpty.dropFrame) // 5

The new implementation is still pretty simple, and quite similar to the original lazy solution:

• We build a new board for the dimensions of the problem and call the recursive peel function on it (1)
• On each peeling step we match on the board (2)
• If it's empty, we are done and produce an empty iterator (3)
• Otherwise, for the non-empty case (4)
• We extract the frame of the board, and prepend it to the result of peeling the board without the frame (5)

We followed the description of the algorithm to the letter, now we just need to implement the interface.

For the Empty case there's nothing more to implement. Rotations are no longer a part of the interface, so the Empty case just needs to exist.

Now, what kind of data does NonEmpty needs to have? Before we kept track of:

• The dimensions of the board, still relevant
• The rotation of the board, no longer relevant
• The shift of the board, still relevant as we will keep shrinking the board

But we can simplify the shift. Previously the shift was a Point because it was difficult to follow the position at each step. But now we just need to move along the main diagonal on each peeling step. So on step i, the shift is (i, i), meaning that we just need a single number, rather than a point to represent the shift.

NonEmpty then becomes:

case class NonEmpty(dims: Dims, shift: Int) extends Board

With these pieces of state we can implement the methods of NonEmpty. First getFrame.

The idea here is similar to getting the first row of a board like we did in the first lazy solution. But this time we need both horizontal and vertical directions, moving forwards and backwards. So, for example, the vertical segment on the left is given by:

Iterator.range(h - 1, 0, step = -1) // 1
  .map(Point(0, _)) // 2

This segment at y = h - 1, and we step backwards till y = 0 (1). This becomes the y coordinate of Points with a fixed x = 0. Figuring out the exact offsets and handling off-by-one errors is of course prone to bugs, but we're not worried, we have a robust test suite to catch such things.

Getting the full frame becomes:

def getFrame: Iterator[Point] =
  import dims.* // 1

  val path1 = Iterator.range(0, w - 1).map(Point(_, 0)) // 2
  val path2 = Iterator.range(0, h - 1).map(Point(w - 1, _))
  val path3 = Iterator.range(w - 1, 0, step = -1).map(Point(_, h - 1))
  val path4 = Iterator.range(h - 1, 0, step = -1).map(Point(0, _))

  val frame = // 3
    path1 ++ path2 ++ path3 ++ path4

  frame.map(_.shiftBy(dx = shift, dy = shift)) // 4

• We start by importing the fields of the Dims instance of the board, just to make the code below more concise (1)
• Then we create the different segments of the frame (2), in clockwise order, the details of the numbering are left as an exercise
• The full frame is composed from concatenating all four segments (3)
• Lastly, we need to shift the frame diagonally down, we do it by moving each point by (shift, shift) (4)

The result is a full frame, shifted to correspond to location of the current step. I don't know about you, but for me it was much easier to figure out this code compared to all the rotation logic we had before.

Like before, we'll use a helper to build boards at the current dimensions and shift:

def buildCoordinateFrom(dims: Dims, shift: Int): Board = // 1
  if dims.area == 0 then Empty // 2
  else NonEmpty(dims, shift) // 3

This time we only get the dimensions and shift (1). In (2) we create an Empty board if the area is 0. If not, we create a NonEmpty board with the given dimensions and shift (3).

With the helper, buildCoordinates is trivial:

def buildCoordinates(dims: Dims): Board =
  buildCoordinateFrom(dims, 0)

And lastly, dropFrame:

def dropFrame: Board =
  val newDims = dims.reduceBy(2) // 1
  val newShift = shift + 1 // 2

  buildCoordinateFrom(newDims, newShift) // 3

• The new dimensions (1) after dropping a frame are computed by reducing the dimensions by 2 both horizontally and vertically (since the frame has two segments in each orientation)
• The new shift (2) is just incrementing by 1 as we move along the main diagonal
• Then we can build a new board with the new state (3)

Done. This should be a fully working, lazy, solution to the problem. As promised it's greatly simplified by not having to deal with rotations at all.

Does it work?

Let's find out by running the tests³¹:

LazyFrameBuggySuite:
  + Traces the correct spiral 0.019s
^C

The good news are that the unit test is passing. The bad news are that I had to terminate the run due to what seems like an infinite loop.

The property-based tests are catching some edge case that the unit test is missing. Great to have them watching our back. Unfortunately, as the blight of Turing completeness is upon us, there's no way for the tests to actually show us what triggered the infinite loop.

Instead we'll be doing some good old-fashioned println debugging. Since the board contains the full state information as we are moving along the solution, we'll start by printing the board on each step. Which might give us the following (output changes due to randomization in property-based test):

...
NonEmpty(Dims(3,1),0)
NonEmpty(Dims(1,-1),1)
NonEmpty(Dims(-1,-3),2)
NonEmpty(Dims(-3,-5),3)
NonEmpty(Dims(-5,-7),4)
NonEmpty(Dims(-7,-9),5)
...

Somehow, we are getting negative dimensions. Philosophical issues aside, how on earth does the board's dimension gets negative?

The clue is in the fact that the dimensions reduce by two on every step. Which was of course part of the algorithm. Unlike the original lazy version where the dimensions reduce by 1 one each step, and we are guaranteed to hit 0 eventually, in the new code we might just jump over it.

Now, if I had any principles, I would be practicing what I preach and make this "illegal state unrepresentable" in a way that's guaranteed by the compiler. But I'm not, and I've already spilt too much ink discussing this one problem.

What we can do instead is to fix the code where we skip over 0 and decide that negative dimensions should yield an empty board:

def buildCoordinateFrom(dims: Dims, shift: Int): Board =
  if dims.w <= 0 || dims.h <= 0 then Empty
  else NonEmpty(dims, shift)

Now whenever any of the dimensions hops into the negative, we decree it to be the Empty board. Does it work now?

The good news is that it no longer goes into an infinite loop, the bad news are that now some tests are actually failing.

We pass the unit test, and the first sanity check:

LazyFrameBuggySuite:
  + Traces the correct spiral 0.016s
  + Sanity: all points in bounds 0.033s

That unit test seems awfully resilient. But then we fail everything else.

Somehow we omit points from the solution³²:

==> X LazyFrameBuggySuite. Sanity: dimensions match number of points  0.023
43:
44:      points.size ==== dims.area
45:
- LazyFrameBuggySuite. Sanity: dimensions match number of points: Falsified after 10 passed tests
> Dims(1,1)
> === Not Equal ===
> --- lhs ---
> 0
> --- rhs ---
> 1

We also duplicate points, something that never happened before:

==> X LazyFrameBuggySuite. Sanity: no duplicate points  0.003s
49:
50:      points.distinct ==== points
- LazyFrameBuggySuite. Sanity: no duplicate points: Falsified after 13 passed tests
> Dims(1,3)
> === Not Equal ===
> --- lhs ---
> List(Point(0,0), Point(0,1), Point(0,2))
> --- rhs ---
> List(Point(0,0), Point(0,1), Point(0,2), Point(0,1))

Since we don't even pass the simple sanity checks, we obviously fail to match the reference solution:

==> X LazyFrameBuggySuite. Matches reference  0.009
13:
14:      actual ==== expected
- LazyFrameBuggySuite. Matches reference: Falsified after 10 passed tests
> Dims(1,1)
> === Not Equal ===
> --- lhs ---
> List()
> --- rhs ---
> List(Point(0,0))

Not for the first time, our comprehensive test suite is paying dividends. Something non-trivial is wrong here.

Of the sanity checks the duplicate points looks like the most informative one. Where can we get a duplicate point?

Since the output is small (but not too small, so it's "interesting"), we can trace the code and see what went wrong. The board we are dealing with is:

---------
| (0,0) |
---------
| (0,1) |
---------
| (0,2) |
---------

The board is not empty, so the first non-trivial step is to take the frame of the board with getFrame. Hmm... What is the frame of a single column?

Clearly it can't be this:

val path1 = Iterator.range(0, w - 1).map(Point(_, 0))
val path2 = Iterator.range(0, h - 1).map(Point(w - 1, _))
val path3 = Iterator.range(w - 1, 0, step = -1).map(Point(_, h - 1))
val path4 = Iterator.range(h - 1, 0, step = -1).map(Point(0, _))

val frame =
  path1 ++ path2 ++ path3 ++ path4

This implies that we have four sides to the frame, but on a column-only (or row-only) board we don't actually have four sides. This also explains why we have duplicate points. With a single column there's an overlapping contribution from path2 and path4 (and similarly for a single row).

And so, it appears that any board that ends up with a single row or column after peeling enough frames is an edge case in this new solution. We were unlucky that the unit test didn't catch it. But that's the nature of unit tests, you're either lucky, or you miss things. With a solid property-based suite, we can take most of the luck out of the equation³³.

Now that we isolated the issue, the fix is fairly straightforward, the frame of single row/column is just that row/column:

val frame = dims match
  case Dims(w, 1) => Iterator.range(0, w).map(Point(_, 0)) // 1
  case Dims(1, h) => Iterator.range(0, h).map(Point(0, _)) // 2
  case Dims(w, h) => // 3
    val path1 = Iterator.range(0, w - 1).map(Point(_, 0))
    val path2 = Iterator.range(0, h - 1).map(Point(w - 1, _))
    val path3 = Iterator.range(w - 1, 0, step = -1).map(Point(_, h - 1))
    val path4 = Iterator.range(h - 1, 0, step = -1).map(Point(0, _))

      path1 ++ path2 ++ path3 ++ path4

This is the code for the frame calculation, with two special cases, for a single row (1) and a single column (2). In both cases we just return the corresponding row/column. The last case (3) is the same as the old code.

Are we there yet?

LazyFrameSuite:
  + Traces the correct spiral 0.019s
  + Sanity: all points in bounds 0.036s
  + Sanity: dimensions match number of points 0.012s
  + Sanity: no duplicate points 0.013s
  + Matches reference 0.034s

Yep! We pass our test suite. And so we now have a solution that's both lazy and (despite the edge cases) has what I think of as simpler code, without all the complication of rotations³⁴.

That's when the product manager steps in with new feature demands...

Spiral Tracing as a Service

Our clients want to get specific points on the spiral on demand. They might say "give me point number 233 on a spiral on a 567x665 board" and our Spiral API™ should quickly produce a result³⁵.

Since our clients only ask for a single point on the board, and care about low latency, it would be wasteful to compute the whole spiral. What we should do instead is do the minimal amount of computation to get that one point.

Unfortunately, I'm not smart enough to come up with a closed-form formula taking an index to its location on the board's spiral³⁶. So all I can do instead is to fetch the point without materializing all intermediate points, and skipping as many steps as I can.

The new function that we'll implement is this:

def findPointAt(index: Int, dims: Dims): Option[Point]

Given an index and dimensions, we compute the point that matches the index (and None when out of bounds). More precisely, ignoring the efficiency requirements we could define:

def findPointAt(index: Int, dims: Dims): Option[Point] =
  Reference.traceSpiral(dims).lift(index)

This solution will first build the whole spiral with traceSpiral and access the element at index. lift turns indexing into a safe, Option-returning operation. Logically, this is correct, but we want something faster, that doesn't go over all the intermediate points, nor should it go to points beyond index. We'll call this new approach "computational".

For inspiration we can use the frame solution, as it has all the ingredients we need.

Recall that we are moving along frames of the board. We do that by skipping one frame at a time, and each frame starts on the next point on the main diagonal of the board:

-------------------------------------------------------------
|  0  |     |     |     |     |     |     |     |     |     |
-------------------------------------------------------------
|     |  1  |     |     |     |     |     |     |     |     |
-------------------------------------------------------------
|     |     |  2  |     |     |     |     |     |     |     |
-------------------------------------------------------------
|     |     |     |  3  |     |     |     |     |     |     |
-------------------------------------------------------------
|     |     |     |     |     |     |     |     |     |     |
-------------------------------------------------------------
|     |     |     |     |     |     |     |     |     |     |
-------------------------------------------------------------
|     |     |     |     |     |     |     |     |     |     |
-------------------------------------------------------------
|     |     |     |     |     |     |     |     |     |     |
-------------------------------------------------------------

The first frame is on the 0 offset, the second on 1, and so on. Each frame corresponds to a range of indices on the spiral. For example, on the board above, the frame on 0 corresponds to indices 0 to 31 (inclusive), the frame on 1 corresponds to indices 32 to 55 (inclusive). In the frame solution we managed to compute all the points of a given frame. By massaging that solution a bit, we can compute a specific index on a frame.

From this we can split up the problem into two parts:

1. Find the frame that contains the index we are looking for
2. Compute the point on the frame that matches the index

This way we are not wasting our time going around the frames, we just skip directly to the frame we need, and do some computation over it. Yielding a speed up over the original solution (or even the lazy one).

Let's code this up. As we had quite enough recursion for one post, let's go back to the procedural/iterative approach, using the recursive frame solution as inspiration (and remembering how to convert recursion to loops from the previous parts). We shall leave behind any pretense for functional elegance.

The first question about the algorithm above, is what are we iterating over? That's the shifts of the board (which correspond to frames), they start from 0 and keep growing, until we find our index.

The next question, is what do we do on every step of iteration? We need to check where the index is relative to the current frame. We have two possible cases, either the index is after the current frame, or within it. I said the word "case", so let's have this coded up as a datatype³⁷:

enum Framing:
    case After // 1
    case Within(frame: FrameData) // 2

The first case is self-evident (1). But why does the second case (2) have an argument? In the spirit of the great "parse don't validate" post, we (retroactively) predict that the point in the code where we discover that we are within the frame is also the location where we have all the data necessary to compute the result we are after. The Within constructor holds on to that data so that it can be used later on and not recomputed. The exact contents of FrameData will be specified later on.

For now, let's pretend that we have a function to compute the current Framing:

def getFraming(index: Int, shift: Int, dims: Dims): Framing

getFraming takes the index we are looking for, a shift on the board, and the dimensions of the board, it then computes the Framing of the index at the given shift. We'll implement this function in a bit.

The last thing we'll need before we proceed with the main loop is a way to convert the frame we found into a specific point that corresponds to the index we are searching for. Let us again pretend that we already have a function for that:

def getPointOnFrame(index: Int, frame: FrameData): Point

Given an index and a FrameData instance, we compute the corresponding Point.

Cool, with these ingredients in place we can implement the main loop:

def findPointAt(index: Int, dims: Dims): Option[Point] =
  if index < 0 || index >= dims.area then None // 1
  else
    var result = Option.empty[Point] // 2
    var shift = 0 // 3

    while result.isEmpty do // 4
      getFraming(index = index, shift = shift, dims) match // 5
        case Framing.After => shift += 1 // 6
        case Framing.Within(point) => // 7
          val point = getPointOnFrame(index, frame) // 8

          result = Some(point) // 9
    end while

    result // 10

The main loop has the following:

• We verify that the index we got is not out of bounds (1), if it is, we return None³⁸
• The variable result starts out as an empty value (2), to be set to the correct point later on
• The initial shift is 0 (3), starting out at the top-left corner of the board, corresponding to the outermost frame
• We set the condition for the loop (4), we iterate until a solution is found, that is, until result stops being empty
• On each step of the loop, we check the framing for the index on the current shift (5)
• If we aren't on the frame we are looking for (6), we increment the shift and move on
• If we are within the correct frame (7), we also have the FrameData for it which we can use
• We use the FrameData instance to convert the index into its Point (8)
• Which we then assign to the result (9)
• Once the loop is complete, result contains the correct Point, which we return (10)

Easy. All we have to do now is implement getFraming and getPointOnFrame. How hard could that be...

Recall how we moved around in the frame solution. We would increment the shift by 1, and then reduce the dimensions by 2, effectively working on an ever decreasing inner board.

Schematically, for shift == 2:

-------------------------------------------------------------
|  x  |  x  |  x  |  x  |  x  |  x  |  x  |  x  |  x  |  x  |
-------------------------------------------------------------
|  x  |  x  |  x  |  x  |  x  |  x  |  x  |  x  |  x  |  x  |
-------------------------------------------------------------
|  x  |  x  |  2  |     |     |  i  |     |     |  x  |  x  |
-------------------------------------------------------------
|  x  |  x  |     |     |  j  |     |     |     |  x  |  x  |
-------------------------------------------------------------
|  x  |  x  |     |     |     |     |     |     |  x  |  x  |
-------------------------------------------------------------
|  x  |  x  |     |     |     |     |     |     |  x  |  x  |
-------------------------------------------------------------
|  x  |  x  |  x  |  x  |  x  |  x  |  x  |  x  |  x  |  x  |
-------------------------------------------------------------
|  x  |  x  |  x  |  x  |  x  |  x  |  x  |  x  |  x  |  x  |
-------------------------------------------------------------

The xs mark the outer part of the board that we already passed. The empty squares mark the inner board, with its corner on shift number 2. i and j mark a couple of indices we might be looking for.

What does it tell us about the current framing? Where is 2 located relative to i or j?

From the drawing we can compute the index that corresponds to 2: it's just the area of the "outer board" marked by x. i is on the frame of 2, we can see that by computing the size of the frame of the inner board and adding it to the index of 2 and comparing that number to i. We can do the same thing for j to see that it's on another frame, after 2.

So to compute the framing we need to compute the area of the outer board, and the size of the current frame. With this insight, let's implement getFraming:

def getFraming(index: Int, shift: Int, dims: Dims): Framing =
  val totalArea = dims.area // 1
  val innerDims = dims.reduceBy(2 * shift) // 2

  val (frame = innerFrame, area = innerArea) =
    frameAndArea(innerDims) // 3

  val outerArea = totalArea - innerArea // 4

  if index >= outerArea + innerFrame then Framing.After // 5
  else
    val frame = FrameData(outerArea, shift, innerDims) // 6

    Framing.Within(frame) // 7

We start by getting the basic measurement of all the parts involved:

• The total area of the full board (1)
• The dimensions of the inner board (2), which we obtain by reducing the original Dims by double the shift number, as implied by the recursive frame solution
• We then call frameAndArea on innerDims (3) to obtain its frame size and area in a tuple (which we intermediately deconstruct)
• By knowing the innerArea and the totalArea we can compute the outerArea (4), which is just subtracting one from the other

Now we can figure out where the index is relative to the current frame:

• If it's outside the outer area and the current frame, we return Framing.After (5)
• Otherwise, we collect info about the frame into a FrameData instance (6)
• And return a Frame.Within with that data (7)

For completeness, here's the definition of FrameData:

case class FrameData(outerArea: Int, shift: Int, dims: Dims)

In FrameData we hold on to the area of the outer board, the shift that got us there, and the dimensions of the (smaller) inner board. We'll see later on how to use this info to compute a point on the frame.

frameAndArea should've been relatively simple, but it suffers from the same edge cases like we had in the lazy frame solution. Lucky that we have that solution to learn lessons from. Accounting for this we get:

def frameAndArea(dims: Dims): (frame: Int, area: Int) = // 1
  dims match // 2
    case _ if dims.w <= 0 || dims.h <= 0 => (frame = 0, area = 0) // 3
    case Dims(1, h) => (frame = h, area = h) // 4
    case Dims(w, 1) => (frame = w, area = w) // 5
    case Dims(w, h) => (frame = 2 * (dims.w + dims.h - 2), area = w * h) // 6

This function returns a named tuple, with one field for the frame size, and one for the area (1). We do this by matching on the Dims we got. The first three case (3, 4, 5) are exactly the edge cases we seen before: negative dimensions and row/column-only boards. The last case (6) is for a full size board. If you're unnerved by all the random numbers here, or by the fear of off-by-one errors. Fret not, we still have the reference solution to back us up with its test suite (adapted so as to call findPointAt for all points of the board). So I fearlessly trial-and-errored this bit of code until it worked out. Also, fair warning, we are going to have much scarier "indexology" coming up very soon.

We are almost done, now that we know where we are relative to the current frame, we need to implement getPointOnFrame to be able to convert the Frame.Within into a concrete point. But first, let's solve a slightly simpler problem.

Recall that we have the "inner board", and the frame we found is its outer frame. If we take the perspective of the inner board (similar to how recursion worked in the previous solution), we can implement the following: given an index that is located on the outer frame of a board, find the point that corresponds to it. Once we have that, we'll need to convert the index into a corresponding index on the inner board, get the point, and then shift it back to the full board.

Be warned, the following helper is not for the faint of heart:

def getPointOnFrameInner(index: Int, dims: Dims): Point = // 1
  dims match // 2
    case Dims(w, 1) => Point(index, 0) // 3
    case Dims(1, h) => Point(0, index) // 4
    case Dims(w, h) => // 5
      index match // 6
        case _ if index < w => Point(index, 0)
        case _ if index < w + h - 1 => Point(w - 1, index - w + 1)
        case _ if index < w + h + w - 2 => Point((w - 1) - (index - w - h + 2), h - 1)
        case _ => Point(0, (h - 1) - (index - w - h - w + 3))

Let's break it down:

• This is helper for getPointOnFrame, written from the perspective of the inner board (1)
• The arguments index and dims refer to the inner board, not necessarily the originals we got in findPointAt
• We match on dims, yet again, to suss out the edge cases (2)
• We don't need to worry about empty/negative boards here, as we only reach this code when the location was found, which cannot happen on an empty/negative board
• For single row/column boards (3, 4), the point is just the index itself (placed horizontally or vertically)
• For a full board (5), we match on the index³⁹ (6)
• Now comes the scary part, where we have to figure out the Point we are on based on the relative values of index, w, and h
• Each branch corresponds to one side of the frame, like we had in the original frame solution
• I won't even try to explain how I got these specific numeric values, suffice it to say that I still have nightmares

Never in a million years would I have gotten those values correct without a reference solution to keep me honest. The sheer number of back and forth off-by-one errors is more than I'm willing to admit. Unlike the other places before, one of the edge cases here was the surprisingly unintuitive 2x2 board. I had to play around with the values until the tests passed, and since we have property-based tests I'm fairly confident that I didn't miss any other weird edge cases.

How far we've come from the minimal, elegant, edge case free reference solution...

Anyways, implementing getPointOnFrame is now just a matter of shifting perspectives (pun intended) back and forth:

def getPointOnFrame(index: Int, frame: FrameData): Point =
  val innerIndex = index - frame.outerArea // 1

  val point = getPointOnFrameInner(innerIndex, frame.dims) // 2

  val shiftedPoint =
    point.shiftBy(dx = frame.shift, dy = frame.shift) // 3

  shiftedPoint // 4

To get the index as viewed from the inner board, we take the original index and subtract the outer area from it (1). This shifts the index to start from the top left corner of the inner board. We then call getPointOnFrameInner (2) with innerIndex and the dimensions of the inner board (coming from the FrameData). With the Point in hand, we must move it back to the full board's perspective. We do that by shifting the point (3) with the shift the frame is on. And this is what we return (4).

That wasn't that hard, was it? Was it?..

Since I wasted what feels like years of my life running the test suite on this solution till I got it right, I'm fairly certain we can say that having a reference solution was justified. We shall pause for a moment an appreciate the distance we made, starting from the lovely reference and the monster we have now. I wouldn't've made it this far without the experience and intuition that I gained from the previous correct solutions.

Are we done yet?

...And Then Make It Fast

Time to wow our interviewer⁴⁰.

It's true that our computational solution is asymptotically faster than the naive implementation with the reference. It's linear in max(w, h), while the reference is O(w * h). But when was any interviewer impressed with anything linear? Can we do better?

Turns out we can. Taking out our dusty CS books we notice that what we are doing here is searching: searching for a frame that matches a certain criteria. Not only that, but the things we are searching over are sorted: the group of indices in each frame are strictly monotonically increasing. This is almost a textbook case for a binary search. Who could've thunk that I'll ever be implementing binary search outside of school...

So instead of going from the 0 shift upwards, we can start from the middle, and go up or down depending on where our index is relative to the current frame. This requires only slight modifications to our computational solution.

For a binary search we need a lower and an upper bound. The lower bound is easy, that's just the 0 shift. But what is the upper one? Looking at the boards we have above we see that we only need to go to about the middle of the board. We'll use that as our upper bound.

Another thing we need to take care of is the Framing data type. When going from 0 upwards we only had two cases. Either the index was after the current frame or within it. But in a binary search we can go back and forth, so it might happen that index is before the current frame:

enum Framing:
    case Before // 1
    case After
    case Within(frame: FrameData)

We just added another simple case here (1).

The main loop for a binary search becomes the following:

def findPointAt(index: Int, dims: Dims): Option[Point] =
  val maxShift = (math.min(dims.w, dims.h) + 1) / 2 - 1  // 1

  var result = Option.empty[Point]
  var min = 0 // 2
  var max = maxShift // 3

  while result.isEmpty && min <= max do // 4
    val shift = min + (max - min) / 2 // 5

    getFraming(index = index, shift = shift, dims) match // 6
      case Framing.Before => max = shift - 1 // 7
      case Framing.After => min = shift + 1 // 8
      case Framing.Within(frame) => // 9
        val point = getPointOnFrame(index, frame)

        result = Some(point)
  end while

  result

This is still pretty similar to what we had before:

• We initialize the maxShift (2) to the middle of the board, as per usual, the right numbers were found by random trial-and-error backed by tests
• Two new variables are needed to keep track of the process:
  • The current lower bound (2) that starts at the 0 shift
  • The current upper bound (3) that starts at maxShift
• We are no longer checking that index is within the correct bounds, instead relying on the stopping condition of the loop (4)
• We stop the loop when either the result stopped being empty, or the lower bound went beyond the upper bound (meaning that the index is not on the board)
• Inside the loop we set the shift to be in the middle between min and max (5)
• With the current shift we can get the Framing for it (6), but now we deal with one of three outcomes:
  • The index is before the current frame (7), we have to go backwards, so max is brought down to the current shift
  • The index is after the current frame (8), we have to go forwards, so min is brought up to the current shift
  • We are within the frame, in which we proceed the same way as before (9)

To finish this, we need to adapt getFraming as well. We just add another branch to the conditional logic there:

if index < outerArea then Framing.Before // 1
else if index >= outerArea + innerFrame then Framing.After
else
  val frame = FrameData(outerArea, shift, innerDims)

    Framing.Within(frame)

The Frame.Before case is produced when the index is in the "outer board" part (1). The rest remains the same.

Finally! We are done. This solution is logarithmic in max(w, h), way better than what we had before⁴¹. Both our clients and our interviewer will be thrilled by the snappy latency that the Spiral API™ can now provide.

Conclusion

Woah, that was quite a journey!

We started out by laying down a solid foundation with an (obviously) correct solution, backed by a property-based test suite. From there we used the initial correct solution both as reference to test against, and as an inspiration to help us think about the problem we are solving.

Guided by various requirements and improvements, we were able to both mechanically adapt the solution, and to use it as a guide and safeguard for more creative approaches. Yielding a diverse collection of solutions:

1. A simple recursive solution, closely following the problem statement
2. A tail recursive solution, to avoid stack overflows; by a mechanical transformation of the original correct solution
3. An iterative solution, to accommodate languages that don't support tail-call elimination; by mechanical transformation
4. A lazy solution, to avoid blowing out the memory; by using the original solution to inspire an interface to code to
5. A lazy frame by frame solution, to avoid the pain of dealing with rotations; by following the pain and using an existing solution for visualization
6. A computational solution, to avoid unnecessary computation when adapting to new requirements; by heavily relying on the reference property-based test suite to weed out edge cases
7. An even faster solution, just because we can and because we wanted to impress the hypothetical interviewer; by throwing a CS book at an existing solution

Starting out with a correct solution gave us clarity of thought about the problem, and a tangible way to test any other solutions that we can come up with. Property-based testing allowed us to maintain confidence even as we tried more and more daring approaches. Without the initial correct solution, none of this would be possible.

And so we circle back to my original statement:

First make it correct, then make it anything you want.

Did I mention that I hate leetcode problems?

---

If you enjoyed this, reach out for a workshop on Functional Programming, where I teach how to apply Functional Programming to improve code quality in any language.

---

1. I would like to consult with my attorney first.↩
2. I.e., not too difficult.↩
3. I've spent way too much time writing the code for this "visualization"...↩
4. Or don't, I don't really care.↩
5. Is he still considered a friend after that?↩
6. The code for this post is available on GitHub.↩
7. In case you get the directions wrong, which I obviously did on my first attempt.↩
8. If you can come up with an even more obviously correct solution, please reach out and let me know.↩
9. In theory we can make it unbounded, but for the tests not to take too long, the specific generator I defined creates dimensions with a linear size of up to 30.↩
10. Kind of like solving differential equations. The unit test is like the initial condition, and the properties are like the smooth function that acts as a solution.↩
11. But we will still continue to use the sanity properties that we defined above, as they will be easier to use as debugging tools in case a candidate solution has a bug.↩
12. Of course the specific numbers depend on the JVM parameters that we use. We could reduce the size of the stack on purpose and get a stack overflow first.↩
13. I leave it as an exercise to my dear readers to figure out how to test for these flaws.↩
14. The ==== operator stands for "very much indeed equals". I guess the other = variants were already taken...↩
15. In this post I'm using the Hedgehog library which does a good job at automatically maintaining shrinking even for custom types. If you're using something like ScalaCheck, you might need some extra code to achieve the same thing.↩
16. What we are experiencing here is basically the difference between a foldRigt and a foldLeft. As illustrated here.↩
17. Java, anyone?↩
18. We could still use pattern matching, but then we'll have to somehow ignore the empty case, as it is already handled by the loop condition. Probably leading to some other form of unsafe code.↩
19. For the life of me, I couldn't write a property that catches infinite loops...↩
20. The other is being greedy.↩
21. With a nod to Steve Yegge↩
22. You could use proper streams for what I'm about to do, the resulting code will be very similar.↩
23. For better or for worse.↩
24. If we really wanted to preserve the pattern matching syntax from List we could define a custom extractor to achieve this goal.↩
25. In the spirit of "make illegal states unrepresentable" we could come up with a more precise representation that won't allow us to express more than 4 rotations. Or at least make the constructor private to prevent the possibility of invalid values. For this small example it's probably not worth it.↩
26. This is an annoying case of overloading. The Point type represents two different things: absolute points and relative deltas (shifts). We could resolve this by introducing a dedicated type for each use case, but the margin of this page is too small... There's some useful mathematics underlying this concept.↩
27. Guess who had some off by one errors here...↩
28. Having obtained this solution we can improve on it. E.g., the interface we came up with is more flexible than actually required. We don't need separate otherRows and rotateCCW methods, we always use them together. By combining them into one we can skip some intermediate steps in the solution.↩
29. Unless it is...↩
30. As an aside, why didn't we get to this solution in the original reference solution? One reason would be that the representation of the board that we used (a nested list of lists) is naturally suited for removing single rows (due to the way pattern matching on lists works), while removing a frame would require some coding effort. This is an example of "function follows form". Choose your forms wisely...↩
31. To see the output below I'm using the -b flag passed to the test runner, to avoid buffering output.↩
32. If you run the tests yourselves you might get different outputs, since minimization doesn't always reach the same cases.↩
33. But not all of it, since the generators are still probabilistic.↩
34. A "fun" riddle for the bored: suppose the board condition in buildCoordinateFrom was (wrongly) set to dims.area <= 0. What will happen? Will the test suite pass or fail? Why?↩
35. Who said that leetcode problems are not realistic enough to reflect the demands of a real job?↩
36. And if you come up with such a solution, please reach out and let me know.↩
37. Okay, so I haven't completly let go of functional pretense. And you could solve this without a custom datatype, but it will be more elegant this way. Goes to show that you can mix the procedural and declarative approaches.↩
38. We could skip this and just assume that the index input is valid, just like we do with dims. But I wanted this code to be compatible with the reference solution including the lift bit, which handles out-of-bound indices. I also coded up this condition as a property-test that you can see in the test suite for this solution.↩
39. I'm using pattern matching as a cheap substitute for a multiway-if, which is something I usually avoid. Here it will get too clumsy if do it with regular if/else expressions.↩
40. Assuming said interviewer is still with us after all this time.↩
41. If you really want to take advantage of this speed up, you should probably stop using Ints though... Also see the riddle from above.↩