Advent of Code 2020 Day 12
Try the simulator for Part 1!
Task: Solve for X where...
X = the sum of the absolute values of the east/west and north/south distances from the ship's starting position
Example input
F10
N3
F7
R90
F11
It represents
 A series of movements and rotations
 Notated as a singlecharacter action and an integer value
Part 1
 A regular expression to extract action and value
 A data structure for X and Y axes
 A data structure for rotation
 A data structure that maps rotation to movement
 Altogether to form a working algorithm
 Building a ship voyage simulator
A regular expression to extract action and value
 For each line, I need the first character and the integer represented by the combination of digits that follow
/(\w)(\d+)/g
This works, but it could be more specific since I know the subset of characters that are the only possibilities: NSEWLRF
/([NSEWLRF])(\d+)/g
A data structure for X and Y axes
 The example offers a typical walkthrough of a solution
 I added the arraypair at the end to indicate how I think the current distance from the start could be represented
F10 = east 10, north 0 > [10, 0] E
N3 = east 10, north 3 > [10, 3] E
F7 = east 17, north 3 > [17, 3] E
R90 = east 17, north 3 > [17, 3] S
F11 = east 17, south 8 > [17, 8] S
A data structure for rotation
 As stated in the puzzle description, the ship starts facing
east
 90 degrees  The input contains two flags that change the ship's direction:
L
andR
followed by a value divisible by 90
How might I account for this scenario?
Direction = 90
L180
Direction = 270
 Subtraction won't work: I'd get 90
 Addition would work, but only coincidentally due to the half turn
What if I used an ordered array of possible degrees acting as a compass?
[90, 180, 270, 0]
With each rotational instruction, check the character used and mutate the array accordingly:
L180
L = shift values right
180 / 90 = 2
Perform 2 shiftrights
Before any:
[90, 180, 270, 0]
After 1:
[0, 90, 180, 270] > Check first cell > Ship facing north
After 2:
[270, 0, 90, 180] > Check first cell > Ship facing west
R90
R = shift values left
90 / 90 = 1
Perform 1 shiftleft
Before any:
[270, 0, 90, 180]
After 1:
[0, 90, 180, 270] > Check first cell > Ship facing north
This feels overly complicated and has a time and space complexity that is drastically exponential.
But I think it will work.
A data structure that maps rotation to movement
 Instructions with any of
NSEW
movement seem like simple conditional clauses that never vary  However, instructions with
F
movement depend on the direction the ship is currently facing  I have an algorithm and data structure now to track the current rotation of the ship
 I want the same two things for moving the ship along the correct axis...without requiring the same number of conditional clauses as for the other four sets of movement
Knowing I will always have one of four numbers as my current degree of rotation stored intentionally as indices in an array
[ 0, 90, 180, 270 ]
I can perform a lookup of the same index of the current degree (always the first location thanks to my algorithm above) in another array that stores modifier values by which to multiply the integer in the instruction for both axes
/*
deg : n/s e/w
*/
{
'0' : [ 1, 0],
'90' : [ 0, 1],
'180': [1, 0],
'270': [ 0, 1]
}
How would this work?
F10
Direction = east (90)
[90, 180, 270, 0]
Current position:
[0, 0]
y x
Lookup '90' in object above:
[0, 1]
[0 + (10 * 0), 0 + (10 * 1)]
[0, 10]
n e
Altogether to form a working algorithm
Use the regular expression to generate a list containing only the two capture groups for each line from the puzzle input
Convert the second capture group's value to a number
Create the data structure and initial state of the compass: degree values for each of the four directions, starting with east
Create the data structure mapping each of the four directions to a triplet containing an ordinal direction and a pair of multiplier modifiers
For each item in the list of matched capture groups
Update a 2element array  starting with both elements set to 0  according to the following rules:
If the character in the first capture group is either 'L' or 'R'
Do as many times as equates to the value from the second capture group divided by 90
If the character is an 'L'
Move the number at the end of the 4element degree array to the beginning
Else  the character is an 'R'
Move the number at the beginning of the 4element degree array to the end
Else
If the character is either 'N','E','S','W'
Lookup and temporarily store the 3element array value in the object mapping degrees to ordinal direction and multiplying modifiers where the ordinal direction matches the character in the first capture group
Update the 2element array such that:
Element 1 reflects a number equivalent to: the sum of the current number and the product of the value from the second capture group and the multiplying modifier in location 2 of the 3element array
Element 2 reflects a number equivalent to: the sum of the current number and the product of the value from the second capture group and the multiplying modifier in location 3 of the 3element array
Else  the character is 'F'
Update the 2element array such that:
Element 1 reflects a number equivalent to: the sum of the current number and the product of the value from the second capture group and the multiplying modifier in location 2 of the 3element array associated with the degree key that matches the number in location 1 of the 4element degree array
Element 2 reflects a number equivalent to: the sum of the current number and the product of the value from the second capture group and the multiplying modifier in location 3 of the 3element array associated with the degree key that matches the number in location 1 of the 4element degree array
Calculate the sum of the absolute values of both elements in the final state of the accumulated array
Return the sum
Building a ship voyage simulator
 It's no fun to watch a pair of coordinates update
 It's way more fun tracking the ship's location topdown along a 2D plane
 Building that experience was quite the additional puzzle
Steps taken to build the simulator
 Create a new 4element array that would store the N,E,S,Wmost coordinates reached by the ship
 Run the algorithm entirely to calculate those four numbers
 Create a 2D array as 'tall' as the range from NS and as 'wide' as the range from WE
Then in the main loop
For each instruction line
Store two coordinates  start and end location
Compare each X,Y coordinate in each location to determine whether the ship moved horizontally or vertically
Place an 'X' at the end location
Place an '' or '' at each location between the start and end location
The hardest part for me was fiddling with the math to correctly draw each bit of the trail:
 Realizing I must use absolute values when moving West
 Recognizing when to add or subtract the incrementing/decrementing value that tracked the ship's vertical or horizontal movement
 Remembering to account for the fact that the topleft point is not 0,0  so I have to offset the north and west values to properly draw the placemarkers
After lots of trial and error  both in the code and playing with the simulator to discover new bugs  I think it works on any input!
Here's what I saw after it ran on my puzzle input
Part 2
 A new player has entered
 A small tweak to make the ship follow the waypoint
 A headscratcher to reorient the waypoint
 An algorithm that doesn't work
 Discovering the exact spot my algorithm breaks
A new player has entered
 This part introduces a 'carrot on a stick' element by way of a waypoint whose location must also be tracked
 It was exciting to learn how the rules and puzzle input adjusted to accommodate this
 And even more exciting to feel like I could solve it
A small tweak to make the ship follow the waypoint
 In Part 1,
F
instructions moved the ship a single integer value along one axis  In Part 2,
F
instructions move the ship along both axis the amount derived from multiplying the waypoint's coordinates by a shared integer
Ships coordinates:
[ x, y]
Waypoint's coordinates:
[ X, Y]
Instruction:
F10
N = 10
Calculation:
[ x + (N * X), y + (N * Y)]
In JavaScript, I represented that using map
:
ship.map((number, index) => number + (waypoint[index] * N))
A headscratcher to reorient the waypoint
 In Part 1,
L
andR
instructions changed the orientation of the ship  which I represented by shifting the order of degrees in an array and always referencing the first one  In Part 2,
L
andR
instructions rotate the waypoint around a central point  the ship  causing the waypoint's coordinates to swap order and positivity/negativity of value
I found this diagram helpful in understanding:

[y,+x]  [+x,+y]

S

[x,y]  [+y,x]

How I thought to represent this model algorithmically:
For each rotation change
Swap the order of the waypoint's coordinates
Adjust the polarity (absolute negative value) based on the current orientation as stored in a lookup table
An algorithm that doesn't work
 Well, it works on the example input
 But not on my puzzle input
 I wanted to know why
 So, once again, I referenced JavaScript solver NullDev's solution
Discovering the exact spot my algorithm breaks
After adding some console.log()
statements to both codebases and shortening the list of instructions to process until reaching the exact moment that our Manhattan Distance was different, I discovered my code's error:
 For some reason, the first
R180
instruction caused my waypoint's coordinates to update incorrectly
The way my algorithm works:
pos is a function that returns the absolute value of a number
neg is a function that returns the negated absolute value of a number
quadrants is a 4element array where each item is a 2element array containing the correct function above that represents each rotation's correct coordinate polarity:
1. NE: [pos, pos]
2. SE: [neg, pos]
3. SW: [neg, neg]
4. NW: [pos, neg]
For each 90degree increment of rotation in any L or R instruction
Shift the order of the elements in the array appropriately
Swap the order of the waypoint's coordinates
Apply each respective function from the nowfirst array element to each of the waypoint's reordered coordinates
 Unfortunately in the case of
R180
, my algorithm incorrectly updates the waypoint's coordinates  I'm not sure how I could adjust it to work properly
 I think it is fundamentally broken
In great news, it seems NullDev shared my reasoning...albeit with a better designed algorithm.
Mixed feelings as I leave this challenge
Feeling bummed:
 I really thought my algorithm would work for part 2
Feeling great:
 I solved part 1
 I built a funtowatch simulator
 I attempted part 2 and got it to work for the example input
 I used another developer's code to identify a bug in mine
 I confirmed that the core of my approach to solving part 2 was spoton...even if not executed correctly
 I learned a few better methods for calculating the current orientation and coordinates by studying NullDev's code
Top comments (0)