Board game: Find maximum green points with restricted red points
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:
- Given a point
(i, j) - The possible directions to go are up to
(i + 1, j)and to the right to(i, j + 1). - For
(i + i, j), the number of red pieces in the rectangle,l_(i + 1)j, is equal to the limit of the previous celll_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 limitl_ij, you don't have to calculate the sum of(i + 1) * jcells for one step, but only the sum ofj + 1cells -jcells in the row plus the one stored value. The same goes for calculatingv_(i + 1)j, just use the stored valuev_ijplus the number of green pieces in the upper row. - 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. - 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.
Since corner (0, 0) is mandatory part of rectangle, whole task is rather simple. Algorithm goes like this:
assuming X, Y are dimension of the board:
green_counts, red_counts = count_pieces()
found_pos = None
found_count = 0
for y in range(0, Y):
x = find_x_for_y_with_max_red_pieces()
g = green_counts(x, y)
if g > found_count:
found_count = g
found_pos = x, y
print(found_pos)
First we create two dimensional array with red and green counts for rectangles (0,0) -> (x,y). Then we iterate over y. For every y we find largest x, for which red pieces limis is met. We calculate green pieces count and check, if it's better, than previous. Whole thing will run in O(n^2), as you need to calculate count of the pieces.
Note, that you might improve memory requirements even further (you don't need full two dimensional array, you only need "previous" row).
Question 2: what to do with float positions? The same. Sort x positions and replace them with index. So for example for points (0, 0), (0.2, 1), (0.2, 2.5), (0.4, 1) you would get (0, 0), (1, 1), (1, 2), (2, 1). Then use the algorithm above.
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)