Advent of Code 2016 - Day 1

Day 1: No Time for a Taxicab

Useful Links

›

• 2016 Main Page
• My solution code

Concepts and Packages Demonstrated

LoggingTiming and ProgressReading filesMathListsDictionaries

Problem Intro

In this problem, Santa needs to find the Easter Bunny Headquarters. He’s given a series of instructions that involve turning 90 degrees left (L) or right (R), and then walking a certain number of blocks. The city is laid out on a grid, so movement is restricted to horizontal and vertical paths, much like a taxicab would travel.

The goal is to determine two things:

1. The “taxicab distance” to the final destination.
2. The taxicab distance to the first location visited twice.

Part 1

How many blocks away is Easter Bunny HQ?

To solve this, we need to keep track of Santa’s current position (x, y coordinates) and his current heading (direction he’s facing). We can represent the heading as an angle, where North is 0 degrees, East is 90 degrees, South is 180 degrees, and West is 270 degrees.

When Santa turns, his heading changes by 90 degrees. A ‘R’ turn adds 90 degrees, and an ‘L’ turn subtracts 90 degrees. We use a helper function convert_angle to keep the heading within 0-359 degrees.

Movement is then determined using unit circle geometry. If Santa moves n blocks:

• If heading North (0 degrees), y increases by n.
• If heading East (90 degrees), x increases by n.
• If heading South (180 degrees), y decreases by n.
• If heading West (270 degrees), x decreases by n.

The math.sin and math.cos functions, combined with math.radians to convert degrees to radians, help us calculate the change in x and y coordinates based on the heading. For example, round(sin(radians(heading))) gives us the x-component of movement, and round(cos(radians(heading))) gives us the y-component. We use round because we’re dealing with integer block movements.

The taxicab distance is simply the sum of the absolute differences in the x and y coordinates from the starting point (0,0).

import logging
import os
import time
from math import cos, radians, sin

SCRIPT_DIR = os.path.dirname(__file__)
INPUT_FILE = "input/input.txt"

X = 'x'
Y = 'y'

def main():
    logging.basicConfig(level=logging.INFO, format="%(asctime)s:%(levelname)s:	%(message)s")

    input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)
    with open(input_file, mode="rt") as f:
        data = f.read().split(", ")

    location = {
        X: 0,
        Y: 0
    }

    visited_locations = []
    visited_locations.append(location.copy())

    heading = 0 # North

    for instr in data:
        location, heading = process_direction(location, visited_locations, heading, instr)

    taxicab_distance = abs(location[X]) + abs(location[Y])
    logging.info(f"Taxicab distance for entire journey: {taxicab_distance}")

def process_direction(location: dict, visited_locations: list, heading: int, instr: str):
    turn = instr[0]
    magnitude = int(instr[1:])
    rotation = 90 if turn == 'R' else -90
    heading = convert_angle(heading + rotation)

    for _ in range(magnitude):
        location[X] += round(sin(radians(heading)))
        location[Y] += round(cos(radians(heading)))
        visited_locations.append(location.copy())

    return location, heading

def convert_angle(angle: int):
    if (angle < 0):
        angle += 360
    return angle % 360

if __name__ == "__main__":
    t1 = time.perf_counter()
    main()
    t2 = time.perf_counter()
    print(f"Execution time: {t2 - t1:0.4f} seconds")

Part 2

What is the distance to the first location Santa visits twice?

For Part 2, we need to find the first location that Santa visits more than once. This means we can’t just track the final position after each instruction; we need to track every single block Santa steps on.

To achieve this, we maintain a list called visited_locations. Before processing any instructions, the starting location (0,0) is added to this list. Then, as Santa moves one block at a time (within the process_direction function), each new coordinate he lands on is added to visited_locations.

After all instructions are processed, we iterate through visited_locations. For each location, we check if it appears more than once in the list using list.count(). The first location encountered that has a count greater than 1 is our answer. We then calculate and report its taxicab distance from the origin.

    # ... (previous code for Part 1) ...

    for visited in visited_locations:
        # we want the first location that was visited twice
        # i.e. where this particular location has a count > 1
        if visited_locations.count(visited) > 1:
            taxicab_distance = abs(visited[X]) + abs(visited[Y])
            logging.info(f"First location visited twice was {visited}")
            logging.info(f"Distance to this location: {taxicab_distance}")
            break

›