Next / Previous / Contents / Shipman's homepage

20. Puzzle.__genSlots(): Detect slots in a row or column

kkck
# - - -   P u z z l e . _ _ g e n C l u m p s

    def __genClumps ( self, j, isV ):
        '''Generate multi-cell clumps in a row or column.

          [ (isV is 0 for horizontal, 1 for vertical) and
            (j is a valid row or column index for that
            orientation) ->
              generate (start, length) tuples for all contiguous
              groups of two or more cells in that orientation
              from self.__cellMap ]
        '''

For example, consider this nine-element row in the framework section:

### # ###

There are two slots here. One starts at column 0 for a length of 3; the other starts at column 6 for a length of 3. The cell at column 4 is not part of a horizontal slot.

So our problem is to detect transitions between elements without cells and elements with cells, and then count the sequence of contiguous cells after each transition, and if the sequence is length 2 or greater, we'll call it a slot.

We'll use a simple state machine here. Variable start is initially set to None, and it is set back to None every time we see an element without a cell. Then, as we step through the elements, we'll set start to the element index whenever it changes from no cell to cell. When we see a transition from cell to no cell, if start is not None, then a slot exists starting at start and extending through the previous position in our scan.

There is one edge case we need to eliminate. If there is a cell at the last position, we will not see the cell→no-cell transition. To eliminate this special case, we will build a list containing 0's where there are no cells and 1's where there are cells, and then append one extra zero so there will always be a cell→no-cell transition even if the last element contains a cell.

First, build the list of 0's and 1's. Cells are detected by calling Section 32, “Puzzle.whatCell(): Is there a cell at a given coordinate?”. Then we run our little state machine and generate the (start, length) tuples.

kkck
        #-- 1 --
        # [ mask  :=  a list containing 1s where row or column j
        #       has cells, 0s where it has no cells, with one
        #       extra 0 appended ]
        mask = [ self.whatCell ( coord ) is not None
                 for coord in self.scan ( j, isV ) ]
        mask.append ( 0 )

        #-- 2 --
        # [ generate (start, length) tuples for consecutive
        #   groups of two or more 1s in mask ]
        start = None
        for i in range(len(mask)):
            if mask[i]:
                if start is None:
                    start = i
            else:
                if start is not None:
                    if (i-start) > 1:
                        yield (start, i-start)
                start = None

        #-- 3 --
        raise StopIteration