Polyominos FTW. Or, WTF.

The Zoom Ensemble folks have been playing with polyominoes. I can’t resist embarrassing myself by trying them.

It all started, Doctor, when GeePaw Hill got interested in a little gerrymandering problem that happened to use 5x5 polyominoes. For those who aren’t aware of this weird term, “polyomino” is a generalization of the word “domino”, those little black rectangle things with the white dots. Or sometimes white things with black dots. And I suppose they come in other colors as well. The “do” part of that word may or may not come from the root for two, as in “dos” and “duo” and so on. Be that as it may, mathematicians and other oddballs like us have generalized the term. There are tromino, guadromino, pentomino … all the way up to poly, which I think is probably the Greek word for “too damn many to actually count right now”.

The gerrymandering game challenges the player to arrange five pentomino tiles so as to give the party with the fewer actual voters a majority of the districts.

Hill started us off with a tweet and Bill Wake has a series of articles going. You should read those. I haven’t read Bill’s articles yet, as I’ trying to keep my brain as empty as possible, but from the conversations we’ve had on the zoom, I’m sure he has some interesting stuff for you.

I have been resisting working on this, because with three of the ensemble members working on this (Bryan is at it as well), I felt sure that I’d embarrass myself.

I’ve decided to embarrass myself. Here goes.

Generating All the Ominoes

The problem I’m going to work on here is to produce a nice little program, in Codea Lua of course, to create all the ominoes (we call them ominoes or even ominos, for short) up to some desired order.

To the extent that the program turns out “nice”, and “little”, I’ll consider it a success. To the extent that it doesn’t turn out nice and little, no so much of a success.

What do I mean by “nice”? I believe that the whole problem is essentially recursive. To get the order N+1 ominos, extend the order N ones. I think there should be no special cases, no real consideration of whether a square is or is not in the omino already, no checking to see which way one has to move to put down a new square, and so on.

I will, for my sins, TDD this program. And we do have some information that’ll be useful, which is the number of these babies that exist for all the orders up to 12. (The values are known much further than that, but the wikipedia article is right here on my screen.)

OK, let’s “design” a bit.

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.

There are two ways of looking at ominoes that we’ll think about. In the trade they are “free”, and “fixed”. “Free” means that two ominos are distinct when no flipping or rotation can make them identical. There is only one “free” domino, because the vertical one can be rotated to make the horizontal one.

“Fixed” ominos are distinct when they can’t be made equal by laying on on top of the other, without rotating or flipping. There are only two free trominoes, but six fixed ones:

The two three-in a row ones, one horizontal, one vertical. The four L-shaped ones, one for each rotation.

Anyway, I have the number of free and fixed ones to use in my tests should I choose to do that.

We are interested in the fixed ones, because they’d be easier to use in the gerrymandering problem, and because 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.

What’s the Plan?

My plan is to generate them recursively. It’s trivial to generate the monomino, we’ll return it as a constant, the root of our recursion.

We’ll generate the ominoes of order N by taking all the ones of order N-1 and placing an additional square along each edge of each of the existing squares. If we still have only N-1 squares, that placement was on top of an existing square, so we will toss it out. (Think of placing a square along the shared edge of a domino. No new square, pitch it.)

If we get N squares, we have an N-omino. We may have already generated that shape, however, so in our output collection, we’ll need to drop any incoming ominos that exactly match one that we already have.

The “big” questions include:

How will we represent these ominos?
How will we check them for “equality”?

There are smaller questions as well.

Here’s my starting idea:

Represent an omino by a table of pairs (vec2?) consisting of integer coordinates.

The horizontal domino could be { vec2(0,0), vec2(1,0) }. Or it could be { vec2(100,31), vec2(99,31) }

A tromino would have three vectors, and so on.

My example above already begins to show the issue of equality. Those two ominos are “equal” as far as ominos go. What, exactly, do we mean by equal, and how can we represent it.

The way one often thinks of things like this is to “normalize” the data. We want to reduce it to a standard form that makes all the like things the same.

We normalize angles all the time. We’re given 370 degrees, we subtract 360 to get 10. (Of course we probably actually use the mod function, but who’s counting?)

Now, unfortunately, I think I understood what Hill was talking about when he told us about his program, so having heard an idea, I will take it as my own. Geometrically, the idea is:

Take your omino and slide it to the left and down until it is as close to the axes as possible. (Use left and up, if you happen to have zero at the top of the screen like some kind of barbarian.)

Let’s start with that. I’ll make a new Codea project, called, naturally enough, Poly. (I considered Polly and then Parrot, but I decided that it could only confuse me later.)

The Hookup

-- RJ 20210504
-- Omino tests

function testOminos()
    CodeaUnit.detailed = true

    _:describe("Ominos", function()

        _:before(function()
        end)

        _:after(function()
        end)

        _:test("HOOKUP", function()
            _:expect("Foo", "testing fooness").is("Foo")
        end)

    end)
end

Yay, the tests are green, ship it.

I think I’ll work toward an omino class that knows its order. And I think I’ll code it in a natural sort of Lua fashion, without any regard for efficiency.

Let me see about sketching a smallish test:

        _:test("Order 2", function()
            local om = Omino()
            om:add(vec2(0,0))
            _:expect(om:order()).is(1)
            om:add(vec2(0,0))
            _:expect(om:order()).is(1)
            om:add(vec2(1,0))
            _:expect(om:order()).is(2)
        end)

Here I add an element to an empty omino and find it to be of order one. Add same element, still order one. Add new element, get order 2.

Naively, I wrote this:

Omino = class()

function Omino:init()
    self.squares = {}
end

function Omino:add(square)
    self.squares[square] = 1
end

function Omino:order()
    local o = 0
    for square,one in pairs(self.squares) do
        o = o + 1
    end
    return o
end

It doesn’t work. Why? Because vec2(0,0) doesn’t hash to the same place as another vec2(0,0). Why? Lua uses the identity of a table as a table’s hash. So we need to be slightly more clever:

function Omino:add(square)
    local key = square.x*10000 + square.y
    self.squares[key] = 1
end

This will hold us until we get to order 10000 ominos, i.e. forever.

Do we need Omino:equals? Not yet. We’re already speculating.

Now we might imagine a method to check whether an omino is “legal”, since right now we could give it 1,1 and 100,100 and it would think it was order 2, but in fact it wouldn’t represent a legal omino. But in fact, I’m not going to do that. What I’m going to do, instead, is never generate an illegal omino. Of, of course, I’m going to mess up.

But Omino instances, for now, will assume they are legal.

Let’s see about generating new ominos from old. I think I can test that.

Well, maybe I can test it. My plan is to start from a monomino at 0,0, and tell it to generate. I should get back a collection (probably an array) of Omino instances, and there should only be two of them, one going 0,0, 1,0 and the other going 0,0, 0,1.I guess I’ll just express that and see if I can make it work.

        _:test("Get order 2 from 1", function()
            local om1 = Omino()
            om1:add(vec2(0,0)) 
            local order2 = om1:generate()
            _:expect(#order2).is(2)
            local om2 = Omino()
            om2:add(vec2(0,0))
            om2:add(vec2(1,0))
            _:expect(order2).has(om2)
        end)

There are a lot of assumptions in here, including that Omino knows how to test for equality. Let’s run this test and maybe force the answer (fake it till you make it).

3: Get order 2 from 1 -- Tests:32: attempt to call a nil value (method 'generate')

function Omino:generate()
    -- assume order 1 and fake result
    local kids = {}
    local om1 = Omino()
    om1:add(vec2(0,0))
    om1:add(vec2(1,0))
    table.insert(kids,om1)
    local om2 = Omino()
    om2:add(vec2(0,0))
    om2:add(vec2(0,1))
    table.insert(kids,om1)
    return kids
end

This should generate what I want the order 2 set to look like. Now the test will, I presume, not pass yet.

3: Get order 2 from 1  -- Actual: table: 0x282ec5c00, Expected: table: 0x282ec4900

This is one of those handy error messages from CodeaUnit. It is, of course telling me that some vectors are not equal.

I think I can’t live with using vec2. I need somewhere to stand. So I’m going to build a Square class.

Sq = class()

function Sq:init(x,y)
    self.x = x
    self.y = y
    self.key = x*10000 + y
end

Plug it into the test and code:

-- RJ 20210504
-- Omino tests

function testOminos()
    CodeaUnit.detailed = true

    _:describe("Ominos", function()

        _:before(function()
        end)

        _:after(function()
        end)

        _:test("HOOKUP", function()
            _:expect("Foo", "testing fooness").is("Foo")
        end)
        
        _:test("Order 2", function()
            local om = Omino()
            om:add(Sq(0,0))
            _:expect(om:order()).is(1)
            om:add(Sq(0,0))
            _:expect(om:order()).is(1)
            om:add(Sq(1,0))
            _:expect(om:order()).is(2)
        end)
        
        _:test("Get order 2 from 1", function()
            local om1 = Omino()
            om1:add(Sq(0,0))
            local order2 = om1:generate()
            _:expect(#order2).is(2)
            local om2 = Omino()
            om2:add(Sq(0,0))
            om2:add(Sq(1,0))
            _:expect(order2).has(om2)
        end)

    end)
end

Sq = class()

function Sq:init(x,y)
    self.x = x
    self.y = y
    self.key = x*10000 + y
end

Omino = class()

function Omino:init()
    self.squares = {}
end

function Omino:add(square)
    local key = square.x*10000 + square.y
    self.squares[key] = 1
end

function Omino:generate()
    -- assume order 1 and fake result
    local kids = {}
    local om1 = Omino()
    om1:add(Sq(0,0))
    om1:add(Sq(1,0))
    table.insert(kids,om1)
    local om2 = Omino()
    om2:add(Sq(0,0))
    om2:add(Sq(0,1))
    table.insert(kids,om1)
    return kids
end

function Omino:order()
    local o = 0
    for square,one in pairs(self.squares) do
        o = o + 1
    end
    return o
end

Test still fails the same way but now:

        _:test("Square equality", function()
            local sq1 = Sq(0,0)
            local sq2 = Sq(0,0)
            local sq3 = Sq(1,0)
            _:expect(sq1, "1:1").is(sq1)
            _:expect(sq2, "2:1").is(sq1)
            _:expect(sq3, "3:1").isnt(sq1)
        end)

And with this:

function Sq:__eq(square)
    return self.key == square.key
end

The equality test runs. But the other test isn’t quite on.

4: Get order 2 from 1  -- Actual: table: 0x282ed3940, Expected: table: 0x282ed3ac0

That’s the second check in this test:

        _:test("Get order 2 from 1", function()
            local om1 = Omino()
            om1:add(Sq(0,0))
            local order2 = om1:generate()
            _:expect(#order2).is(2)
            local om2 = Omino()
            om2:add(Sq(0,0))
            om2:add(Sq(1,0))
            _:expect(order2).has(om2)
        end)

It may be that ‘has’ isn’t serving me. Let’s print the table just to see.

            local order2 = om1:generate()
            _:expect(#order2).is(2)
            for i,s in ipairs(order2) do
                print(i,s)
            end

It’s printing tables, not squares, and I have a tostring method on square. Did I mess up generate? I bet I did.

Oh sure, there are Ominos in there, not squares. I need to implement Omino:__eq. Yucch. But OK.

I’m not going to write an extra test for that. The original failing test requires it and when it works the test will run.

function Omino:eq(omino)
    if self:order() ~= omino:order() then return false end
    for sq,one in pairs(self.squares) do
        if not omino:has(sq) then
            return false
        end
    end
    return true
end

function Omino:has(square)
    for sq,one in pairs(self.squares) do
        if sq == square then return true end
    end
    return false
end

This is a bit more intricate than I had been thinking, but I’ll continue.

After a short delay, I’m still struggling a bit with these basics. Bodes ill for my plan to just whip this thing out in a couple of articles.

Reboot iPad and Mind

I couldn’t get Breakfast with the Beatles to play through my Homepod, so I rebooted my iPad and went to find a granola bar. Upon my return, I implemented __eq instead of eq on Omino. The tests and code now run:

-- RJ 20210504
-- Omino tests

function testOminos()
    CodeaUnit.detailed = true

    _:describe("Ominos", function()

        _:before(function()
        end)

        _:after(function()
        end)

        _:test("HOOKUP", function()
            _:expect("Foo", "testing fooness").is("Foo")
        end)
        
        _:test("Square equality", function()
            local sq1 = Sq(0,0)
            local sq2 = Sq(0,0)
            local sq3 = Sq(1,0)
            _:expect(sq1, "1:1").is(sq1)
            _:expect(sq2, "2:1").is(sq1)
            _:expect(sq3, "3:1").isnt(sq1)
        end)
        
        _:test("Order 2", function()
            local om = Omino()
            om:add(Sq(0,0))
            _:expect(om:order()).is(1)
            om:add(Sq(0,0))
            _:expect(om:order()).is(1)
            om:add(Sq(1,0))
            _:expect(om:order()).is(2)
        end)
        
        _:test("Get order 2 from 1", function()
            local om1 = Omino()
            om1:add(Sq(0,0))
            local order2 = om1:generate()
            _:expect(#order2).is(2)
            for i,om in ipairs(order2) do
                print("order2",i,om)
            end
            local om2 = Omino()
            om2:add(Sq(0,0))
            om2:add(Sq(1,0))
            _:expect(order2, "has").has(om2)
        end)

    end)
end

Sq = class()

function Sq:init(x,y)
    self.x = x
    self.y = y
    self.key = x*10000 + y
end

function Sq:__eq(square)
    return self.key == square.key
end

function Sq:__tostring()
    local result = "Sq("..self.x..","..self.y..")\n"
    return result
end

Omino = class()

function Omino:init()
    self.squares = {}
end

function Omino:__tostring()
    local result = "Omino order "..self:order().."\n"
    for key,sq in pairs(self.squares) do
        --print("om ts", key, sq)
    result = result ..", "..sq:__tostring()
    end
    return result
end

function Omino:__eq(omino)
    if self:order() ~= omino:order() then return false end
    for key,sq in pairs(self.squares) do
        if not omino:has(sq) then
            return false
        end
    end
    return true
end

function Omino:add(square)
    local key = square.x*10000 + square.y
    self.squares[key] = square
end

function Omino:generate()
    -- assume order 1 and fake result
    local kids = {}
    local om1 = Omino()
    om1:add(Sq(0,0))
    om1:add(Sq(1,0))
    table.insert(kids,om1)
    local om2 = Omino()
    om2:add(Sq(0,0))
    om2:add(Sq(0,1))
    table.insert(kids,om1)
    return kids
end

function Omino:has(square)
    for key,sq in pairs(self.squares) do
        if key == square.key then return true end
    end
    return false
end

function Omino:order()
    local o = 0
    for key,sq in pairs(self.squares) do
        o = o + 1
    end
    return o
end

Now the test for Omino equality is hideously brute force, it checks for equal order, which loops over all the elements of each Omino, and then it loops over one of them again, looking to see whether it contains the other. That loops again, but wait, I don’t quite have to do that, do I?

I can at least do this, it seems to me:

function Omino:has(square)
    if self.squares[square.key] then
        return true
    else
        return false
    end
end

Tests still run. Now then, I think we have the basics in place so that we can trust CodeaUnit messages. And this would be a marvelous time to put this project under WorkingCopy, so that we can commit some code, have revert points, and all that good stuff. Now how do we do that …

Here are the instructions from the dungeon program:

Setting Up Working Copy

Init new repository, name it Dung-2;
Go back to repo list, long press Dung-2;
Select Share;
Select package sync with Codea logo;
Scroll through Codea programs find D2, select it.
Connected, do initial commit.

We won’t quite call this one Dung-2, that’s taken.

Here are some pictures this time for the subject and the next time I have to figure out how to do it:

Setting up Working Copy

Or setting up WorkingCopy, to make the other obvious search work:

Init new repository:

init

init2

Back to repo list, long press new repo name:

long press

Tap Share, get this popup:

Select “Package Sync”. Note the Codea logo. Up come all your codea projects:

project

Scroll to the one you want, Poly for us, tap it.

This will open a window which I unfortunately didn’t photo, showing the project’s files. Close that and commit the project as usual, “Initial Commit”.

OK, great documentation, Ron. Back to work.

Where Were We? Where Should We Be?

OK, I actually think that Sq and Omino can be compared for equality now, which is a key issue. What now?

We need to get to normalization. What we would like to have be the case is that we never expose an Omino that isn’t normalized. The current construction approach is to make an empty one and add to it. I’m not sure we’re going to love that in the future. I would much prefer an object that can never be out of shape, For now, though, let’s just do a normalize function on Omino.

Begin with a test:

        _:test("Omino normalize", function()
            local omun = Omino()
            omun:add(Sq(1,1))
            omun:add(Sq(2,1))
            omun:add(Sq(1,2))
            local omnorm = Omino()
            omnorm:add(Sq(0,0))
            omnorm:add(Sq(1,0))
            omnorm:add(Sq(0,1))
            local normalized = omun:normalize()
            _:expect(normalized).is(omnorm)
        end)

I hope you can visualize that. I’ve got an unnormalized Omino, omun, L-shaped, starting at 1,1, extending right and down from there. If it is to be normalized, I expect it to be as shown in omnorm.

To do this, I think I want to find the least x and y in my omino, and adjust all the sqs downward by whatever values I find. (If they happen to be on the negative side of the axes, the adjustment will be negative and thus add:

Code:

function Omino:normalize()
    local x,y = self:minima()
    for key,sq in pairs(self.squares) do
        sq:adjust(x,y)
    end
end

Looks like I need minima and adjust:

function Omino:minima()
    local x,y
    for key,sq in  pairs(self.squares) do
        if x==nil or x >sq.x then x = sq.x end
        if y==nil or y > sq.y then y = sq.y end
    end
    return x,y
end

function Omino:adjust(x,y)
    self.x = self.x - x
    self.y = self.y - y
end

Optimistically, I expect this to work. Let’s see why I’m wrong.

Bizarre. The fourth test doesn’t run at all. What am I missing?

        _:test("Get order 2 from 1", function()
            local om1 = Omino()
            om1:add(Sq(0,0))
            local order2 = om1:generate()
            _:expect(#order2).is(2)
            for i,om in ipairs(order2) do
                print("order2",i,om)
            end
            local om2 = Omino()
            om2:add(Sq(0,0))
            om2:add(Sq(1,0))
            _:expect(order2, "has").has(om2)
        end)
        
        _:test("Omino normalize", function()
            local omun = Omino()
            omun:add(Sq(1,1))
            omun:add(Sq(2,1))
            omun:add(Sq(1,2))
            local omnorm = Omino()
            omnorm:add(Sq(0,0))
            omnorm:add(Sq(1,0))
            omnorm:add(Sq(0,1))
            local normalized = omun:normalize()
            _:expect(normalized).is(omnorm)
        end)

I do the Codea “save all tabs and run” trick. Still nothing.

I exit Codea, go back, and my changes aren’t even there. I’m glad I’m writing this article, so I can paste them back.

I discover that adjust is supposed to be a method on Sq, not Omino:

function Sq:adjust(x,y)
    self.x = self.x - x
    self.y = self.y - y
end

My normalize test fails with an interesting message:

4: Omino normalize  -- Actual: nil, Expected: Omino order 3
, Sq(0,1)
, Sq(0,0)
, Sq(1,0)

I’m not returning the normalized object. Nor should I: we’re normalizing in place. Change the test:

        _:test("Omino normalize", function()
            local omun = Omino()
            omun:add(Sq(1,1))
            omun:add(Sq(2,1))
            omun:add(Sq(1,2))
            local omnorm = Omino()
            omnorm:add(Sq(0,0))
            omnorm:add(Sq(1,0))
            omnorm:add(Sq(0,1))
            _:expect(omun, "prenorm").isnt(omnorm)
            omun:normalize()
            _:expect(omun, "postnorm").is(omnorm)
        end)

Run tests.

4: Omino normalize postnorm -- Actual: Omino order 3
, Sq(1,0)
, Sq(0,1)
, Sq(0,0)
, Expected: Omino order 3
, Sq(0,1)
, Sq(0,0)
, Sq(1,0)

Well, if I can trust CodeaUnit here, my answer is correct and my equality checker isn’t. Need an easier test:

Oh. I can’t just change those guys in place: they’re indexed by their old key. We need to create a new table for them.

function Omino:normalize()
    local newTable = {}
    local x,y = self:minima()
    for key,sq in pairs(self.squares) do
        sq:adjust(x,y)
        newTable[sq.key] = sq
    end
    self.squares = newTable
end

function Sq:adjust(x,y)
    self.x = self.x - x
    self.y = self.y - y
    self.key = self.x*10000 + self.y
end

This is truly horrid, as these objects are almost value objects and now I’m tearing into their guts. But make it work, then make it right.

I also wrote a new test:

        _:test("Omino equality", function()
            local om1 = Omino()
            om1:add(Sq(0,0))
            om1:add(Sq(1,0))
            om1:add(Sq(0,1))
            local om2 = Omino()
            om2:add(Sq(0,0))
            om2:add(Sq(0,1))
            om2:add(Sq(1,0))
            _:expect(om1).is(om2)
        end)

But that one would already have run. It’s normalize that was borked.

Anyway run tests. They are green. Normalize works.

Now let’s think about this value object thing. Let’s create a new Sq, adjusted:

function Omino:normalize()
    local newTable = {}
    local x,y = self:minima()
    for key,sq in pairs(self.squares) do
        local newsq = sq:adjusted(x,y)
        newTable[newsq.key] = newsq
    end
    self.squares = newTable
end

I’m going to allow the normalize method to change the internal state of the Omino. Why? Because I don’t have a better idea yet. We could produce a new normalized omino. Not much harm if we did. But first this:

function Sq:adjusted(x,y)
    return Sq(self.x-x, self.y-y)
end

I expect the tests to run.

They do. Now let’s think. We could change this normalize method to normalized and return a new, normalized omino. Let’s do that to see how we like it:

function Omino:normalized()
    local omino = Omino()
    local x,y = self:minima()
    for key,sq in pairs(self.squares) do
        omino:add(sq:adjusted(x,y))
    end
    return omino
end

Have to change the test (back to how I originally had it):

        _:test("Omino normalize", function()
            local omun = Omino()
            omun:add(Sq(1,1))
            omun:add(Sq(2,1))
            omun:add(Sq(1,2))
            local omnorm = Omino()
            omnorm:add(Sq(0,0))
            omnorm:add(Sq(1,0))
            omnorm:add(Sq(0,1))
            _:expect(omun, "prenorm").isnt(omnorm)
            omnorm = omun:normalized()
            _:expect(omnorm, "postnorm").is(omnorm)
        end)

Should work. Does work. Commit: Ominos now normalize, compare for equality. Squares can return adjusted squares.

Interrupted by a Yak

A wild yak has appeared and derailed me somewhat. I found a strange effect in the cooperation of Codea and Working Copy, where changes in my tests were not reflected in the run. So I’ve diverted for a while to create a report to the authors of the two systems, documenting the behavior.

It’s now 1250. I think I’ll proceed just a bit further here and see if I can build dominos from a monomino.

        _:test("Dominos from a monomino", function()
            local mon = Omino()
            om:add(Sq(0,0))
            local doms = om:extend()
            local omh = Omino()
            omh:add(Sq(0,0))
            omh:add(Sq(1,0))
            local omv = Omino()
            omv:add(Sq(0,0))
            omv:add(Sq(0,1))
            _:expect(doms).has(omh)
            _:expect(doms).has(omv)
        end)

I’m supposing that extend returns a collection of all the extensions of a given omino. Just now, it’ll be assumed to be a monomino, but we’ll deal with that in due time.

This took me a bit of fiddling but it was all due to the last two lies of the test above, which should be:

        _:test("Dominos from a monomino", function()
            local mon = Omino()
            mon:add(Sq(0,0))
            local doms = mon:extend()
            doms:print()
            local omh = Omino()
            omh:add(Sq(0,0))
            omh:add(Sq(1,0))
            local omv = Omino()
            omv:add(Sq(0,0))
            omv:add(Sq(0,1))
            _:expect(doms.coll).has(omh)
            _:expect(doms.coll).has(omv)
        end)

I’m ripping the collection out of my new OminoCollection object, which looks like this:

OminoCollection = class()

function OminoCollection:init()
    self.coll = {}
end

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

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

function OminoCollection:print()
    for i,om in ipairs(self.coll) do
        print(om)
    end
end

That behaves like a set. Let’s call it a set:

OminoSet = class()

function OminoSet:init()
    self.coll = {}
end

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

function OminoSet:print()
    for i,om in ipairs(self.coll) do
        print(om)
    end
end

I’d better just dump out the rest of the code, as I’ve been twiddling it without writing. But first let’s look at this:

function Omino:extend()
    local result = OminoSet()
    local order = self:order()
    for key,sq in pairs(self.squares) do
        local newSquares = sq:neighbors()
        for i,sq in pairs(newSquares) do
            local candidate = self:copy()
            candidate:add(sq)
            if candidate:order() > order then
                local norm = candidate:normalized()
                result:add(norm)
            end
        end
    end
    return result
end

What’s going on here? I’ve created an OminoSet, which keeps only unique copies of normalized Omino instances. And what goes into it? For each Sq(uare) in the input Omino, we create a copy of the original omino, and add one neighbor to it. Then, if it has the desired new order (i.e. greater than our own saved order), we normalize it, and add it to our OminoSet.

This collection is all the order N+1 ominos from a single Omino.

That’s not quite what we really want. We really want a collection of all the order N+1 ominos from a collection of all the order N ominos.

I think we can make that happen. Let’s change extend to take an OminoSet as an input:

function Omino:extendInto(ominoSet)
    local order = self:order()
    for key,sq in pairs(self.squares) do
        local newSquares = sq:neighbors()
        for i,sq in pairs(newSquares) do
            local candidate = self:copy()
            candidate:add(sq)
            if candidate:order() > order then
                local norm = candidate:normalized()
                ominoSet:add(norm)
            end
        end
    end
end

I’ve renamed it extendInto and given it the set to put results in.

Change the test:

        _:test("Dominos from a monomino", function()
            local mon = Omino()
            mon:add(Sq(0,0))
            local doms = OminoSet()
            mon:extendInto(doms)
            local omh = Omino()
            omh:add(Sq(0,0))
            omh:add(Sq(1,0))
            local omv = Omino()
            omv:add(Sq(0,0))
            omv:add(Sq(0,1))
            _:expect(doms.coll).has(omh)
            _:expect(doms.coll).has(omv)
        end)

Should still work. It does.

Now we should be able to get all the extended ominos from an omino set, like this:

function OminoSet:extend(ominoSet)
    local newSet = OminoSet()
    for i,om in ominoset.coll do
        om:extendInto(newSet)
    end
    return newSet
end

I’d best write a test for that.

        _:test("Trominos from dominos, from monomino", function()
            local mon = Omino()
            mon:add(Sq(0,0))
            local mons = OminoSet()
            mons:add(mon)
            local doms = mons:extend(mons)
            _:expect(#doms.coll).is(2)
            local troms = doms:extend(doms)
            _:expect(#troms.coll).is(6)
        end)

I have a few typos in my code above:

function OminoSet:extend(ominoSet)
    local newSet = OminoSet()
    for i,om in ipairs(ominoSet.coll) do
        om:extendInto(newSet)
    end
    return newSet
end

There are six free trominos, and I got six elements in my troms set. I’m not checking the individuals. That’ll be a pain. Let’s instead do the quads:

        _:test("extend up to quads, from monomino", function()
            local mon = Omino()
            mon:add(Sq(0,0))
            local mons = OminoSet()
            mons:add(mon)
            local doms = mons:extend(mons)
            _:expect(#doms.coll).is(2)
            local troms = doms:extend(doms)
            _:expect(#troms.coll).is(6)
            local quads = troms:extend(troms)
        end)

I finally notice that I’m sending to a collection and giving it itself as the parameter. That seems excessive:

        _:test("extend up to quads, from monomino", function()
            local mon = Omino()
            mon:add(Sq(0,0))
            local mons = OminoSet()
            mons:add(mon)
            local doms = mons:extend()
            _:expect(#doms.coll).is(2)
            local troms = doms:extend()
            _:expect(#troms.coll).is(6)
            local quads = troms:extend()
            _:expect(#quads.coll).is(19)
        end)

And fix extend:

function OminoSet:extend()
    local newSet = OminoSet()
    for i,om in ipairs(self.coll) do
        om:extendInto(newSet)
    end
    return newSet
end

Let’s roll the dice and see if we get 19.

Yes! The tests run. Let’s do five.

            local pents = quads:extend()
            _:expect(#pents.coll).is(63)

Will it be correct? Of course it will:

And it is.

I am quite confident that this program is generating all the fixed polyominos of any order you want. I want to convert it to recursive, maybe, but just for fun, a few more:

            local pents = quads:extend()
            _:expect(#pents.coll).is(63)
            local hexes = pents:extend()
            _:expect(#hexes.coll).is(216)
            local hepts = hexes:extend()
            _:expect(#hepts.coll).is(760)
            local octs = hepts:extend()
            _:expect(#octs.coll).is(2725)

Commit: OminoSet extend works up to octominos (and beyond).

Permit me to sum up and crow a bit.

Summary Crowing

OK, let’s review this code. We have a handful of tests:

        
        _:test("Square equality", function()
            local sq1 = Sq(0,0)
            local sq2 = Sq(0,0)
            local sq3 = Sq(1,0)
            _:expect(sq1, "1:1").is(sq1)
            _:expect(sq2, "2:1").is(sq1)
            _:expect(sq3, "3:1").isnt(sq1)
        end)
        
        _:test("Order 2", function()
            local om = Omino()
            om:add(Sq(0,0))
            _:expect(om:order()).is(1)
            om:add(Sq(0,0))
            _:expect(om:order()).is(1)
            om:add(Sq(1,0))
            _:expect(om:order()).is(2)
        end)
        
        _:test("Get order 2 from 1", function()
            local om1 = Omino()
            om1:add(Sq(0,0))
            local order2 = om1:generate()
            _:expect(#order2).is(2)
            local om2 = Omino()
            om2:add(Sq(0,0))
            om2:add(Sq(1,0))
            _:expect(order2, "has").has(om2)
        end)
        
        _:test("Omino equality", function()
            local om1 = Omino()
            om1:add(Sq(0,0))
            om1:add(Sq(1,0))
            om1:add(Sq(0,1))
            local om2 = Omino()
            om2:add(Sq(0,0))
            om2:add(Sq(0,1))
            om2:add(Sq(1,0))
            _:expect(om1).is(om2)
        end)
        
        _:test("Omino normalize", function()
            local omun = Omino()
            omun:add(Sq(1,1))
            omun:add(Sq(2,1))
            omun:add(Sq(1,2))
            local omnorm = Omino()
            omnorm:add(Sq(0,0))
            omnorm:add(Sq(1,0))
            omnorm:add(Sq(0,1))
            _:expect(omun, "prenorm").isnt(omnorm)
            omnorm = omun:normalized()
            _:expect(omnorm, "postnorm").is(omnorm)
        end)
        
        _:test("Dominos from a monomino", function()
            local mon = Omino()
            mon:add(Sq(0,0))
            local doms = OminoSet()
            mon:extendInto(doms)
            local omh = Omino()
            omh:add(Sq(0,0))
            omh:add(Sq(1,0))
            local omv = Omino()
            omv:add(Sq(0,0))
            omv:add(Sq(0,1))
            _:expect(doms.coll).has(omh)
            _:expect(doms.coll).has(omv)
        end)
        
        _:test("extend up to octs, from monomino", function()
            local mon = Omino()
            mon:add(Sq(0,0))
            local mons = OminoSet()
            mons:add(mon)
            local doms = mons:extend()
            _:expect(#doms.coll).is(2)
            local troms = doms:extend()
            _:expect(#troms.coll).is(6)
            local quads = troms:extend()
            _:expect(#quads.coll).is(19)
            local pents = quads:extend()
            _:expect(#pents.coll).is(63)
            local hexes = pents:extend()
            _:expect(#hexes.coll).is(216)
            local hepts = hexes:extend()
            _:expect(#hepts.coll).is(760)
            local octs = hepts:extend()
            _:expect(#octs.coll).is(2725)
        end)

We moved from checking squares for equality, to checking order of an omino, to creating the order 2 ones from an order 1 (and implementing Omino equality along the way). We tested and wrote “normalize”, to move an omino up against the axes, so that they’d compare correctly for equality.

We generated a function on Omino to produce all the Ominos of the next order into a collection, and then extended the collection until it served as an OminoSet, containing only unique (fixed) ominos.

We used the generate repeatedly to create the collections of ominos from size 1 to size 8 and checked that we got the right number.

At no time did we ever look at an OminoSet and try to figure out from looking at the ones and zeros what the shapes are.

What we know is that an extended Omino will have one square added to the side of one of its squares, such that the new square doesn’t overlap and old one. (Because if it does, the Omino eats the duplicate square and stays at the old order.)

We know that OminoSet only accepts a new omino if it doesn’t have an equal one. So we know we have one and only one copy of every next-order Omino in an extended OminoSet.

How do the objects work? Like this:

Squares

Sq = class()

function Sq:init(x,y)
    self.x = x
    self.y = y
    self.key = x*10000 + y
end

function Sq:__eq(square)
    return self.key == square.key
end

function Sq:__tostring()
    local result = "Sq("..self.x..","..self.y..")\n"
    return result
end

function Sq:adjusted(x,y)
    return Sq(self.x-x, self.y-y)
end

function Sq:neighbors()
    local n = {}
    for i,step in ipairs({ {0,1}, {1,0}, {-1,0}, {0,-1} }) do
        table.insert(n,self:adjusted(step[1], step[2]))
    end
    return n
end

Sq(uares) have an x, a y, and a unique key 10000x + y.

They can print. They can return a new square with x and y adjusted based on input x and y And they can produce a table of their neighbors, defined as the four squares at 1,0, 0,1, -1,0 and 0,-1 from them, i.e. the four squares adjacent to them.

That’s all they know

Ominos

There’s a bit more to Omino. They can init, and print their order and contents. They can determine whether they are equal to another omino by checking mutual order and if they have the same order, checking each square of one to be sure it’s in the other.

Omino = class()

function Omino:init()
    self.squares = {}
end

function Omino:__tostring()
    local result = "Omino order "..self:order().."\n"
    for key,sq in pairs(self.squares) do
    result = result ..", "..sq:__tostring()
    end
    return result
end

function Omino:__eq(omino)
    if self:order() ~= omino:order() then return false end
    for key,sq in pairs(self.squares) do
        if not omino:has(sq) then
            return false
        end
    end
    return true
end

You can add a square to an Omino. That’s how you create them. I’d prefer that they have a complete creation method but the whole process here is one of incremental addition, so we may be stuck with it.

function Omino:add(square)
    local key = square.x*10000 + square.y
    self.squares[key] = square
end

An Omino can produce a copy of itself. This allows us to extend a given omino by copying it and then adding a new square into it.

function Omino:copy()
    local result = Omino()
    for key, sq in pairs(self.squares) do
        result:add(sq:adjusted(0,0))
    end
    return result
end

function Omino:extendInto(ominoSet)
    local order = self:order()
    for key,sq in pairs(self.squares) do
        local newSquares = sq:neighbors()
        for i,sq in pairs(newSquares) do
            local candidate = self:copy()
            candidate:add(sq)
            if candidate:order() > order then
                local norm = candidate:normalized()
                ominoSet:add(norm)
            end
        end
    end
end

We have a generate function that isn’t used except in a test. It’s an appendix left over from the evolutionary process and we could remove it and the test. But it sort of led us in the right direction.

function Omino:generate()
    local kids = {}
    local om1 = Omino()
    om1:add(Sq(0,0))
    om1:add(Sq(1,0))
    table.insert(kids,om1)
    local om2 = Omino()
    om2:add(Sq(0,0))
    om2:add(Sq(0,1))
    table.insert(kids,om1)
    return kids
end

We have a few utility functions to tell whether an Omino already contains a given square, to calculate the minimum x and y in the Omino in preparation for normalizing, and a function returning a new normalized Omino from an unnormalized one.

(We could probably use that to implement copy, if we wanted to.)

function Omino:has(square)
    if self.squares[square.key] then
        return true
    else
        return false
    end
end

function Omino:minima()
    local x,y
    for key,sq in  pairs(self.squares) do
        if x==nil or x >sq.x then x = sq.x end
        if y==nil or y > sq.y then y = sq.y end
    end
    return x,y
end

function Omino:normalized()
    local omino = Omino()
    local x,y = self:minima()
    for key,sq in pairs(self.squares) do
        omino:add(sq:adjusted(x,y))
    end
    return omino
end

And we have a trivial function to return the order of an Omino.

function Omino:order()
    local o = 0
    for key,sq in pairs(self.squares) do
        o = o + 1
    end
    return o
end

And we have a class OminoSet which is a set of ominos with no duplicates under Omino:__eq()

OminoSet = class()

function OminoSet:init()
    self.coll = {}
end

We add a new omino only if we don’t already have it.

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

We extend an Omino set by iterating over it and putting all the extended versions of our ominos into a new OminoSet:

function OminoSet:extend()
    local newSet = OminoSet()
    for i,om in ipairs(self.coll) do
        om:extendInto(newSet)
    end
    return newSet
end

And we can print an OminoSet:

function OminoSet:print()
    for i,om in ipairs(self.coll) do
        print(om)
    end
end

And that’s all there is to it.

There are no checks for right left up down, no checks for order other than “is this one’s order the same as mine, or larger”.

I am pleased with this. It had seemed to me that we should be able to do this thing with no special cases of any kind, and it seems to have happened.

I love it when a plan comes together.

Next time, maybe I’ll draw them all on the screen so we can see what they look like. But I’m already quite sure that they are correct. Won’t it be funny if I’m wrong?

Poly.zip