Find group of available stalls in an aisle

Question

An aisle is defined as two rows of six stalls each. A stall is adjacent to another if it is directly next to it or across from it. My method finds out how many stalls can be found in a chain from the stall currently being worked with that are available for use. For example, * is a stall that is already occupied, and . is a stall that is available. With an aisle like this:

...*..
......

the get_available_adjacents method of the top left stall would return a set of eleven stalls, every stall except the occupied one. With

...*..
...*..

the top left stall would return a set of six stalls because the occupied ones form a break in the line. One of the occupied ones, however, would return a set of ten stalls because it is connected to both groups of available stalls. My solution below seems inefficient. With only twelve stalls per aisle, it is figured out quickly enough, but I would like to know if there is a more efficient solution.

It works by creating a set found to store all of the stalls that we find. It also creates a set used that contains all stalls for which the get_available_adjacents method has been called. It then loops through each adjacent of the current stall, and if it is available, adds it to the used set and updates found by calling the adjacent's get_available_adjacents method.

class Stall:
    def __init__(self, occupant=None):
        self.occupant = occupant
        self.available = True

    def get_available_adjacents(self, used=None):
        if used is None:
            used = {self}

        found = set()
        if self.available:
            found.add(self)

        for adjacent in self.adjacents:
            if adjacent in used or not adjacent.available:
                continue
            used.add(adjacent)
            found.update(adjacent.get_available_adjacents(used))
        return found

For testing:

class Aisle:
    def __init__(self, row_length=6):
        self.top = [Stall() for _ in range(row_length)]
        self.bottom = [Stall() for _ in range(row_length)]

        self.top[0].adjacents = (self.top[1], self.bottom[0])
        self.top[-1].adjacents = (self.top[-2], self.bottom[-1])
        self.bottom[0].adjacents = (self.bottom[1], self.top[0])
        self.bottom[-1].adjacents = (self.bottom[-2], self.top[-1])

        for i, (t, b) in enumerate(zip(self.top[1:-1], self.bottom[1:-1]), 1):
            t.adjacents = (self.top[i-1], self.top[i+1], b)
            b.adjacents = (self.bottom[i-1], self.bottom[i+1], t)


aisle = Aisle()
print(aisle.top[0].get_available_adjacents()) # gives 12 results
aisle.top[2].available = False
print(aisle.top[0].get_available_adjacents()) # gives 11 results
aisle.bottom[2].available = False
print(aisle.top[0].get_available_adjacents()) # gives 4 results
print(aisle.top[2].get_available_adjacents()) # gives 10 results

Answer 1

1. There are no docstrings. What does an object belonging to the Stall class represent? What do the methods do? How should I call them?

2. The get_available_adjacents method relies on the adjacents attribute. But there is no method on the class that sets this attribute. This makes it hard to reason about the behaviour of this method.

   Update: I recognize that you can't supply the adjacent stalls at initialization time (because maybe they haven't been created yet), so I recommend initializing the adjacents attribute to an empty collection in the __init__ method, and providing a method to extend the collection.

   Alternatively (as suggested by Sjoerd Job Postmus in comments), since aisles have a standard layout, it might make sense to move the adjacency computation to the aisle class. If you do the latter then you'll find that the Stall class becomes redundant — all it represents is whether there is an occupant or not, and that could be represented by an Occupant object, or None if there is no occupant. (Assuming that no occupant can occupy more than one stall.)

3. I don't like the way that get_available_adjacents has been implemented as a method on the Stall class. That's because finding an available set of stalls in an aisle is an operation on an aisle, not an operation on an individual stall. Methods should be placed where they make logical sense, not just attached to any old class.

4. The algorithm you have implemented is known as flood fill. If you read the Wikipedia article, you'll see a couple of approaches for making it faster: (i) use a queue instead of a stack, to avoid function call overhead; (ii) run as far as you can along horizontal rows to reduce the amount of queue management. (But neither of these approaches improves the efficiency: all algorithms take time proportional to the size of the flooded region.)

Answer 2

To add to Gareth Rees's excellent comments, I'd like to suggest the following:

Replace the top/bottom lists with a list-of-lists. That way you can use the same implementation for when you are looking for a region in multiple aisles.

Furthermore: don't bother with the stalls, just make None in the list mean: no occupant, and a value mean 'occupied by …'.