Day 15 - Advent of Code 2018

day15.exs

# https://adventofcode.com/2018/day/15

defmodule Day15 do
  @default_attack_power 3

  def parse_map(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.reduce({0, %{}}, fn row, {y, map} ->
      {y + 1, parse_row(map, row, y)}
    end)
    |> elem(1)
  end

  def parse_row(map, row, y) do
    row
    |> String.to_charlist()
    |> Enum.reduce({0, map}, fn square, {x, map} ->
      {x + 1, Map.put(map, {y, x}, parse_square(square))}
    end)
    |> elem(1)
  end

  def parse_square(square) do
    case square do
      ?# -> :wall
      ?. -> :open_cavern
      ?G -> {:goblin, 200}
      ?E -> {:elf, 200}
    end
  end

  def determine_order(map) do
    map
    |> Enum.flat_map(fn {point, square} ->
      case square do
        {:goblin, _} -> [point]
        {:elf, _} -> [point]
        _ -> []
      end
    end)
    |> Enum.sort()
  end

  def nearest_wanted_point(point, map, wanted?) do
    nearest_wanted_point([point], %{point => 0}, wanted?, map, [], [])
  end

  defp nearest_wanted_point([head | rest], distances, wanted?, map, new_points, wanted_points) do
    {new_points, wanted_points, distances} =
      head
      |> adjacent_points
      |> Enum.reject(fn point -> Map.has_key?(distances, point) end)
      |> Enum.reduce({new_points, wanted_points, distances}, fn point,
                                                                {new_points, wanted_points,
                                                                 distances} ->
        case wanted?.(point, map) do
          :skip -> {new_points, wanted_points, distances}
          :ok -> {[point | new_points], wanted_points, Map.put(distances, point, true)}
          :wanted -> {new_points, [head | wanted_points], distances}
        end
      end)

    nearest_wanted_point(rest, distances, wanted?, map, new_points, wanted_points)
  end

  defp nearest_wanted_point([], _distances, _wanted?, _map, [], []), do: nil

  defp nearest_wanted_point([], distances, wanted?, map, new_points, []) do
    nearest_wanted_point(new_points, distances, wanted?, map, [], [])
  end

  defp nearest_wanted_point([], _distances, _wanted?, _map, _new_points, wanted_points) do
    wanted_points
    |> Enum.sort()
    |> List.first()
  end

  defp adjacent_points({y, x}) do
    [
      {y - 1, x},
      {y, x - 1},
      {y, x + 1},
      {y + 1, x}
    ]
  end

  def target_move_point(current_point, map) do
    {unit_race, _} = Map.get(map, current_point)

    nearest_wanted_point(current_point, map, fn point, map ->
      case Map.get(map, point) do
        :wall -> :skip
        :open_cavern -> :ok
        {^unit_race, _} -> :skip
        {_, _} -> :wanted
      end
    end)
  end

  def move_point(nil, _current_point, _map), do: nil
  def move_point(target_point, current_point, _map) when target_point == current_point, do: nil

  def move_point(target_point, current_point, map) do
    nearest_wanted_point(target_point, map, fn point, map ->
      case {point, Map.get(map, point)} do
        {^current_point, _} -> :wanted
        {_, :open_cavern} -> :ok
        {_, _} -> :skip
      end
    end)
  end

  def move(map, current_point) do
    current_point
    |> target_move_point(map)
    |> move_point(current_point, map)
    |> case do
      nil ->
        {map, current_point}

      next_point ->
        map =
          map
          |> Map.replace!(current_point, :open_cavern)
          |> Map.replace!(next_point, Map.get(map, current_point))

        {map, next_point}
    end
  end

  def attack(map, current_point, elf_attack_power \\ @default_attack_power) do
    {race, _} = Map.get(map, current_point)

    attack_power =
      case race do
        :elf -> elf_attack_power
        _ -> @default_attack_power
      end

    current_point
    |> adjacent_points
    |> Enum.filter(&enemy?(Map.get(map, &1), race))
    |> Enum.sort(fn x, y -> elem(Map.get(map, x), 1) <= elem(Map.get(map, y), 1) end)
    |> List.first()
    |> hit(map, attack_power)
  end

  defp enemy?(square, race) do
    case square do
      {^race, _} -> false
      {_, _} -> true
      _ -> false
    end
  end

  defp hit(nil, map, _attack_power), do: map

  defp hit(point, map, attack_power) do
    Map.update!(map, point, fn {race, hp} ->
      if hp > attack_power do
        {race, hp - attack_power}
      else
        :open_cavern
      end
    end)
  end

  def turn(map, current_point, elf_attack_power \\ @default_attack_power) do
    {map, current_point} = move(map, current_point)
    attack(map, current_point, elf_attack_power)
  end

  def single_round(_map, elf_attack_power \\ @default_attack_power)

  def single_round(map, elf_attack_power) do
    single_round(map, elf_attack_power, determine_order(map))
  end

  defp single_round(map, elf_attack_power, [current_point | rest]) do
    cond do
      Map.get(map, current_point) == :open_cavern ->
        single_round(map, elf_attack_power, rest)

      continue_combat?(map) ->
        map
        |> turn(current_point, elf_attack_power)
        |> single_round(elf_attack_power, rest)

      true ->
        {:finished, map}
    end
  end

  defp single_round(map, _elf_attack_power, []), do: {:continue, map}

  def continue_combat?(map) do
    Enum.any?(map, fn {_, square} -> enemy?(square, :goblin) end) &&
      Enum.any?(map, fn {_, square} -> enemy?(square, :elf) end)
  end

  def combat(map, n \\ 0)

  def combat(map, n) do
    case single_round(map) do
      {:continue, map} -> combat(map, n + 1)
      {:finished, map} -> {map, n}
    end
  end

  def calc_outcome({map, n}) do
    map
    |> Enum.flat_map(fn {_point, square} ->
      case square do
        {:goblin, hp} -> [hp]
        {:elf, hp} -> [hp]
        _ -> []
      end
    end)
    |> Enum.reduce(0, fn hp, acc -> hp + acc end)
    |> Kernel.*(n)
  end

  def part1(map) do
    map
    |> parse_map
    |> combat
    |> calc_outcome
  end

  def combat_with_modified_elf_attack_power(map, elf_attack_power, n \\ 0)

  def combat_with_modified_elf_attack_power(map, elf_attack_power, 0) do
    combat_with_modified_elf_attack_power(map, elf_attack_power, 0, count_elfs(map))
  end

  def combat_with_modified_elf_attack_power(map, elf_attack_power, n, n_elfs) do
    {status, next_map} = single_round(map, elf_attack_power)

    case {status, next_map, count_elfs(next_map)} do
      {:continue, map, ^n_elfs} ->
        combat_with_modified_elf_attack_power(map, elf_attack_power, n + 1, n_elfs)

      {:finished, map, ^n_elfs} ->
        {map, n}

      _ ->
        :elf_died
    end
  end

  defp count_elfs(map) do
    Enum.count(map, fn {_point, square} ->
      case square do
        {:elf, _} -> true
        _ -> false
      end
    end)
  end

  def combat_with_optimal_elf_attack_power(_map, attack_power \\ @default_attack_power + 1)

  def combat_with_optimal_elf_attack_power(map, attack_power) do
    case combat_with_modified_elf_attack_power(map, attack_power) do
      :elf_died -> combat_with_optimal_elf_attack_power(map, attack_power + 1)
      result -> result
    end
  end

  def part2(map) do
    map
    |> parse_map
    |> combat_with_optimal_elf_attack_power
    |> calc_outcome
  end
end

defmodule Day15Test do
  use ExUnit.Case

  def remove_hp(map) do
    Enum.map(map, fn square ->
      case square do
        {race, _hp} -> race
        square -> square
      end
    end)
  end

  test "parsing the map (our puzzle input)" do
    assert Day15.parse_map("""
           ####
           #.GE
           """) == %{
             {0, 0} => :wall,
             {0, 1} => :wall,
             {0, 2} => :wall,
             {0, 3} => :wall,
             {1, 0} => :wall,
             {1, 1} => :open_cavern,
             {1, 2} => {:goblin, 200},
             {1, 3} => {:elf, 200}
           }
  end

  test "parsing the row of the map (single line of our puzzle input)" do
    input = %{
      {0, 0} => :wall,
      {0, 1} => :wall
    }

    output = %{
      {0, 0} => :wall,
      {0, 1} => :wall,
      {1, 0} => :open_cavern,
      {1, 1} => :open_cavern
    }

    assert Day15.parse_row(input, "..", 1) == output
  end

  test "parsing the square of the map (single char from our puzzle input)" do
    assert Day15.parse_square(?#) == :wall
    assert Day15.parse_square(?.) == :open_cavern
    assert Day15.parse_square(?G) == {:goblin, 200}
    assert Day15.parse_square(?E) == {:elf, 200}
  end

  test "choosing the point with the shortest distance which meets the given conditions" do
    assert Day15.nearest_wanted_point(
             {3, 5},
             Day15.parse_map("""
             #######
             #.G...#
             #...#.#
             #.E.#G#
             #######
             """),
             fn point, map ->
               case Map.get(map, point) do
                 :wall -> :skip
                 :open_cavern -> :ok
                 {:goblin, _} -> :skip
                 {:elf, _} -> :wanted
               end
             end
           ) == {2, 2}
  end

  test "choosing the point with the shortest distance to the enemy unit" do
    assert Day15.target_move_point(
             {1, 2},
             Day15.parse_map("""
             #######
             #.E...#
             #.....#
             #...G.#
             #######
             """)
           ) == {2, 4}

    assert Day15.target_move_point(
             {1, 1},
             Day15.parse_map("""
             #######
             #E..G.#
             #...#.#
             #.G.#G#
             #######
             """)
           ) == {1, 3}

    assert Day15.target_move_point(
             {1, 2},
             Day15.parse_map("""
             #######
             #.G...#
             #.....#
             #...G.#
             #######
             """)
           ) == nil

    assert Day15.target_move_point(
             {1, 2},
             Day15.parse_map("""
             #######
             #.GE..#
             #..G..#
             #######
             """)
           ) == {1, 2}
  end

  test "choosing the first point on the path to the given point" do
    assert Day15.move_point(
             {2, 4},
             {1, 2},
             Day15.parse_map("""
             #######
             #.E...#
             #.....#
             #...G.#
             #######
             """)
           ) == {1, 3}

    assert Day15.move_point(
             {2, 4},
             {2, 4},
             Day15.parse_map("""
             #######
             #.E...#
             #.....#
             #...G.#
             #######
             """)
           ) == nil
  end

  test "moving units" do
    assert Day15.move(
             Day15.parse_map("""
             #######
             #.E...#
             #.....#
             #...G.#
             #######
             """),
             {1, 2}
           ) == {
             Day15.parse_map("""
             #######
             #..E..#
             #.....#
             #...G.#
             #######
             """),
             {1, 3}
           }

    assert Day15.move(
             Day15.parse_map("""
             ####
             #EE#
             #EE#
             #G.#
             ####
             """),
             {1, 1}
           ) == {
             Day15.parse_map("""
             ####
             #EE#
             #EE#
             #G.#
             ####
             """),
             {1, 1}
           }

    assert Day15.move(
             Day15.parse_map("""
             #######
             #.E...#
             #.GG..#
             #...G.#
             #######
             """),
             {1, 2}
           ) == {
             Day15.parse_map("""
             #######
             #.E...#
             #.GG..#
             #...G.#
             #######
             """),
             {1, 2}
           }
  end

  test "attacking" do
    assert Day15.attack(
             %{
               {0, 1} => {:elf, 200},
               {0, 2} => {:goblin, 200}
             },
             {0, 1}
           ) ==
             %{
               {0, 1} => {:elf, 200},
               {0, 2} => {:goblin, 197}
             }

    assert Day15.attack(
             %{
               {0, 1} => {:elf, 200},
               {0, 2} => {:goblin, 3}
             },
             {0, 1}
           ) ==
             %{
               {0, 1} => {:elf, 200},
               {0, 2} => :open_cavern
             }

    assert Day15.attack(
             %{
               {0, 0} => {:goblin, 200},
               {0, 1} => {:elf, 200},
               {0, 2} => {:goblin, 200}
             },
             {0, 1}
           ) ==
             %{
               {0, 0} => {:goblin, 197},
               {0, 1} => {:elf, 200},
               {0, 2} => {:goblin, 200}
             }

    assert Day15.attack(
             %{
               {0, 0} => {:goblin, 200},
               {1, 0} => {:elf, 200},
               {2, 0} => {:goblin, 200}
             },
             {1, 0}
           ) ==
             %{
               {0, 0} => {:goblin, 197},
               {1, 0} => {:elf, 200},
               {2, 0} => {:goblin, 200}
             }

    assert Day15.attack(
             %{
               {0, 0} => {:goblin, 200},
               {0, 1} => {:elf, 200},
               {0, 2} => {:goblin, 199}
             },
             {0, 1}
           ) ==
             %{
               {0, 0} => {:goblin, 200},
               {0, 1} => {:elf, 200},
               {0, 2} => {:goblin, 196}
             }
  end

  test "single round" do
    assert Day15.single_round(
             Day15.parse_map("""
             #########
             #G..G..G#
             #.......#
             #.......#
             #G..E..G#
             #.......#
             #.......#
             #G..G..G#
             #########
             """)
           )
           |> elem(1)
           |> remove_hp ==
             Day15.parse_map("""
             #########
             #.G...G.#
             #...G...#
             #...E..G#
             #.G.....#
             #.......#
             #G..G..G#
             #.......#
             #########
             """)
             |> remove_hp

    assert Day15.single_round(
             Day15.parse_map("""
             #########
             #.G...G.#
             #...G...#
             #...E..G#
             #.G.....#
             #.......#
             #G..G..G#
             #.......#
             #########
             """)
           )
           |> elem(1)
           |> remove_hp ==
             Day15.parse_map("""
             #########
             #..G.G..#
             #...G...#
             #.G.E.G.#
             #.......#
             #G..G..G#
             #.......#
             #.......#
             #########
             """)
             |> remove_hp

    assert Day15.single_round(
             Day15.parse_map("""
             #########
             #..G.G..#
             #...G...#
             #.G.E.G.#
             #.......#
             #G..G..G#
             #.......#
             #.......#
             #########
             """)
           )
           |> elem(1)
           |> remove_hp ==
             Day15.parse_map("""
             #########
             #.......#
             #..GGG..#
             #..GEG..#
             #G..G...#
             #......G#
             #.......#
             #.......#
             #########
             """)
             |> remove_hp

    assert Day15.single_round(
             Day15.parse_map("""
             #######
             #.G...#
             #...EG#
             #.#.#G#
             #..G#E#
             #.....#
             #######
             """)
           )
           |> elem(1) ==
             Day15.parse_map("""
             #######
             #..G..#
             #...EG#
             #.#G#G#
             #...#E#
             #.....#
             #######
             """)
             |> Map.merge(%{
               {1, 3} => {:goblin, 200},
               {2, 4} => {:elf, 197},
               {2, 5} => {:goblin, 197},
               {3, 3} => {:goblin, 200},
               {3, 5} => {:goblin, 197},
               {4, 5} => {:elf, 197}
             })
  end

  test "determining whether to continue the combat" do
    assert Day15.continue_combat?(Day15.parse_map("GE")) == true
    assert Day15.continue_combat?(Day15.parse_map("GG")) == false
    assert Day15.continue_combat?(Day15.parse_map("#EE.")) == false
  end

  test "all rounds of the combat" do
    final_map =
      Day15.parse_map("""
      #######
      #G....#
      #.G...#
      #.#.#G#
      #...#.#
      #....G#
      #######
      """)
      |> Map.merge(%{
        {1, 1} => {:goblin, 200},
        {2, 2} => {:goblin, 131},
        {3, 5} => {:goblin, 59},
        {5, 5} => {:goblin, 200}
      })

    assert Day15.combat(
             Day15.parse_map("""
             #######
             #.G...#
             #...EG#
             #.#.#G#
             #..G#E#
             #.....#
             #######
             """)
           ) == {final_map, 47}
  end

  test "calculating the outcome of the combat" do
    map =
      Day15.parse_map("""
      #######
      #G....#
      #.G...#
      #.#.#G#
      #...#.#
      #....G#
      #######
      """)
      |> Map.merge(%{
        {1, 1} => {:goblin, 200},
        {2, 2} => {:goblin, 131},
        {3, 5} => {:goblin, 59},
        {5, 5} => {:goblin, 200}
      })

    assert Day15.calc_outcome({map, 47}) == 27_730
  end

  test "the outcome of the combat (the whole part 1)" do
    assert Day15.part1("""
           #######
           #.G...#
           #...EG#
           #.#.#G#
           #..G#E#
           #.....#
           #######
           """) == 27_730
  end

  test "all rounds of the combat with increased the Elves' attack power to the given value" do
    assert Day15.combat_with_modified_elf_attack_power(
             Day15.parse_map("""
             #######
             #.G...#
             #...EG#
             #.#.#G#
             #..G#E#
             #.....#
             #######
             """),
             3
           ) == :elf_died

    final_map =
      Day15.parse_map("""
      #######
      #..E..#
      #...E.#
      #.#.#.#
      #...#.#
      #.....#
      #######
      """)
      |> Map.merge(%{
        {1, 3} => {:elf, 158},
        {2, 4} => {:elf, 14}
      })

    assert Day15.combat_with_modified_elf_attack_power(
             Day15.parse_map("""
             #######
             #.G...#
             #...EG#
             #.#.#G#
             #..G#E#
             #.....#
             #######
             """),
             15
           ) == {final_map, 29}

    final_map =
      Day15.parse_map("""
      #######
      #.E.#.#
      #.#E..#
      #..#..#
      #...#.#
      #.....#
      #######
      """)
      |> Map.merge(%{
        {1, 2} => {:elf, 8},
        {2, 3} => {:elf, 86}
      })

    assert Day15.combat_with_modified_elf_attack_power(
             Day15.parse_map("""
             #######
             #E.G#.#
             #.#G..#
             #G.#.G#
             #G..#.#
             #...E.#
             #######
             """),
             15
           ) == {final_map, 37}
  end

  test "the outcome of the combat with optimal Elves' attack power to the given value (part 2)" do
    assert Day15.part2("""
           #######
           #.G...#
           #...EG#
           #.#.#G#
           #..G#E#
           #.....#
           #######
           """) == 4_988

    assert Day15.part2("""
           #######
           #E..EG#
           #.#G.E#
           #E.##E#
           #G..#.#
           #..E#.#
           #######
           """) == 31_284

    assert Day15.part2("""
           #######
           #E.G#.#
           #.#G..#
           #G.#.G#
           #G..#.#
           #...E.#
           #######
           """) == 3_478

    assert Day15.part2("""
           #######
           #.E...#
           #.#..G#
           #.###.#
           #E#G#G#
           #...#G#
           #######
           """) == 6_474

    assert Day15.part2("""
           #########
           #G......#
           #.E.#...#
           #..##..G#
           #...##..#
           #...#...#
           #.G...G.#
           #.....G.#
           #########
           """) == 1_140
  end
end