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: MEDIUM_HARD
Tags: Mathematics

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) ** 0.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) ** 0.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 + 0.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) ** 0.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]])
	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)
	elif 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
	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]
	max_x = latch_points[-1][0]
	current_location = [0, 50]
	swing_list = []
	swing_end = None
	best_ratio = -999.0
	best_building = None
	while True:
		building = latch_points.pop(0)
		if building[0] <= current_location[0]:
			continue
		(x_travel, length, height) = calc_web_length(current_location, building)
		ratio = float(x_travel) / length
		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
				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
		if ratio > best_ratio and height >= 20.0:
			best_ratio = ratio
			best_building = building
			swing_end = current_location[0] + x_travel
		if height < 20.0:
			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) ** 0.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) ** 0.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