Advent of Code 2020 - Day 12

Hello, guys. I’m back again, but only for the weekends, maybe.

This topic is about Day 12 of the Advent of Code 2020 .

Thanks to @egze, we have a private leaderboard:
https://adventofcode.com/2020/leaderboard/private/view/39276

The join code is:
39276-eeb74f9a

Just did the first part. Nothing fancy, plain old pattern matching. Now on to the second part :slight_smile:

I ended up reimplementing complex addition, multiplication and exponentiation to solve this quiz.

I accidentally removed the code for Part 1, so here’s Part 2:

#!/usr/bin/env elixir

defmodule Navigation do
  import Kernel, except: ["+": 2, "*": 2]

  def apply_instruction(instruction, state) do
    {action, arg} = parse_instruction(instruction)
    action.(state, arg)
  end

  defp parse_instruction("N" <> value) do
    {&translate/2, {0, String.to_integer(value)}}
  end

  defp parse_instruction("S" <> value) do
    {&translate/2, {0, -String.to_integer(value)}}
  end

  defp parse_instruction("E" <> value) do
    {&translate/2, {String.to_integer(value), 0}}
  end

  defp parse_instruction("W" <> value) do
    {&translate/2, {-String.to_integer(value), 0}}
  end

  defp parse_instruction("L" <> value) do
    {&rotate/2, exp({0, 1}, div(String.to_integer(value), 90))}
  end

  defp parse_instruction("R" <> value) do
    {&rotate/2, exp({0, -1}, div(String.to_integer(value), 90))}
  end

  defp parse_instruction("F" <> value) do
    {&forward/2, String.to_integer(value)}
  end

  defp translate({position, waypoint}, value) do
    {position, waypoint + value}
  end
  
  defp rotate({position, waypoint}, value) do
    {position, waypoint * value}
  end

  defp forward({position, waypoint}, value) do
    {position + waypoint * value, waypoint}
  end

  defp {r1, i1} + {r2, i2} do
    {
      r1 + r2,
      i1 + i2
    }
  end

  defp a + b do
    Kernel.+(a, b)
  end

  defp {r1, i1} * {r2, i2} do
    {
      r1 * r2 - i1 * i2,
      r1 * i2 + r2 * i1
    }
  end

  defp n * {r, i} when is_integer(n) do
    {
      n * r,
      n * i
    }
  end

  defp c * n when is_tuple(c) and is_integer(n) do
    n * c
  end

  defp a * b do
    Kernel.*(a, b)
  end

  defp exp(c, n) do
    Stream.repeatedly(fn-> c end)
    |> Stream.take(n)
    |> Enum.reduce(&*/2)
  end
end

{x, y} = "day12.txt"
         |> File.stream!()
         |> Stream.map(&String.trim/1)
         |> Enum.reduce({{0,0}, {10,1}}, &Navigation.apply_instruction/2)
         |> elem(0)

IO.inspect(abs(x) + abs(y))

That’s where I was heading as well :slight_smile:

I really enjoyed this one. Pretty happy with my answer too, I think this is my favourite answer so far this year.

Parts 1 and 2 are almost identical, so here’s Part 2.

defmodule Day12Part2 do
  def run do
    File.read!("input")
    |> String.split("\n", trim: true)
    |> Enum.map(fn <<action::binary-1>> <> value -> {action, String.to_integer(value)} end)
    |> Enum.reduce({{0, 0}, {10, 1}}, &process/2)
    |> manhattan_distance()
    |> IO.puts()
  end

  def process({"N", value}, {boat, {vx, vy}}), do: {boat, {vx, vy + value}}
  def process({"S", value}, {boat, {vx, vy}}), do: {boat, {vx, vy - value}}
  def process({"E", value}, {boat, {vx, vy}}), do: {boat, {vx + value, vy}}
  def process({"W", value}, {boat, {vx, vy}}), do: {boat, {vx - value, vy}}
  def process({"L", value}, {boat, waypoint}), do: {boat, rotate_left(waypoint, value)}
  def process({"R", value}, {boat, waypoint}), do: {boat, rotate_right(waypoint, value)}
  def process({"F", value}, {{x, y}, {vx, vy}}), do: {{x + vx * value, y + vy * value}, {vx, vy}}

  def rotate_left(waypoint, 0), do: waypoint
  def rotate_left({vx, vy}, degrees), do: rotate_left({-vy, vx}, degrees - 90)

  def rotate_right(waypoint, 0), do: waypoint
  def rotate_right({vx, vy}, degrees), do: rotate_right({vy, -vx}, degrees - 90)

  def manhattan_distance({{x, y}, _}), do: abs(x) + abs(y)
end

Day12Part2.run()
3 Likes

derpaderp

There’s a problem in turn(deg):

          270 ->        
            case dir do    
              :east -> %{ship | facing: :north}    
              :south -> %{ship | facing: :east}    
              :west -> %{ship | facing: :south}    
              :north -> %{ship | facing: :east}  #<-- Should be :west    
            end
1 Like

yeah I caught it 30 seconds ago. Thanks.

The (almost) inevitable Manhattan distance puzzle.

defmodule Day12.Navigation1 do
  @compass [:north, :east, :south, :west]

  def run([], _dir, {x, y}), do: abs(x) + abs(y)

  def run([nav | navigation], dir, pos) do
    {newdir, newpos} = move(nav, dir, pos)
    run(navigation, newdir, newpos)
  end

  def move({"F", dist}, dir, pos) do
    case dir do
      :north -> move({"N", dist}, dir, pos)
      :south -> move({"S", dist}, dir, pos)
      :east -> move({"E", dist}, dir, pos)
      :west -> move({"W", dist}, dir, pos)
    end
  end

  def move({"N", dist}, dir, {x, y}), do: {dir, {x, y + dist}}
  def move({"S", dist}, dir, {x, y}), do: {dir, {x, y - dist}}
  def move({"E", dist}, dir, {x, y}), do: {dir, {x + dist, y}}
  def move({"W", dist}, dir, {x, y}), do: {dir, {x - dist, y}}

  def move({"R", 0}, dir, pos), do: {dir, pos}
  def move({"R", 360}, dir, pos), do: {dir, pos}

  def move({"R", angle}, dir, pos) do
    multiple = div(angle, 90)
    newdir = Enum.at(@compass, rem(multiple + Enum.find_index(@compass, &(&1 == dir)), 4))
    {newdir, pos}
  end

  def move({"L", angle}, dir, pos), do: move({"R", 360 - angle}, dir, pos)
end

defmodule Day12.Navigation2 do
  def run([], _dir, {x, y}, _wp), do: abs(x) + abs(y)

  def run([nav | navigation], dir, pos, wp) do
    {newdir, newpos, newwp} = move(nav, dir, pos, wp)
    run(navigation, newdir, newpos, newwp)
  end

  def move({"F", dist}, dir, {x, y}, {wpx, wpy} = wp) do
    case dir do
      :north -> {dir, {x + dist * wpx, y + dist * wpy}, wp}
      :south -> {dir, {x + dist * wpx, y - dist * wpy}, wp}
      :east -> {dir, {x + dist * wpx, y + dist * wpy}, wp}
      :west -> {dir, {x - dist * wpx, y + dist * wpy}, wp}
    end
  end

  def move({"N", dist}, dir, pos, {wpx, wpy}), do: {dir, pos, {wpx, wpy + dist}}
  def move({"S", dist}, dir, pos, {wpx, wpy}), do: {dir, pos, {wpx, wpy - dist}}
  def move({"E", dist}, dir, pos, {wpx, wpy}), do: {dir, pos, {wpx + dist, wpy}}
  def move({"W", dist}, dir, pos, {wpx, wpy}), do: {dir, pos, {wpx - dist, wpy}}

  def move({"R", 0}, dir, pos, wp), do: {dir, pos, wp}
  def move({"R", 360}, dir, pos, wp), do: {dir, pos, wp}

  def move({"R", angle}, dir, pos, {wpx, wpy}) do
    case angle do
      90 -> {dir, pos, {wpy, -wpx}}
      180 -> {dir, pos, {-wpx, -wpy}}
      270 -> {dir, pos, {-wpy, wpx}}
    end
  end

  def move({"L", angle}, dir, pos, wp), do: move({"R", 360 - angle}, dir, pos, wp)
end

defmodule Day12 do
  alias Day12.Navigation1
  alias Day12.Navigation2

  def readinput() do
    File.read!("12.input.txt")
    |> String.split("\n", trim: true)
    |> Enum.map(&command/1)
  end

  def command(cmdstr) do
    {dir, dist} = String.split_at(cmdstr, 1)
    {dir, String.to_integer(dist)}
  end

  def part1(input \\ readinput()) do
    input
    |> Navigation1.run(:east, {0, 0})
  end

  def part2(input \\ readinput()) do
    input
    |> Navigation2.run(:east, {0, 0}, {10, 1})
  end
end

Agree with @adamu, this one was enjoyable and felt like a nice fit for Elixir (as opposed to how I felt after yesterdays puzzle).

Posting part 2:

defmodule AdventOfCode.Day12 do
  @data_dir Path.expand("../data", __DIR__)

  # Data structure is {position, waypoint} where both position and waypoint are {east, north}
  @initial_boat {{0, 0}, {10, 1}}

  def distance({east, north}), do: abs(east) + abs(north)

  def run_instructions(instructions), do: run_instructions(@initial_boat, instructions)
  def run_instructions({position, _}, []), do: position
  def run_instructions(boat, [h | t]), do: boat |> execute(h) |> run_instructions(t)

  def execute(boat, <<instr::binary-size(1), distance::binary>>) do
    execute(boat, instr, String.to_integer(distance))
  end

  def execute(boat, "F", distance), do: move_position(boat, distance)

  def execute(boat, "N", distance), do: move_waypoint(boat, {0, 1}, distance)
  def execute(boat, "S", distance), do: move_waypoint(boat, {0, -1}, distance)
  def execute(boat, "W", distance), do: move_waypoint(boat, {-1, 0}, distance)
  def execute(boat, "E", distance), do: move_waypoint(boat, {1, 0}, distance)

  def execute(boat, "R", 0), do: boat
  def execute({pos, {waypoint_e, waypoint_n}}, "R", degrees) do
    execute({pos, {waypoint_n, -waypoint_e}}, "R", degrees - 90)
  end

  def execute(boat, "L", 0), do: boat
  def execute({pos, {waypoint_e, waypoint_n}}, "L", degrees) do
    execute({pos, {-waypoint_n, waypoint_e}}, "L", degrees - 90)
  end

  def move({x, y}, {dir_x, dir_y}, distance) do
    {x + dir_x * distance, y + dir_y * distance}
  end

  def move_waypoint({position, waypoint}, direction, distance) do
    {position, move(waypoint, direction, distance)}
  end

  def move_position({position, waypoint}, distance) do
    {move(position, waypoint, distance), waypoint}
  end

  def run() do
    @data_dir
    |> Path.join("day12.txt")
    |> File.read!()
    |> String.split("\n", trim: true)
    |> run_instructions()
    |> distance()
  end
end

Hi there :wave:
Not too much of a challenge today, but still funny :slight_smile:

Part1 / Part2

1 Like

That was a nice trick implementing rotate left as rotate right(360 - n).

2 Likes

I was sure there was some clever trick for the rotation, but this morning I was especially sleepy and settled for a map…

defmodule AdventOfCode.Day12 do
  @dirs %{
    :north => :west,
    :west => :south,
    :south => :east,
    :east => :north
  }

  def part1(input) do
    {{x, y}, _} =
      input
      |> String.split("\n", trim: true)
      |> Enum.map(&parse_instruction/1)
      |> Enum.reduce({{0, 0}, :east}, &move_ship/2)

    manhattan_dist(x, y)
  end

  def part2(input) do
    {{x, y}, _} =
      input
      |> String.split("\n", trim: true)
      |> Enum.map(&parse_instruction/1)
      |> Enum.reduce({{0, 0}, {10, 1}}, &move_ship_and_wp/2)

    manhattan_dist(x, y)
  end

  def parse_instruction(line) do
    {dir, amt} = String.split_at(line, 1)
    {dir, String.to_integer(amt)}
  end

  def move_ship(step, {ship, dir}) do
    case step do
      {"N", n} -> {forward(ship, :north, n), dir}
      {"S", n} -> {forward(ship, :south, n), dir}
      {"W", n} -> {forward(ship, :west, n), dir}
      {"E", n} -> {forward(ship, :north, n), dir}
      {"F", n} -> {forward(ship, dir, n), dir}
      {"L", n} -> {ship, change_dir(dir, :left, div(n, 90))}
      {"R", n} -> {ship, change_dir(dir, :right, div(n, 90))}
    end
  end

  def move_ship_and_wp(step, {ship, wp}) do
    case step do
      {"N", n} -> {ship, forward(wp, :north, n)}
      {"S", n} -> {ship, forward(wp, :south, n)}
      {"W", n} -> {ship, forward(wp, :west, n)}
      {"E", n} -> {ship, forward(wp, :east, n)}
      {"F", n} -> {move_to_wp(ship, wp, n), wp}
      {"L", n} -> {ship, rotate_wp(wp, :left, div(n, 90))}
      {"R", n} -> {ship, rotate_wp(wp, :right, div(n, 90))}
    end
  end

  def change_dir(curr, _, 0), do: curr

  def change_dir(curr, dir, n) do
    change_dir(Map.get(dirs(dir), curr), dir, n - 1)
  end

  def move_to_wp(ship, _, 0), do: ship

  def move_to_wp({sx, sy}, wp = {wx, wy}, n) do
    move_to_wp({sx + wx, sy + wy}, wp, n - 1)
  end

  def rotate_wp(wp, _, 0), do: wp
  def rotate_wp({x, y}, :left, n), do: rotate_wp({-y, x}, :left, n - 1)
  def rotate_wp({x, y}, :right, n), do: rotate_wp({y, -x}, :right, n - 1)

  def forward({x, y}, :north, n), do: {x, y + n}
  def forward({x, y}, :south, n), do: {x, y - n}
  def forward({x, y}, :west, n), do: {x - n, y}
  def forward({x, y}, :east, n), do: {x + n, y}

  def dirs(:left), do: @dirs
  def dirs(:right), do: Map.new(@dirs, fn {k, v} -> {v, k} end)

  def manhattan_dist(x, y), do: abs(x) + abs(y)
end
defmodule Day12 do
  @moduledoc false

  @input File.read!("lib/input")
         |> String.split("\n", trim: true)
         |> Enum.map(fn <<cmd::binary-size(1)>> <> dist -> {cmd, String.to_integer(dist)} end)

  defmodule Ship do
    @moduledoc false

    defstruct heading: {1, 0}, coord: {0, 0}

    use Agent

    def start_link do
      Agent.start_link(fn -> %Ship{} end, name: __MODULE__)
    end

    def start_link({x, y}) do
      Agent.start_link(fn -> %Ship{heading: {x, y}} end, name: __MODULE__)
    end

    def direction do
      Agent.get(__MODULE__, fn ship -> ship.heading end)
    end

    def manhattan_dist do
      Agent.get(__MODULE__, fn ship ->
        {x, y} = ship.coord
        abs(x) + abs(y)
      end)
    end

    def forward(dist) do
      Agent.update(__MODULE__, fn ship ->
        {x, y} = ship.coord
        {a, b} = ship.heading

        %{ship | coord: {x + dist * a, y + dist * b}}
      end)
    end

    def turn do
      Agent.update(__MODULE__, fn ship ->
        {x, y} = ship.heading

        %{ship | heading: {y, -x}}
      end)
    end

    def move(dir, dist) do
      Agent.update(__MODULE__, fn ship ->
        {x, y} = ship.coord

        case dir do
          :east -> %{ship | coord: {x + dist, y}}
          :south -> %{ship | coord: {x, y - dist}}
          :west -> %{ship | coord: {x - dist, y}}
          :north -> %{ship | coord: {x, y + dist}}
        end
      end)
    end

    def to_waypoint(count) do
      Agent.update(__MODULE__, fn ship ->
        {lat, long} = ship.coord
        {x, y} = ship.heading

        %{ship | coord: {lat + x * count, long + y * count}}
      end)
    end

    def move_waypoint(dir, dist) do
      Agent.update(__MODULE__, fn ship ->
        {x, y} = ship.heading

        case dir do
          :east -> %{ship | heading: {x + dist, y}}
          :south -> %{ship | heading: {x, y - dist}}
          :west -> %{ship | heading: {x - dist, y}}
          :north -> %{ship | heading: {x, y + dist}}
        end
      end)
    end

    def status do
      Agent.get(__MODULE__, & &1)
    end

    def stop do
      Agent.stop(__MODULE__)
    end
  end

  def part_1() do
    Ship.start_link()

    @input
    |> Enum.each(fn {cmd, dist} ->
      case cmd do
        "E" -> Ship.move(:east, dist)
        "S" -> Ship.move(:south, dist)
        "W" -> Ship.move(:west, dist)
        "N" -> Ship.move(:north, dist)
        "F" -> Ship.forward(dist)
        "R" -> 1..div(dist, 90) |> Enum.each(fn _ -> Ship.turn() end)
        "L" -> 1..div(360 - dist, 90) |> Enum.each(fn _ -> Ship.turn() end)
      end
    end)

    IO.puts(Ship.manhattan_dist())
    Ship.stop()
  end

  def part_2() do
    Ship.start_link({10, 1})

    @input
    |> Enum.each(fn {cmd, dist} ->
      case cmd do
        "E" -> Ship.move_waypoint(:east, dist)
        "S" -> Ship.move_waypoint(:south, dist)
        "W" -> Ship.move_waypoint(:west, dist)
        "N" -> Ship.move_waypoint(:north, dist)
        "F" -> Ship.to_waypoint(dist)
        "R" -> 1..div(dist, 90) |> Enum.each(fn _ -> Ship.turn() end)
        "L" -> 1..div(360 - dist, 90) |> Enum.each(fn _ -> Ship.turn() end)
      end
    end)

    IO.puts(Ship.manhattan_dist())
    Ship.stop()
  end
end

Day12.part_1()
Day12.part_2()

This challenge highlighted how important it is that I sleep as I once mistyped :east for :west and once put div(360 - 90, 90) instead of div(360-deg, 90). I was sure my logic was sound and could not spot the errors for far too long. This was a nice way for me to get my feet wet with Agents though.

Finally I got around to do todays quiz :slight_smile:

defmodule Aoc2020.Day12 do
  def part1(input) do
    simulate({{0, 0}, {1, 0}}, input)
    |> distance()
  end

  def part2(input) do
    simulate_waypoint({{0, 0}, {10, 1}}, input)
    |> distance()
  end

  def simulate_waypoint(state, instructions) do
    for instruction <- instructions, reduce: state do
      {ship, waypoint} ->
        case instruction do
          {:forward, value} ->
            {translate(ship, scale(waypoint, value)), waypoint}

          {:move, vector} ->
            {ship, translate(waypoint, vector)}

          {:right, times} ->
            {ship, rotate({:right, times}, waypoint)}

          {:left, times} ->
            {ship, rotate({:left, times}, waypoint)}
        end
    end
    |> elem(0)
  end

  def simulate(state, instructions) do
    for instruction <- instructions, reduce: state do
      {pos, dir} ->
        case instruction do
          {:forward, units} -> {translate(pos, scale(dir, units)), dir}
          {:left, units} -> {pos, rotate({:left, units}, dir)}
          {:right, units} -> {pos, rotate({:right, units}, dir)}
          {:move, vector} -> {translate(pos, vector), dir}
        end
    end
    |> elem(0)
  end

  def distance({x, y}), do: abs(x) + abs(y)

  def scale({x, y}, factor), do: {x * factor, y * factor}
  def translate({x1, y1}, {x2, y2}), do: {x1 + x2, y1 + y2}

  def rotate({_, 0}, dir), do: dir
  def rotate({:right, n}, dir), do: rotate({:right, n - 1}, rotate(:right, dir))
  def rotate({:left, n}, dir), do: rotate({:left, n - 1}, rotate(:left, dir))
  def rotate(:left, {x, y}), do: {-y, x}
  def rotate(:right, {x, y}), do: {y, -x}

  def input_stream(path) do
    File.stream!(path)
    |> Stream.map(&parse/1)
  end

  def direction(:north), do: {0, 1}
  def direction(:east), do: {1, 0}
  def direction(:west), do: {-1, 0}
  def direction(:south), do: {0, -1}

  def parse(line) do
    line
    |> String.trim()
    |> case do
      "F" <> value -> {:forward, String.to_integer(value)}
      "R" <> value -> {:right, round(String.to_integer(value) / 90)}
      "L" <> value -> {:left, round(String.to_integer(value) / 90)}
      "N" <> value -> {:move, scale(direction(:north), String.to_integer(value))}
      "E" <> value -> {:move, scale(direction(:east), String.to_integer(value))}
      "S" <> value -> {:move, scale(direction(:south), String.to_integer(value))}
      "W" <> value -> {:move, scale(direction(:west), String.to_integer(value))}
    end
  end
end

input = Aoc2020.Day12.input_stream("input.txt")

Aoc2020.Day12.part1(input)
|> IO.inspect(label: "part1")

Aoc2020.Day12.part2(input)
|> IO.inspect(label: "part2")

part2 - O(n)

*rotate_step can be improved to avoid recursion

defmodule Advent.Day12b do
  # part 2
  def start(file \\ "/tmp/input.txt"), do:
    File.read!(file) |> String.split() |> execute({ {1, 10},  {0, 0} })

  def execute([], {_waypt, {x, y}}), do: abs(x) + abs(y)
  def execute([h|t], {waypt, ship}), do: execute(t, execute(:binary.at(h, 0), String.to_integer(:binary.part(h, 1, byte_size(h) - 1)), waypt, ship))

  def execute(?F, v,{xw, yw}, {x, y}), do: {{xw, yw}, {x + v * xw,  y + v * yw} }
  def execute(n, v, waypt, ship) when n in [?R, ?L], do: {rotate(waypt, n == ?R && v || -v), ship}
  def execute(n, v, {x, y}, ship) when n in [?N, ?S], do: { {x + (n == ?N && v || -v), y}, ship}
  def execute(n, v, {x, y}, ship), do: { {x, y + (n == ?E && v || -v)}, ship}

  def rotate(waypt, radius), do: (rem(radius, 360) / 90) |> trunc() |> rotate_step(waypt)

  def rotate_step(0, waypt), do: waypt
  def rotate_step(v, {x, y}) when v > 0, do: rotate_step(v - 1, {-y, x})
  def rotate_step(v, {x, y}), do: rotate_step(v + 1, {y, -x})

end

I forgot String.split defaults to splitting on white-space with trimming, so the single-argument version is fine for this exercise. Still, being explicit doesn’t help. :innocent:

1 Like

A bit late to the party for this one: I used almost exclusively vector math (besides for rotation in part 1) and as a result I only have 3 helpers (8 loc) dealing with actual math, while the rest of the code only deals with the higher level logic: