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]

Difficulty: interview

Starter code:

def spidey_swings(building_params):
	

Solutions:
def spidey_swings(building_params):
    buildings = get_buildings(building_params)
    end_position = get_total_length(buildings)
    latch_positions = []
    jump_position = 0
    while is_not_possible_to_reach_the_end(buildings, jump_position, end_position):
        candidate_jumps = [
            building.get_variables_for_max_displacement(jump_position)
            for building in buildings
            if building.is_reachable(jump_position)
        ]
        candidate_jumps.sort(reverse=True)
        _, latch_position, jump_position = candidate_jumps[0]
        latch_positions.append(latch_position)

    candidate_final_jumps = [
        building.get_variables_aiming_end(jump_position, end_position)
        for building in buildings
        if (building.is_reachable(jump_position) and
            building.is_possible_to_reach_the_end(jump_position, end_position))
    ]
    candidate_final_jumps.sort(reverse=True)
    _, latch_position = candidate_final_jumps[0]
    latch_positions.append(latch_position)

    return latch_positions


def get_buildings(building_params):
    pos = 0
    buildings = []
    for (height, width) in building_params:
        building = Building(height, width, pos)
        buildings.append(building)
        pos += width
    return buildings


def get_total_length(buildings):
    return sum(building.width for building in buildings)


def is_not_possible_to_reach_the_end(buildings, jump_position, end_position):
    return not any(building.is_possible_to_reach_the_end(jump_position, end_position)
                   for building in buildings)


class Building:
    def __init__(self, height, width, pos):
        self.height = height
        self.width = width
        self.pos = pos

    def max_rope_length(self):
        return self.height - 20

    def distance_to_rooftop(self):
        return self.height - 50

    def max_horizontal_displacement(self):
        hypotenuse = self.max_rope_length()
        vertical = self.distance_to_rooftop()
        return (hypotenuse ** 2 - vertical ** 2) ** .5

    def latch_pos_for_max_displacement(self, jump_pos):
        if jump_pos < self.pos - self.max_horizontal_displacement():
            return None
        if jump_pos < self.pos + self.width - self.max_horizontal_displacement():
            return int(jump_pos + self.max_horizontal_displacement())
        if jump_pos < self.pos + self.width:
            return int(self.pos + self.width)
        return None

    def rope_length_for_max_displacement(self, jump_pos):
        horizontal = (self.latch_pos_for_max_displacement(jump_pos) - jump_pos)
        vertical = self.distance_to_rooftop()
        return (horizontal ** 2 + vertical ** 2) ** .5

    def advanced_distance_for_max_displacement(self, jump_pos):
        return (self.latch_pos_for_max_displacement(jump_pos) - jump_pos) * 2

    def ratio_max_displacement_rope(self, jump_pos):
        return (self.advanced_distance_for_max_displacement(jump_pos) /
                self.rope_length_for_max_displacement(jump_pos))

    def get_variables_for_max_displacement(self, pos):
        latch_pos = self.latch_pos_for_max_displacement(pos)
        next_jump_pos = pos + self.advanced_distance_for_max_displacement(pos)
        ratio = self.ratio_max_displacement_rope(pos)
        return ratio, latch_pos, next_jump_pos

    def latch_pos_aiming_end(self, jump_pos, end_pos):
        max_latch_pos = (jump_pos + end_pos) / 2
        if jump_pos < self.pos - self.max_horizontal_displacement():
            return None
        if jump_pos <= max_latch_pos:
            max_latch_pos = max(max_latch_pos, self.pos)
            return int(max_latch_pos + .5)
        return None

    def rope_length_aiming_end(self, pos, end_pos):
        horizontal = self.latch_pos_aiming_end(pos, end_pos) - pos
        vertical = self.distance_to_rooftop()
        return (horizontal ** 2 + vertical ** 2) ** .5

    def ratio_aiming_end(self, pos, end_pos):
        horizontal = end_pos - pos
        rope = self.rope_length_aiming_end(pos, end_pos)
        ratio = horizontal / rope
        return ratio

    def get_variables_aiming_end(self, pos, end_pos):
        latch_pos = self.latch_pos_aiming_end(pos, end_pos)
        ratio = self.ratio_aiming_end(pos, end_pos)
        return ratio, latch_pos

    def is_possible_to_reach_the_end(self, pos, end_pos):
        if not self.is_reachable(pos):
            return False
        return pos + self.advanced_distance_for_max_displacement(pos) >= end_pos

    def is_reachable(self, pos):
        return self.latch_pos_for_max_displacement(pos) is not None


def spidey_swings(buildings):
    answer = []
    corners = []
    sumWidths = 0
    for (height, width) in buildings:
        sumWidths += width
        corners.append((sumWidths, height))
    xSpidey, ySpidey = 0, 50
    while True:
        maxAvgYield, bestDist, bestX, bestReached = 0, None, None, False
        minRope = 9999
        xCornerLast = 0
        for xCorner, yCorner in corners:
            if xCorner <= xSpidey:
                xCornerLast = xCorner
                continue
            for x in range(max(xSpidey, xCornerLast), xCorner + 1):
                xDist = x - xSpidey
                yDist = yCorner - ySpidey
                lenRope = (xDist ** 2 + yDist ** 2) ** 0.5
                if yCorner - lenRope < 20:
                    break
                dist = xDist * 2
                reached = (xSpidey + dist >= sumWidths)
                avgYield = dist / lenRope
                if not reached and maxAvgYield < avgYield:
                    maxAvgYield = avgYield
                    bestDist = dist
                    bestX = x
                elif not bestReached and reached:
                    minRope = lenRope
                    bestDist = dist
                    bestX = x
                    bestReached = reached
                elif bestReached and reached and minRope > lenRope:
                    minRope = lenRope
                    bestDist = dist
                    bestX = x
            xCornerLast = xCorner
        answer.append(bestX)
        xSpidey += bestDist
        if xSpidey >= sumWidths:
            break
    return answer

import math

def web_length(delta_x, height):
    return math.sqrt(delta_x**2+(height-50)**2)

def score(distance, delta_x, height):
    return distance/math.sqrt(delta_x**2+(height-50)**2)

def select_next_latch(cur_pos, buildings):

    potiential_latch = []
    for bd in buildings:
        x_lower_bound = max(bd[0], cur_pos)
        delta_x_upper_bound = min(math.floor(math.sqrt(bd[2]*60-2100)), bd[1]-cur_pos)
        if x_lower_bound <= cur_pos + delta_x_upper_bound:
            potiential_latch.append([x_lower_bound, cur_pos + delta_x_upper_bound, bd[2]])
    
    #latch loc, score, height
    common_best = [cur_pos, 0, 0]
    special_best = [-1, 0, 0]
    for bd in potiential_latch:
        for x in range(bd[0], bd[1]+1):
            if cur_pos + 2*(x-cur_pos) >= buildings[-1][1]:
                cur_score = score(buildings[-1][1]-cur_pos, x-cur_pos, bd[2])
                if cur_score >= special_best[1]:
                    special_best = [x, cur_score, bd[2]]
            else:
                cur_score = score(2*(x-cur_pos), x-cur_pos, bd[2])

            if cur_score >= common_best[1]:
                common_best = [x, cur_score, bd[2]]

    return common_best, special_best

def search(cur_pos, end_pos, buildings):

    if cur_pos >= end_pos: return 0, []
    
    cb, sb = select_next_latch(cur_pos, buildings)
    
    last_r = web_length(sb[0]-cur_pos, sb[2])
    best_r = web_length(cb[0]-cur_pos, cb[2])

    min_lenth, latch_list = search(cur_pos+2*(cb[0]-cur_pos), end_pos, buildings)

    if sb[0] == -1 or sb[0] == cb[0]:
        return min_lenth + best_r, [cb[0]] + latch_list
    else:
        if min_lenth + best_r > last_r:
            return last_r, [sb[0]]
        else:
            return min_lenth + best_r, [cb[0]] + latch_list

def spidey_swings(ar):

    buildings = []
    start_pos = 0
    for b in ar:
        buildings.append([start_pos, start_pos+b[1], b[0]])
        start_pos += b[1]
    
    cur_pos = 0
    latch_points = []
    while(cur_pos < buildings[-1][1]):
        cb, sb = select_next_latch(cur_pos, buildings)

        if sb[0] == -1 or sb[0] == cb[0]:
            latch_points.append(cb[0])
            cur_pos += (cb[0] - cur_pos)*2
        else:
            _, final_points = search(cur_pos, buildings[-1][1], buildings) 
            latch_points += final_points
            cur_pos += (sb[0] - cur_pos)*2    
    
    return latch_points

import math

def calc_web_length(current_loc, swing_point):
    x = swing_point[0] - current_loc[0]
    y = swing_point[1] - current_loc[1]
    x_travel = 2 * x
    web_length = math.sqrt(pow(x, 2) + pow(y, 2))
    bottom_height = swing_point[1] - web_length
    return x_travel, web_length, bottom_height

def spidey_swings(ar):
    buildings = ar

    # replace the building X positions with cumulative distances and
    # ALL integer points along the way (inclusive)
    # swap the order while we're at it to get normal (x,y) points
    latch_points = []
    prev_x = 0
    for building in buildings:
        for x in range(building[1] + 1):
            latch_points.append([x + prev_x, building[0]])
        prev_x += building[1]

    # Record the final X position to be used for termination criteria
    max_x = latch_points[-1][0]

    # Loop Variables
    current_location = [0, 50]
    swing_list = []
    swing_end = None
    best_ratio = -999.0
    best_building = None

    while True:
        building = latch_points.pop(0)

        # Skip all latch points we may have passed during the swing
        if building[0] <= current_location[0]:
            continue

        # Calculate data for the current 'test' latch point
        x_travel, length, height = calc_web_length(current_location, building)
        ratio = float(x_travel) / length

        # Special check for end condition, this may be an non 'optimal' swing but
        # if it lands exactly on the final position, it is the final latch point
        if current_location[0] + x_travel >= max_x:
            best_ratio = ratio
            best_building = building
            for ltch_pt in latch_points[:20]:
                x_travel2, length2, height2 = calc_web_length(current_location, ltch_pt)
                swing_end2 = current_location[0] + x_travel2

                # Since this is at the end, we might over-travel, remove that extra
                # distance when calculating the web ratio
                extra_x = swing_end2 - max_x
                x_travel2 -= extra_x
                ratio2 = float(x_travel2) / length2

                if ratio2 > best_ratio and height2 >= 20:
                    best_ratio = ratio2
                    best_building = ltch_pt

            swing_list.append(best_building[0])
            return swing_list

        # Basic check: the point is good, check if it's better than any previous latch point
        if ratio > best_ratio and height >= 20.0:
            best_ratio = ratio
            best_building = building
            swing_end = current_location[0] + x_travel

        # End check: if this point goes negative, all further ones will too, so use the best
        # point up to here as the latch point and move current
        if height < 20.0:
            # just to be sure there aren't any better results, peak ahead for the next 50
            # latch points to see if one is better
            for ltch_pt in latch_points[:100]:
                x_travel2, length2, height2 = calc_web_length(current_location, ltch_pt)
                ratio2 = float(x_travel2) / length2
                swing_end2 = current_location[0] + x_travel2
                if swing_end2 >= max_x and height2 >= 20.0:
                    swing_list.append(ltch_pt[0])
                    return swing_list

            best_ratio = -999.0
            current_location[0] = swing_end
            swing_list.append(best_building[0])

    return swing_list


from math import *

def horizontal_yield(x, point, end):
    length = hypot(point[0]-x, point[1]-50)
    distance = 2*(point[0]-x)
    if distance > end - x: distance = end - x
    return distance / length if point[1] - length >= 20 else 0

def optimal_latch(ar, x):
    x_opt = 0
    yield_opt = 0
    for building in ar:        
        if building[1] + building[2] < x: continue
        x_max = x + int(sqrt((building[0]-20)**2-(building[0]-50)**2))
        if x_max < building[2]: continue
        if 2 * x_max - x > ar[-1][1] + ar[-1][2]:
            x_max = max(building[2], int(ceil((ar[-1][1] + ar[-1][2] + x) / 2)))
        x_max = min(x_max, building[1] + building[2])
        yield_x = horizontal_yield(x, [x_max, building[0]], ar[-1][1] + ar[-1][2])
        if yield_x > yield_opt or (2 * x_max - x >= ar[-1][1] + ar[-1][2] and 2 * x_opt - x < ar[-1][1] + ar[-1][2]):
            yield_opt = yield_x
            x_opt = x_max
    return int(x_opt)
        

def spidey_swings(ar):
    print(ar)
    spidey_x = 0
    latches = []
    for i in range(len(ar)):
        ar[i].append(0 if i==0 else ar[i-1][1] + ar[i-1][2])
    while spidey_x < ar[-1][1] + ar[-1][2]:
        latches.append(optimal_latch(ar,spidey_x))   
        spidey_x = 2 * latches[-1] - spidey_x
    return latches

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

import math

def spidey_swings(ar):
    cur_pos = n = i = tz = 0
    ratio = thyp = None
    tome = []
    ln = len(ar)
    lim = int(math.sqrt(230**2-200**2))
    buildings = []
    for x in ar:
        tz += x[1]
        buildings.append(tz)
    end = buildings[-1]

    def find_index(r,g):
        for q,z in enumerate(r):
            if z > g: return q
        return -1
    
    while i < ln:
        h,w = ar[i]
        pt1 = buildings[i] - cur_pos
        pt0 = pt1 - w
        max_x = int(math.sqrt((h-20)**2 - (h-50)**2))
        if max_x >= pt0:
            max_x = min(pt1,max_x)
            ratio = [max_x,i] if ratio == None or max_x/math.hypot(max_x,h-50) > ratio[0]/math.hypot(ratio[0],ar[ratio[1]][0]-50) else ratio
        if buildings[i] - w >= cur_pos + lim:
            if end - lim * 2 < cur_pos:
                i += 1
                break
            npos = cur_pos + ratio[0] * 2
            tome.append(cur_pos + ratio[0])
            while n < ln and buildings[n] <= npos: n += 1
            cur_pos = npos
            i = n - 1
            ratio = None
        i += 1
    
    if cur_pos == end: return tome
    if cur_pos > end:
        cur_pos -= (cur_pos - tome.pop()) * 2
    tz = math.ceil((end-cur_pos)/2)
    i = find_index(buildings,tz+cur_pos) + 1 or ln
    thyp = math.hypot(tz,ar[i-1][0]-50)
    if thyp > ar[i-1][0]-20: thyp = None
    
    for j in range(i,ln):
        h,w = ar[j]
        zz = math.hypot(h-50,buildings[j-1]-cur_pos)
        if zz <= h - 20:
            if thyp == None or thyp > zz:
                tz = buildings[j-1] - cur_pos
                thyp = zz
                i = j
    
    if thyp == None:
        tome.append(cur_pos+ratio[0])
        cur_pos += ratio[0] * 2
        tz = math.ceil((end-cur_pos)/2)
        i = find_index(buildings,tz+cur_pos) + 1 or ln
    
    final_val = [tz+cur_pos,math.hypot(tz,ar[i-1][0]-50)]
    for q,z in enumerate(ar[i:]):
        h,w = z
        hyp = math.hypot(buildings[i+q] - cur_pos - w,ar[i+q][0] - 50)
        if final_val[1] > hyp and hyp < ar[i+q][0] - 20: final_val = [buildings[i+q]-w,hyp]
    
    tome.append(final_val[0])
    return tome