Board game: Find maximum green points with restricted red points

Question

Scenario:

• On a checkerboard of size MxN, there are red and green pieces.

• Each square on the board may contain any number of pieces, of any color. (We can have 5 pieces - 3 green and 2 red in the same square, or for e.g. green green, or red red, or whatever number)

• I'm looking for an axis-aligned rectangle on the board with as many green pieces as possible.

• However, the rectangle may not contain more than a given number of red pieces.

• One corner of the rectangle must be (0,0).

Example:

Board size is 6x4, red pieces are marked "x", green pieces are marked "o".

      +-+-+-+-+-+-+
    3 | | | |o|x|o|
      +-+-+-+-+-+-+
    2 |o| |x| | |o|
      +-+-+-+-+-+-+
    1 |o| |o| |o|x|
      +-+-+-+-+-+-+
    0 | |o| |x| |x|
      +-+-+-+-+-+-+
       0 1 2 3 4 5

• If we allow 2 red pieces, then (4,2) is an optimal solution, because the area between (0,0) and (4,2) contains 5 green pieces and 2 red pieces. No point with up to 2 red pieces contains more than 5 green pieces. (3,3) is also an optimal solution.

• If we allow 3 red pieces, then (4,3) is the only optimal solution, with 6 green pieces.

I'm given:

• the board size,
• the coordinates of all green and red pieces,
• the number of allowed red pieces ("maxRed")

Goal: For any given "maxRed", the class should be able to calculate coordinates (x,y) such that the axis-aligned rectangle between (0,0) and (x,y) contains at most "maxRed" red pieces, and the number of green pieces is maximal.

My Question:

Solving this by traversing all the possible matrices (in order to find the largest triangle) with maximum green points and the given maximum red points is clearly inefficient, I'm trying to find a way to find that without using brute-force.

Some intuition:

I thought looking at the closet maximum red points that are allowed to be in the rectangle (if maxRed = 2, then closest two red points) from the origin (0,0), and then checking all the possible 'extensions' of the rectangle from that points (just width, just height, width & height, and so on..) which is also not so efficient I believe (in worst case scenario it's inefficient).

Then I thought maybe if maxRed equals to 2 and we found the closest two red points, then we can check where is the 3rd maxRed (if it doesn't exist the return the whole matrix as rectangle), and somehow search 'less' the number of options - still need to think of all the cases (the 3rd point can be on top that current rectangle, or from the left of it, or in diagonal) and if it's from e.g. the top of it, then there may be a case that I can extend it in width - and maybe not (because maybe there's another red points from the right of it). but you get the idea, somehow find an algorithm which isn't brute-force and as efficient as possible.

Question 2: Also another interesting question I'd like to know how to approach: How would you solve the problem if the coordinates were defined as "float", meaning that the board has no grid on it. Now you are required to return the best floating point (x,y) coordinates, such that the area between (0,0) and (x,y) contains at most "maxRed" red pieces and the number of green pieces is maximal. How would you find it, and what would the complexity be?

Case 1 for e.g.:

Case 2:

Another in-depth intuition:

Edge cases: if redpoints in the map are less than 2, return rectangle of all the matrix.

1. Then, We start by creating our rectangle cover the closet two red points. (for e.g. our rectangle will extend to y = 3, and x = 2) cover all that area.

2. Then we check what's the closet y axis of our red points which is bigger than our current rectangle's y (which is y=3), and what's the closet x axis of our red points which is bigger than our current rectangle's x (which is x=2), the closet x and y can also come from the same 3rd red point, it doesn't have to be from two different red points.

3. In that way we can see 'how far' we can extend our rectangle.

4. Then, in step 3, we will try iteratively go up (i+1) if possible, and check all the extensions of j, then go i+2 and check all the j..

4.1 then go right (j+1) if possible of course, and check all the i, then keep going j+2, and so on..

and return the highest rectangle we could build - and we won't check too many i, and j's in the process.

But that's not enough,

because there's an edge case like in the 'Case 2'

which there there're 2 red points in the same spot, so we will have to carefully check if the second farthest red point (it's farther if it's x or y or both are bigger than the first closet red point obviously) has another red point in it, if it does have in total two red points in the same cell, then we extend until its x or y - and from there keep extending up/down.

(we can see if its in diagonal or just from the right or just from the top) if it's from the right of the first red point (meaning x is bigger than our current x - only in x axis) then we can check how far we can extend top - by looking at the list of red points if we have on top of us red points, if not then we extend till the end immediately, and same approach if the 2nd red point in on top of us, we can check how far to extend to the right.

and if the 2nd red point is in diagonal of us (like in the usage example) then we check how far we can extend to the left only, and how far we can extend to top only, and see what's better for us in regard of searching for more green points.

This solution should work I guess, and give about O(1) Time complexity I guess.

Answer 1

If you consider that there are only two integer variables, i, j with 0 <= i <= M, 0 <= j <= N, you can probably solve this using dynamic programming. I'll try to write this both clearly and without a LaTeX engine, so please bear with me.

Say that you create four M * N matrices of integers G, R, V, and L. For each point (i, j), g_ij denote the number of green pieces on that square, and r_ij the number of red pieces. v_ij denotes the number of green pieces within the rectangle (0, 0) - (i, j), or 0 if the number of red pieces is too high, and l_ij denotes the number of red pieces in the rectangle, or infinity if the original value was going to exceed the limit. If I talk about the value of a cell, I mean v_ij, the limit of a cell is equivalent to l_ij.

Starting at the point (0, 0), a programming approach would be as follows:

1. Given a point (i, j)
2. The possible directions to go are up to (i + 1, j) and to the right to (i, j + 1).
3. For (i + 1, j), the number of red pieces in the rectangle, l_(i + 1)j, is equal to the limit of the previous cell l_ij + the number of red pieces in the row above the rectangle, so the cells (0, j) through (i + 1, j). If you use the limit l_ij, you don't have to calculate the sum of (i + 1) * j cells for one step, but only the sum of j + 1 cells -j cells in the row plus the one stored value. The same goes for calculating v_(i + 1)j, just use the stored value v_ij plus the number of green pieces in the upper row.
4. If the limiting number of red pieces is exceeded, you can create a rectangle between (i + 1, j) and the upper right corner (M, N) and designate the limit of all those cells as exceeded - because all possible rectangles that can be formed there must contain the rectangle (0, 0) - (i + 1, j) and thus they must contain too many red pieces. The calculations to go right are very similar.
5. Once there are no more unknown pieces, just find the highest value in V in O(MN) time and you're done.

For your second question, a possible approximation would be to take a stepsize between 0 and 1, and divide all the values by that step, then round down, so (2/3, 7/5) with a step size of 1/10 would become (6, 14). Then apply the algorithm using those step. You can run it multiple times, with decreasing step sizes, storing and transforming the matrix V between runs so you can avoid a lot of the calculations. I hope this helped!

UPDATE: now with an example execution

An example, in each cell (x, y) denotes the number of green and red pieces, respectively. Next to it are the matrices G and R - empty values mean 0. The limit on the number of red pieces is 3.

                                       G                   R
  +-----+-----+-----+-----+    +---+---+---+---+   +---+---+---+---+ 
3 |(1,2)|     |     |(4,0)|  3 | 1 |   |   | 4 | 3 | 2 |   |   |   | 
  +-----+-----+-----+-----+    +---+---+---+---+   +---+---+---+---+ 
2 |     |(3,1)|     |(1,2)|  2 |   | 3 |   | 1 | 2 |   | 1 |   | 2 | 
  +-----+-----+-----+-----+    +---+---+---+---+   +---+---+---+---+ 
1 |(1,1)|(1,1)|     |     |  1 | 1 | 1 |   |   | 1 | 1 | 1 |   |   | 
  +-----+-----+-----+-----+    +---+---+---+---+   +---+---+---+---+ 
0 |     |(0,1)|(3,1)|(1,1)|  0 |   |   | 3 | 1 | 0 |   | 1 | 1 | 1 | 
  +-----+-----+-----+-----+    +---+---+---+---+   +---+---+---+---+ 
     0     1     2     3         0   1   2   3       0   1   2   3   

Starting at (0, 0), we have 0 red pieces and 0 green pieces, so V and L look as follows:

          V                   L         
  +---+---+---+---+   +---+---+---+---+ 
3 |   |   |   |   | 3 |   |   |   |   | 
  +---+---+---+---+   +---+---+---+---+ 
2 |   |   |   |   | 2 |   |   |   |   | 
  +---+---+---+---+   +---+---+---+---+ 
1 |   |   |   |   | 1 |   |   |   |   | 
  +---+---+---+---+   +---+---+---+---+ 
0 | 0 |   |   |   | 0 | 0 |   |   |   | 
  +---+---+---+---+   +---+---+---+---+ 
    0   1   2   3       0   1   2   3    

For completeness, I do fill zero values in V and L. Now we can go up, to (1, 0), and right, to (0, 1). Up, we get l_10 = l_00 + r_10 = 0 + 1 = 1, and v_10 = v_00 + g_10 = 0 + 1 = 1. To the right, we get l_01 = l_00 + r_01 = 0 + 1 = 1, and v_01 = v_00 + g_01 = 0. This gives us the following situation:

          V                   L         
  +---+---+---+---+   +---+---+---+---+ 
3 |   |   |   |   | 3 |   |   |   |   | 
  +---+---+---+---+   +---+---+---+---+ 
2 |   |   |   |   | 2 |   |   |   |   | 
  +---+---+---+---+   +---+---+---+---+ 
1 | 1 |   |   |   | 1 | 1 |   |   |   | 
  +---+---+---+---+   +---+---+---+---+ 
0 | 0 | 0 |   |   | 0 | 0 | 1 |   |   | 
  +---+---+---+---+   +---+---+---+---+ 
    0   1   2   3       0   1   2   3    

We can now go up from (1, 0), right from (1, 0), which is equivalent to going up from (0, 1), and we can go right from (0, 1). If we go up from (1, 0) to (2, 0), we get l_20 = l_10 + r_20 = 1 + 0 = 1 and v_20 = v_10 + g_20 = 1 + 0 = 1. If we go right from (1, 0) to (1, 1), we get l_11 = l_10 + r_01 + r_11 = 1 + 1 + 1 = 3. Note that this is exactly the same as going up from (0, 1), as l_11 = l_01 + r_10 + r_11 = 1 + 1 + 1 = 3. Similarly v_11 = v_10 + g_01 + g_11 = 1 + 1 = 2. Finally, if we go right from (0, 1) to (0, 2), we get l_02 = l_01 + r_02 = 1 + 1 = 2 and v_02 = v_01 + g_02 = 0 + 3 = 3. This results in the following schema:

          V                   L         
  +---+---+---+---+   +---+---+---+---+ 
3 |   |   |   |   | 3 |   |   |   |   | 
  +---+---+---+---+   +---+---+---+---+ 
2 | 1 |   |   |   | 2 | 1 |   |   |   | 
  +---+---+---+---+   +---+---+---+---+ 
1 | 1 | 2 |   |   | 1 | 1 | 3 |   |   | 
  +---+---+---+---+   +---+---+---+---+ 
0 | 0 | 0 | 3 |   | 0 | 0 | 1 | 2 |   | 
  +---+---+---+---+   +---+---+---+---+ 
    0   1   2   3       0   1   2   3    

We can now go up from (2, 0), right from (2, 0), which is equivalent to going up from (1, 1), right from (1, 1), which is equivalent to going up from (0, 2), or right from (0, 2). If we go up from (2, 0) to (3, 0), we get l_30 = l_20 + r_30 = 1 + 2 = 3 and v_30 = v_20 + g_30 = 1 + 1 = 2. We can calculate (2, 1) by going up from (2, 0), but going up from (1, 1) allows us to do the same calculation with a larger portion of the rectangle pre-calculated (4 cells instead of 3). We get l_21 = l_11 + r_20 + r_21 = 3 + 0 + 1 = 4. Since this exceeds the limit, v_21 = 0. Now any rectangle that contains (2, 1) will have exactly the same cells as (2, 1), including those that add up to 4 red pieces. Therefore, all rectangles that contain (2, 1) must be invalid. These are all cells with x >= 2 and y >=1. We give them l_xy = Inf for explicitness. Cell (1, 2) contains (0, 0), but because l_12 = l_11 + r_02 + r_12 = 3 + 1 + 0 = 4, the cell is invalid, as is (1, 3) following the same logic as above.

Finally, if we go right from (0, 2) to (0, 3), we get l_03 = l_02 + r_03 = 2 + 1 = 3 and v_03 = v_02 + g_03 = 3 + 1 = 4. This results in the following schema:

          V                   L         
  +---+---+---+---+   +---+---+---+---+ 
3 | 2 | 0 | 0 | 0 | 3 | 3 |Inf|Inf|Inf| 
  +---+---+---+---+   +---+---+---+---+ 
2 | 1 | 0 | 0 | 0 | 2 | 1 |Inf|Inf|Inf| 
  +---+---+---+---+   +---+---+---+---+ 
1 | 1 | 2 | 0 | 0 | 1 | 1 | 3 |Inf|Inf| 
  +---+---+---+---+   +---+---+---+---+ 
0 | 0 | 0 | 3 | 4 | 0 | 0 | 1 | 2 | 3 | 
  +---+---+---+---+   +---+---+---+---+ 
    0   1   2   3       0   1   2   3    

So as you can see, the rectangle with the highest value is the one formed with points (0, 3) with value 4, and we found this out while calculating only 10 out of 16 cells. Of course, the upper bound for this algorithm is O(MN), but in practice that is unavoidable, because consider the case where there are no red pieces or the limit is very high. Then you must still calculate the sum of all M * N cells.

Answer 2

O(n log n) solution, where n is the number of pieces

Here is an algorithm that works by scanning the pieces rather than the grid. I think it runs in O(p log p), where p is the number of pieces, rather than O(grid_size^2).

It is a sort of double sweep line algorithm. Imagine two lines, a horizontal line that defines the top of the rectangle (top in the code) and a vertical line (x) that defines the right side. The top line starts at top of the grid the y-axis and the vertical line starts at the y-axis. The vertical line sweeps to the right and an action is taken when it reaches a piece. If the piece lies below the top line, the piece is added to the current rectangle. If there would be too many red pieces, then the horizontal line is swept downward until the number of red pieces is within the limits. Any green pieces that are at or above the horizontal line are removed, because they are not in the new rectangle. Before moving the top of the rectangle down, the number of green pieces is checked to see if it a new maximum.

Works for floating point coordinates.

In a manner analogous to the way python's range() excludes the upper bound, the rectangle includes (0,0) but excludes the bounds returned by the function. For example, the test case returns ((4,4),5) meaning the rectangle defined by 0 <= x < 4 and 0 <= y < 4 has 5 green pieces (note the '<' on the upper bound). For integer coordinates, the rectangle is (0,0) to (3,3) inclusive. For floating point coordinates, the upper bound is exclusive of the given point.

import sortedcontainers as sc   # http://www.grantjenks.com/docs/sortedcontainers/

X,Y,Color = 0,1,2

def solve(pieces, size, max_reds):
    # Sort pieces by x, then red before green, then bottom-to-top
    pieces.sort(key=lambda t:(t[X],t[Color]=='g',t[Y]))

    # These keep track of the pieces that are in the rectangle. They
    # are sorted by 'y' value, so it is easy to remove pieces when 
    # 'top' is lowered due to too many reds in the rectangle.
    reds_in_rect = sc.SortedKeyList(key=lambda t:t[Y])
    greens_in_rect = sc.SortedKeyList(key=lambda t:t[Y])

    # For keeping track of the maximum number of green 
    # pieces and the corresponding coordinates.
    max_greens = 0
    max_x = 0
    max_y = 0

    # 'top' scans from top to bottom and represents the top of
    # the current rectangle.  It gets lowered to remove red pieces
    # from the rectangle when there are too many of them.   
    top = size[Y]

    # The pieces are sorted so this loop scans the pieces left-to-right.
    # If multiple pieces have the same x-coordinate, red ones come before
    # green ones, then lower ones before higher ones.
    for x,y,p in pieces:

        # Only pieces below the top of the rectangle are considered.
        # And they are added to the rectangle
        if y < top:

            if p == 'g':
                greens_in_rect.add((x,y,p))

            elif p == 'r':
                reds_in_rect.add((x,y,p))

                # If there are too many red pieces in the rectangle, 'top' gets
                # lowered to the 'y' value of the top-most red piece.  Then any
                # red or green pieces at or above the new 'top' get removed from
                # the rectangle.
                if len(reds_in_rect) > max_reds:

                    # before lowering the top of the rectangle check if current
                    # rectangle has a maximum number of green pieces
                    if len(greens_in_rect) > max_greens:
                        max_greens = len(greens_in_rect)
                        max_x = x
                        max_y = top

                    # lower to top to the 'y' value of the highest
                    # red piece seen so far
                    top = reds_in_rect[-1][Y]

                    # remove any red pieces at or above the top
                    # of the new rectangle
                    while reds_in_rect and reds_in_rect[-1][Y] >= top:
                        reds_in_rect.pop()

                    # remove any green pieces at or above the top
                    # of the new rectangle
                    while greens_in_rect and greens_in_rect[-1][Y] >= top:
                        greens_in_rect.pop()

    # last check of the number of green pieces
    if len(greens_in_rect) > max_greens:
        max_greens = len(greens_in_rect)
        max_x = size[X]
        max_y = top

    return (max_x, max_y), max_greens

The test case:

#    +-+-+-+-+-+-+
#  3 | | | |o|x|o|
#  +-+-+-+-+-+-+
#  2 |o| |x| | |o|
#    +-+-+-+-+-+-+
#  1 |o| |o| |o|x|
#    +-+-+-+-+-+-+
#  0 | |o| |x| |x|
#    +-+-+-+-+-+-+
#     0 1 2 3 4 5

size = 6,4
max_reds = 2

red = [(3,0), (5,0), (5,1), (2,2), (4,3)]
green = [(1,0), (0,1), (2,1), (4,1), (0,2), (5,2), (3,3), (5,3)]

pieces = [(x,y,'r') for x,y in red] + [(x,y,'g') for x,y in green]

solve(pieces, size, max_reds)  # --> returns ((4,5),5)