day22.exs

defmodule Main do
  def run() do
    get_input() |> parse |> solve()
  end

  def get_input() do
    "/Users/andrew/Downloads/input.txt"
    |> File.read!()
  end

  def parse(data) do
    lines = String.split(data, "\n")
    {path, lines} = List.pop_at(lines, -1)
    lines = List.delete_at(lines, -1)
    gm = GridMap.from_lines(lines)
    moves = Regex.scan(~r/\d+|[RL]/, path) |> List.flatten()
    {gm, moves}
  end

  def solve({grid, moves}) do
    part1(grid, moves) |> IO.inspect()
    part2(grid, moves) |> IO.inspect()
  end

  def part1(grid, moves) do
    pos = GridMap.find_first(grid, ?.)
    facing = :right
    {pos, facing} = P1.apply_moves_2d(grid, pos, facing, moves)
    score(pos, facing)
  end

  def part2(grid, moves) do
    pos = GridMap.find_first(grid, ?.)
    facing = :right
    cube = Cube.from_grid(grid)
    {pos, facing} = P2.apply_moves_3d(cube, pos, facing, moves)
    score(pos, facing)
  end

  def score({r, c}, facing) do
    1000 * (r + 1) + 4 * (c + 1) + Direction.value(facing)
  end
end

defmodule Pos do
  def add({a, b}, {c, d}) do
    {a + c, b + d}
  end
end

defmodule GridMap do
  defstruct [:grid, :rows, :cols]

  def from_lines(lines) do
    # Constructs a map from {r, c} coordinates to characters, returns a Grid struct
    grid =
      lines
      |> Enum.with_index()
      |> Enum.flat_map(fn {line, r} ->
        line
        |> String.to_charlist()
        |> Enum.with_index()
        |> Enum.filter(fn {char, _} -> char != ?\s end)
        |> Enum.map(fn {char, c} -> {{r, c}, char} end)
      end)
      |> Map.new()

    rows = (grid |> Map.keys() |> Enum.map(fn {r, _} -> r end) |> Enum.max()) + 1
    cols = (grid |> Map.keys() |> Enum.map(fn {_, c} -> c end) |> Enum.max()) + 1

    %GridMap{grid: grid, rows: rows, cols: cols}
  end

  def find_first(grid, val) do
    grid.grid
    |> Map.keys()
    |> Enum.sort()
    |> Enum.find(fn rc -> Map.fetch!(grid.grid, rc) == val end)
  end
end

defmodule Direction do
  @values %{
    right: 0,
    down: 1,
    left: 2,
    up: 3
  }

  @from_value Map.new(@values, fn {key, val} -> {val, key} end)

  def value(t) do
    @values[t]
  end

  def from_value(v) do
    @from_value[v]
  end

  def to_move(d) do
    case d do
      :right -> {0, 1}
      :down -> {1, 0}
      :left -> {0, -1}
      :up -> {-1, 0}
    end
  end

  def add_move(pos, d) do
    Pos.add(pos, to_move(d))
  end

  def opposite(d) do
    from_value(Integer.mod(value(d) + 2, 4))
  end
end

defmodule Turn do
  @values %{
    left_turn: -1,
    straight: 0,
    right_turn: 1
  }

  @from_value Map.new(@values, fn {key, val} -> {val, key} end)

  def value(t) do
    @values[t]
  end

  def from_value(v) do
    @from_value[v]
  end

  def apply_turn(direction, turn) do
    val = Integer.mod(Direction.value(direction) + value(turn), 4)
    Direction.from_value(val)
  end
end

defmodule P1 do
  def apply_moves_2d(_grid, pos, facing, []) do
    {pos, facing}
  end

  def apply_moves_2d(grid, pos, facing, [move | moves]) do
    {pos, facing} = move_2d(grid, pos, facing, move)
    apply_moves_2d(grid, pos, facing, moves)
  end

  def move_2d(_grid, pos, facing, "L") do
    {pos, Turn.apply_turn(facing, :left_turn)}
  end

  def move_2d(_grid, pos, facing, "R") do
    {pos, Turn.apply_turn(facing, :right_turn)}
  end

  def move_2d(grid, pos, facing, num_steps) when is_bitstring(num_steps) do
    move_2d(grid, pos, facing, String.to_integer(num_steps))
  end

  def move_2d(_grid, pos, facing, 0) do
    {pos, facing}
  end

  def move_2d(grid, pos, facing, num_steps) do
    next_pos = get_next_pos_2d(grid, pos, facing)

    case Map.fetch!(grid.grid, next_pos) do
      ?# -> {pos, facing}
      _ -> move_2d(grid, next_pos, facing, num_steps - 1)
    end
  end

  def get_next_pos_2d(grid, pos, facing) do
    new_pos = Direction.add_move(pos, facing)

    cond do
      Map.has_key?(grid.grid, new_pos) -> new_pos
      true -> go_max(grid, pos, Direction.opposite(facing))
    end
  end

  def go_max(grid, pos, facing) do
    move = Direction.to_move(facing)
    new_pos = Pos.add(pos, move)

    case Map.has_key?(grid.grid, new_pos) do
      true -> go_max(grid, new_pos, facing)
      false -> pos
    end
  end
end

defmodule P2 do
  def apply_moves_3d(_cube, pos, facing, []) do
    {pos, facing}
  end

  def apply_moves_3d(cube, pos, facing, [move | moves]) do
    {pos, facing} = move_3d(cube, pos, facing, move)
    apply_moves_3d(cube, pos, facing, moves)
  end

  def move_3d(_cube, pos, facing, "L") do
    {pos, Turn.apply_turn(facing, :left_turn)}
  end

  def move_3d(_cube, pos, facing, "R") do
    {pos, Turn.apply_turn(facing, :right_turn)}
  end

  def move_3d(cube, pos, facing, num_steps) when is_bitstring(num_steps) do
    move_3d(cube, pos, facing, String.to_integer(num_steps))
  end

  def move_3d(_cube, pos, facing, 0) do
    {pos, facing}
  end

  def move_3d(cube, pos, facing, num_steps) do
    # IO.inspect(["Moving from", pos, facing])
    {next_pos, next_facing} = get_next_pos_3d(cube, pos, facing)
    # IO.inspect(["...perhaps to", next_pos, next_facing])

    case Map.fetch!(cube.grid.grid, next_pos) do
      ?# -> {pos, facing}
      _ -> move_3d(cube, next_pos, next_facing, num_steps - 1)
    end
  end

  def get_next_pos_3d(cube, pos, facing) do
    new_pos = Direction.add_move(pos, facing)

    cond do
      Map.has_key?(cube.grid.grid, new_pos) -> {new_pos, facing}
      true -> Stitching.wrap(cube, pos, facing)
    end
  end
end

defmodule Minimap do
  @face_names [:A, :B, :C, :D, :E, :F]

  def from_grid(grid) do
    square_size = BasicMath.gcd(grid.rows, grid.cols)
    rows = div(grid.rows, square_size)
    cols = div(grid.cols, square_size)

    minimap_coords = for r <- 0..(rows - 1), c <- 0..(cols - 1), do: {r, c}

    valid_minimap_coords =
      minimap_coords
      |> Enum.map(fn {r, c} -> {r * 50, c * 50} end)
      |> Enum.filter(&Map.has_key?(grid.grid, &1))
      |> Enum.filter(fn pos -> Map.fetch(grid.grid, pos) != ' ' end)
      |> Enum.map(fn {r, c} -> {div(r, 50), div(c, 50)} end)

    grid_map =
      valid_minimap_coords
      |> Enum.zip(@face_names)
      |> Map.new()

    %GridMap{grid: grid_map, rows: rows, cols: cols}
  end
end

defmodule Cube do
  defstruct [:grid, :minimap, :stitches]

  def from_grid(grid) do
    minimap = Minimap.from_grid(grid)
    stitches = Stitching.from_minimap(minimap)
    %Cube{grid: grid, minimap: minimap, stitches: stitches}
  end

  def scale(cube) do
    div(cube.grid.rows, cube.minimap.rows)
  end

  def pos_to_face(cube, {r, c}) do
    s = scale(cube)
    mini_rc = {div(r, s), div(c, s)}
    Map.fetch!(cube.minimap.grid, mini_rc)
  end

  def edge_pos(cube, edge, {r, c}) do
    # How far down (l->r or t->b) the edge `pos` is
    s = scale(cube)
    {mini_r, mini_c} = GridMap.find_first(cube.minimap, edge.face)
    {start_r, start_c} = {mini_r * s, mini_c * s}

    if edge.direction == :up or edge.direction == :down do
      c - start_c
    else
      r - start_r
    end
  end

  def pos_on_edge(cube, edge, pos) do
    s = scale(cube)
    {mini_r, mini_c} = GridMap.find_first(cube.minimap, edge.face)
    {start_r, start_c} = {mini_r * s, mini_c * s}

    case edge.direction do
      :up -> {start_r, start_c + pos}
      :down -> {start_r + s - 1, start_c + pos}
      :left -> {start_r + pos, start_c}
      :right -> {start_r + pos, start_c + s - 1}
    end
  end
end

defmodule Edge do
  defstruct [:face, :direction]
end

defmodule EdgeConnection do
  defstruct [:edge1, :edge2, :turn]

  def get_clockwise_edge_conns(minimap) do
    first_edge = %Edge{face: :A, direction: :up}
    first_turn = get_next_clockwise_edge_conn(minimap, first_edge)
    get_clockwise_edge_conns(minimap, [first_turn])
  end

  def get_clockwise_edge_conns(minimap, turns) do
    last_turn = List.last(turns)
    next_turn = get_next_clockwise_edge_conn(minimap, last_turn.edge2)

    case next_turn.edge1 do
      %Edge{face: :A, direction: :up} -> turns
      _ -> get_clockwise_edge_conns(minimap, turns ++ [next_turn])
    end
  end

  @moves_to_check %{
    right: [{1, 1}, {1, 0}, {0, 0}],
    down: [{1, -1}, {0, -1}, {0, 0}],
    left: [{-1, -1}, {-1, 0}, {0, 0}],
    up: [{-1, 1}, {0, 1}, {0, 0}]
  }
  def get_next_clockwise_edge_conn(minimap, edge) do
    pos = GridMap.find_first(minimap, edge.face)
    moves = Map.fetch!(@moves_to_check, edge.direction)

    {next_pos, t} =
      List.first(
        moves
        |> Enum.zip([:left_turn, :straight, :right_turn])
        |> Enum.map(fn {move, t} -> {Pos.add(pos, move), t} end)
        |> Enum.filter(fn {next_pos, _t} -> Map.has_key?(minimap.grid, next_pos) end)
        |> Enum.filter(fn {next_pos, _t} -> Map.fetch!(minimap.grid, next_pos) != ' ' end)
      )

    next_face = Map.fetch!(minimap.grid, next_pos)
    # The 'turn' is a bit brain-bendy because the edge side-name is not the same as the direction,
    # but it works.
    next_face_direction = Turn.apply_turn(edge.direction, t)
    next_edge = %Edge{face: next_face, direction: next_face_direction}
    %EdgeConnection{edge1: edge, edge2: next_edge, turn: t}
  end
end

defmodule Stitching do
  defstruct [:edge1, :edge2, :invert]

  def from_minimap(minimap) do
    minimap
    |> EdgeConnection.get_clockwise_edge_conns()
    |> clockwise_edge_conns_to_stitches()
  end

  def clockwise_edge_conns_to_stitches(edge_conns) do
    clockwise_edge_conns_to_stitches(edge_conns, [])
  end

  def clockwise_edge_conns_to_stitches([t1, _t2], stitches) do
    # If there are only two turns left, they point to each other, and we're done
    s = make_stitch(t1.edge1, t1.edge2)
    [s | stitches]
  end

  def clockwise_edge_conns_to_stitches(edge_conns, stitches) do
    idx = Enum.find_index(edge_conns, fn t -> t.turn == :left_turn end)
    val = Enum.at(edge_conns, idx)
    s = make_stitch(val.edge1, val.edge2)
    prv_idx = Integer.mod(idx - 1, length(edge_conns))
    nxt_idx = Integer.mod(idx + 1, length(edge_conns))
    prv = Enum.at(edge_conns, prv_idx)
    nxt = Enum.at(edge_conns, nxt_idx)
    new_turn_val = Turn.from_value(Turn.value(prv.turn) + Turn.value(nxt.turn) - 2)
    new_edge_conn = %EdgeConnection{edge1: prv.edge1, edge2: nxt.edge2, turn: new_turn_val}

    edge_conns =
      edge_conns
      |> List.replace_at(idx, new_edge_conn)
      |> List.replace_at(prv_idx, nil)
      |> List.replace_at(nxt_idx, nil)
      |> Enum.filter(fn x -> x != nil end)

    clockwise_edge_conns_to_stitches(edge_conns, [s | stitches])
  end

  def make_stitch(edge1, edge2) do
    %Stitching{edge1: edge1, edge2: edge2, invert: inverted?(edge1, edge2)}
  end

  def inverted?(edge1, edge2) do
    cond do
      edge1.direction == edge2.direction -> true
      # Oppsite sides add up to 2 - don't invert
      # top-left and bottom-right add up to 1 - don't invert
      # top-right and bottom-left add up to 3 - invert
      rem(Direction.value(edge1.direction) + Direction.value(edge2.direction), 4) == 3 -> true
      true -> false
    end
  end

  def wrap(cube, pos, facing) do
    exit_face = Cube.pos_to_face(cube, pos)
    exit_edge = %Edge{face: exit_face, direction: facing}
    {enter_edge, inverted} = get_matching_edge(cube.stitches, exit_edge)
    new_facing = Direction.opposite(enter_edge.direction)
    exit_edge_pos = Cube.edge_pos(cube, exit_edge, pos)

    enter_edge_pos =
      case inverted do
        true -> Cube.scale(cube) - exit_edge_pos - 1
        false -> exit_edge_pos
      end

    new_pos = Cube.pos_on_edge(cube, enter_edge, enter_edge_pos)
    {new_pos, new_facing}
  end

  def get_matching_edge(stitches, edge) do
    # Return the edge that matches the given edge, and whether it's inverted
    Enum.find_value(stitches, fn s ->
      cond do
        s.edge1 == edge -> {s.edge2, s.invert}
        s.edge2 == edge -> {s.edge1, s.invert}
        true -> nil
      end
    end)
  end
end

defmodule BasicMath do
  # From https://programming-idioms.org/idiom/75/compute-lcm/983/elixir
  def gcd(a, 0), do: a
  def gcd(0, b), do: b
  def gcd(a, b), do: gcd(b, rem(a, b))

  def lcm(0, 0), do: 0
  def lcm(a, b), do: div(a * b, gcd(a, b))
end

Main.run()