Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
28-liner: recursive cached solution in Clear category for Park Benches by przemyslaw.daniel
from typing import List, Tuple
def park_benches(benches: List[Tuple[int, int]], distance: int) -> int:
""" The idea here is to split benches in two parts and
continue calculations for these subsets. In case when the gap
is smaller than minimal distance we need to remove left and
right bench to see which solution is better """
def park_cache(bcs: List[Tuple[int, int]]) -> int:
""" Cache every solution for keys in the form of
bench1, gap0, bench1, gap1, ... to speed up calculation """
key = tuple((b, c - a - b) for (a, b), (c, _) in zip(bcs, bcs[1:]))
key = sum(key, ()) + (bcs[-1][-1],) if bcs else ()
visited[key] = visited.get(key, park_benches(bcs, distance))
return visited[key]
if len(benches) <= 1:
return bool(benches) and benches[0][-1]
half, pc, visited = len(benches) // 2, park_cache, {}
left, right = benches[:half], benches[half:]
(a, b), (c, _) = left[-1], right[0]
return pc(left) + pc(right) if c - a - b >= distance else \
max(pc(left[:-1]) + pc(right), pc(left) + pc(right[1:]))
Dec. 29, 2020
Comments:
