I saw this puzzle, supposedly credited as an interview question asked by Google: How would you find a winner in a tic-tac-toe board of arbitrary size ?
Let us see how we can check if a 3x3 tic-tac-toe board has a valid winner. A convenient representation of a square board like (I) is a sequence like (II), organized as row major mode. To see if there is a winner, we need to find the expected pattern 'XXX' or 'OOO' in a row, column or diagonal. So the real work is in partitioning the space into rows, columns and diagonals.
"""
-------------
| 0 | 1 | 2 |
------------- -------------------------------------
| 3 | 4 | 5 | ==> | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
------------- -------------------------------------
| 6 | 7 | 8 | (II)
-------------
(I)
"""
Let us start with defining a couple of convenience variables: (a) span = 3, which is the length of the edge of the square / board, (b) length = 9, which is the length of the sequence (= span*span) and (c) pos, which is the current position.
Getting rows is straight-forward: start from top-left corner and iterate over each element until a distance of span has been covered. Getting the columns requires traveling in step = span from the starting position. For example, if start is element at (0,1), which is pos = 1 itself, the next element in column-major traversal is (1,1) for which pos = (pos + span). Effectively, we always travel in distances of 'span' to the next
element in the column. Diagonal traversing requires us to start at a corner. If we start at top-left corner (0,0), which is pos = 0, the next diagonal element is pos + (span+1), the (+1) giving that diagonal movement (otherwise it would be a column-traversal). Similarly, if we start from bottom left corner (3,0) = position 6, which is pos = (length-span), the next element is at pos - (span-1) = 4. In short, we travel a positive step of (span+1) from top-left and negative step of (span-1) from bottom left to find next diagonal element. Iterations are limited to 'span' number of times. The algorithm should work neatly for any length which is a perfect square.
Now, to writing some code to do this elegantly. In typical C style, getting rows, columns and diagonals would look like this:
/* this is not compile clean C... */
int rows[length], columns[length], diagonals[2*span];
int i, j, k; k = 0;
for (i = 0; i < length; i += span)
for (j = 0; j < span, ++j)
{
rows[k] = i + j;
++k;
}
k = 0;
for (i = 0; i < span, ++i)
for (j = 0; j < length; j += span)
{
columns[k] = i + j;
++k;
}
k = 0;
for (i = 0; i < length; i += span+1)
diagonals[k] = i;
for (i = length-span; i > 0; i -= (span-1) )
diagonals[k] = i;
The loops are already getting unwieldy and I do not think code to check if a row has pattern 'XXX' is going to be any better with strcmp() and the likes. Attempting to use Python, I stumbled across a couple of nifty features: the function range(), which allows you to step in specific increments across a range, up or down, and list comprehension, a functional programming paradigm to apply filters on a given list of objects. For example, our sequence can be constructed with a single call to range(), and we can produce a list of all even numbers in the sequence, with a list comprehension. List comprehensions should be read from right to left: in this case for i in range(...), make a list containing sequence[i]
>>> length = 9
>>> sequence = range(length)
>>> print sequence
[0, 1, 2, 3, 4, 5, 6, 7, 8]
>>> print [sequence[i] for i in range(0, length, 2)]
[0, 2, 4, 6, 8]
>>>
With these features, the code becomes ridiculously simple and intiuitive:
import math
sequence_ = range(9)
length = len(sequence_)
span = int(math.sqrt(length))
# read list comprehensions from right to left...
rows = [[sequence_[i+j] for j in range(span)] for i in range(0, length, span)]
print "rows: ",rows
columns = [[sequence_[i+j] for j in range(0, length, span)] for i in range(span)]
print "columns: ",columns
diagonals = [[sequence_[i] for i in range(0, length, span+1)],
[sequence_[i] for i in range(length-span, 0, -(span-1))]]
print "diagonals: ", diagonals
The output looks like this:
rows: [[0, 1, 2], [3, 4, 5], [6, 7, 8]]
columns: [[0, 3, 6], [1, 4, 7], [2, 5, 8]]
diagonals: [[0, 4, 8], [6, 4, 2]]
So, given a tic-tac-toe as a sequence of characters such as 'XXOXXXXOO', it is trivial to partition them into rows, columns and diagonals. But wait ! it would have been easy to compare each row, column or diagonal against possible winning patterns 'XXX' and 'OOO'
Python gives us yet another feature: join() elements of a list into a string, if elements are either characters or strings. In quintessential Python style, '' is an empty string, and join() can be called on any string type, which means, all elements in the iterable type (sequence which is a list in this case) will be concatenated into a single string !
>>> sequence = [str(i) for i in range(9)] # list of strings containing numbers 0 - 9
>>> print sequence
['0', '1', '2', '3', '4', '5', '6', '7', '8']
>>> print [''.join([sequence_[i+j] for j in range(span)]) for i in range(0, length, span)]
[ '012', '345', '678' ]
If we generate a single list called partitions that has the rows, columns and diagonals - use extend() method of list - solving a tic-tac-toe board is then as simple as:
pattern_x, pattern_y = 'XXX', 'OOO'
if pattern_x in partitions:
winner = 'X'
else if pattern_y in partitions:
winner = 'O'
else:
winner = None
Now, that was a simple and elegant solution in a few lines of intuitive code...
