AoC Day1 – No Time for a Taxicab

This is the puzzle for Day 1 of Advent Of Code 2016.  All of my code for this day can be found in my Day 1 Repository

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?

This is the input for the puzzle:

L4, R2, R4, L5, L3, L1, R4, R5, R1, R3, L3, L2, L2, R5, R1, L1, L2, R2, R2, L5, R5, R5, L2, R1, R2, L2, L4, L1, R5, R2, R1, R1, L2, L3, R2, L5, L186, L5, L3, R3, L5, R4, R2, L5, R1, R4, L1, L3, R3, R1, L1, R4, R2, L1, L4, R5, L1, R50, L4, R3, R78, R4, R2, L4, R3, L4, R4, L1, R5, L4, R1, L2, R3, L2, R5, R5, L4, L1, L2, R185, L5, R2, R1, L3, R4, L5, R2, R4, L3, R4, L2, L5, R1, R2, L2, L1, L2, R2, L2, R1, L5, L3, L4, L3, L4, L2, L5, L5, R2, L3, L4, R4, R4, R5, L4, L2, R4, L5, R3, R1, L1, R3, L2, R2, R1, R5, L4, R5, L3, R2, R3, R1, R4, L4, R1, R3, L5, L1, L3, R2, R1, R4, L4, R3, L3, R3, R2, L3, L3, R4, L2, R4, L3, L4, R5, R1, L1, R5, R3, R1, R3, R4, L1, R4, R3, R1, L5, L5, L4, R4, R3, L2, R1, R5, L3, R4, R5, L4, L5, R2

To solve this problem, I need to read in the instructions and follow each one:

CurrentX = 0
CurrentY = 0
CurrentOrientation = 0

inputArray = open('Input', 'r').read().split(", ")

for instruction in inputArray:
    CurrentOrientation = Turn(CurrentOrientation, instruction[0][0])
    CurrentX, CurrentY = Move(CurrentX, CurrentY, CurrentOrientation, int(instruction[1:]))

In order to find the new orientation, I created a Turn method that keeps the orientation value from 0 to 3 representing directions North, East, South, and West:

def Turn(orientation, direction):
    if direction == "R":
        orientation += 1
    if direction == "L":
        orientation -= 1
    return orientation % 4

And a method to move the current position the correct distance:

def Move(X, Y, orientation, distance):
    if orientation == 0:
        X += distance
    if orientation == 1:
        Y += distance
    if orientation == 2:
        X -= distance
    if orientation == 3:
        Y -= distance

    return X, Y

After following all of the instructions, the distance to the end can be calculated and displayed:

print "Manhattan Distance from start to end:", abs(CurrentX) + abs(CurrentY)

Then Part 2 of the problem:

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.

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

For this part, I needed to keep track of which spaced had already been visited.  First I created a variable to hold the route traveled, and set the initial location to true:

route = [[0 for x in range(300)] for y in range(300)] 
route[0][0] = 1

Since I only wanted to mark visited spaces once per instruction, I created one method to mark horizontal lines visited and a different method to mark vertical lines:

def VisitHorizontal(oldX, newX, Y, map):
    for X in range(oldX+1, newX+1):
        if map[X][Y] == 1:
            print "Found a repeat!  X:", X, " Y:", Y
            map[X][Y] = 1

I updated my Move method to call these and passed the route variable in:

def Move(X, Y, orientation, distance, route):
    if orientation == 0:
        VisitHorizontal(X, X+distance, Y, route)
        X += distance
    if orientation == 1:
        VisitVertical(X, Y, Y+distance, route)
        Y += distance
    if orientation == 2:
        VisitHorizontal(X, X-distance, Y, route)
        X -= distance
    if orientation == 3:
        VisitVertical(X, Y, Y-distance, route)
        Y -= distance

    return X, Y

Instead of having the program keep track of how many times the route had crossed itself, I just looked through the output for the first “Found a repeat!” statement and calculated the answer from there.