Advent of Code 2016: Day 1 "No Time for a Taxicab"

Question

Here I'm talking about Part 2 of the puzzle, where we need to find "How many blocks away is the first location you visit twice?".

At first I solved it as everybody else using a set of all visited points. Peter Norvig employed that approach, you can check his solution on GitHub.

My code was not that elegant, but Peter's notebook reminded me of existence of complex type, so I modified my function and ended up here:

def solve_set(instructions):
    direction, loc, visited = 1j, 0, {0}
    for i in instructions.split(', '):
        direction *= {'R': -1j, 'L': 1j}[i[0]]
        for _ in range(int(i[1:])):
            loc += direction
            if loc in visited:
                return abs(loc.real) + abs(loc.imag)
            visited.add(loc)

Now let's try to optimize it.

The puzzle uses Taxicab geometry, and if we assume that all instructions have a positive number of steps (greater than zero), we can split segments into two subsets, parallel and orthogonal, and for each new segment check only orthogonal segments for an intersection. No matter what, on a new instruction (i.e. new segment) those two sets interchange, so parallel segments become orthogonal and orthogonal become parallel. To update subsets (represented as lists) we use insort function from bisect module which inserts an element into a list keeping it sorted. Then we get a list of candidates from orthogonal set of segments using bisect function and iterate over it in the direction of current segment to get the first intersection:

from bisect import bisect, insort

def solve_bisect(instructions):
    N, E, S = 1j, 1, -1j
    direction, cur, prev, prev_s = N, 0, 0, None
    parallel, orthogonal = [], []  # segments
    for i in instructions.split(', '):
        direction *= {'R': -1j, 'L': 1j}[i[0]]
        cur += direction * int(i[1:])
        if direction in (N, S): s = prev.real, prev.imag, cur.imag
        else:                   s = prev.imag, prev.real, cur.real
        insort(parallel, s)
        candidates = orthogonal[bisect(orthogonal, s[1:2]) : bisect(orthogonal, s[2:])]
        for c in candidates if direction in (N, E) else candidates[::-1]:
            if prev_s != c and (c[1] <= s[0] <= c[2] or c[2] <= s[0] <= c[1]):
                return abs(s[0]) + abs(c[0])
        prev, prev_s, parallel, orthogonal = cur, s, orthogonal, parallel

Now we need to generate a large input for comparison:

from random import choice, randrange
instructions = ', '.join(f'{choice("LR")}{randrange(1, 1000000)}' for _ in range(100000))

I don't know what you will end up with, but I get these results:

In [15]: %timeit solve_bisect(instructions)
5.91 ms ± 144 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [16]: %timeit solve_set(instructions)
465 ms ± 8.75 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

So in this case solve_bisect is roughly 100x times faster than the naive approach.

But I'd like to know if there's an even better way to solve the problem.

Answer 1

Before starting to make timing comparisons, it's important to check that the optimized code is correct. It's no good being a hundred times faster if you get the wrong answer! So let's look at the results of the two functions on a simple test case:

>>> instructions = 'L1, L1, L1, L1, R1, R1, R1, R1'
>>> solve_set(instructions)
0.0
>>> solve_bisect(instructions)
1.0

Oops.

Answer 2

Gareth pointed out that solve_bisect is not correct.

There is obviously a bug and here's a fixed version of the function:

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 loop for a couple of minutes and it didn't stop on its 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).