This is the hardest problem from the HackerRank contest University CodeSprint 2.
Consider a hexagonal board with \$ n \times m \$ cells where each cell is black or white. The board's rows are numbered from bottom to top, and its columns are numbered from left to right (where columns at a \$ 60° \$ incline from rows). We say that the cell in the \$i^{th} \$ row and \$ j^{th} \$ column is at coordinate \$ (i,j) \$.
We define parallelogram \$R(x_1,y_1,x_2,y_2)\$ on the board as the set of cells \$ \left\{ (i,j) : x_1 \leq i \leq x_2, y_1 \leq j \leq y_2 \right\} \$.
Two cells, \$ a \in R \$ and \$ b \in R \$ are connected with respect to set \$R\$ if they satisfy the following conditions:
- They are of the same color.
- They are directly touching each other or there is a cell \$ c \in R \$ of the same color such that \$c\$ directly touches \$a\$ and \$c\$ and \$b\$ are connected.
A set of cells, \$ A \subset R \$, is connected with respect to set \$R\$ if \$ \forall a,b \in A \$, \$a\$ and \$b\$ are connected with respect to \$R\$.
Given the configuration of the board's white and black cells, answer \$q\$ queries in the form of paralelogram, \$R(x_1,y_1,x_2,y_2)\$. For each parallelogram, find the number of maximal inclusive connected sets with respect to \$R(x_1,y_1,x_2,y_2)\$ and print it on a new line.
Input Format
The first line contains two space-separated integers describing the respective values of \$n\$ (the number of rows) and \$m\$ (the number of columns).
Each line \$i\$ of the \$m\$ subsequent lines contains a string of \$m\$ characters describing row \$i\$ (where \$ 1 \leq u \leq n \$) of the board from column \$1\$ to column \$m\$. Each character in this string is a
B
(for black) or aW
(for white).The next line contains an integer denoting \$q\$ (the number of queries). Each of the subsequent lines contains a four space-separated integers describing the respective values of \$x_1\$, \$y_1\$, \$x_2\$, and \$y_2\$ for a query.
Constraints
- \$ 1 \leq n,m \leq 800 \$
- \$ 1 \leq q \leq 15000 \$
- \$ 1 \leq x_1 \leq x_2 \leq n \$
- \$ 1 \leq y_1 \leq y_2 \leq m \$
Output Format
For each query, print number of maximal inclusive connected components with respect to \$R\$ on a new line.
Sample Input
4 5 BWBBW BWWBB WBWWW BWBBW 6 1 1 1 1 1 1 2 2 1 1 4 5 3 1 4 4 2 1 3 3 2 1 4 4
Sample Output
1 2 6 4 3 5
My algorithm
To determine the connected set of points given a parallelogram and a starting point, I initialize a set connected
of just the given point and a set nearby
of all neighboring points which are on the parallelogram. Then, while nearby
contains any points, I remove a point, and if it is the same color as the original point, I add it to connected
and all of its neighbors which are on the parallelogram and not in connected
or nearby
to nearby
. Then, the maximal connected set is in connected
.
To determine the number of connected sets, I maintain a set found
which contains any point which was in an already discovered set. Then, for every point on the parallelogram, if that point has not been added to found
, I add all connected points to found
and increment my count of connected sets.
This implementation of this algorithm solves about 25% of the test cases on HackerRank and times out on the rest.
#!/bin/python3
from collections import namedtuple
Point = namedtuple('Point', 'x y')
Point.neighboring = lambda pt: [
Point(pt.x + 1, pt.y),
Point(pt.x - 1, pt.y),
Point(pt.x, pt.y + 1),
Point(pt.x, pt.y - 1),
Point(pt.x + 1, pt.y - 1),
Point(pt.x - 1, pt.y + 1)
]
def connected_sets(board):
sets = 0
found = set()
for y in range(len(board[0])):
for x in range(len(board)):
if Point(x, y) in found:
continue
found |= connected_set(board, Point(x, y))
sets += 1
return sets
def connected_set(board, pt):
connected = {pt}
color = board[pt.x][pt.y]
def in_bounds(point):
return 0 <= point.x < len(board) and \
0 <= point.y < len(board[point.x])
nearby = set(filter(in_bounds, pt.neighboring()))
while nearby:
pt = nearby.pop()
if board[pt.x][pt.y] == color:
connected.add(pt)
for point in pt.neighboring():
if in_bounds(point) and \
point not in connected and \
point not in nearby:
nearby.add(point)
return connected
def split_2d(matrix, x1, y1, x2, y2):
return tuple(map(lambda l: l[y1:y2], matrix[x1:x2]))
def main():
n = int(input().split()[0])
board = tuple(tuple(input()) for _ in range(n))
q = int(input().strip())
for _ in range(q):
x1, y1, x2, y2 = map(int, input().split(' '))
print(connected_sets(split_2d(board, x1 - 1, y1 - 1, x2, y2)))
if __name__ == '__main__':
main()
Because this is certifiably a hard problem, an answer needn't show any graph theory which is likely necessary to get this program out of time-limit-exceeded, even though it is tagged as such. Merely a review of the algorithm and code at hand and what speedup is available without drastically changing the algorithm would be acceptable.