Taxicab distance from path specification (Advent of Code - Day 01)

Question

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 definitely be some low hanging fruit here as I got it to work and then didn't really even touch it.

input = 'L1, L5, R1, R3, L4, L5, R5, R1, L2, L2, L3, R4, L2, R3, R1, L2, R5, R3, L4, R4, L3, R3, R3, L2, R1, L3, R2, L1, R4, L2, R4, L4, R5, L3, R1, R1, L1, L3, L2, R1, R3, R2, L1, R4, L4, R2, L189, L4, R5, R3, L1, R47, R4, R1, R3, L3, L3, L2, R70, L1, R4, R185, R5, L4, L5, R4, L1, L4, R5, L3, R2, R3, L5, L3, R5, L1, R5, L4, R1, R2, L2, L5, L2, R4, L3, R5, R1, L5, L4, L3, R4, L3, L4, L1, L5, L5, R5, L5, L2, L1, L2, L4, L1, L2, R3, R1, R1, L2, L5, R2, L3, L5, L4, L2, L1, L2, R3, L1, L4, R3, R3, L2, R5, L1, L3, L3, L3, L5, R5, R1, R2, L3, L2, R4, R1, R1, R3, R4, R3, L3, R3, L5, R2, L2, R4, R5, L4, L3, L1, L5, L1, R1, R2, L1, R3, R4, R5, R2, R3, L2, L1, L5'


dirs = input.split(', ')


def get_next_dirs(cur_xdir, cur_ydir, turn_dir):
    if turn_dir == 'L':
        if cur_xdir != 0:
            return 0, cur_xdir
        return -cur_ydir, 0
    elif turn_dir == 'R':
        if cur_xdir != 0:
            return 0, -cur_xdir
        return cur_ydir, 0
    else:
        raise RuntimeError('Unknown turn direction')


assert (get_next_dirs(0, 1, 'L') == (-1, 0))
assert (get_next_dirs(1, 0, 'L') == (0, 1))
assert (get_next_dirs(-1, 0, 'L') == (0, -1))
assert (get_next_dirs(0, -1, 'L') == (1, 0))


assert (get_next_dirs(0, 1, 'R') == (1, 0))
assert (get_next_dirs(1, 0, 'R') == (0, -1))
assert (get_next_dirs(-1, 0, 'R') == (0, 1))
assert (get_next_dirs(0, -1, 'R') == (-1, 0))

dx = 0
dy = 0
xdir = 0
ydir = 1
locations = set()
loc_found = False
duplicate_location = None

for d in dirs:
    xdir, ydir = get_next_dirs(xdir, ydir, d[0])
    steps = int(d[1:])

    for s in range(steps):
        loc = dx, dy

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

        dx += xdir
        dy += ydir

print('Part 1: dx={dx}, dy={dy}, dist={d}'.format(dx=dx, dy=dy, d=abs(dx) + abs(dy)))
print('Part 2: duplicated location={loc}'.format(loc=duplicate_location))

It's all in one script, for simplicity. It feels like the get_next_dirs function would be easy to make better, but I'm not actually sure at first glance.

And I'm sure my hacky testing will get some feedback ;-) I'm never really sure when doing programming challenges like this whether to do a "real" unittest setup or just run basic tests with asserts. The asserts "work" well enough.

Github link here.

Answer 1

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 < 0:
            self.index = len(self.directions) - 1

    def right(self):
        self.index += 1
        if self.index == len(self.directions):
            self.index = 0

    @property
    def dx(self):
        return self.directions[self.index][0]

    @property
    def dy(self):
        return self.directions[self.index][1]


def turn(cur_dir, turn_dir):
    """
    >>> 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

Answer 2

We don't need loc_found as a variable; we can use duplicate_location for that, since it starts off as None (which is false) and gets set to a pair (which are all true). So instead of

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

we can simply

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

---

Instead of str.format(), it's simpler to use interpolated strings ("f-strings"):

print(f'Part 1: dx={dx}, dy={dy}, dist={abs(dx) + abs(dy)}')
print(f'Part 2: duplicated location={duplicate_location}')