AbAb
bAbA
bbAAbAAA
This grid has two rectangles, one of which is emphasized below.... .A.A .... .A.AFinding 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
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_commonwhere 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_infoThe 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.
