[SOLVED] Board game: Find maximum green points with restricted red points

Issue

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 6×4, 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.:
enter image description here

Case 2:
enter image description here

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.

Solution

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.

Answered By – Ruben Helsloot

Answer Checked By – Gilberto Lyons (BugsFixing Admin)

Leave a Reply

Your email address will not be published. Required fields are marked *