Update
There is a bug in solve_bisect. Here's a fixed version:
def solve_bisect_v2(instructions):
N, E, S = 1j, 1, -1j
_inf, inf = float('-inf'), float('inf')
direction, pos, prev_pos, prev_segment = N, 0, 0, None
parallel, orthogonal = [], [] # segments
for i in instructions.split(', '):
direction *= {'R': -1j, 'L': 1j}[i[0]]
pos += direction * int(i[1:])
# "Level" start-end
if direction in (N, S): segment = (prev_pos.real, *sorted([prev_pos.imag, pos.imag]))
else: segment = (prev_pos.imag, *sorted([prev_pos.real, pos.real]))
if orthogonal and segment[0] == 0 and segment[1] <= 0 <= segment[2]:
return 0
insort(parallel, segment)
start = bisect_left (orthogonal, (segment[1], _inf))
end = bisect_right(orthogonal, (segment[2], inf))
candidates = orthogonal[start:end]
for c in candidates if direction in (N, E) else candidates[::-1]:
if prev_segment != c and c[1] <= segment[0] <= c[2]:
return abs(segment[0]) + abs(c[0])
prev_pos, prev_segment, parallel, orthogonal = pos, segment, orthogonal, parallel
I've changed some variable names to make it more readable.
solve_bisect_v2 passes next tests:
cases = [
('R1', None),
('L1, L1, L1, L1', 0),
('R1, R1, R2, R1, R1', 0),
('R8, R4, R4, R8', 4),
]
for instructions, answer in cases:
assert solve_bisect_v2(instructions) == answer
I've also run the next code for a couple of minutes and it didn't stop on it's own:
while True:
instructions = ', '.join(f'{choice("LR")}{randrange(1, 1000000)}' for _ in range(100000))
assert solve_set(instructions) == solve_bisect_v2(instructions)
The logic hasn't really changed. I've fixed candidates calculation and added a check for segments running through (0, 0) that are colinear to the first segment (cases[2] checks that).
