Advent of Code 2020 - Day 12

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 N means to move north by the given value.
  • Action S means to move south by the given value.
  • Action E means to move east by the given value.
  • Action W means to move west by the given value.
  • Action L means to turn left the given number of degrees.
  • Action R means to turn right the given number of degrees.
  • Action F means to move forward by the given value in the direction the ship is currently facing.
Figure 1: After loading the file

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         S
      

      Waypoint horizontal coordinate becomes the vertical and the vertical becomes the horizontal multiplied by -1

    • 180

        E         W
      N   S --> S   N
        W         E
      

      Waypoint 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         N
      

      Waypoint 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!!

 Share!

 
comments powered by Disqus