Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
BFS solution in Clear category for Fast Train by Sim0000
from collections import deque
def fast_train(sections):
limit = []
for sec in sections: limit += [sec[1]]*sec[0]
goal = len(limit)
q = deque([(1, (1,))])
while q:
pos, log = q.popleft()
speed = log[-1]
if pos == goal and speed == 1: return len(log) # found
if pos < 0 or goal <= pos: continue
if any(speed > limit[pos - 1 - i] for i in range(speed)): continue
for d in (-1, 0, 1):
speed_next = speed + d
q.append((pos + speed_next, log + (speed_next,)))
print("not found")
if __name__ == '__main__':
assert fast_train([(4, 3)]) == 3, 'basic'
assert fast_train([(9, 10)]) == 5, '1 section'
assert fast_train([(5, 5), (4, 2)]) == 6, '2 section'
print("Coding complete? Click 'Check' to earn cool rewards!")
Oct. 27, 2018
