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
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…
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.
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()
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()
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;
scene.add(mesh);
}
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
Such a beautiful set of LoCs! Thank you for this, helped me quite a bit!
© Copyright Elixir Forum | Terms | Privacy & Cookies
