After the waiting room we are at a ferry navigating to the island. There seems to be a problem with the navigation system, and we volunteered to help. We have a set of instructions and we need to make some sense of them to help the captain circumvent the storm.
The solution to the problem will be given by calculating the Manhattan distance (sum of the absolute values of its east/west position and its north/south position).
If you want to follow along please download AdventOfCode2020.pbit and check Day 1 post for instructions.
Part 1
Our input consists of a file with an instruction per line. The first character on each instruction will tell us the type of instruction and the number after the character will be it’s value.
- Action
Nmeans to move north by the given value. - Action
Smeans to move south by the given value. - Action
Emeans to move east by the given value. - Action
Wmeans to move west by the given value. - Action
Lmeans to turn left the given number of degrees. - Action
Rmeans to turn right the given number of degrees. - Action
Fmeans to move forward by the given value in the direction the ship is currently facing.
Figure 1: After loading the file
Now we need to loop over the lines while keeping track of the direction of the ship and it’s coordinates. We start from coordinates \((0,0)\) and with ship faced East.
To make things easier while looping we are going to map the directions to numbers like so:
- 0 – East
- 1 – South
- 2 – West
- 3 – North
Now we are in conditions to use modular arithmetic described in a book
in 1801 by Carl Gauss. A great example is the mathematics behind
clocks. In our case, we will be using modulus 4, the number of
directions. This will allow us to receive an instruction like R270,
calculate the modulus, add that to our current direction and get the
new one. If we were heading West, we would calculate \((3+2)\ mod\ 4\),
this returns [1 – South] as our new direction.
There’s only one catch, the Number.Mod function in Power Query
only works correctly for positive numbers.
Number.Mod(3,4) = 3
Number.Mod(-1,4) = -1
Because of this, after the first modulus operation we need to add 4 and repeat the operation for it to return the correct value.
Placing these starting positions on the loop and rowCount as the
stopping condition:
loopP1 = List.Generate(
()=> [Direction=0, Horizontal=0, Vertical=0, Row=0],
each [Row] <= rowCount,
The conditions for the direction to change with our modulus logic:
Direction = if instructions{[Row]} = "R"
then Number.Mod(Number.Mod([Direction] + steps{[Row]}/90, 4) + 4, 4)
else
if instructions{[Row]} = "L"
then Number.Mod(Number.Mod([Direction] - steps{[Row]}/90, 4) + 4, 4)
else [Direction],
Horizontal movements:
Horizontal = if instructions{[Row]} = "E"
then [Horizontal] + steps{[Row]}
else
if instructions{[Row]} = "W"
then [Horizontal] - steps{[Row]}
else
if instructions{[Row]} = "F" and [Direction] = 0
then [Horizontal] + steps{[Row]}
else
if instructions{[Row]} = "F" and [Direction] = 2
then [Horizontal] - steps{[Row]}
else [Horizontal]
Vertical movements:
Vertical = if instructions{[Row]} = "N"
then [Vertical] + steps{[Row]}
else
if instructions{[Row]} = "S"
then [Vertical] - steps{[Row]}
else
if instructions{[Row]} = "F" and [Direction] = 3
then [Vertical] + steps{[Row]}
else
if instructions{[Row]} = "F" and [Direction] = 1
then [Vertical] - steps{[Row]}
else [Vertical]
After we take the last result of the loop we just add the absolute values of the horizontal and vertical values and we have our solution:
Number.Abs(lastResultP1[Horizontal]) + Number.Abs(lastResultP1[Vertical])
Part 2
Our initial assumptions were wrong. There are instructions indicating
that the movement actions are associated with a waypoint except for
the F instruction that means the ship moves forward the number of
times equal to the given value.
The waypoint is relative to the ship, so when the ship moves the waypoint moves with it.
This means that now we will be tracking four coordinates. The ship and the waypoint horizontal/vertical coordinates.
here’s the possibilities:
- E – we add the value to waypoint horizontal coordinate
- W – we subtract the value to waypoint horizontal coordinate
- N – we add the value to waypoint y vertical coordinate
- S – we subtract the value to waypoint y vertical coordinate
- F – we add to the ship horizontal/vertical coordinates the multiplication of the horizontal/vertical coordinates of the waypoint with the value of the instruction respectively
- R
-
90
E N N S --> W E W SWaypoint horizontal coordinate becomes the vertical and the vertical becomes the horizontal multiplied by -1
-
180
E W N S --> S N W EWaypoint horizontal coordinate becomes the horizontal multiplied by -1 and the vertical becomes the vertical multiplied by -1
-
270
E S N S --> E W W NWaypoint horizontal coordinate becomes the vertical multiplied by -1 and the vertical becomes the horizontal
-
- L is just be the inverse of the R actions
Where’s our loop in all it’s glory:
List.Generate(
() => [WX=10, WY=1, SX=0, SY=0, Row=0],
each [Row] <= rowCount,
each [WX= if instructions{[Row]} = "E" then [WX] + steps{[Row]} else
if instructions{[Row]} = "W" then [WX] - steps{[Row]} else
if instructions{[Row]} = "R" then
if steps{[Row]} = 90 then [WY] else
if steps{[Row]} = 180 then [WX] * -1 else
if steps{[Row]} = 270 then [WY] * -1 else [WX]
else
if instructions{[Row]} = "L" then
if steps{[Row]} = 90 then [WY] * -1 else
if steps{[Row]} = 180 then [WX] * -1 else
if steps{[Row]} = 270 then [WY] else [WX]
else [WX],
WY= if instructions{[Row]} = "N" then [WY] + steps{[Row]} else
if instructions{[Row]} = "S" then [WY] - steps{[Row]} else
if instructions{[Row]} = "R" then
if steps{[Row]} = 90 then [WX] * -1 else
if steps{[Row]} = 180 then [WY] * -1 else
if steps{[Row]} = 270 then [WX] else [WY]
else
if instructions{[Row]} = "L" then
if steps{[Row]} = 90 then [WX] else
if steps{[Row]} = 180 then [WY] * -1 else
if steps{[Row]} = 270 then [WX] * -1 else [WY]
else [WY],
SX= if instructions{[Row]} = "F" then [SX] + steps{[Row]} * [WX] else [SX],
SY= if instructions{[Row]} = "F" then [SY] + steps{[Row]} * [WY] else [SY],
Row=[Row]+1
]
)
Conclusion
An interesting puzzle that made me draw a lot to understand all the movement logic. Hope you’ve enjoyed this one.
Have fun!!