I was going to move back into the dungeon today, but realized I wanted to talk about what I learned doing the ominoes exercise. Here goes …

Warning: I’ve done my best here to figure out how I do what I do. I wasn’t entirely successful. I hope I wasn’t entirely unsuccessful. Let me know …

I was at first resisting playing with the polyominoes, even though 60 percent of the Zoom Ensemble people were doing so. I’m not sure why I was resisting. Partly I’m having fun with the Dungeon, and partly with those wizards working on it, what could I possibly have to offer? How could I do other than embarrass myself?

Then I realized that my hobby seems to be writing an article every day in which I embarrass myself, and I am perhaps the best person in the world at doing that. So my excuse was weak.

But then I listened to what one of the other ZE members was saying, and looking at the code they were writing, and it just didn’t seem right to me. My intuition about the problem was saying that their solution was somehow not fitting the problem. I had had the same feeling with some other code. So I wanted to do the ominoes to see whether my intuition would hold up.

TL;DR: It did.

Here I’m going to talk about what I was thinking, and what I think I’m doing.

Now what we do in TDD is to start with some simple easy-to-pass test, make it work, repeat until somehow, magically, the whole solution emerges. But it isn’t quite that easy, is it?

Let me give a trivial example. Suppose we were told to write a program that, given a number in, produces the square of the number. And, suppose we didn’t know what “square” meant, and were afraid to ask. We figure we can TDD it, so we have them give us some examples.

  1. 1 squared is 1
  2. 2 squared is 4
  3. 3 squared is 9
  4. 9 squared is 81

We TDD this program. And because we don’t know what square means, we’ll never get it right. In this case, we won’t even get close.

When we TDD, at our best, we’re not just picking off cases that don’t work, we are test-driving the program. We are driving it, pushing it, toward an ideal shape for solving whatever the problem is. We do the red-green-refactor cycle in a fashion that moves our starting program closer and closer, not just to a program that does the thing, but to an ideal program that does the thing.

What does “ideal” mean? Well, at its simplest, I guess it means that the program runs all the tests, expresses all our ideas, includes no duplication, and minimizes the number of programming entities. Kent Beck’s four rules of simple design.

There are surely other notions of “ideal”, and the better we understand the “idea of ideal”, the better our programs will become. Well, they will if we do the work to get there.

One of the notions of “ideal” has to do with what in mathematics they call “elegance”. Elegance, like so many things, is in the eye of the beholder, and in a math class, to get that “A” you need to suss out what the instructor’s notion of elegance is, and match your proofs to that notion.

The same is true in programming, and my notion of elegance won’t line up exactly with that of some other programmer. One example for me is Ward Cunningham, who has often been able to take code that I’ve written and do it in a more elegant fashion than I have done … and I can see that it is more elegant.

He’s better at my idea of elegance than I am. Which tells us, if nothing else, that we can always do better. The trick, of course, is that we need to know when to stop, because we could keep polishing the code forever. What we need to do is to learn to get to “good enough” more and more quickly, because that lets us get to better and better values of “good enough” within a reasonable amount of time.

And that brings me to the polyominoes.

Polyominoes

Long ago, there was a puzzle game called “Pentominoes”. You got a box of shapes made from 5 squares, and a book of patterns, and the game was to arrange the shapes to fill in the pattern.

I believe I first encountered them in 1957 in Martin Gardner’s Mathematical Games column in Scientific American, and I recall having a set of plastic ones when I was around that age. I don’t recall everything I learned about them at that time.

And I have at least two degrees in mathematics. So I am historically familiar with the notions of transformations, groups, and all that stuff. So I am familiar with the notions of translation, rotation, and flipping that allow us to say whether the L-shaped one is the same as the L-shaped one. Again, that was a long time ago, and I don’t recall everything about it.

So, when I look at polyominoes, I immediately look for patterns, similarities, regularities, invariants.

When programming–yes, I have a degree in that as well, though I didn’t learn much of use–I am always looking for patterns, similarities, regularities, invariants.

And these habits, long grooved into my brain, lead me quite often to look at a problem and its solution and to think “There has to be a simpler way to do this”.

Relation to “Technical Debt”

There’s a connection here to Ward’s notion of “technical debt”. If I understood him correctly, Ward intended the term to refer to the difference between the solution we have right now, and the solution we now understand that we could have. The one we now wish we had written.

In general, that more ideal solution is smaller than the one we have in hand, because we now see regularities, similarities, duplication, that can be exploited to make the code smaller.

Relation to “Generality”

There are two ways to make a program “more general”. One way is to put more cases into it. It used to handle positive numbers. We put in code to handle negative numbers. This makes the program more general, at a cost in size and complexity.

The other way is to fold the new cases into the old. We find a place where the code is overly constrained, and we relax the constraint, which allows negative numbers to flow right through, getting the correct answer. The program is more general … and smaller and simpler.

TDD and the Refactoring Step

In TDD, we repeatedly add cases to our tests, make the code pass the tests. And then refactor.

What are we supposed to be doing in the refactoring step? We’re supposed to be folding the new cases into the old ones. We’re supposed to be finding the commonalities, and merging them. We’re supposed to be finding the four special cases and turning them into two more general ones … and then into on even more general one. In so doing, we cut that part of the code in half, and in half again.

The program gets smaller … or it becomes more capable without getting bigger … or without getting very much bigger.

What About the Damn Ominoes???

Well, in the solution that was bugging me, I just kept thinking “it has to be simpler than that”. It seemed there was a case, and another case, and another case and another and another.

So I wanted to see if it could be as simple as I felt it could, or at least simpler than it was.

I think my example is just about as simple as I expected, mixing in the limited object structures of Lua.

How did you do it?

Well, I tried to write down my process in the first article, but here I’m going to try to talk about what was underneath that process. I’ll quote or reiterate some of the reasoning from the first article here, and perhaps elaborate.

I started by just refreshing my mind with a clear statement of what a polyomino is:

An omino of order N has N squares in it. They are adjacent edge to edge. (Not just diagonally.) So a 1-omino has 1 square, the 2-omino or domino has 2, and so on.

I went on to make it clear that I wasn’t planning to reduce down to the “free” form, where the backwards L is the same as the forwards L, but to the “fixed” form, where if the one is rotated 90 degrees from the other, we consider them different.

I had two reasons for that choice. My top-level one was a rationalization, really: those are the ones we’ll want for the larger “gerrymandering” problem anyway. But my real reason, I put second:

I think it’s probably easier to generate the fixed ones than the free ones, because we’d have to check the fixed ones to see if they matched, to get the free ones.

Imagine for a moment that our problem was to produce the “free” ones, where the two rotated ones had to be collapsed together and the two flipped Ls had to be collapsed together.

That problem could be reduced to two parts:

  1. Produce any omino of the right order;
  2. Check to see whether we have it, or any flipped or rotated version of it.

Even stating the problem that way makes it clear that #2 is probably difficult.

I was able to skip that part entirely. At this writing, I’m not quite sure how I’d solve it. Probably I’d solve it by writing code that produced all the flips and turns of any omino.

Reduction is Important

Reducing the problem to two smaller problems is important. It’s especially important if you can skip one of the problems entirely, as I did two days ago.

This is exactly analogous to splitting stories in an Agile method. We split stories down as far as we can, so that each story is as simple as we can make it, and so that we can then build the whole big story back up from the pieces.

When we do that, we provide ourselves with a stream of easy things to do. That’s our best hope, because on a given day, we can’t do the hardest thing that might turn up that day, but we can probably do some of the easy things.

Reassembly is Important

But the micro-stories have to add up to the big story … and the code that makes the micro-stories work has to come together into a simple program, not just pasting all the simple stories code together. We don’t want to solve squaring numbers with a huge list of numbers and their squares. We want to find the commonality, the simple generalization that makes the answer easy.

If we were to look at this table a while:

Input Output
1 1
2 4
3 9
9 81

We’re supposed to figure out that

Output = Input*Input

When we do, our big case-by-case square program suddenly gets smaller.

So i looking at the ominos, I needed to figure stuff out.

The rules tell us that a new Nth order omino is made by pasting a square onto the side of an existing square in the omino. And, they don’t say it, but it’s pretty clear that if you choose an “internal” side, so that your new square is flat on top of an existing square, that’s a no-go.

Now with an order 1 omino, there is just one square, and it has four sides, and we can paste a square on there and get a new 2-omino, often called a domino. And if we’re ignoring rotations (and we are), we see that there are four ways to past, but just two shapes we consider different, a vertical one and a horizontal one.

We also see, right away, that given the domino, there are two edges that aren’t going to work: the two that are connected.

And there are two ways to deal with this concern.

One is to look at the edges of all the squares in an omino, and see if they match another edge in the omino, and if they don’t match, try putting a square there. If we do that for all the edges of all the squares, we’ll generate all the next order ominos and never try to create a dud.

The other way is to add a square to every edge of every square, and ask whether the resulting thing is of the next order. If it is, keep it. If it isn’t, move along, nothing to see here.

Which of these ways is best? I don’t know. I chose the second way, and I think I know why. It seemed to me that it was easy to find the order of an omino: count the (unique) squares in it. It seemed to me that finding an edge, and deciding whether it was internal, was not easy. In fact, as I write this, I really don’t know how I might do that.

And, if I even considered the first way, eliminating edges to try, I considered it so briefly that I don’t remember it even entering my mind.

Now … I can’t tell you how to have a mind that so quickly considers two alternatives that you can’t later remember even thinking about one of them. But I do have a suggestion for choosing ways to do things:

  1. Think of more than one way of doing the thing;
  2. If you can’t think of any, don’t do it;
  3. If you can only think of one, do that one;
  4. Consider each way briefly, how might you do it, what additional problems might arise;
  5. If a way seems more complicated than the others, drop it from consideration;
  6. Repeat until you know the simplest idea that could work;
  7. Try that.

As Kent Beck used to ask all the time:

What is the simplest thing that could possibly work?

And, as I, in my naïveté, used to say:

Do the simplest thing that could possibly work.

So my first choice was this:

Create the next size of omino by putting a square adjacent to every edge of every square in the omino, and keeping the result if it is of the next size (order).

I then went forward with some bad ideas, like representing squares with vec2 and such. I quickly discovered that that didn’t help, and instead wrote a “square” class, which I called Sq. It had an x and y, and a key, 10000x+6so that I could store it in a Lua table and quickly find out whether I already had that square.

That was a programmery thing to think about: in Lua, tables can act like arrays, in which case you have to search them to see if something is in there, or they can act like hashmaps, in which case you can just try to fetch by the thing’s key and see if you get it.

I went down a few weak paths as I programmed, but quickly came to the notion of the square (Sq) and the Omino class, which is a collection of Sq, indexed by the key of the Sq.

I tested and wrote a generate function that, given an Omino, returned its “children”, all the ominos of the next order. I used “fake it till you make it” on that method, to pass its test. I never improved that method, nor did I remove it. I’ll remove it and its test right now, since I’m thinking about it.

Commit: remove unused generate.

Writing that test and code, however, drove me to create the Sq object, and to implement the __eq method on it, so that the generate test would run. I also needed an __eq has method on Omino, to check for a square. After that, the test ran.

As we moved forward, that test because redundant, so slowly that I didn’t notice until yesterday. It had caused some important methods to be written, and those methods remained useful even though the actual test was still just “fake it till you make it” … because I didn’t really want “generate” any more.

According to the first Poly article, I was a bit confused at this point. I had expected not to have to drill down to such basic matters as whether two squares were equal or whether an omino had a given square.

I wasn’t necessarily wrong to be surprised. GeePaw Hill did his version in Kotlin and I gather that Kotlin has better collections and such than Lua, so he just made a set of this and a set of that and things dropped out.

After a short break, I noticed a improvement to my test for Omino:has, which was searching the Omino for an equal square and could instead just look at the hash table. So that simplified the code a bit, which reduced the load on my brain.

I then diverted again, to get the program under Working Copy, I was pretty sure by then that having some save points would come in handy.

Now I had an __eq method for an Omino, which was “has the same number of squares, and for each square in one, that square is in the other”. However, that wasn’t quite what I needed, yet, because I was planning to create dominoes by putting a square on each edge of my starting Omino, so I’d start with

( (0,0) )

Then, among the four, I’d generate these two candidates:

( (-1,0), (0,0) )
( (0,0), (1,0) )

And because those are both horizontal, I wanted them to be equal.

This means that I have to “normalize” the Omino. I have to put it into “standard form”.

Why does it mean that? I’m not sure. Somewhere in my math and CS background, I learned that in geometric things like this, you want to “normalize” the things that are supposed to be equal. You put them into a “standard form”.

And here I stole an idea from Hill, because I remembered him saying something that sounded to me like sliding the omino toward the axes, so that it has a zero x and a zero y somewhere in it.

But despite the fact that I only got around to it when I was this far along, the original article makes clear that I had it as a design idea at the very beginning. Partly, I’m sure, because we had spoken of it the preceding Friday, and partly because that’s how one “always” does this kind of thing.

So I had a reminder … and a built-in pattern of design, both leading to a rule something like:

When things that should be equal don’t seem equal, consider putting them into a standard form so that they do seem equal.

If I didn’t have that pattern, I’m not even sure how I could compare two ominoes for equality, since they could slide all over.

What would I do if I couldn’t see how to normalize them? I think I would try to ensure that when I generated them I only generated ones that would compare equal when I wanted them to. I honestly don’t know. I think you have to slide them down when you put something on top, slide them right when you put something to the right.

Instead, I just build them any old way and told them to normalize afterward. Simpler.

Then I ran into a problem between Working Copy and Codea. When your tools aren’t working, it’s very distracting and can take the steam out of your sails1. Anyway, I paused, created a bug report, sent it to the authors of Codea and Working Copy, and got back to work.

I found some dumb mistakes, perhaps because the Yak distracted me, and I tolerated a horrid solution for a while. The horrid solution was that I was changing an omino’s square in place, and thus removing it at its old key and adding it back with the new key.

But I went back and fixed that.

Why? Because a square feels to me like a “value object”, that is, an object that, once created, never changes its value. Yet we adjust them all the time, when we normalize. We move the Sq(1,1) over to the left, to (0,1). I changed my adjusted method just to return a new Omino instead of a modified old one.

Another Pattern

Objects that change value are necessary, but they are harder to reason about. When we can, we often find that we do better with value objects, objects that never change, and to create new ones rather than modify the old ones.

That pattern is called Value Object.

What Is He Doing?

As I go along, I’m not just writing a test and making it work. I’m looking at what I’ve written, and assessing it against some kind of internal list of quality measures. When what I have deviates from “good”, one of those list elements fires, and I go “Oh!” and change course to make things better.

Except that I don’t have a list like that, that I’m aware of2:.

I really don’t. I couldn’t tell you what SOLID stands for, or INVEST, or AVAST, or any of those things. My mind just doesn’t work by memorizing a lot of stuff and working through checklists. Somehow, I just let myself become aware of a difference between this thing and that thing and I think things like:

  • It ought to be simpler than this.
  • Aren’t these somehow the same?
  • This code looks a lot like that code.
  • Wow, changing that thing’s value broke stuff!

And perhaps most important:

  • Damn this is hard. I must be on the wrong track.

I’m terrible and just grinding things out. I admire people, like my wife, or my sainted mother, who just get down to it and do what has to be done. I’m one of those people who will spend a day thinking of an easy way to do a thing that would take an hour. I’m one of those people who, when the going gets tough, gets someone else to do it.

I’m serious. My skills are very intuitive, very integrated into my thinking. And I’m really sensitive to things being more complicated than they could be.

Anyway

After shaving the Working Copy / Codea Yak fight, I looked at my OminoCollection object, which was behaving like a set, so I called it OminoSet.

This is a Pattern Too

“Set” is a pattern. A “set” is a collection that can contain at most one copy of any of its elements3. You could have an array like this:

{ "Hello", "World", "Hello" }

But a set can’t be like that. It can only contain one of each:

{ "World", "Hello" }

Since I wanted my collection of ominos to contain all the ominos of a given order but each one only once, the thing was a Set, not just a Collection.

I moved forward. Given an omino, I created all the possible ominoes of the next order, by just adding a square at each edge of each existing square. Since my Omino class’s collection of square eliminated duplicate squares (a Set), this meant that adding redundant squares resulted in an omino of the same order. (It would also be equal to itself, of course.)

Given a new Omino of the higher order, my OminoSet accepted all the new ones, and condensed them down, by checking them for equality to one the set already had:

function OminoSet:add(omino)
    if not self:has(omino) then
        table.insert(self.coll, omino)
    end
end

function OminoSet:has(omino)
    for i,om in ipairs(self.coll) do
        if om == omino then return true end
    end
    return false
end

The “Result”

The result, for me, was that I got what I had expected to get, a program for generating all the order n ominoes, without there being any special cases in it. It treats creating a domino from a monomino exactly the same as creating an octomino from a heptonomo. And the program strikes me as “good enough”, although I’m sure one of my many betters could improve it, or produce a simpler one.

I might even try to improve it, maybe tomorrow, but today, I’m trying, as best I can, to explore why I got a program that, for me, is “better” than the one from the Zoom Ensemble that bothered me.

It started from “too many notes”4, a general feeling that there was too much going on. Too many decisions, too many cases. Too much stuff. And I didn’t even get this from reading the other code. I got it from listening to the code’s author talking about the code.

Then, as I built my version, I applied formal and informal design patterns, pulling them from my general bag of tricks. I didn’t use a canned “checklist” of good ideas, or bad things to look for. I just listened to my code, and applied the ideas that came to me.

It wasn’t even a particularly beautiful path to a working program. There were false starts and mistakes. But it has turned out to be “good enough” to satisfy my belief that there was a simpler way, at least a way that is simpler to me.

If another programmer were to like what they saw here, how might they work so as to get to similar results? I’d like to have better advice than “be smarter”. I wish I had better advice than I have.

As I write future articles and make decisions, I’ll see if I can draw more general lessons from the specific. For how, here are some of the ideas that I’d offer if some poor devil were to say “OK, I like what you did there, how might I learn to do that?”

Read and Study
To the extent that you can, read and study programming topics. Patterns, the idioms of the languages you use and those you don’t. Learn how data structures work. Learn patterns like “Value Object”. Try to find a use for “Flyweight”.

Do what you can here. A little learning is better than none, and we all have better things to do with our lives than read programming books and articles. At least I hope we do. But reading and study do help.

Attend to Duplication
Practice spotting patches of code that “look alike”. Sometimes they’ll be obvious, like these six times we search through a table looking for an object. There’s an idea waiting for us there, even if it’s just “find in table”.

Sometimes duplication is less obvious. The same thing might be done two different ways. Consider picking just one way. Two objects might have similar code inside. Are they both wishing for the same kind of helper object?

Attend to Mess
If the code to do something is intricate, the odds are that there’s something wrong with it. Maybe it’s too clever. Maybe it’s not clever enough.
Attend to Value Objects
Are there things that never change? Are there things that change but needn’t? Code with value objects–objects that never change value–is often simpler than otherwise.
Attend to Invariants
Is there something the same about all the cases in what we’re working on? Make the code the same. In the polyominoes, extending from any order to the next order is always exactly the same. In extending a given omino into a larger omino, the code is exactly the same no matter if it’s order one or order ninety-one.
Attend to Math and Science
This goes back to the reading and study topic, but even when the application doesn’t seem to involve math or science, often there is an idea from those disciplines that will give us an assist.
Refactor toward Simplicity
Let’s not forget the refactor step in red-green-refactor. Especially when we add a new case with new code, let’s be sure to look and see whether there isn’t something now that can be folded together.

All this advice may not be much better than “Be smarter”, but at this moment, it’s the best I can do. Probably the best advice I can give is

Even when in the tight loop of TDD, never fail to pause and think about whether this is going better or worse than last time around.

Oh, and

If you’re feeling tension in your neck and shoulders, something is going wrong!


Poly.zip


  1. What?

  2. We at the FBI do not have a sense of humor we’re aware of. – Kay

  3. Formally speaking, it’s not quite that simple. Some folks distinguish a “bag” {a,b,c,b,c} from a “set” {a,b,c}. That way lies trouble. Fortunately as programmers, we’re happy with “contains at most one copy”.

  4. Too many notes, dear Mozart, too many notes.” – Emperor Joseph II, supposedly.