4
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Please see What to do when someone answers. I have rolled back Rev 5 → 3. \$\endgroup\$ – 200_success Jan 24 '18 at 21:05
  • 1
    \$\begingroup\$ @200_success, I've posted an answer below. Gareth's answer helped me to find a bug and fix it. I suppose I have to accept it and move my answer to a new question if I want to get feedback on the updated version of code, is that right? \$\endgroup\$ – skovorodkin Jan 24 '18 at 21:17
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Gareth, thanks for your time! There was a bug in solve_bisect. I've updated my post, hopefully it's correct now (see Update section). I can't agree with your last statement: just run something like solve_set('R100000000'). The "only extra work" takes a lot of resources actually :) \$\endgroup\$ – skovorodkin Jan 24 '18 at 21:02
  • \$\begingroup\$ It still doesn't matter if the result you get is wrong :) What Gareth tried to tell you is: "Focus first on correctness, then speed" \$\endgroup\$ – Grajdeanu Alex. Jan 24 '18 at 21:05
  • \$\begingroup\$ @MrGrj, yeah, I didn't pay enough attention to correctness the first time. solve_bisect_v2 is (hopefully) correct. And I still want to hear some feedback on it :) \$\endgroup\$ – skovorodkin Jan 24 '18 at 21:12
  • \$\begingroup\$ Ah, I think I misunderstood the problem. I've edited my answer to remove the incorrect claim. \$\endgroup\$ – Gareth Rees Jan 24 '18 at 22:18
2
\$\begingroup\$

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).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.