It’s a shame that I almost found the shoelace formula myself, but in the end I turned to ChatGPT

When I came back to my thinking, I found some beauty in math.

Suppose you have a convex polygon. You can pick any point inside that polygon and split that polygon into triangles.

image1147×751 25.3 KB

For example, in the image above, you can calculate the area of the polygon ABCDEFG by calculating the area of the triangles PAB, PBC, PCD, …, PGA and adding them up. The area of the triangle PAB is

Same for the other triangles.

Be ware that we are doing vector cross product here, so the order matters.

It turns out that this process also works for concave polygons.

image925×710 26.9 KB

In the image above, the area of triangle PCD is

which is negative, but that’s OK because the area of the triangle marked 1 is also in PBC and PDE, so it’s counted twice positive so we need to cancel it once. And the area marked 2 is in PDE but not in the polygon, so we also need to cancel it. The negative area of PCD does both jobs.

It turned out that we can not only pick the P inside the polygon, but anywhere, even outside the polygon or on the edge or corner.

image972×999 26.7 KB

For example, if we choose a P outside the polygon ABCDE, we can always create a polygon that encloses P and shares some of the edges of ABCDE (in the image above, that is the polygon ABCQR). The area of the polygon ABCDE is equal to the area of ABCQR minus the area of AEDCQR. Note that P is both inside ABCQR and AEDCQR, so we can just use the formula above to calculate the area of both polygons.

image2561×462 46.7 KB

That’s the proof that even when P is outside the polygon, the formula still works.

If we pick P at (0, 0), then we get the triangular form of the shoelace formula.

As for the trapezoid form of the shoelace formula, though it comes from a very different mindset, if we expand each (y1 + y2) * (x1 - x2) to x1 * y1 + x1 * y2 - x2 * y1 - x2 * y2, then we notice that, after sum up all the terms, those terms with the same suffixes are canceled out, and the remaining terms are just a permutation of the triangular form.

I adapted my code from day 10.
Actually ended up completely rewriting it.
But the concept of storing “L”, “F”, “J”, “7”, “|”, “-” helped me.
Took an hour to run on part 2.

import AOC

aoc 2023, 18 do
  def p1(input) do
    input
    |> parse()
    |> chunker()
    |> Enum.reduce({{0,0}, %{}}, &dig/2)
    |> elem(1)
    |> count_enclosed()
  end

  def dig([{dir1, n1, hex1}, {dir2, n2, hex2}], {{row, col}, map}) do
    {filler, final} = case {dir1, dir2} do
      {"R", "D"} -> {"-", "7"}
      {"R", "U"} -> {"-", "J"}
      {"L", "D"} -> {"-", "F"}
      {"L", "U"} -> {"-", "L"}
      {"D", "R"} -> {"|", "L"}
      {"U", "R"} -> {"|", "F"}
      {"D", "L"} -> {"|", "J"}
      {"U", "L"} -> {"|", "7"}
    end

    {delta_row, delta_col} = %{"R" => {0, 1}, "L" => {0, -1}, "U" => {-1, 0}, "D" => {1, 0}}[dir1]
    coord = {row+delta_row, col+delta_col}
    map = Map.put(map, coord, if(n1 == 1, do: final, else: filler))
    if n1==1 do
      {coord, map}
    else
      dig([{dir1, n1-1, hex1}, {dir2, n2, hex2}], {coord, map})
    end
  end

  def count_enclosed(loop_map) do
    loop_map
    |> Enum.group_by(fn ({{row, _}, _}) -> row end)
    |> Enum.sort()
    |> Enum.map(&count_row/1)
    |> Enum.sum()
  end

  def count_row({_, items}) do
    items
    |> Enum.sort()
    |> Enum.reduce(
      {{false, 0}, {nil, nil}},
      fn {{_, col}, pipe}, {{interior, count}, {last_col, last_turn}} ->
        case pipe do
          "L" -> {{interior, count+1+ add_count(interior, last_col, col)}, {col, "L"}}
          "F" -> {{interior, count+1+ add_count(interior, last_col, col)}, {col, "F"}}
          "J" -> {{if(last_turn == "F", do: not interior, else: interior), count+1}, {col, "J"}}
          "7" -> {{if(last_turn == "L", do: not interior, else: interior), count+1}, {col, "7"}}
          "|" -> {{not interior, count+1 + add_count(interior, last_col, col)}, {col, "|"}}
          "-" -> {{interior, count+1}, {last_col, last_turn}}
        end
      end)
    |> elem(0)
    |> elem(1)
  end

  def add_count(false, _, _), do: 0
  def add_count(true, last_col, col), do: col - last_col - 1

  def chunker(l), do: Enum.chunk_every(l, 2, 1, l)

  def parse(input) do
    input
    |> String.split("\n")
    |> Enum.map(fn line -> line |> String.split(" ", trim: true) |> then(fn [x, y, z] -> {x, String.to_integer(y), z} end) end)
  end

  def extract_hex({_, _, <<"(#", distance::binary-5, direction::binary-1, ")">>}) do
    {Enum.at(["R", "D", "L", "U"], String.to_integer(direction, 16)), String.to_integer(distance, 16), nil}
  end

  def p2(input) do
    input
    |> parse()
    |> Enum.map(&extract_hex/1)
    |> chunker()
    |> Enum.reduce({{0,0}, %{}}, &dig/2)
    |> elem(1)
    |> count_enclosed()
  end
end

I did a flood fill for part 1, figured I’d have to implement that ray-casting algorithm for part 2, but got spooked by the large segments. I remembered that folks had mentioned the Shoelace Algorithm for similar problems, so I tried implementing that in Nx. That alone didn’t produce the right answer and I didn’t know enough about the Shoelace Algorithm to tell why, so I converted it to plain Elixir. I had a hunch that the answer was off because the perimeter wasn’t being considered. I don’t fully understand why my math works. I just divided the perimeter in half and added one plus the area and it was correct.

defmodule Part1 do
  @deltas %{
    "U" => {-1, 0},
    "D" => {1, 0},
    "L" => {0, -1},
    "R" => {0, 1}
  }

  def dig(input) do
    {_, map} =
      for line <- String.split(input, "\n", trim: true),
          reduce: {{0, 0}, MapSet.new()} do
        {curr, acc} ->
          [dir, amt, _] = String.split(line)
          amt = String.to_integer(amt)
          {dy, dx} = @deltas[dir]

          {next, acc} =
            for _ <- 0..(amt - 1), reduce: {curr, acc} do
              {{y, x}, acc} ->
                next = {y + dy, x + dx}
                acc = MapSet.put(acc, next)
                {next, acc}
            end

          {next, acc}
      end

    map
  end

  def bounds(map) do
    {{y0, _}, {y1, _}} = Enum.min_max(map)
    {{_, x0}, {_, x1}} = Enum.min_max_by(map, fn {_, x} -> x end)
    {{y0, x0}, {y1, x1}}
  end

  def print(map) do
    {{y0, x0}, {y1, x1}} = bounds(map)

    for y <- y0..y1 do
      for x <- x0..x1 do
        char = if MapSet.member?(map, {y, x}), do: "#", else: "."
        IO.write(char)
      end

      IO.puts("")
    end
  end

  def interior(map) do
    {{y0, x0}, {y1, x1}} = bounds(map)
    {{y0, x0}, {y1, x1}} = bbox = {{y0 - 1, x0 - 1}, {y1 + 1, x1 + 1}}
    exterior = flood(map, bbox)
    (y1 - y0 + 1) * (x1 - x0 + 1) - MapSet.size(exterior)
  end

  def flood(map, {start, _} = bbox), do: flood(map, bbox, [start], MapSet.new())
  def flood(_, _, [], explored), do: explored

  def flood(map, {{y0, x0}, {y1, x1}} = bbox, [{y, x} = next | frontier], explored) do
    explored = MapSet.put(explored, next)

    neighbors =
      @deltas
      |> Map.values()
      |> Enum.map(fn {dy, dx} -> {y + dy, x + dx} end)
      |> Enum.reject(fn {y, x} = neighbor ->
        y < y0 or y > y1 or x < x0 or x > x1 or
          MapSet.member?(explored, neighbor) or
          MapSet.member?(map, neighbor)
      end)

    frontier = neighbors ++ frontier
    flood(map, bbox, frontier, explored)
  end
end

Part1.dig(input)
|> Part1.interior()

defmodule Part2 do
  @deltas %{
    "0" => {0, 1},
    "1" => {1, 0},
    "2" => {0, -1},
    "3" => {-1, 0}
  }

  def dig(input) do
    origin = [0, 0]

    {points, _} =
      input
      |> String.split("\n", trim: true)
      |> Enum.map_reduce(origin, fn line, [y, x] ->
        [_, <<distance::binary-size(5), direction::binary>>] =
          String.split(line, ~r/[()#]/, trim: true)

        distance = String.to_integer(distance, 16)
        {dy, dx} = @deltas[direction]
        next = [y + distance * dy, x + distance * dx]
        {next, next}
      end)

    segments =
      [origin | points]
      |> Enum.chunk_every(2, 1, :discard)

    area =
      segments
      |> Enum.map(fn [[y1, x1], [y2, x2]] -> y1 * x2 - x1 * y2 end)
      |> Enum.sum()
      |> abs()
      |> div(2)

    perimeter =
      segments
      |> Enum.map(fn [[y1, x1], [y2, x2]] -> abs(y2 - y1) + abs(x2 - x1) end)
      |> Enum.sum()
      |> div(2)

    area + perimeter + 1
  end
end

Part2.dig(input)

EDIT: Went back and did part 2 with Nx now that I get the math working in plain Elixir.

    tensor =
      [origin | points]
      |> Enum.chunk_every(2, 1, :discard)
      |> Nx.tensor(type: :f64)

    area_nx =
      tensor
      |> Nx.LinAlg.determinant()
      |> Nx.sum()
      |> Nx.abs()
      |> Nx.divide(2)

    perimeter_nx =
      Nx.abs(Nx.subtract(tensor[[.., 0, 0]], tensor[[.., 1, 0]]))
      |> Nx.add(Nx.abs(Nx.subtract(tensor[[.., 0, 1]], tensor[[.., 1, 1]])))
      |> Nx.sum()
      |> Nx.divide(2)
      |> Nx.add(1)

    Nx.add(area_nx, perimeter_nx) |> Nx.as_type(:s64)

Unfortunately I didn’t know about the shoelace formula So here’s my manual solution:

Logic: similar to Day 10, we can find the inner area by casting a horizontal ray, but since part 2 introduces numbers in hundreds of thousands, filling in the grid would take forever (and probably exhaust my RAM anyway), so I only record corners, i.e. {0, 0, “F”}. Then I group and sort them by the y-coordinate. Then, we have to consider two types of lines: a) lines that don’t have corners, b) lines that have corners.

For lines that have corners, calculate area inside by casting a ray with a modified algorithm from day 10. For lines that don’t, we can infer what they would look like based on the current corners, calculate their area, and multiply by the total number of missing lines. Throughout this, I also needed to keep track of where edges already occured when inferring future lines and calculating the area inside the current line.

I was a bit afraid of accidentally double-counting so I only calculated the inner area and then added the total length of the polygon edges based on the input.

Ah sorry I missed that, I’ll read it carefully later! Thank you!