Iterators in Python lead to a lot of overhead. Python generators are a simple way of creating iterators in which all overheads are automatically handled. The use of generators results in elegant and minimal code.
The Python programming language has many constructs that enable programmers to write elegant and minimal code. Other than its aesthetic charm, elegant code has practical benefits, primarily with regard to readability and, thereby, maintainability. Such code typically comes out as cleanly separating the different aspects of the solution, which helps the maintainer both in fixing bugs and extending the code for adjacent requirements. As Python provides a wide set of features, some of them are occasionally overlooked but each feature is effective for a particular type of problem. The generator construct is one such feature that allows one to write elegant code. The generator functionality is realised with the yield statement.
We start with looking at a simple example of how generators operate (reference [1]):
# a generator that yields items instead of returning a list def firstn(n): num = 0 while num < n: yield num ## generate next number in the sequence num += 1 sum_of_first_n = sum(firstn(1000000))
In the above example, the entire list of the first one million numbers is not built in memory and then given to the sum function. Instead, the numbers in the sequence are generated on-the-fly. As the function firstn is called repeatedly, it remembers its previous state, specifically the value of num and continues execution from thereon. When execution reaches the yield statement, the value of num is returned and the state checkpointed. When the function is invoked again, it resumes from the statement after yield and continues. Eventually, when the function performs a regular return or falls off the end, the state is destroyed, and the generator terminates.
As the per information provided at https://wiki.python.org/moin/Generators, the power of generator expressions is derived from being “… very similar to the implementation that built a list in memory, but has the memory usage characteristic of the iterator implementation.”
However, programmers accustomed to a single ‘flow of control’ model, especially as supported in the C family of languages, may not find generators very intuitive, at least when they first encounter them. This article is intended to help understand the power of generators and the way they promote expressing the ‘separation of concerns’. As the Python documentation already covers generators very crisply, here we follow an example-driven approach to demonstrate the power of this concept.
Sample problem being solved
The problem used in the rest of the article is the ‘Connect-4’ game. This is a two-player game in which players take turns to drop chips into a vertical board, as shown in Figure 1.
Each player has a stack of chips of one colour. The player who first gets four ‘connected’ (adjacent) chips is the winner. The adjacency could be in a row, a column or a diagonal. A similar problem statement can be posed in other games, like the popular Android version of ‘Jewels’, where the idea is to find the longest successive connected sequence of beads of a colour.
The objective of the required software is to identify if a given board position represents a winning position. It needs to answer the following questions:
1. Does the board represent a winning position?
2. If yes, which colour is the winner and at which board location?
Solutions design
Niklaus Wirth, the designer of the Pascal programming language, made the following observation about programs:
Programs = Algorithms + Data structures
So, let us set out to work out both for the problem at hand.
Data structures
Here, the key data structure is the one that models the board, which we represent as a list of lists, where each sub-list represents the elements of a single row. Also, for the purpose of this program, let us consider a 6 x 7 board; i.e., it has six rows and seven columns. With this board size, a sample Python list that represents the board is shown below:
board = [ [e00, e01, e02, e03, e04, e05, e06], # top most row [e10, e11, e12, e13, e14, e15, e16], … [e50, e51, e52, e53, e54, e55, e56], # bottom most row ]
In our representation, board[i][j], represents the element at i+1-th row and j+1-th column, where rows are numbered from top to bottom and columns from left to right. I chose this ordering as it is very natural to the array ordering in programming languages, though we may sometimes count rows from bottom to top. Each element is either a blank (i.e., has no chip), or has a red or a yellow chip. For example, the bottom-most row shown in Figure 1 would be represented as:
[ ‘r’, ‘y’, ‘y’, ‘y’, ‘r’, ‘y’, ‘r’ ]
And the top-most row would be represented as all-blanks:
[ ‘b’, ‘b’, ‘b’, ‘b’, ‘b’, ‘b’, ‘b’ ]
The algorithm
The algorithm is straightforward – it is required to go over each row, column and diagonal to look for four connected chips of the same colour.
1. Walk each row to find a contiguous sequence of four chips of the same colour. If found, return the colour and location.
2. Walk each column to a find a contiguous sequence of four chips of the same colour. If found, return the colour and location.
3. Walk each diagonal to a find a contiguous sequence of four chips of the same colour. If found, return the colour and location.
The first two of the above steps are self-explanatory but the third step merits some discussion as the diagonal referred to here does not mean just the two regular geometric diagonals of a rectangle. Instead, all the oblique sequences that are parallel to the geometric diagonals are to be considered (unless they have less than four elements) – so, it involves a set of diagonals. Also, diagonals from left to right are distinct from diagonals that go from right to left and hence, both sets have to be considered. With this understanding, the second version of our pseudo code is shown below:
1. Walk each row to find a contiguous sequence of four chips of the same colour. If found, return the colour and location.
2. Walk each column to a find a contiguous sequence of four chips of the same colour. If found, return the colour and location.
3. Handling diagonals.
- Walk each left-to-right diagonal contiguous sequence of four chips of the same colour. If found, return the colour and location.
- Walk each right-to-left diagonal contiguous sequence of four chips of the same colour. If found, return the colour and location.
First attempt at the solution
This attempt does not use Python’s generators but finds a reasonable solution. However, as we are interested in the process of developing code, the solution is presented in an iterative fashion. Initially, we develop the code just for handling rows and then extend it for checking within columns. Then, we refine the extended code to minimise redundancies.
The code for the first version that only handles rows in the board is shown below:
def compare_element(current, running, running_count): if current != running: return current, 1 else: return running, running_count + 1 def walk_rows_for_connect4(board): # walk over each row for i in range(len(board)): c, count = None, 0 ## inner loop to look for 4-connected in a row for j in range(len(board[0])): c, count = compare_element(board[i][j], c, count) if count == 4 and c != ‘b’: return (c, i, j,) return (None, (-1, -1))
The above should appear fairly intuitive to most programmers. The walk_rows_for_connect4 function implements nested loops – the outer loop to walk over all the rows and the inner one to walk through elements of a row. In the inner loop, we keep track of a run, i.e., a contiguous sequence of same coloured chips. Once a run of length four is found, the function returns with the colour and the position. If none is found, it indicates failure by returning ‘None’ as the colour.
Implementing Step 2 in our algorithm (to handle columns) should also be similar. Let’s scratch some code for it:
def walk_cols_for_connect4(board): # walk each column for i in range(len(board[0])): c, count = None, 0 ## inner loop to look for 4-connected within a column for j in range(len(board c, count = compare_element(board[j][i], c, count) if count == 4 and c != 'b': return (c, i, j,) return (None, -1, -1,)
The reader will observe that the above code for walk_cols_for_connect4 has a significant overlap with its rows’ counterpart. The reader might also note that both a row and column represent a sequence (or slice) on which connect4 must be checked. Thus, in the next version, we employ a ‘slice walker’ that is called by both the row and column functions.
# compare_element not repeated for brevity def walk_slices_for_connect4(board, outer, inner, is_reversed=False): for i in range(outer): c, count = None, 0 ## inner loop to look for 4-connected in a slice for j in range(inner): v = board[j][i] if is_reversed else board[i][j] c, count = compare_element(v, c, count) if count == 4 and c != 'b': return (c, i, j,) return (None, -1, -1,) def walk_rows_for_connect4(board): return walk_slices_for_connect4(board, len(board), len(board[0])) def walk_cols_for_connect4(board): return walk_slices_for_connect4(board, len(board[0]), len(board), is_reversed=True)
While duplicated code was mostly eliminated, it was necessary to add the is_reversed flag, as the order of indices when walking rows and columns is different. This flag does stick out as a little ugly, but is needed to manage the order of the indices. It is easier to explain this with an example.
To walk the first row, the board elements to be checked are:
Board[0][0], board[0][1], board[0][2], board[0][3], etc.
Walking the first column entails the following sequence of elements:
Board[0][0], board[1][0], board[2][0], board[3][0] and so on.
For now, the flag serves this purpose and we move on. (We will look at it again at the end of this section.)
As we further analyse the walk_slices_for_connect4 function, we observe that it performs three activities:
1. Enumerates all slices – driven by the ‘outer’ variable
2. Walks through one slice – driven by the ‘inner’ variable
3. Looks for four connected chips in a slice
In the most recent version, the slice walker handles both the Steps 1 and 2 above. To match the modularity of the code with the described steps, the final version of this section is arrived at, as follows:
def walk_a_slice_for_connect4(board, outer_index, inner, is_reversed=False): c, count, i = None, 0, outer_index for j in range(inner): ## Step 2 v = board[j][i] if is_reversed else board[i][j] c, count = compare_element(v, c, count) if count == 4 and c != 'b': return (c, i, j,) return (None, -1, -1,) def walk_slices_for_connect4(board, outer, inner, is_reversed=False): for i in range(outer): ## Step 1 c, x, y = walk_a_slice_for_connect4(board, i, inner, is_reversed) if c: return (c, x, y) return (None, -1, -1,) def walk_rows_for_connect4(board): return walk_slices_for_connect4(board, len(board), len(board[0])) def walk_cols_for_connect4(board): return walk_slices_for_connect4(board, len(board[0]), len(board), is_reversed=True)
While the above code looks reasonably modular, consider the complexity of extending this for the diagonals. By employing the is_reversed flag to swap the order of indices, we have managed to handle rows and columns. However, the value of indices for diagonals is quite different and that requires us to extend the definition of the simple flag to cover all the three types of slices. Such a solution is not very desirable, as it moves the complexity of slice construction to the slice walker.
One way this can be circumvented is to build a fresh slice from the original board cells. Given the limited board size, that approach may be acceptable in this example. But for large matrices, creating temporary slices can be quite costly in terms of both CPU and memory usage. Hence, it is not workable, in general. In the next section, we see how Python’s generators can help address this situation.
Solution using Python generators
We now rewrite the solution to our problem in terms of generators. These are used to generate an arbitrary slice that the check function operates on, which provides a clean separation of concerns. The final implementation using generators is shown below.
def col_generator(board, col): rows = len(board) for r in range(rows): yield (board[r][col], (r, col,),) def row_generator(board, row): cols = len(board[0]) for c in range(cols): yield (board[row][c], (row, c,),) def check_4connected(board, loc, slice_generator): c, count = None, 0 for t in slice_generator(board, loc): c, count = compare_element(t[0], c, count) if count == 4 and c != ‘b’: return c, t[1][0], t[1][1] return (None, -1, -1) def walk_slices_for_connect4(board, n_slices, generator_fn): for i in range(n_slices): c, x, y = check_4connected(board, i, generator_fn) if c: return (c, x, y) return (None, -1, -1,) def walk_rows_for_connect4(board): return walk_slices_for_connect4(board, len(board), row_generator) def walk_cols_for_connect4(board): return walk_slices_for_connect4(board, len(board[0]), col_generator)
If we consider the board to contain different top-level features like rows, columns and diagonals, then the above implementation can be mapped as:
- The top level functions like walk_rows_for_connect4 and walk_cols_for_connect4 express the intent to search for 4-connectedness over board features like, rows, columns and diagonals.
- The second level function walk_slices_for_connect4 realises the above by walking multiple instances of the same feature, regardless of the type of the feature.
- The third level function check_4connected performs the actual checking in the context of one instance of a feature.
- Generator functions, like row_generator or col_generator, which are the third level functions, call out into the generator to dynamically iterate on the feature-specific slice. Both the second and third level functions are intentionally kept agnostic of how the slice is obtained.
With this design, it is easier to implement walking both kinds of diagonals. For each diagonal type, a top-level function and a generator function have to be implemented. The second and third level functions just remain unchanged and work seamlessly. Readers are encouraged to try out the generator functions for the diagonals and then compare their work with a solution posted by the author (see References).
Using a real-life example, we have seen how Python’s generator functions can be used to realise and reap the benefits of key software design principles like the ‘separation of concerns’. As mentioned at the outset, leveraging this Python feature led to an elegant implementation that promotes extensibility and maintainability of the code.
