# Advent of Code 2023 - Day 18

I confess that I asked ChatGPT about the math. It gave me a name of an algorithm called the Shoelace formula. I still have to pay attention to the off-by-1 problem though.

Here’s my code (omit the input parsing part):

``````actions = [{"R", 6}, {"D", 5}, ...]

directions = %{
"L" => {0, -1},
"R" => {0, 1},
"U" => {-1, 0},
"D" => {1, 0}
}

vertices =
for {dir, meters} <- actions,
reduce: [{0, 0}] do
[{i, j} | _] = acc ->
{di, dj} = directions[dir]
next_pos = {i + di * meters, j + dj * meters}
[next_pos | acc]
end

area =
vertices
|> Stream.map(fn [{i1, j1}, {i2, j2}] ->
(i1 - i2) * (j1 + j2)
end)
|> Enum.sum()
|> div(2)
|> abs()

perimeter = actions |> Enum.map(&elem(&1, 1)) |> Enum.sum()

IO.inspect(area + div(perimeter, 2) + 1)
``````

Part 2 only differs in parsing the input.

1 Like

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.

1 Like

Oh my…

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

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
``````
3 Likes

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.

Part 1
``````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()
``````
Part 2
``````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]

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.

Part 2 Nx
``````    tensor =
[origin | points]
|> 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)

``````
2 Likes

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

code
``````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"
|> 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)]

# 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} ->
{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.

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.

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.

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.

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.

4 Likes

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

1 Like

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:

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

1 Like

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.