Advent of Code 2023 - Day 22

bjorng

Erlang Core Team

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.

https://github.com/bjorng/advent-of-code-2023/blob/main/day22/lib/day22.ex

6 comments

#advent-of-code #2023

0 825 6

2023-12-31 17:27:19 UTC

Showing Posts 1 to 6

Show Best Posts
Show All (oldest first)
Show All (newest first)

lud

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.

Post #1

lud

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

Post #2

exists

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)

Post #3

pehbehbeh

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…

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

Post #4

midouest

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:

output

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;
        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

Post #5