Advent of Code - Day 01

Advent of Code is a fun competition. Here is a link to the first day. Each day has two parts.

--- Day 1: No Time for a Taxicab ---

Santa's sleigh uses a very high-precision clock to guide its
movements, and the clock's oscillator is regulated by stars.
Unfortunately, the stars have been stolen... by the Easter Bunny. To
save Christmas, Santa needs you to retrieve all fifty stars by
December 25th.

Collect stars by solving puzzles. Two puzzles will be made available
on each day in the advent calendar; the second puzzle is unlocked when
you complete the first. Each puzzle grants one star. Good luck!

You're airdropped near Easter Bunny Headquarters in a city somewhere.
"Near", unfortunately, is as close as you can get - the instructions
on the Easter Bunny Recruiting Document the Elves intercepted start
here, and nobody had time to work them out further.

The Document indicates that you should start at the given coordinates
(where you just landed) and face North. Then, follow the provided
sequence: either turn left (L) or right (R) 90 degrees, then walk
forward the given number of blocks, ending at a new intersection.

There's no time to follow such ridiculous instructions on foot,
though, so you take a moment and work out the destination. Given that
you can only walk on the street grid of the city, how far is the
shortest path to the destination?

For example:

Following R2, L3 leaves you 2 blocks East and 3 blocks North, or 5
blocks away. R2, R2, R2 leaves you 2 blocks due South of your starting
position, which is 2 blocks away. R5, L5, R5, R3 leaves you 12 blocks
away.

How many blocks away is Easter Bunny HQ?

And then part 2:

Then, you notice the instructions continue on the back of the
Recruiting Document. Easter Bunny HQ is actually at the first location
you visit twice.

For example, if your instructions are R8, R4, R4, R8, the first
location you visit twice is 4 blocks away, due East.

How many blocks away is the first location you visit twice?

Going to d

Making it simpler

The get_next_dirs function is not very intuitive.
It's returning a pair of values,
one of them a zero, the other is one of the parameters,
sometimes negated.

Instead of an if-else chain,
it would be simpler to arrange the directions in a circular list:

north = 0, 1
east = 1, 0
south = 0, -1
west = -1, 0
directions = (north, east, south, west)

This is of course not circular, yet, but you could create an abstract data type around it with that behavior. Then, tracking the index pointing into this tuple, you could turn right by moving the index forward, and turn left left by moving the index backward.

Something like this:

class Direction:
    north = 0, 1
    east = 1, 0
    south = 0, -1
    west = -1, 0
    directions = (north, east, south, west)

    def __init__(self, index=0):
        self.index = index

    def left(self):
        self.index -= 1
        if self.index >> d = Direction(0); turn(d, 'L'); (d.dx, d.dy)
    (-1, 0)

    >>> d = Direction(0); turn(d, 'R'); (d.dx, d.dy)
    (1, 0)

    >>> d = Direction(3); turn(d, 'L'); (d.dx, d.dy)
    (0, -1)

    >>> d = Direction(3); turn(d, 'R'); (d.dx, d.dy)
    (0, 1)

    :param cur_dir: the current direction
    :param turn_dir: turn direction; 'L' to turn left, 'R' to turn right
    :return: None, raise error on invalid turn direction
    """
    if turn_dir == 'L':
        cur_dir.left()
    elif turn_dir == 'R':
        cur_dir.right()
    else:
        raise RuntimeError('Unknown turn direction')

Ok so that's a lot more code, but now it's easier to read.

Hacky tests

Insert of assert statements, a neat alternative is using doctests.
You can see an example of that in the previous section.
Doctests can be executed with python -mdoctest yourscript.py,
which produces nice reports when one or more tests are failing.
By contrast, the first assert would immediately halt execution.
At the same time, doctests also serve as documentation and example usage.

However, as long as you have code in the main scope,
that will get executed together with the doctests.
To avoid that, it's good to make it a habit to (at least) move all the code into a main function, and call it from within a if __name__ == '__main__': guard.

Performance

The least pretty part about this code is walking over all the blocks in for s in range(steps), and storing all locations in a set.
With small distances walked as in your example, this may be fine as it is.
But if the distances were very larger numbers,
this solution could take unnecessarily long and use unnecessarily large amount of memory.

Short of checking for intersections with the path segments walked so far,
a simpler optimization is possible:
after you found a duplicate_location,
you could stop walking step by step.

dx = 0
dy = 0
cur_dir = Direction()
locations = set()
duplicate_location = None

for d in dirs:
    turn(cur_dir, d[0])
    steps = int(d[1:])

    if not duplicate_location:
        for _ in range(steps):
            loc = dx, dy

            if loc not in locations:
                locations.add(loc)
            else:
                duplicate_location = loc

            dx += cur_dir.dx
            dy += cur_dir.dy

    else:
        dx += cur_dir.dx * steps
        dy += cur_dir.dy * steps

StackExchange Code Review Q#148841, answer score: 5