Let’s look into a suggestion from @blackoverflow. Turns out to be a good idea needing a little improvement. (Minor edit, courtesy @blackoverflow.)

Here’s the current generator:

class Cell:
    def generate(self, cond):
        return generate(self, cond)

def generate(start, condition=None):
    def accept_any(_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)

New friend @blackoverflow suggests that the final examined.add(neighbor) isn’t needed. Why? Well, it seems to me that soon enough it’ll turn up in the frontier. However … frontier isn’t a set, because we can’t pop a set. So we will get duplicates in frontier as the cells get generated, because cells can be approached many different ways. Anyway, yesterday at first glance I thought I agreed that we can remove that, but today I am not so sure.

Can too, can too!
Turns out below that we can pop a set. I was sure I’d discovered that we can’t. This will let us change frontier to a set and apply @blackoverflow’s idea. Read on:

I suspect the tests will run if we remove the final examined.add(neighbor). Let’s find out. Aha! Two tests fail! What are they?

    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

This fails, with 46 in count. So what has happened is that we put multiple copies of some cells into frontier, and took them out again, visiting some cells more than once.

An interesting question is whether we can remove the first addition to examined. Let’s try that. That does pass, because we initialized examined to include start, and all the other cells will pass through our neighbor code.

Now another consideration is what might happen if frontier were a set. We would have to come up with a way to pull one element from the set. Can we send next to a set?

First, I notice that we can get rid of the add at the beginning with a set literal:

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

Let’s commit this, since it’s working: refactoring generate.

Turns out that we cannot send next to a set. However, I was mistaken when I said we cannot pop a set. In fact we can. So this works:

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

Now I think we can move the examined line up. That works:

def generate(start, condition=None):
    def accept_any(_cell):
        return True
    cond = condition or accept_any
    frontier = {start}
    examined = {start}
    while frontier:
        next = frontier.pop()
        yield next
        examined.add(next) # <=== moved
        for neighbor in next.neighbors:
            if neighbor not in examined and cond(neighbor):
                frontier.add(neighbor)

Commit again.

A nice improvement. Thanks, @blackoverflow, for reading and for the idea!

Now I want to see if we can adjust PathFinder to use generate. Seems reasonable. Let’s sum up here and start another article.

Summary

The big lesson here is well-known: two heads are better than one, especially when one of them isn’t mine. This is why pair programming and mob programming work so well: better ideas are found sooner. For most people who try them, they are also more enjoyable, although I do know people who do not enjoy pairing with me. I suspect that my thoughts seem to flicker randomly, and after years of programming in public with Chet, I tend to say things that seem snarky.

But generally people who try pairing and mobbing enjoy it and find it more productive.

Another lesson is that almost any code can be improved. That’s not to say that we should spend the rest of our lives improving the same code over and over, but that we should be alert to possibilities to make things a bit more expressive, a bit simpler, or even just a bit better looking.

I’d not have found this improvement without @blackoverflow’s suggestion, which was a good idea even though it wasn’t quite the thing. That’s what we find with ideas: they aren’t always quite right, but they are very often useful.

Thanks! See you next time!