bjorng

bjorng

Erlang Core Team

I finally got some time to finish my solution for day 9.

Here is my cleaned up solution stripped of all debugging code. A slightly interesting thing about my solution is that I do ray-casting or walking from one corner to another, but only in the horizontal directions. To check the vertical lines, I ran the same check on the tiles rotated 90 degrees.

The combined runtime for both parts and the examples are 0.4 seconds on my computer.

defmodule Day09 do
  def part1(input) do
    tiles = parse(input)
    tiles
    |> Enum.flat_map(fn a ->
      Enum.flat_map(tiles, fn b ->
        if a < b, do: [area(a, b)], else: []
      end)
    end)
    |> Enum.sort(:desc)
    |> Enum.take(1)
    |> hd
  end

  def part2(input) do
    tiles = parse(input)

    transposed = tiles
    |> Enum.map(fn {x, y} -> {y, x} end)
    |> Enum.reverse

    plain = prepare_tiles(tiles)
    transposed = prepare_tiles(transposed)

    {tiles, _, _} = plain

    tiles = Enum.sort(tiles)
    Enum.reduce(tiles, 0, fn a, max_area ->
      Enum.reduce(tiles, max_area, fn b, max_area ->
        if a >= b do
          max_area
        else
          area = area(a, b)
          if area <= max_area do
            max_area
          else
            region1 = [a, b]
            region2 = Enum.map(region1, fn {x, y} -> {y, x} end)
            if solve_one(region1, plain) and solve_one(region2, transposed) do
              area
            else
              max_area
            end
          end
        end
      end)
    end)
  end

  defp prepare_tiles(tiles) do
    edges = Enum.chunk_every(tiles, 2, 1, tiles)
    |> Enum.map(&List.to_tuple/1)

    convex = Enum.chunk_every(edges, 2, 1, edges)
    |> Enum.map(fn [{p1, p2}, {p2, p3}] ->
      convex? = if cross_z(p1, p2, p3) > 0, do: :convex, else: :concave
      {p2, {convex?, p1, p3}}
    end)
    |> Map.new

    {tiles, edges, convex}
  end

  # Given two diagonal corners, check that the two horizontal
  # lines going to the other two corners of the rectangle
  # only have red and green tiles.
  defp solve_one([a, b], {_tiles, edges, convex}) do
    {lx, y1} = a
    {rx, y2} = b
    c = {lx, y2}
    d = {rx, y1}

    cond do
      c === a or d === b ->
        [{b, c, sign(lx - rx)}]
      true ->
        [{b, c, sign(lx - rx)}, {a, d, sign(rx - lx)}]
    end
    |> Enum.all?(fn {from, to, dir} ->
      if from === to do
        false
      else
        walk(from, to, dir, edges, convex)
      end
    end)
  end

  defp sign(int) do
    cond do
      int < 0 -> -1
      int > 0 -> 1
      true -> 0
    end
  end

  defp area({x1, y1}, {x2, y2}) do
    (abs(x1 - x2) + 1) * (abs(y1 - y2) + 1)
  end

  defp walk(from, to, dir, edges, convex) do
    case classify_corner(from, dir, convex) do
      :outside ->
        false
      where ->
        {from_x, from_y} = from
        {to_x, _} = to

        # Only keep the relevant vertical edges.
        edges = edges
        |> Enum.filter(fn {{_,y1}, {_,y2}} ->
          y1 !== y2 and from_y in min(y1, y2)..max(y1, y2)
        end)

        case dir do
          -1 ->
            edges
            |> Enum.reject(fn {{x1,_}, {x1,_}} ->
              from_x < x1 or to_x > x1
            end)
            |> Enum.sort(:desc)
            |> then(fn edges ->
              walk_1(tl(edges), dir, to, convex, where)
            end)
          1 ->
            edges
            |> Enum.reject(fn {{x1,_}, {x1,_}} ->
              x1 < from_x or x1 > to_x
            end)
            |> Enum.sort
            |> then(fn edges ->
              walk_1(tl(edges), dir, to, convex, where)
            end)
        end
    end
  end

  # Classify a corner with respect to the horizontal direction.
  # Returns one of :edge, :inside, or :outside.
  defp classify_corner(from, dir, convex) do
    {from_x, _} = from
    other_corner = case convex do
                     %{^from => {_, {^from_x, _}, other}} -> other
                     %{^from => {_, other, {^from_x, _}}} -> other
                   end

    {diff_x, _} = sub(other_corner, from)
    case sign(diff_x) do
      ^dir ->
        # Walking in the given direction is along the edge to
        # the other corner.
        :edge
      _ ->
        # We will not walk along the edge, but we will enter move to
        # to the inside or outside.
        case is_convex(convex, from) do
          :concave -> :inside
          :convex -> :outside
        end
    end
  end

  # Walk from a corner point horizontally in either direction.
  # Returns `true` if the destination point `to` can be reached
  # by only passing red and green tiles.
  defp walk_1(_, _dir, _to, _convex, :outside) do
    false
  end
  defp walk_1([], _dir, _to, _convex, _) do
    true
  end
  defp walk_1([{a, b} | edges], dir, to, convex, where) do
    {to_x, to_y} = to
    {ab_x, a_y} = a
    {_, b_y} = b
    cond do
      dir === -1 and ab_x <= to_x ->
        # Destination is on the edge or at the corner.
        where === :edge or where === :inside
      dir === 1 and to_x <= ab_x ->
        # Destination is on the edge or at the corner.
        where === :edge or where === :inside
      a_y === to_y and corner?(convex, a) ->
        # Destination is beyond this corner.
        where = pass_corner(where, is_convex(convex, a))
        walk_1(edges, dir, to, convex, where)
      b_y === to_y and corner?(convex, b) ->
        # Destination is beyond this corner.
        where = pass_corner(where, is_convex(convex, b))
        walk_1(edges, dir, to, convex, where)
      true ->
        # Destination is beyond this edge.
        false
    end
  end

  defp corner?(convex, point) do
    Map.has_key?(convex, point)
  end

  defp is_convex(convex, corner) do
    {convex?, _, _} = Map.get(convex, corner)
    convex?
  end

  defp pass_corner(:edge, :convex), do: :outside
  defp pass_corner(:edge, :concave), do: :inside
  defp pass_corner(:inside, :concave), do: :edge

  defp cross_z({x1, y1}, {x2, y2}, {x3, y3}) do
    (x2 - x1) * (y3 - y2) - (y2 - y1) * (x3 - x2)
  end

  defp sub({x1, y1}, {x2, y2}) do
    {x1 - x2, y1 - y2}
  end

  defp parse(input) do
    input
    |> Enum.map(fn line ->
      line
      |> String.split(",")
      |> Enum.map(&String.to_integer/1)
      |> List.to_tuple
    end)
  end
end
1
Post #11
— All posts loaded —