I think a generator might be an interesting way to do this flooding thing. Let’s see if we can gin one up. And we can!!

I mentioned, in today’s earlier article, the feeling that the SuiteFinder has two separable aspects, the flooding of the space, finding all the cells, and the accumulation of the interesting information, the set of all rooms that the cells are in. So as I was trying to rest, it occurred to me that perhaps we would do well to have a Python generator that produces the cells, and then do something with them. We wouldn’t want to store all the cells: there might be quite a few of them in a large enough space, but with a generator we would produce them one at a time.

Besides, it might be cool.

Review

Reviewing what I “know” about generators, a generator in Python is a function that produces elements one at a time, using the yield statement to provide the next element, and doing whatever calculations need to be done to decide what to yield next.

I think we’ll begin with a test, if I can think of one. Something like setting up a space and a couple of adjacent rooms and seeing if we generate all the cells we expect. I think it might be wise to make a new test file for this.

    def test_generate_cells(self):
        random.seed(37)
        space = CellSpace(10, 10)
        start = space.at(5,5)
        size = 30
        room = Room(space, size, start)
        assert len(room.cells) == size
        count = 0
        for cell in generate(start):
            count += 1
        assert count == size

Perfect except for the lack of generate. I’m going to just try to code this up directly, based on memory and glancing at the SuiteFinder if I need to.

This took a bit longer than I’d have liked, but I think we’re good:

def generate(start: Cell):
    frontier = [start]
    examined = set()
    examined.add(start)
    while frontier:
        cell = frontier.pop()
        yield cell
        examined.add(cell)
        for neighbor in cell.neighbors:
            if neighbor not in examined:
                if neighbor.is_in_a_room():
                    frontier.append(neighbor)
                    examined.add(neighbor)

I think I’d like the condition, currently is_in_a_room to be pluggable, so that we could use this scheme for other purposes, such as path finding. And I don’t like that deep nesting. We can remove one level with and, but we’ll still have more than I like:

Let’s do the pluggable condition, first with the room default to keep the test running. On, and let’s commit first since we are green.

I forgot to show you the intermediate step. Here we are now:

def generate(start: Cell, condition=None):
    def accept_any(_cell: Cell):
        return True
    cond = condition or accept_any
    frontier = [start]
    examined = set()
    examined.add(start)
    while frontier:
        next = frontier.pop()
        yield next
        examined.add(next)
        for neighbor in next.neighbors:
            if neighbor not in examined and cond(neighbor):
                frontier.append(neighbor)
                examined.add(neighbor)

And the test is:

    def test_generate_cells(self):
        random.seed(37)
        space = CellSpace(10, 10)
        start = space.at(5,5)
        size = 30
        room = Room(space, size, start)
        assert len(room.cells) == size
        count = 0
        for cell in generate(start, lambda c: c.is_in_a_room()):
            count += 1
        assert count == size

I didn’t write a test for that. Let’s do:

    def test_default_cond(self):
        space = CellSpace(10, 10)
        start = space.at(5,5)
        size = 45
        room = Room(space, size, start)
        assert len(room.cells) == size
        count = 0
        for cell in generate(start):
            count += 1
        assert count == 100

We get 100 because we accept any cell and there are 100 in a 10x10 space.

Commit: added user-provided condition on cells processed.

That’s enough for an afternoon’s diversion, let’s sum up:

Summary

That went fairly well, though I made some mistakes along the way the greatest of which was not copying code that already worked. As for the function, on the one hand I like it, as it is clean and seems clearly to be usable for other flooding activities such as path-finding. On the other hand I don’t feel that comfortable with free-standing functions, preferring objects and methods. I’ll have to sit with that a while to decide whether to do something about it.

This morning’s refactoring tells us what would happen if we embedded this in a class and then refactored it to death. In the cold light of just now, I think I prefer the compact version to the “extremely expressive” version, despite my love for small expressive methods. But, again, I’ll sit with it and see what I think.

I think the pluggable condition will pay off in letting us reuse the same code for path finding if we care to, and if I decide not to throw this away, we probably will commit to using it for all flooding purposes, adjusting it if we need to. But with the yield in place, something like the suite logic can be placed outside the generator, which was a big part of my motivation.

Net net net, I think I like it. I’ll sit with it and see what I think tomorrow.

See you then!

Oh I thought of an enhancement for that final test, let’s have it:

    def test_default_cond(self):
        space = CellSpace(10, 10)
        start = space.at(5,5)
        size = 45
        room = Room(space, size, start)
        assert len(room.cells) == size
        room_count = 0
        other_count = 0
        for cell in generate(start):
            if cell.is_in_a_room():
                room_count += 1
            else:
                other_count += 1
        assert room_count == size
        assert other_count == 100 - size

Not much more information, really but with both counts right we gain a little confidence, if we needed it. Should we check to be sure we got 100 unique cells? Sure, let’s do:

    def test_default_cond(self):
        space = CellSpace(10, 10)
        start = space.at(5,5)
        size = 45
        room = Room(space, size, start)
        assert len(room.cells) == size
        room_count = 0
        other_count = 0
        all = set()
        for cell in generate(start):
            all.add(cell)
            if cell.is_in_a_room():
                room_count += 1
            else:
                other_count += 1
        assert room_count == size
        assert other_count == 100 - size
        assert len(all) == 100

Enough already. But when I think of an easy additional check, I like to add it. Gives those extra little confidence boosts.

But enough: a nice little generator that may soon grow into something we actually use, in just a bit of time in the afternoon.

See you next time!