Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Fast Train by tokiojapan55
from typing import List
def check(speed, line):
path = []
for s in speed:
path = path + [s] * s
while len(path) < len(line):
path = path + [1 if path[-1] <= 1 else path[-1] - 1]
#####
if len(path) <= 0:
return False
if len(line) <= 0:
return False
if len(path) != len(line):
return False
if path[0] != 1 or path[-1] != 1:
return False
for n in range(1, len(path)):
if abs(path[n-1] - path[n]) > 1:
return False
#####
for s,l in zip(path, line):
if s > l:
return False
return True
def fast_train(sections: List[List[int]]) -> int:
line = []
for s in sections:
line += [s[1]] * s[0]
length = len(line)
stack = []
speed = [1]
while sum(speed) < length:
if check(speed + [speed[-1] + 1], line):
stack.append(speed + [speed[-1]])
speed.append(speed[-1] + 1)
elif check(speed + [speed[-1]], line):
stack.append(speed + [speed[-1] - 1])
speed.append(speed[-1])
else:
s = 1 if speed[-1] <= 1 else speed[-1] - 1
if check(speed + [s], line):
speed.append(s)
else:
speed = stack.pop()
return len(speed)
June 2, 2020