Spider-Man ("Spidey") needs to get across town for a date with Mary Jane and his web-shooter is low on web fluid. He travels by slinging his web rope to latch onto a building rooftop, allowing him to swing to the opposite end of the latch point.
Write a function that, when given a list of buildings, returns a list of optimal rooftop latch points for minimal web expenditure.
Input
Your function will receive an array whose elements are subarrays in the form [h,w] where h and w represent the height and width, respectively, of each building in sequence
Output
An array of latch points (integers) to get from 0 to the end of the last building in the input list
Technical Details
An optimal latch point is one that yields the greatest horizontal distance gain relative to length of web rope used. Specifically, the highest horizontal distance yield per length unit of web rope used. Give this value rounded down to the nearest integer as a distance from Spidey's origin point (0)
At the start of each swing, Spidey selects a latch point based on his current position.
At the end of each swing, Spidey ends up on the opposite side of the latch point equal to his distance from the latch point before swing.
Spidey's initial altitude is 50, and will always be the same at the start and end of each swing. His initial horizontal position is 0.
To avoid collision with people/traffic below, Spidey must maintain a minimum altitude of 20 at all times.
Building height (h) range limits: 125 <= h < 250
Building width (w) range limits: 50 <= w <= 100
Inputs will always be valid.
Test Example
- Spidey's initial position is at `0`. His first latch point is marked at `76` (horizontal position) on `buildings[0]`.
- At the end of the swing, Spidey's position is at the point marked `B` with a horizontal position of `152`. The green arc represents Spidey's path during swing.
- The marker on the 3rd building and the arc going from point `B` to point `C` represent the latch point (`258`) and arc path for the next swing.
```python
buildings = [[162,76], [205,96], [244,86], [212,68], [174,57], [180,89], [208,70], [214,82], [181,69], [203,67]]
spidey_swings(buildings)# [76,258,457,643,748]
def spidey_swings(Q) :
    End = At = Pos = 0
    Left = []
    for V in Q :
        Left.append(End)
        End += V[1]
    Left.append(End)
    R = []
    while At < len(Q) :
        L = I = 0
        F = At
        while F < len(Q) :
            W = Q[F][0] - 20
            T = int((W * W - (W - 30) ** 2) ** .5)
            if Left[F] <= Pos + T :
                if End < Pos + T + T : T = max(1 + End - Pos >> 1,Left[F] - Pos)
                if Left[1 + F] < Pos + T : T = Left[1 + F] - Pos
                U = End <= Pos + T + T
                W = (T * T + (Q[F][0] - 50) ** 2) ** .5
                W = (T + T if Pos + T + T < End else End - Pos) / W
                if L < W or not I and U : N,L = T,W
                I = U
            F += 1
        R.append(Pos + N)
        Pos += N + N
        while At < len(Left) and Left[At] <= Pos : At += 1
        At -= 1
    return R
def spidey_swings(Q) :
    End = At = Pos = 0
    Left = []
    for V in Q :
        Left.append(End)
        End += V[1]
    Left.append(End)
    R = []
    while At < len(Q) :
        L = I = 0
        F = At
        while F < len(Q) :
            W = Q[F][0] - 20
            T = int((W * W - (W - 30) ** 2) ** .5)
            if Left[F] <= Pos + T :
                if End < Pos + T + T : T = max(1 + End - Pos >> 1,Left[F] - Pos)
                if Left[1 + F] < Pos + T : T = Left[1 + F] - Pos
                U = End <= Pos + T + T
                W = (T * T + (Q[F][0] - 50) ** 2) ** .5
                W = (T + T if Pos + T + T < End else End - Pos) / W
                if L < W or not I and U : N,L = T,W
                I = U
            F += 1
        R.append(Pos + N)
        Pos += N + N
        while At < len(Left) and Left[At] <= Pos : At += 1
        At -= 1
    return R