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?
This looks to be a simple trace the path sort of problem.
Assume we start at origin (0,0),
then use counters to keep track of where we are
on a virtual grid. Also need to keep track of direction.
Read the input, then parse it to read whether to go left or right.
Keep a variable direction to indicate where we are currently moving.
Direction is a vector (x,y)
to represent the math to do when calculcating the
next point on the grid.
North(0,1); South(0,-1); East(1,0); West(-1,0)
Tricky: how to convert north to west by reading in left?
North is (0,1) and West is (-1,0)
Similarly, West --left--> South,
which can be written as (-1,0)--L-->(0,-1)
Drawing up a table to see if I can find a pattern or a formula
**Table: Turning LEFT** Direction Value Turned Value North (0,1) West (-1,0) West (-1,0) South (0,-1) South (0,-1) East (1,0) East (1,0) North (0,1) **Table: Turning RIGHT** Direction Value Turned Value North (0,1) East (1,0) West (-1,0) North (0,1) South (0,-1) West (-1,0) East (1,0) South (0,-1)
Looking at the table, it is apparent that on every turn, there is a change in the field which contain a non-zero value (x or y) So we always swap the active (that's what I'll call the non-zero field) field The trick here is the sign of the values. It is not true that the sign always changes. For e.g. East--Left-->North
Turn left: - swap (x,y = y,x) - apply mask (-1,1) Turn right: - swap (x,y = y,x) - apply mask (1,-1)
- Initialise starting direction as North - Read the input - For every input: - based on turn, get new direction - multiply the direction vector by distance in input - add the new vector to point on graph
That is simply the number of block we need to walk to get there
That is the total x distance + total y distance
So the formula is to take the absolute values of both co-ordinates,
and add them
abs(x) + abs(y)
Get the input data from a file in the inputs folder. The file contains the tokens seperated by comma(,).
In [1]:
with open('../inputs/day01.txt', 'r') as f:
data = [x.strip() for x in f.read().split(',')]
Use namedtuples, because they're so nice ;) Actually, use them because they are still tuples, look like class-objects, and give more semantic context to the code.
In this case, the Turn is LEFT and RIGHT.
In [2]:
from collections import namedtuple
Turns = namedtuple('Turns', ('left', 'right'))
turns = Turns('L', 'R')
A VectorPoint is a point with a direction I use them to plot the point on the graph, and also to represent the direction of movement.
In [3]:
VectorPoint = namedtuple('VectorPoint', ('x', 'y'))
When turning, we apply this mask (the logic if above).
In [4]:
mask_left = VectorPoint(-1, 1)
mask_right = VectorPoint(1, -1)
The direction is the starting face, which the problem describes as being NORTH.
In [5]:
direction = VectorPoint(0, 1)
The point to be tracked, this is the position on graph.
In [6]:
point = VectorPoint(0, 0)
(x,y) becomes (y,x) * mask(x,y).
In [7]:
for token in data:
turn, blocks = token[:1], int(token[1:])
if turn == turns.left:
mask = mask_left
if turn == turns.right:
mask = mask_right
#
direction = VectorPoint(direction.y * mask.x, direction.x * mask.y)
point = VectorPoint(
point.x + blocks * direction.x,
point.y + blocks * direction.y)
The final distance from origin is the distance of x and y axis.
In [8]:
distance = abs(point.x) + abs(point.y)
# print(distance)
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?
As per the previous solution, this looks to be a trivial problem. We only have to check when we visit the place twice, so there has to be some way to check whether we have been to the place, which means we need to store the point we have been on the graph.
For this, we will use a set to store the points, and check at every
iteration, whether we have been to that point.
The naive solution would be to store every point we visit, so it merely
becomes a problem of sifting through searches (binary search would suffice).
But to make it more efficient, we only store the paths,
and check if the current movement cross any of the previous paths.
Let's use the property of points lying on a line segment. Suppose we have the
line segment AB, and a point P lies on the line, then the sum of the
distance of P from A and P to B
is equal to the distance from A to B. Or specified as:
AB = AP + PB
So we save every point we end up at, as endpoints, and check if the movement is along the path by checking for every point in the saved set.
Another interesting observation in terms of optimisation, is that if the
point does lie on the line, then one of the axis co-ordinates will be the
same in all three points (A, B, C). This is true in this case because all
movesments are in the single direction along a grid. So we can eliminate
points which do not satisfy this condition.
A path contains two points, A and B. Create a path namedtuple to hold them.
In [9]:
Path = namedtuple('Path', ('A', 'B'))
Paths will save all visited paths, but we do not need the constraint that they must be unique, since we are checking for intersecting points.
In [10]:
paths = []
last_point was the last point traversed
In [11]:
point = VectorPoint(0, 0)
last_point = point
(x,y) becomes (y,x) * mask(x,y).movement_mask represents the mask applied to the last point to iterate over to the current point. This gives us every point along the path. The mask takes care of negatives and direction, and helps keep the logic clear.
In [12]:
for token in data:
turn, blocks = token[:1], int(token[1:])
if turn == turns.left:
mask = mask_left
if turn == turns.right:
mask = mask_right
direction = VectorPoint(direction.y * mask.x, direction.x * mask.y)
point = VectorPoint(
point.x + blocks * direction.x,
point.y + blocks * direction.y)
if point.x == last_point.x:
if point.y > last_point.y:
movement_mask = VectorPoint(0, 1)
else:
movement_mask = VectorPoint(0, -1)
else:
if point.x > last_point.x:
movement_mask = VectorPoint(1, 0)
else:
movement_mask = VectorPoint(-1, 0)
last_point_holder = last_point
while last_point.x != point.x or last_point.y != point.y:
last_point = VectorPoint(
last_point.x + movement_mask.x,
last_point.y + movement_mask.y)
for path in paths:
if path.A.x == last_point.x and path.B.x == last_point.x:
if abs(path.A.y - last_point.y)\
+ abs(last_point.y - path.B.y)\
== abs(path.A.y - path.B.y):
break
if path.A.y == last_point.y and path.B.y == last_point.y:
if abs(path.A.x - last_point.x)\
+ abs(last_point.x - path.B.x)\
== abs(path.A.x - path.B.x):
break
else:
# No paths match, move ahead.
continue
# Some path is found. Stop searching.
break
else:
# Save the path.
# `last_point = point` at this juncture
path = Path(last_point_holder, point)
last_point = point
paths.append(path)
continue
# We found a path that has been visited
distance = abs(last_point.x) + abs(last_point.y)
# print(distance)
break
else:
print(0)
== END ==