Post a Comment On: Only Python

In the previous post, I talked about the 17x17 challenge, but did not provide any code.  Today, I will describe the code I use to represent a given grid.  Consider the following grid where A and b are used to represent two different colours:
AbAb bAbA bbAAbAAA This grid has two rectangles, one of which is emphasized below
.... .A.A .... .A.A Finding such a rectangle in a small grid is fairly easy to do.  A naive, but very inefficient way to do this is to have a function like the following:
def find_rect_candidates(row_1, row_2): points_in_common = [0, 0, ...] # one per colour for i, point in enumerate(row_1): if row_1[i] == row_2[i]: points_in_common[row_1[i]] += 1 return points_in_commonwhere row_x[i] is set to a given colour, represented by an integer (0, 1, 2, ...). For an NxN grid, the first loop is of order N.  Note that this does not tell us (yet) if we have found a rectangle; we still have to loop over points_in_common and see if any entry is greater than 1.

A better way to do the comparison, which does not grow with N, is mentioned in this post and is based on the following observation:  for a given row, at a given point, a given colour is either present (True or 1) or not (False or 0). Thus, a given colour distribution on a single row can be represented as a string of 0s and 1s ... which can be thought of as the binary representation of an integer.  For example, the row containing the colour "A" in the pattern ".....A..A" can have this pattern represented by the number 9="1001".  Consider another row represented by the number 6="110". These two rows have no points in common (for this colour) and hence do not form a rectangle.  If we do a bitwise "and" for these two rows, i.e. 9&6 we will get zero.  This is achieved by a single operation instead of a series of comparisons.

What happens if two rows have a single point in common (for a given colour) so that no rectangle is present?  For example, consider 9="1001" and 15="1110".  If we do a bitwise "and" we have

answer = 9 & 15 = 8 = "1000"

Taking the bitwise "and" of answer and answer-1, we get

answer & (answer-1) = 8 & 7 = "1000" & "111" = 0.

If we have two points (1 bit) in common, it is easy to see that the bitwise comparison of answer & (answer-1) will not give zero.

Going back to the function above, we could rewrite it instead as follows:

def find_rect_candidates(row_1, row_2, colours): points_in_common = [0, 0, ...] # one per colour for c in colours: points_in_common[c] = row_1[c] & row_2[c] return points_in_common

where we still have to do the same (N-independent) processing of the return value as with the function above to determine if we do have rectangles.

Now, without further ado, here is the basic code that I use to represent a grid, together with two utility functions.

def rectangles_for_two_rows(row_1, row_2): '''returns 0 if two rows (given colour, encoded as a bit string) do not form a rectangle - otherwise returns the points in common encoded as a bit string''' intersect = row_1 & row_2 if not intersect: # no point in common return 0 # perhaps there is only one point in common of the form 00010000... if not(intersect & (intersect-1)): return 0 else: return intersect def count_bits(x): '''counts the number of bits see http://stackoverflow.com/questions/407587/python-set-bits-count-popcount for reference and other alternative''' return bin(x).count('1') class AbstractGrid(object): def __init__(self, nb_colours, max_rows, max_columns): self.nb_colours = nb_colours self.colours = list(range(nb_colours)) self.max_rows = max_rows self.max_columns = max_columns self.powers_of_two = [2**i for i in range(max_columns)] self.grid = {} def initialise(self): '''initialise a grid according to some strategy''' raise NotImplemented def print_grid(self): '''prints a representation of the grid. Used for diagnostic only - no need to optimize further.''' for row in self.grid: row_rep = [] for column in range(self.max_columns-1, -1, -1): for colour_ in self.colours: if self.powers_of_two[column] & self.grid[row][colour_]: row_rep.append(str(colour_)) print("".join(row_rep)) def identify_intersect_points(self): '''identifies the dots that contribute to forming rectangles''' # possibly could cut down the calculation time by only computing # for colours that have changed... nb_intersect = [0 for colour in self.colours] intersect_info = [] for colour in self.colours: for row in self.grid: for other_row in range(row+1, self.max_rows): intersect = rectangles_for_two_rows( self.grid[row][colour], self.grid[other_row][colour]) if intersect != 0: nb_intersect[colour] += count_bits(intersect) intersect_info.append([colour, row, other_row, intersect]) return nb_intersect, intersect_info
The actual code I use has a few additional methods introduced for convenience.  If anyone can find a better method to identify intersection points between rows (from which rectangles can be formed), I would be very interested to hear about it.