Advent of Code 2021 Day 19 in Elixir - Beacon Scanner 풀이

문제 보기

올해 AoC에서 처음으로 두 문제를 모두 풀기에 실패한 날이었다. 각 스캐너를 기준으로 한 여러 개의 비콘의 상대 위치가 주어졌을 때 전체 비콘의 개수(문제 1), 각 스캐너의 위치(문제 2)를 구하는 문제였다. 한 비콘이 여러 스캐너의 범위 안에 들어올 수 있어서 그 중복을 제거하는 것이 우선 필요했고, 각 스캐너가 바라보고 있는 축 방향이 제각각이라 주어진 데이터를 가능한 모든 방향으로 돌려서 확인할 필요가 있었다.
스캐너 A와 스캐너 B의 스캔 영역이 겹치는지를 확인하기 위해, 일단 각 스캐너에서 감지되는 각 비콘을 기준으로 하여 다른 비콘을 상대 위치로 나타낸 데이터를 만들고, 여기에 더해 두 스캐너의 축 방향이 다를 수 있으니 스캐너 A * 스캐너 B의 모든 조합을 확인하는 과정에 모든 축 방향 변환도 다 한 번씩 해봐야 하는 뭐 그런 상황이었다. 반복문을 대체 몇 겹을 썼는지... 더 간단한 방법이 있을 것 같은데 도저히 떠오르지 않아서 한참 하다가 문제 1까지 겨우 푼 시점에서 자체종료했다. 공간감각이 더 좋으면 쉽게 풀었으려나 싶기도 하다.
일단 돌아가도록 코드를 막 누더기로 짠 탓에 변수명도 일관되지 않고 영 마음에 들지 않지만, 이걸 정리할 용기는 또 나지 않아 기록을 겸하여 그냥 올린다.

defmodule Day19 do
  def parse_input(file_name \\ "input/day19.txt") do
    file_name
    |> File.read!()
    |> String.split("\n\n")
    |> Enum.map(fn scans ->
      ["--- scanner" <> _ | beacons] = String.split(scans, "\n")

      beacons
      |> Enum.map(fn beacon ->
        String.split(beacon, ",")
        |> Enum.map(&String.to_integer/1)
        |> List.to_tuple()
      end)
    end)
  end

  def run_q1() do
    scanners = parse_input()

    do_run_q1(scanners |> Enum.with_index(), %{})
    |> reduce()
    |> IO.inspect()
    |> Map.values()
    |> hd()
    |> MapSet.size()
  end

  def run_q2() do
    scanners = parse_input()

    do_run_q1(scanners |> Enum.with_index(), %{})
  end

  def do_run_q1([_], beacons), do: beacons

  def do_run_q1([{h, h_idx} | t] = _scanners, beacons) do
    new_beacons =
      t
      |> Enum.map(fn {scanner, idx} ->
        # |> IO.inspect()
        res = get_union_when_overlapped(h, scanner)

        if elem(res, 0) do
          IO.inspect("#{h_idx} * #{idx} => #{elem(res, 0)}")
          IO.inspect(MapSet.size(elem(res, 1)))
        end

        {res, idx}
      end)
      |> Enum.filter(fn {{overlapped?, _union}, _idx} -> overlapped? end)
      |> Enum.reduce(beacons, fn {{true, union}, idx}, acc ->
        Map.put(acc, [h_idx, idx], union)
      end)

    do_run_q1(t, new_beacons)
  end

  defp reduce(unions) when map_size(unions) == 1, do: unions

  defp reduce(unions) do
    IO.inspect(DateTime.utc_now())

    first_key =
      Map.keys(unions)
      |> Enum.sort_by(&length/1, :desc)
      |> hd()
      |> IO.inspect(label: "first_key")

    first_key_set = MapSet.new(first_key)

    unions
    |> Enum.filter(fn {k, _v} ->
      has_common_key? =
        MapSet.new(k)
        |> MapSet.intersection(MapSet.new(first_key))
        |> MapSet.size()
        |> Kernel.!=(0)

      k != first_key and has_common_key?
    end)
    |> Enum.sort_by(&length(elem(&1, 0)), :desc)
    |> hd()
    |> tap(fn {k, _v} -> IO.inspect(k) end)
    |> then(fn {k, v} ->
      if MapSet.subset?(MapSet.new(k), first_key_set) do
        unions
        |> Map.delete(k)
      else
        {true, union} =
          Map.get(unions, first_key)
          |> MapSet.to_list()
          |> get_union_when_overlapped(v |> MapSet.to_list())

        unions
        |> Map.delete(first_key)
        |> Map.delete(k)
        |> Map.put(Enum.uniq(k ++ first_key), union)
      end
    end)
    |> reduce()
  end

  defp get_union_when_overlapped(a, b) do
    a = a |> scanner_to_rel_coord()
    b = b |> scanner_to_rel_coord()

    a
    |> Enum.map(fn beacons_a_relative_to_point ->
      overlaps =
        b
        |> Enum.map(fn beacons_b_relative_to_point ->
          0..23
          |> Enum.map(fn orient ->
            beacons_b_relative_to_point
            |> MapSet.to_list()
            |> Enum.map(&orientation(&1, orient))
            |> MapSet.new()
          end)
          |> Enum.find(fn v ->
            MapSet.intersection(beacons_a_relative_to_point, v)
            |> MapSet.size()
            |> Kernel.>=(12)
          end)
        end)
        |> Enum.find(&(not is_nil(&1)))

      if is_nil(overlaps) do
        {false, nil}
      else
        MapSet.intersection(beacons_a_relative_to_point, overlaps) |> IO.inspect()
        {true, MapSet.union(beacons_a_relative_to_point, overlaps)}
      end
    end)
    |> Enum.find({false, nil}, &(elem(&1, 0) == true))
  end

  defp scanner_to_rel_coord(scanner) do
    scanner
    |> List.duplicate(length(scanner))
    |> Enum.zip(scanner)
    |> Enum.map(fn {beacons, base} ->
      Enum.map(beacons, fn beacon -> rel_coord(base, beacon) end)
      |> MapSet.new()
    end)
  end

  defp rel_coord({base_x, base_y, base_z}, {target_x, target_y, target_z}) do
    {target_x - base_x, target_y - base_y, target_z - base_z}
  end

  # +x를 바라보고 회전
  defp orientation({x, y, z}, 0), do: {x, y, z}
  defp orientation({x, y, z}, 1), do: {x, -z, y}
  defp orientation({x, y, z}, 2), do: {x, -y, -z}
  defp orientation({x, y, z}, 3), do: {x, z, -y}

  # -x를 바라보고 회전
  defp orientation({x, y, z}, 4), do: {-x, -y, z}
  defp orientation({x, y, z}, 5), do: {-x, -z, -y}
  defp orientation({x, y, z}, 6), do: {-x, y, -z}
  defp orientation({x, y, z}, 7), do: {-x, z, y}

  # +y를 바라보고 회전
  defp orientation({x, y, z}, 8), do: {y, -x, z}
  defp orientation({x, y, z}, 9), do: {y, z, x}
  defp orientation({x, y, z}, 10), do: {y, x, -z}
  defp orientation({x, y, z}, 11), do: {y, -z, -x}

  # -y를 바라보고 회전
  defp orientation({x, y, z}, 12), do: {-y, x, z}
  defp orientation({x, y, z}, 13), do: {-y, -z, x}
  defp orientation({x, y, z}, 14), do: {-y, -x, -z}
  defp orientation({x, y, z}, 15), do: {-y, z, -x}

  # +z를 바라보고 회전
  defp orientation({x, y, z}, 16), do: {z, y, -x}
  defp orientation({x, y, z}, 17), do: {z, x, y}
  defp orientation({x, y, z}, 18), do: {z, -y, x}
  defp orientation({x, y, z}, 19), do: {z, -x, -y}

  # -z를 바라보고 회전
  defp orientation({x, y, z}, 20), do: {-z, -y, -x}
  defp orientation({x, y, z}, 21), do: {-z, x, -y}
  defp orientation({x, y, z}, 22), do: {-z, y, x}
  defp orientation({x, y, z}, 23), do: {-z, -x, y}
end