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(input):
    direction, loc, visited = 1j, 0, {0}
    for i in input.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],)) : 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.