Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
get unsocial chains and with product\compress remove combinations of benches from chains solution in Clear category for Park Benches by kdim
from itertools import product, compress
from typing import List, Tuple
def park_benches(benches: List[Tuple[int, int]], dist: int) -> int:
def is_social(chain): # simple check of social distance
chain = list(chain) # if social chain, return sum of lenght of benches
if not chain or any(j[0] - sum(i) < dist for i, j in zip(chain, chain[1:])):
return 0
return sum(i[1] for i in chain)
# here in the cycle we remove the combinations of benches
comb = lambda x: max(is_social(compress(x, p)) for p in product([0, 1], repeat=len(x)))
max_len, benches = 0, benches + [(float('inf'), 0)]
while len(benches) > 1:
bench = benches.pop(0) # pop benches with social distance
if benches[0][0] - sum(bench) >= dist: #
max_len += bench[1] # and summ lenght
continue #
chain = [bench] # if find unsocial distance,
while benches[0][0] - sum(bench) < dist:# then get chain of all unsocial benches
bench = benches.pop(0) #
chain.append(bench) #
max_len += comb(chain) # and get max lenght of combinations of unsocial chain
return max_len
Feb. 22, 2021
Comments:
