# Advent of Code 2023 - Day 22

I went for a brute-force solution, implementing the most straight-forward algorithm I could think of. That initial implementation solved both parts in about 10 minutes.

After that, I did some simple improvements that reduced the time to about two and a half minutes.

Now I will optimize my spare time and take the rest of the day off.

Iâ€™m just discovering part 2 at the moment and I was planning to do the same, just run everything and count.

I was coming here in the hope to find a better simulation algorithm because mine is slow AF.

But I am glad that part 2 was not â€śactually just drop 10 000 times the set of bricks from the sky and do the same as P1â€ť. Thank goodness.

Ok so finally finished itâ€¦ Iâ€™m slow

It takes 28 seconds for each part, mostly to make all the bricks fall. Summing each chain reaction takes 1 second.

Iâ€™m all ears for a better falling algorithm if anyone reads this ever

Edit, ok, got it under 2sec for part 1 and 2.5 for part 2, thanks to this monstruosity:

``````  defp on_top_of?(
{_, {xdeb, ydeb, zdeb}, {xfin, yfin, zfin}},
{_, {xbotdeb, ybotdeb, zbotdeb}, {xbotfin, ybotfin, zbotfin}}
)
when (zdeb == zbotdeb + 1 or
zfin == zbotfin + 1 or
zdeb == zbotfin + 1 or
zfin == zbotdeb + 1) and
(xdeb in xbotdeb..xbotfin or
xfin in xbotdeb..xbotfin or
xbotdeb in xdeb..xfin or
xbotfin in xdeb..xfin) and
(ydeb in ybotdeb..ybotfin or
yfin in ybotdeb..ybotfin or
ybotdeb in ydeb..yfin or
ybotfin in ydeb..yfin) do
true
end

defp on_top_of?(_, _) do
false
end
``````

I LOVE that it is possible to do basic math in guards

Solution

1 Like

No fancy algorithm needed this time. To adjust for part 2, I just needed to add an extra bit of the result thatâ€™s passed up (whether a brick fell or not). Mine runs in under a second for both partsâ€¦ the most â€śinventiveâ€ť thing I used is that for each {x,y} position I remember the highest occupied â€śzâ€ť coordinate, which gives an easy way to check how deep the next brick can fallâ€¦

code
``````defmodule Main do
def run() do
get_input()
|> Enum.map(&parse/1)
|> prep()
# |> solve1()
|> solve2()
end

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

def parse(l) do
for e <- (l |> String.split("~")) do
Regex.run(~r/(\d+),(\d+),(\d+)/,e) |> tl()
|> Enum.map(fn s -> String.to_integer(s) end)
|> List.to_tuple()
end
end

def land_brick([{x0,y0,z0},{x1,y1,z1}], grid) do
mx = for x <- x0..x1, y <- y0..y1, reduce: 0 do m -> max(m, grid[{x,y}]) end
newg = for x <- x0..x1, y <- y0..y1, reduce: grid do g -> Map.put(g,{x,y},mx+1+z1-z0) end
{[{x0,y0,mx},{x1,y1,mx+z1-z0}], newg, (if mx==z0, do: 0, else: 1)}
end

def land_bricks(sorted_bricks,base) do
sorted_bricks
|> Enum.reduce({base,[],0}, fn b,{trr,bs,fell} ->
{lb,ntrr,f?} = land_brick(b,trr)
{ntrr,[lb|bs],fell+f?}
end)
|> project_and_sort()
end

def project_and_sort({_,bs,fell}) do
{Enum.sort_by(bs,fn [{_,_,z0},{_,_,z1}] -> min(z0,z1) end, :asc), fell}
end

def check_removable(b,lbs,base), do: 0 == count_fell(b,lbs,base)

def count_fell(b,lbs,base) do
tbs = List.delete(lbs,b)
land_bricks(tbs,base) |> elem(1)
end

def prep(bs) do
maxx = bs |> Enum.map(fn [{x0,_,_},{x1,_,_}] -> max(x0,x1) end) |> Enum.max()
maxy = bs |> Enum.map(fn [{_,y0,_},{_,y1,_}] -> max(y0,y1) end) |> Enum.max()
base = for x <- 0..maxx, y <- 0..maxy, into: %{}, do: {{x,y}, 1}
bs = bs |> Enum.sort_by(fn [{_,_,z0},{_,_,z1}] -> min(z0,z1) end, :asc)
{lbs,_} = land_bricks(bs,base)
{lbs,base}
end

def solve1({lbs,base}) do
lbs |> Enum.filter(&check_removable(&1,lbs,base)) |> Enum.count()
end

def solve2({lbs,base}) do
lbs |> Enum.map(&count_fell(&1,lbs,base)) |> Enum.sum()
end
end

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

Solved part 1 with a graph and part 2 is just brute force. Could have also brute forced part 1 after the â€ścountingâ€ť adjustments for part 2â€¦

Got stuck on part 1 for a couple days and could not figure out what I was doing wrong. My code was working on all the examples I could find, but no the puzzle input. This morning I decided I would try to visualize the stack using three.js and a custom Kino:

The z-fighting between the bricks revealed that my stacking algorithm was off. I thought that I could sort the bricks and then just use `Enum.find` to take the first intersecting brick that was settled. I actually needed to take the intersecting brick with the maximum z position.

Part 1 runs in 0.3s and part 2 runs in 0.8s.

Part 1
``````defmodule Part1 do
def to_alpha(i), do: to_alpha(i, [])
def to_alpha(i, acc) when i < 26, do: to_string([rem(i, 26) + 65 | acc])
def to_alpha(i, acc), do: to_alpha(div(i, 26) - 1, [rem(i, 26) + 65 | acc])

def parse(input) do
for {line, i} <- String.split(input, "\n", trim: true) |> Enum.with_index() do
{x, y, z} =
String.split(line, [",", "~"], trim: true)
|> Enum.map(&String.to_integer/1)
|> Enum.chunk_every(3)
|> Enum.zip_with(fn [a, b] -> Range.new(min(a, b), max(a, b)) end)
|> List.to_tuple()

{to_alpha(i), x, y, z}
end
end

def disjoint?(bricks) do
Enum.all?(bricks, fn {_, ax, ay, az} = brick ->
Enum.filter(bricks, fn other -> other != brick end)
|> Enum.all?(fn {_, bx, by, bz} ->
Range.disjoint?(ax, bx) or
Range.disjoint?(ay, by) or
Range.disjoint?(az, bz)
end)
end)
end

def drop(bricks),
do:
bricks
|> Enum.sort_by(fn {_, _, _, z1.._} -> z1 end)
|> drop([])

def drop([], settled), do: settled

def drop([{_, _, _, 1.._} = brick | bricks], settled),
do: drop(bricks, [brick | settled])

def drop([{id, ax, ay, az} | bricks], settled) do
{_, _, _, _..bz2} =
Enum.filter(settled, fn {_, bx, by, _} ->
not (Range.disjoint?(ax, bx) or
Range.disjoint?(ay, by))
end)
|> Enum.max_by(
fn {_, _, _, _..bz2} -> bz2 end,
fn -> {nil, nil, nil, 0..0} end
)

az1 = bz2 + 1
az2 = bz2 + Range.size(az)
brick = {id, ax, ay, az1..az2}
drop(bricks, [brick | settled])
end

def support(bricks), do: support(bricks, bricks, %{})

def support([], _, supports), do: supports

def support([{_, ax, ay, az1.._} = current | rest], bricks, supports) do
others =
Enum.filter(bricks, fn {_, bx, by, _..bz2} ->
bz2 == az1 - 1 and
not (Range.disjoint?(ax, bx) or
Range.disjoint?(ay, by))
end)

supports =
Map.update(
supports,
current,
%{is_above: others, is_below: []},
fn %{is_above: above} = existing ->
%{existing | is_above: others ++ above}
end
)

supports =
Enum.reduce(others, supports, fn other, supports ->
Map.update(
supports,
other,
%{is_above: [], is_below: [current]},
fn %{is_below: below} = existing ->
%{existing | is_below: [current | below]}
end
)
end)

support(rest, bricks, supports)
end

def free(supports) do
required =
supports
|> Enum.filter(fn {_, %{is_above: is_above}} -> length(is_above) == 1 end)
|> Enum.flat_map(fn {_, %{is_above: is_above}} -> is_above end)
|> MapSet.new()

supports
|> Map.keys()
|> MapSet.new()
|> MapSet.difference(required)
|> Enum.to_list()
end
end

bricks =
input
|> Part1.parse()
|> Part1.drop()

bricks
|> Part1.disjoint?()
|> IO.inspect(label: "disjoint?")

bricks
|> KinoThree.new(z: 15, y: 0, w: 640, h: 480)
|> Kino.render()

bricks
|> Part1.support()
|> Part1.free()
|> length()
``````
Part 2
``````defmodule Part2 do
def disintegrate(supports) do
supports
|> Map.keys()
|> Enum.map(fn brick ->
brick
|> chain(supports)
|> MapSet.size()
end)
|> Enum.sum()
end

def chain(brick, supports), do: chain([brick], supports, MapSet.new())
def chain([], _, acc), do: acc

def chain([brick | rest], supports, acc) do
destroyed =
supports[brick].is_below
|> Enum.filter(fn above_brick ->
below_bricks = supports[above_brick].is_above

length(below_bricks) == 1 or
Enum.all?(below_bricks, fn below -> MapSet.member?(acc, below) end)
end)

acc =
destroyed
|> MapSet.new()
|> MapSet.union(acc)

chain(rest ++ destroyed, supports, acc)
end
end

input
|> Part1.parse()
|> Part1.drop()
|> Part1.support()
|> Part2.disintegrate()
``````
Kino + three.js
``````defmodule KinoThree do
use Kino.JS

def new(bricks, opts) do
bricks =
for {id, x, y, z} <- bricks do
%{
id: id,
x: x.first,
y: z.first,
z: y.first,
w: Range.size(x),
h: Range.size(z),
d: Range.size(y)
}
end

%{y: y, h: h} = Enum.max_by(bricks, fn %{y: y, h: h} -> y + h end)
max_y = y + h

z = Keyword.get(opts, :z, 5)
y = Keyword.get(opts, :y, 0)
w = Keyword.get(opts, :w, 640)
h = Keyword.get(opts, :h, 480)

opts = %{bricks: bricks, max_y: max_y, z: z, y: y, w: w, h: h}
Kino.JS.new(__MODULE__, opts)
end

asset "main.js" do
"""
import * as THREE from "https://unpkg.com/three@0.160.0/build/three.module.min.js";

export function init(ctx, opts) {
const renderer = new THREE.WebGLRenderer();
renderer.setSize(opts.w, opts.h);
ctx.root.appendChild(renderer.domElement);

const scene = new THREE.Scene();
const camera = new THREE.PerspectiveCamera(75, opts.w / opts.h, 0.1, 1000);

for (const {id, x, y, z, w, h, d} of opts.bricks) {
const geometry = new THREE.BoxGeometry(w, h, d);
const color = new THREE.Color(Math.random(), Math.random(), Math.random());
const material = new THREE.MeshBasicMaterial({ color });
const mesh = new THREE.Mesh(geometry, material);
mesh.position.x = x + w / 2;
mesh.position.y = y + h / 2;
mesh.position.z = z + d / 2;
}

let dy = opts.max_y / 1000;
camera.position.y = opts.y;
camera.position.z = opts.z;

function animate() {
requestAnimationFrame(animate);
scene.rotation.y += 0.01;

camera.position.y += dy;
if (camera.position.y > opts.max_y) {
camera.position.y = opts.max_y;
dy = -dy;
} else if (camera.position.y < 0) {
camera.position.y = 0;
dy = -dy;
}

renderer.render(scene, camera);
}
animate();
}
"""
end
end
``````
1 Like

Such a beautiful set of LoCs! Thank you for this, helped me quite a bit!

1 Like