Dazbo's Advent of Code solutions, written in Python
Unit CircleTaxicab Geometrylist.count()Loggingos.pathtime.perf_counter
Welcome to Advent of Code 2016, Day 1! In this puzzle, you’re airdropped near Easter Bunny Headquarters in a city with a grid-like street layout. You start at coordinates (0,0) facing North. You’re given a sequence of instructions, each telling you to either turn left (L) or right (R) 90 degrees, and then walk forward a specified number of blocks.
The input data looks like a comma-separated string of instructions, for example:
R2, L3, R2, R2, R2, R5, L5, R5, R3
How many blocks away is Easter Bunny HQ?
For Part 1, the goal is to determine the “taxicab distance” (also known as Manhattan distance) to the final destination after following all instructions. This means summing the absolute differences of the final X and Y coordinates from the starting point (0,0).
My solution uses a location
dictionary to keep track of the current x
and y
coordinates, and a heading
variable (0 for North, 90 for East, 180 for South, 270 for West) to represent the current direction.
The core logic resides in the process_direction
function:
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)
# We need to process the instruction one unit at a time,
# so that we store the path taken, not just the final landing location of each instruction
for _ in range(magnitude):
# unit circle geometry
location[X] += round(sin(radians(heading)))
location[Y] += round(cos(radians(heading)))
# store all coords visited whilst following this direction
visited_locations.append(location.copy())
return location, heading
def convert_angle(angle: int):
""" Convert any angle to %360
Args:
angle (int): An angle
Returns:
[int]: The angle
"""
if (angle < 0):
angle += 360
return angle % 360
turn
(L or R) determines the rotation
(90 or -90 degrees).heading
is updated and normalized using convert_angle
to stay within 0-359 degrees.x
and y
coordinates. See the “Unit Circle” section below for a more detailed explanation.magnitude
(number of blocks to walk) is processed one unit at a time. This is crucial for Part 2, as it allows us to record every intermediate step.To determine the change in our x
and y
coordinates, we can use the concept of a unit circle. A unit circle is a circle with a radius of 1, centered at the origin (0,0) of a Cartesian plane.
In our solution, we represent the direction of travel as a heading in degrees: 0° for North, 90° for East, 180° for South, and 270° for West. We can use trigonometry to determine the change in x
and y
for each step we take.
sin(heading)
.cos(heading)
.Let’s look at how this works for our four cardinal directions:
sin(0°) = 0
, cos(0°) = 1
. So, x
changes by 0, and y
changes by 1.sin(90°) = 1
, cos(90°) = 0
. So, x
changes by 1, and y
changes by 0.sin(180°) = 0
, cos(180°) = -1
. So, x
changes by 0, and y
changes by -1.sin(270°) = -1
, cos(270°) = 0
. So, x
changes by -1, and y
changes by 0.This is exactly what we need to update our coordinates as we move one block at a time. The Python code uses the math.sin
and math.cos
functions, which work with radians, so we convert our degree heading
to radians before using them.
After all instructions are processed, the taxicab distance is simply abs(final_x) + abs(final_y)
.
What is the distance to the first location you visit twice?
For Part 2, the challenge is to find the very first location that is visited more than once. This includes all intermediate steps taken during movement.
My solution addresses this by maintaining a visited_locations
list. As shown in the process_direction
function above, for each block walked, the current location
is appended to this list. This creates a complete history of the path taken.
copy()
You might have noticed the use of location.copy()
when appending to the visited_locations
list. This is a crucial detail. In Python, dictionaries are mutable objects. If we had simply appended location
directly, we would be appending a reference to the location
dictionary. This means that every time the location
dictionary was updated, all the entries in visited_locations
would also change, because they would all be pointing to the same single dictionary object. By the end, visited_locations
would just contain the final location repeated many times.
By using .copy()
, we create a shallow copy of the dictionary at that moment in time. This new dictionary object is then appended to the list, preserving the coordinates at that specific step. This ensures that visited_locations
contains a true history of the path taken, with each entry being a distinct snapshot of the coordinates at each point along the way.
After processing all instructions, the code iterates through the visited_locations
list to find the first coordinate that appears more than once. The list.count()
method is used for this purpose.
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
The list.count(element)
method returns the number of times element
appears in the list. By iterating through visited_locations
and checking count(visited) > 1
, the first such visited
location found is the answer to Part 2.
The execution of the solution yields results that look something like this:
Taxicab distance for entire journey: 230
First location visited twice was {'x': 116, 'y': 5}
Distance to this location: 121
Execution time: 0.0059 seconds