Advent of Code 2023 - Day 18

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

https://github.com/ibarakaiev/advent-of-code-2023/blob/main/lib/advent_of_code/day_18.ex

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.

Oh my..

I am 385 LOC and not finished … I’ll try to finish anyway but man your solution is short.

I can’t grasp the wikipedia page infortunately.

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)

Wow, the Shoelace formula is something I should learn…
But since I didn’t know about it until now, my solution is – much like others here – a rewrite of the same algorithm as on Day 10: going along horizontal lines, essentially counting places with odd number of crossings from the left. For part 1 I did this directly on the grid, but obviously this didn’t work for part 2, and so I did a complete rewrite. The approach for part 2 is the same, but now moving in chunks. For rows inspecting only the ones with horizontal parts of the boundary, and only one of the “in between” ones. Likewise for columns only check those where there are any vertical parts of the boundary.

The whole thing runs quickly, under 1/10 s, but I am afraid the code is rather unreadable. Apologies

defmodule Main do
  def run() do
    get_input()
    |> Enum.map(&parse/1)
    # |> Enum.map(&prep1/1)
    |> Enum.map(&prep2/1)
    |> solve()
	end

  def get_input() do
    # "testinput18"
    "input18"
    |> File.read!()
    |> String.trim()
    |> String.split("\n")
  end

  def parse(l), do: Regex.run(~r/([RLUD]) (\d+) \(#([0-9a-f]+)([0-9a-f])\)/,l) |> tl()

  def prep1([d,n|_]), do: [d,String.to_integer(n)]

  @n_to_dir %{"0"=>"R", "1"=>"D", "2"=>"L", "3"=>"U"}
  def prep2([_,_,n,d]), do: [@n_to_dir[d],String.to_integer(n,16)]

  def addsctup({a,b},k,{c,d}), do: {a+k*c, b+k*d}

  # visually checked (part1), and the boundary is always separated from other parts
  # of the boundary by at least one empty tile, so can do this algo
  @dirs %{"R"=>{0,1},"L"=>{0,-1},"U"=>{-1,0},"D"=>{1,0}}
  def mkbdry2(ls) do
    lss = ([Enum.at(ls,-1)|ls] ++ [hd(ls)]) |> Enum.chunk_every(3,1,:discard) # to capture first and last
    {_, verts, horzs} =
      for [[pdir|_],[dir,dist],[ndir|_]] <- lss, reduce: {{0,0},MapSet.new(),MapSet.new()} do
        {pt,verts,horzs} ->
          npt = addsctup(pt,dist,@dirs[dir])
          {p1,p2} = if dir in ["R","D"] do {pt,npt} else {npt,pt} end # sort by size
          case {dir in ["R","L"], pdir, ndir} do
            {true, d, d} -> {npt, verts, MapSet.put(horzs, {p1,p2,dir,dist,true})}
            {true, _, _} -> {npt, verts, MapSet.put(horzs, {p1,p2,dir,dist,false})}
            {false,_, _} -> {npt, MapSet.put(verts,{p1,p2,dir,dist}), horzs}
          end
      end
    { Enum.group_by(horzs, fn {{r,_},_,_,_,_} -> r end), 
      Enum.group_by(verts, fn {{_,c},_,_,_} -> c end) }
  end

  def is_in_vert?(r,c,vs) do
    vs[c] |> Enum.map(fn {{r1,_},{r2,_},_,_} -> r1 <= r and r <= r2 end) |> Enum.any?()
  end

  def is_start_horz?(c,hh) do
    f =  hh |> Enum.map(fn {{_,c1},{_,c2},_,_,flip} -> {c1 == c, c2, flip} end)
            |> Enum.filter(&elem(&1,0))
    if f == [] do {false,nil,nil} else hd(f) end
  end
 
  def count_along(r,vs,hs) do
    vss = Map.keys(vs) |> Enum.sort()
    hh = Map.get(hs,r,[])
    {finhz,fcc,fflip} = is_start_horz?(hd(vss),hh)
    fio = if finhz do false else is_in_vert?(r, hd(vss), vs) end
    fct = if fio or finhz do 1 else 0 end
    for [c1,c2] <- (vss |> Enum.chunk_every(2,1,:discard)),
      reduce: {fct, fio, finhz, fcc, fflip}
      # { count_so_far, in_or_out, in_horizontal_bdry, col_where_horiz_bit_ends, do_we_flip_after_horiz? }
      do {ct, io, inhz, cc, flip} ->
        {ninhz,ncc,nflip} = is_start_horz?(c2,hh)
        cond do
          cc == c2 -> {ct + c2 - c1, if flip do not io else io end, false, nil, nil } 
          inhz     -> {ct + c2 - c1, io, true, cc, flip}
          ninhz and io     -> {ct + c2 - c1, io, true, ncc, nflip}
          ninhz and not io -> {ct + 1,       io, true, ncc, nflip}
          true -> (
            case {is_in_vert?(r, c2, vs), io} do
              {true,  true} -> { ct + c2 - c1, false, ninhz, ncc, nflip }
              {true, false} -> { ct + 1, true, ninhz, ncc, nflip }
              {false, true} -> { ct + c2 - c1 , true, ninhz, ncc, nflip }
              {false,false} -> { ct, false, ninhz, ncc, nflip }
            end)
        end
    end |> elem(0)
  end

  def solve(ls) do
    {hs,vs} = ls |> mkbdry2()
    intervals = (Map.keys(hs) |> Enum.sort() |> Enum.chunk_every(2,1,:discard))
      |> Enum.map(fn [r1,r2] -> { r1 + 1, r2 - r1 - 1} end)
      |> Enum.filter(fn {_,l} -> l > 0 end)
      |> Enum.map(fn {r,l} -> l*count_along(r,vs,hs) end)
      |> Enum.sum()
    Map.keys(hs) |> Enum.sort() |> Enum.map(fn r -> count_along(r,vs,hs) end)
      |> Enum.sum()
      |> Kernel.+(intervals)
  end

end

:timer.tc(&Main.run/0)
|> IO.inspect(charlists: :as_lists)

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.

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

But how can this work with pixel-like geometries where a point is not actually a point, but has width

Anyway thank you ! I also looked other sources and videos and I have a basic understanding now

TIL about shoelace formula and pick’s theorem:

https://github.com/woojiahao/aoc/blob/main/lib/aoc/y2023/day_18.ex

I felt day 18 was not as interesting since it required some really specific geometry knowledge, but still interesting!

I finally took a look at the Shoelace formula and Pick’s Theorem after ignoring it on day 10. After that, Part 1 and 2 are just different inputs.

https://github.com/pehbehbeh/adventofcode/blob/main/2023/18.livemd