Here I'm talking about Part 2 of the [puzzle](https://adventofcode.com/2016/day/1), 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](https://github.com/norvig/pytudes/blob/master/ipynb/Advent%20of%20Code.ipynb).

My code was not that elegant, but Peter's notebook reminded me of existence of [`complex`](https://docs.python.org/3/library/functions.html#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](https://en.wikipedia.org/wiki/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.