Long time lazy flying bird can survive - serial break between two arrays
for two arrays:
import numpy as np L1 = np.array([3, 1, 4, 2, 3, 1]) L2 = np.array([4, 8, 9, 5, 6, 7])
I want to efficiently find the longest in-between gap that exists.
For example, let i
is the i-th index of both arrays.
i = 0: elements = (3,4) -> gap in range 3-4 -> longest path = 1
i = 1: elements = (1,8) -> 3-4 intersect 1-8 is 3-4 -> longest path = 2
i = 2: elements = (4, 9) -> 3-4 intersect 4-9 is NULL -> longest path = 2
##this is what slows my approach down
#now, we must return to i = 1
i = 1: elements = (1,8) -> candidate interval is 1-8 -> path = 1, longest path = 2
i = 2: elements = (4,9) -> 1-8 intersect 4-9 is 4-8 -> path = 2, longest path = 2
i = 3: element = (2,5) -> 4-8 intersect 2-5 is 4-5 -> path = 3, longest path = 3
...
If you try to visualize it, it looks a bit like a flappy bird and so I'm trying to find the longest time a bird can stay at the same level without dying
I need a way not to trace back, so I go through every i
once. Any suggestions? preferably in python
Update
I wrote some code to visualize the problem (note that here I assumed that the maximum number of lines is 10, this is not always the case:
def get_flappy_matrix(ceiling, floor):
'''
given ceiling and floor heights
returns matrix of 1s and 0s
representing the tunnel
'''
ceil_heights = np.array(ceiling)
floor_heights = np.array(floor)
nmb_cols = len(ceil_heights)
flappy_m = np.ones(shape=(10, nmb_cols), dtype=np.int)
for col in range(nmb_cols):
for row in range(ceil_heights[col], floor_heights[col]):
flappy_m[row, col] = 0
return flappy_m
N = 6
L1 = np.array([3, 1, 4, 2, 3, 1])
L2 = np.array([4, 8, 9, 5, 6, 7])
m = get_flappy_matrix(L1, L2)
plt.pcolor(m, cmap=plt.cm.OrRd)
plt.yticks(np.arange(0, 10, 1), range(0, 11))
plt.xticks(np.arange(0, N+1),range(0,N+1))
plt.title(str(max_zero_len))
plt.gca().invert_yaxis()
plt.gca().set_aspect('equal')
plt.show()
Now, from another answer, this is one (still slow for large input) approach to the problem:
max_zero_len = max(sum(1 for z in g if z == 0) for l in m for k, g in itertools.groupby(l))
print(max_zero_len)
# 5
source to share
Keep a window with sequential openings through which a bird can fly. Expand it in the desired hole one at a time, and if necessary, remove the holes on the left using the following strategy. When you reach the end, the longest window you have managed to build is the solution.
Trace the bottom top wall in the window and the lowest top wall that follows this wall and the bottom top wall that follows this wall to the last top wall in the window. Do something similar for the lower walls. For example, if the window goes from holes 3 to 9:
| | | | | | | | upper wall sections
| | | | | | |
| | | |
| | |
| | |
... | ------------- window
| -------------
| |
| | | | |
| | | | | | | lower wall sections
2 3 4 5 6 7 8 9
wall numbers
then the upper boundary walls are 6, 8, and 9, and the lower boundary walls are 4 and 9. (We break ties by selecting the walls on the right).
Let's say we expand the window to the tenth hole, and the tenth hole looks like this:
| | | | | | | | |upper wall sections
| | | | | | | |
| | | | |
| | | |
| | |
... | --------------- window
| ---------------
| |
| | | | |
| | | | | | | | lower wall sections
2 3 4 5 6 7 8 9 10
wall numbers
The top wall 10 is lower than the top walls 9 and 8, so 9 and 8 are no longer upper bounds. The upper bounds are now 6 and 10, and the lower bounds are now 4, 9 and 10.
On the other hand, if hole 10 looks like this:
| | | | | | | | | upper wall sections
| | | | | | |
| | | |
| | |
| | | |
... | |
| |
| | |
| | | | | |
| | | | | | | |
2 3 4 5 6 7 8 9 10
wall numbers
The bottom wall 10 is higher than the bottom top border, so we need to remove the walls to the left of the window. We advance the window to start at hole 7, deleting everything up to the oldest bottom border (wall 6), and we find that the next top border, wall 8, is high enough to create a valid window:
| | | | | | | | | upper wall sections
| | | | | | |
| | | |
| | | ------- window
| | | |
... | |
| |
| | |
| | | | | |
| | | | | | | |
2 3 4 5 6 7 8 9 10
wall numbers
If the top wall 8 was still too low, we would move the window to start at hole 9, etc.
source to share