Day 18

2024/day18.livemd

Łukasz Jan Niemier

@hauleth

advent-of-code

More notebooks

Day 18

Mix.install([:kino_aoc, :image])

Section

{:ok, puzzle_input} =
  KinoAOC.download_puzzle("2024", "18", System.fetch_env!("LB_ADVENT_OF_CODE_SESSION"))

{:ok,
 "21,9\n69,53\n31,24\n2,9\n50,53\n2,5\n3,44\n69,49\n25,26\n50,31\n68,41\n54,67\n19,8\n11,9\n9,29\n1,31\n13,12\n28,5\n69,41\n51,66\n53,43\n65,35\n40,67\n43,13\n21,34\n49,3\n65,61\n25,9\n39,21\n59,37\n11,24\n9,30\n63,62\n41,69\n6,29\n68,47\n45,1\n9,1\n11,14\n59,19\n67,54\n12,5\n41,44\n59,45\n3,28\n57,42\n7,25\n43,11\n31,19\n9,6\n53,60\n29,8\n53,67\n17,1\n11,17\n31,3\n55,35\n2,21\n67,61\n37,5\n6,1\n51,24\n39,1\n31,1\n69,58\n61,19\n49,63\n40,21\n28,25\n59,59\n66,69\n30,1\n7,5\n53,49\n4,17\n39,23\n23,20\n62,67\n51,36\n55,39\n41,3\n57,30\n18,7\n6,37\n29,25\n55,48\n37,16\n65,69\n21,5\n43,48\n3,11\n3,9\n63,39\n23,23\n43,67\n47,3\n69,47\n67,53\n65,24\n67,52\n35,20\n46,45\n57,26\n15,32\n35,68\n15,16\n41,1\n63,29\n15,3\n15,18\n51,50\n60,43\n50,1\n35,12\n41,10\n58,39\n27,18\n50,69\n55,40\n2,3\n51,47\n1,11\n16,9\n23,9\n19,7\n29,12\n37,3\n1,15\n11,1\n25,11\n65,56\n37,70\n60,41\n48,69\n62,29\n53,38\n12,35\n67,42\n49,67\n31,5\n39,7\n65,43\n5,25\n23,24\n43,68\n11,11\n9,32\n62,39\n69,39\n51,46\n38,21\n67,37\n5,26\n62,19\n27,21\n48,51\n55,62\n11,33\n25,4\n13,20\n61,58\n62,55\n41,66\n11,40\n16,7\n9,17\n67,65\n1,1\n9,33\n7,35\n1,3\n11,4\n29,21\n47,47\n61,67\n41,70\n42,65\n55,47\n54,49\n36,13\n61,36\n18,23\n26,23\n45,5\n9,18\n61,27\n36,21\n59,32\n4,9\n6,35\n51,23\n1,17\n12,11\n65,67\n41,65\n37,65\n1,24\n21,8\n59,28\n17,14\n63,68\n20,19\n17,10\n63,69\n57,44\n55,56\n45,64\n25,27\n27,4\n22,23\n5,13\n19,14\n47,46\n49,4\n21,15\n63,58\n60,31\n25,28\n6,3\n61,38\n33,5\n58,37\n11,32\n21,7\n44,61\n55,45\n55,37\n35,22\n10,15\n36,5\n19,11\n59,31\n33,19\n30,5\n69,69\n69,63\n57,69\n5,33\n60,27\n29,7\n57,43\n61,61\n3,26\n13,33\n57,59\n66,39\n63,27\n33,11\n51,1\n52,67\n5,29\n35,3\n17,2\n9,31\n37,24\n61,23\n9,5\n68,35\n21,28\n2,25\n51,48\n68,49\n4,19\n43,66\n7,34\n13,15\n36,1\n42,63\n13,0\n23,7\n48,47\n56,31\n55,43\n47,45\n18,15\n56,45\n61,64\n48,45\n69,65\n40,11\n51,68\n51,51\n53,46\n3,30\n49,62\n4,13\n17,27\n38,69\n41,0\n5,23\n65,32\n9,35\n55,21\n65,55\n51,39\n67,51\n5,9\n39,5\n58,49\n21,17\n63,41\n21,18\n57,65\n53,51\n2,13\n53,0\n53,6\n27,17\n55,59\n61,42\n27,7\n25,25\n39,13\n62,53\n51,44\n2,27\n19,17\n58,65\n8,1\n30,23\n14,5\n33,3\n43,65\n18,27\n35,7\n11,35\n12,29\n57,68\n59,63\n44,19\n36,25\n68,37\n15,19\n53,39\n62,69\n35,4\n61,55\n59,43\n23,17\n69,45\n18,5\n50,59\n39,6\n69,32\n17,5\n11,8\n21,2\n39,4\n64,65\n33,2\n17,22\n33,50\n25,24\n44,51\n31,7\n11,38\n11,25\n63,59\n25,21\n42,7\n8,11\n33,9\n45,63\n62,63\n33,4\n66,59\n61,29\n5,27\n59,27\n55,20\n38,9\n8,7\n51,3\n23,1\n53,65\n69,55\n1,34\n70,49\n61,57\n22,9\n17,26\n17,12\n61,69\n49,43\n9,28\n33,26\n15,35\n13,34\n55,27\n68,45\n45,61\n59,47\n13,29\n59,33\n65,53\n10,1\n35,21\n13,27\n28,1\n23,10\n61,37\n69,57\n23,21\n5,28\n57,48\n41,21\n11,13\n20,11\n1,21\n61,66\n66,47\n63,26\n5,15\n3,20\n17,4\n43,5\n16,29\n63,44\n63,55\n55,69\n5,22\n37,11\n50,39\n59,39\n25,16\n48,1\n43,60\n13,6\n49,37\n3,32\n57,23\n46,69\n2,35\n37,1\n53,27\n31,22\n63,36\n46,43\n68,57\n45,67\n32,9\n48,65\n15,15\n8,29\n13,1\n55,41\n65,65\n13,31\n49,69\n19,6\n29,19\n32,23\n49,41\n15,24\n65,22\n15,33\n6,21\n7,9\n69,64\n63,23\n5,21\n15,1\n44,1\n11,27\n63,34\n15,13\n39,9\n63,20\n58,29\n28,21\n7,37\n39,65\n41,16\n21,6\n49,47\n47,61\n50,63\n23,15\n68,67\n64,57\n19,13\n69,61\n1,22\n27,3\n28,13\n19,31\n23,2\n3,31\n25,6\n61,47\n51,63\n59,64\n27,2\n7,33\n63,63\n65,42\n5,12\n12,15\n27,9\n15,7\n6,17\n17,17\n15,2\n59,61\n63,47\n57,33\n13,17\n47,67\n11,26\n20,3\n13,7\n17,33\n10,5\n57,32\n58,53\n7,18\n66,65\n6,5\n11,5\n41,9\n21,21\n69,43\n11,20\n41,14\n38,3\n67,69\n15,17\n45,58\n51,61\n54,23\n49,39\n59,29\n53,63\n45,69\n16,1\n55,51\n21,13\n56,47\n63,40\n63,37\n37,19\n43,3\n7,17\n27,5\n14,25\n17,3\n44,69\n31,8\n14,9\n14,7\n63,45\n4,1\n49,34\n19,44\n46,53\n38,17\n33,0\n50,55\n27,25\n63,21\n19,12\n35,10\n54,3\n65,50\n47,62\n38,65\n61,39\n33,1\n65,52\n5,5\n0,3\n63,33\n30,27\n29,27\n29,1\n48,67\n33,23\n46,5\n60,35\n39,14\n59,46\n51,49\n64,21\n69,60\n3,3\n59,58\n9,36\n9,37\n48,41\n23,5\n7,3\n61,65\n61,22\n3,15\n4,37\n43,20\n66,45\n69,66\n43,12\n54,43\n52,49\n15,23\n33,21\n36,67\n61,24\n5,7\n37,7\n60,55\n53,70\n52,1\n21,33\n53,69\n67,43\n61,34\n6,31\n55,55\n59,40\n16,17\n65,25\n24,29\n59,21\n66,63\n61,41\n17,24\n0,15\n17,19\n1,13\n23,3\n49,45\n39,2\n59,49\n31,25\n65,40\n7,7\n70,43\n57,63\n65,54\n18,1\n41,15\n25,19\n33,18\n5,24\n13,3\n64,37\n43,7\n31,9\n30,11\n56,63\n65,34\n67,39\n17,18\n65,37\n49,56\n59,25\n7,11\n65,38\n37,18\n5,3\n21,22\n47,69\n19,9\n70,39\n15,14\n40,3\n5,31\n19,21\n55,34\n67,49\n45,11\n17,23\n41,5\n33,6\n37,10\n55,2\n17,9\n57,39\n5,1\n9,10\n17,7\n60,23\n55,68\n5,11\n63,67\n59,65\n7,19\n51,56\n26,1\n30,3\n15,20\n19,15\n3,21\n59,51\n11,7\n61,26\n19,23\n22,11\n25,8\n18,17\n27,26\n17,29\n7,13\n65,33\n44,5\n22,13\n56,65\n24,19\n25,17\n55,66\n65,39\n32,19\n3,19\n9,15\n54,63\n55,23\n61,59\n21,11\n46,39\n57,40\n65,19\n65,59\n65,48\n64,47\n32,21\n1,5\n15,11\n65,23\n4,2" <> ...}

bytes =
  puzzle_input
  |> String.split("\n", trim: true)
  |> Enum.map(fn row ->
    [x, y] = String.split(row, ",")

    {String.to_integer(x), String.to_integer(y)}
  end)

[
  {21, 9},
  {69, 53},
  {31, 24},
  {2, 9},
  {50, 53},
  {2, 5},
  {3, 44},
  {69, 49},
  {25, 26},
  {50, 31},
  {68, 41},
  {54, 67},
  {19, 8},
  {11, 9},
  {9, 29},
  {1, 31},
  {13, 12},
  {28, 5},
  {69, 41},
  {51, 66},
  {53, 43},
  {65, 35},
  {40, 67},
  {43, 13},
  {21, 34},
  {49, 3},
  {65, 61},
  {25, 9},
  {39, 21},
  {59, 37},
  {11, 24},
  {9, 30},
  {63, 62},
  {41, 69},
  {6, 29},
  {68, 47},
  {45, 1},
  {9, 1},
  {11, 14},
  {59, 19},
  {67, 54},
  {12, 5},
  {41, 44},
  {59, 45},
  {3, 28},
  {57, 42},
  {7, 25},
  {43, 11},
  {31, ...},
  {...},
  ...
]

Image.new!(71, 71, color: :forestgreen)
|> Image.mutate(fn img ->
  for x <- 0..70, y <- 0..70, {x, y} in Enum.take(bytes, 1024) do
    Image.Draw.point(img, x, y, color: :firebrick)
  end

  img
end)
|> elem(1)
|> Image.resize!(4, interpolate: :nearest)

defmodule Memory do
  @d [{-1, 0}, {1, 0}, {0, -1}, {0, 1}]
  def find_path(from, to, bytes), do: do_find([{0, from}], to, MapSet.new(bytes), %{})

  def do_find([], _, _, _), do: :none

  def do_find([{dist, to} | _], to, _, _visited), do: dist

  def do_find([{dist, {x, y} = p} | rest], {w, h} = to, bytes, visited)
      when not is_map_key(visited, p)
      when dist < :erlang.map_get(p, visited)
  do
    visited = Map.put(visited, p, dist)

    next =
      for {dx, dy} <- @d,
          (x + dx) in 0..w,
          (y + dy) in 0..h,
          p = {x + dx, y + dy},
          p not in bytes,
          not is_map_key(visited, p),
          do: {dist + 1, p}

    next
    |> Enum.concat(rest)
    |> Enum.sort()
    |> do_find(to, bytes, visited)
  end

  def do_find([_ | rest], to, bytes, visited), do: do_find(rest, to, bytes, visited)
end

{:module, Memory, <<70, 79, 82, 49, 0, 0, 13, ...>>, {:do_find, 4}}

Part 1

Memory.find_path({0, 0}, {70, 70}, Enum.take(bytes, 1024))

Part 2

{x, y} =
  bytes
  |> Enum.reverse()
  |> Stream.unfold(fn
    [] -> nil
    [_ | rest] = curr -> {curr, rest}
  end)
  |> Enum.find_value(fn [pos | fallen] ->
    path = Memory.find_path({0, 0}, {70, 70}, fallen)

    if path != :none do
      pos
    end
  end)

IO.puts("#{x},#{y}")

56,8

:ok

Back