Parallelogram Connectivity

Question

This is the hardest problem from the HackerRank contest University CodeSprint 2.

Problem Statement

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 a W (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.

Answer 1

Posting profiler stats would be helpful.

You have two colors, 'B' & 'W'. I submit that connected_set() should be mutating board so that already processed cells (nearby.add()) are marked 'D' for done (or marked with a number corresponding to the current set we're working on). The goal is to avoid having the flood-fill neighboring() function repeatedly re-visit a cell we're already done with.

Here's a similar idea. For each point, pre-calculate its set of within-bounds neighbor points and store the set with the point. Is there an opportunity to sometimes prune such stored sets after a region has been processed?

On the whole, the coding style is admirably clear.