Powered by AppSignal & Oban Pro
Would you like to see your link here? Contact us
Notesclub
Sign in with GitHub
created by hec & contributors
terms privacy

Day 13

2023/day13.livemd

avatar
Łukasz Jan Niemier
avatar
avatar
More notebooks
1

Day 13

Mix.install([:kino_aoc])

Setup

{:ok, puzzle_input} =
  KinoAOC.download_puzzle("2023", "13", System.fetch_env!("LB_ADVENT_OF_CODE_SESSION"))
{:ok,
 ".#..#......\n..#.#......\n..#...#....\n#.##...####\n.#..#..####\n#.#.##.####\n###..#.#..#\n\n.#.##.#.###\n..####..##.\n#########..\n.##..##..##\n.##..##..##\n#########..\n..####..##.\n.#.##.#.###\n#.#..#.##.#\n..#####.###\n...##.....#\n..#..#..#..\n...##...#..\n\n..##.#.\n#...###\n#...###\n..##.##\n..#..#.\n....##.\n#.#.#..\n.#...##\n##.#...\n###.###\n###.###\n##.#...\n.#...##\n\n#.#.###\n..##.##\n...####\n##....#\n##....#\n...####\n..##.##\n#.#.###\n#.#####\n....##.\n.#...#.\n#.#####\n#....##\n#..##.#\n#..##.#\n#..#.##\n#.#####\n\n###...#...#.#..\n.#.##.#.....#..\n..###..#..#....\n..###..#..#....\n.#.##.#........\n###...#...#.#..\n###..#..##.#.##\n\n##.#.....\n##.#...#.\n..#.#..##\n..##....#\n#..#....#\n#.#..##..\n#.#..##..\n#..#....#\n..##....#\n..#.#..##\n##.#...#.\n##.#.....\n#.#..#.#.\n\n#..#..#..#.##\n..........###\n..........###\n#..#..#..#.##\n###....####.#\n....##......#\n##..##..##..#\n###....####..\n....##.....##\n.#......#.#.#\n.##....##..##\n..#.##.#....#\n####..######.\n.##..#.##.###\n..##..##...#.\n\n..#.###..#.\n####.#.....\n..#.##.##..\n...##...#.#\n###.#......\n#######.###\n..#.#...###\n###.###.##.\n###..#...##\n##....##.#.\n####...#.##\n..###......\n.###..#.#..\n##.##..#.#.\n##.##..#.#.\n\n#.##.###......#\n.#..#.#..##..##\n..##..#.#..#...\n#....##.#.#.#..\n#....##.######.\n######....###.#\n#.##.#...##.##.\n..##..#####.###\n..##..######..#\n..##..######..#\n..##..#####.###\n#.##.#...##.##.\n######....###.#\n#....##.######.\n#....##...#.#..\n\n......#....#...\n.####...##...#.\n######..##..###\n######..##..###\n......##..##...\n.####.######.##\n.#..#.######.#.\n\n#############..##\n.########...###.#\n.########...#.#.#\n#.##..##.###..##.\n..#.##.#....#.#..\n..#....#...####..\n#.#....#.##.#.#..\n.#......#......##\n.#......#......##\n#.#....#.##.#.##.\n..#....#...####..\n\n...#.###.#.\n....##.#.##\n..##..#.###\n..##..#.###\n....##.#.##\n...#.###.#.\n#.#.#.#.#..\n...##.#..##\n.#.####...#\n.#.#.##...#\n...##.#..##\n#.#.#.#.#..\n...#.###.#.\n....##.#.##\n..##..#.###\n\n.#.##.#.#.#..#.\n.........######\n###..####.#..#.\n##.##.##.......\n..#..#..##....#\n.#.##.#...####.\n##.....#..####.\n..####..#..##..\n##....##...##..\n\n....####.####..\n.#..####.####..\n#.#.##..#####..\n##..#.#.#######\n.#.#.##.##.##..\n..##..#.##..#..\n####....#...#..\n..#.#....##.#..\n#..#..#..##.#..\n.#.......#.####\n..........##...\n#.....####.#.##\n##....##....###\n.....#.##.#####\n.#..#.##....#..\n#.....###...#..\n#....##........\n\n#..##..#....###\n#..#.#......###\n.....#..####...\n.##.##.##...###\n.....##.###..##\n.##..##....#.#.\n.##...#.#.#.#..\n\n.###.....##\n..#......#.\n..####.####\n#.##...#.#.\n#..#...####\n##.#.#..###\n##.#.#..###\n#..#...####\n#.##...#.#.\n..####.####\n..#......#.\n.###.....##\n.#.##.#..#.\n..#...###..\n..#...###..\n.#.#..#..#.\n.###.....##\n\n###..##\n...####\n.#..#.#\n#.##...\n#...#..\n#...#..\n#.##...\n\n..#......#.....\n#.#......#.#..#\n.#..####..#....\n.#.#....#.#.##.\n..########..##.\n..#.####.#.....\n..###..###..##.\n#..######..####\n.#####.####.##.\n#..#....#..#..#\n##........##..#\n.....##.....##.\n.##.#..#.##....\n\n...#.##\n...#...\n#..####\n#..####\n...#...\n...#.##\n#.###.#\n.##.#.#\n.#.###.\n.##.##.\n.##..#.\n.#.###.\n.##.#.#\n\n..#...##.\n..###..##\n...##.#..\n###.#.##.\n..##..##.\n###..###.\n..#.#.#..\n####..#..\n...#####.\n##.####..\n###.#..##\n..#######\n..#######\n###.#...#\n##.####..\n...#####.\n####..#..\n\n.##...##.\n#..##..#.\n###..####\n#..##.##.\n.##..##..\n#..###.##\n.##.##.##\n....##.##\n.##.##..#\n.##.##...\n.##.##...\n.##.##..#\n....##.##\n\n#...#.##.##..#.##\n##..#.###...#####\n##..#.###...###.#\n#...#.##.##..#.##\n...#.....###..##.\n..####.#.#.####.#\n..####.#.#.####.#\n...#.....###..##.\n#...#.##.##..#.##\n\n.##..####.#####\n.##..####.####.\n.##.#.##..#.###\n#..#.######.#.#\n.#....##..##...\n##..#.####..##.\n.....#......##.\n##..##..#.#.###\n...##..#.#.#.#.\n...#..##.###...\n...#..##.###...\n\n#..##.#.#.#\n######..##.\n#..#...#..#\n#..#...#..#\n######..##.\n#..##.#.#.#\n#..#..##..#\n#...##.#.##\n######.##.#\n....#..####\n####..##.#.\n\n##.##..##.#.##.#.\n....##.###..##..#\n.##.#.##..######.\n.##.#.##..######.\n....##.###..##..#\n##.##..##.#.##.#.\n#####..#...####..\n..##....###.##.##\n.####...##.#..#.#\n.####....#......#\n##..#...#........\n.##.#..#..##...#.\n#####..#.##....##\n#.#.#.#..#.####.#\n##.######........\n\n....#.#..\n....#.##.\n##.##.#..\n##...#.#.\n#.##..###\n#.##..###\n##...#.#.\n\n##....###.####..#\n" <> ...}
# puzzle_input =
"""
#.##..##.
..#.##.#.
##......#
##......#
..#.##.#.
..##..##.
#.#.##.#.

#...##..#
#....#..#
..##..###
#####.##.
#####.##.
..##..###
#....#..#
"""
"#.##..##.\n..#.##.#.\n##......#\n##......#\n..#.##.#.\n..##..##.\n#.#.##.#.\n\n#...##..#\n#....#..#\n..##..###\n#####.##.\n#####.##.\n..##..###\n#....#..#\n"
defmodule Day13 do
  def find_axes(list) do
    reversed = Enum.reverse(list)

    len = length(list)

    back = dbg(do_find(list, 0))
    front = dbg(do_find(reversed, 0))

    [
      if(back, do: div(len - back, 2) + back),
      if(front, do: div(len - front, 2))
    ]
    |> Enum.filter(&amp; &amp;1)
  end

  defp do_find([_], _), do: nil

  defp do_find([_ | a], n) when rem(n, 2) == 0, do: do_find(a, n + 1)

  defp do_find(a, n) do
    if palindrome?(a) do
      n
    else
      do_find(tl(a), n + 1)
    end
  end

  def palindrome?(list) do
    list == Enum.reverse(list)
  end

  def print_mirror({rows, cols, _, _}) do
    width = length(cols)

    display =
      for row <- rows do
        for digit <- Integer.digits(row, 2) do
          if digit == 1, do: "#", else: "."
        end
        |> List.to_string()
        |> String.pad_leading(width, ".")
      end

    IO.puts(Enum.intersperse(display, "\n"))
  end
end
{:module, Day13, <<70, 79, 82, 49, 0, 0, 20, ...>>, {:print_mirror, 1}}
mirrors =
  puzzle_input
  |> String.split("\n\n", trim: true)
  |> Enum.map(fn grid ->
    mirror =
      grid
      |> String.split("\n", trim: true)
      |> Enum.map(fn line ->
        for <>, do: if(c == ?#, do: 1, else: 0)
      end)

    rows = Enum.map(mirror, &amp;Integer.undigits(&amp;1, 2))
    cols = Enum.zip_with(mirror, &amp;Integer.undigits(&amp;1, 2))

    row = Day13.find_axes(rows)
    col = Day13.find_axes(cols)

    {rows, cols, row, col}
  end)
[
  {[576, 320, 272, 1423, 591, 1391, 1833], [11, 69, 59, 8, 102, 3, 16, 15, 14, 14, 15], [], ~c"\t"},
  {[727, 486, 2044, 819, 819, 2044, 486, 727, 1325, 503, 193, 292, 196],
   [1168, 6048, 4058, 7405, 7405, 4058, 6056, 1168, 7419, 7016, 4924], [4], []},
  {[26, 71, 71, 27, 18, 6, 84, 35, 104, 119, 119, 104, 35],
   [3166, 63, 4940, 4626, 3276, 8109, 3629], ~c"\n", []},
  {[87, 27, 15, 97, 97, 15, 27, 87, 95, 6, 34, 95, 67, 77, 77, 75, 95],
   [78655, 12352, 100129, 52527, 84909, 118771, 130879], [4], []},
  {[28948, 11524, 7312, 7312, 11520, 28948, 29291],
   [67, 103, 91, 60, 60, 1, 102, 24, 1, 1, 90, 1, 98, 1, 1], [], [14]},
  {[416, 418, 83, 97, 289, 332, 332, 289, 97, 83, 418, 416, 330],
   [6631, 6150, 1753, 6966, 1032, 193, 192, 3085, 1848], [6], []},
  {[4683, 7, 7, 4683, 7229, 385, 6553, 7228, 387, 2069, 3123, 1441, 7806, 3255, 1634],
   [19844, 1462, 1183, 18437, 840, 842, 18437, 1183, 1462, 19844, 13478, 30807, 32634], [2], []},
  {[370, 1952, 364, 197, 1856, 2039, 327, 1910, 1827, 1562, 1931, 448, 916, 1738, 1738],
   [9971, 9975, 30684, 10783, 24459, 29376, 17060, 4147, 7044, 17395, 2896], [14], []},
  {[23425, 9523, 6472, 17236, 17278, 32285, 23094, 6647, 6649, 6649, 6647, 23094, 32285, 17278,
    17172],
   [20239, 8708, 21500, 21500, 8708, 20239, 31987, 16624, 7410, 9722, 12287, 5734, 3999, 9626,
    25332], [], [3]},
  {[264, 15458, 32359, 32359, 408, 15867, 9722],
   [24, 59, 58, 58, 59, 24, 71, 7, 59, 59, 7, 71, 24, 59, 26], [], [3]},
  {[131059, 65309, 65301, 91878, 23060, 16956, 82644, 33027, 33027, 82646, 16956],
   [1170, 1804, 2035, 1920, 1856, 1856, 1920, 2035, 1804, 1170, 1170, 1185, 1907, 545, 1011, 1166,
    1804], [], [5]},
  {[186, 107, 407, 407, 107, 186, 1364, 211, 753, 689, 211, 1364, 186, 107, 407],
   [264, 96, 6409, 23285, 9690, 26214, 23549, 26118, 6409, 32407, 15603], [3], []},
  {[11602, 63, 29650, 28032, 4705, 11550, 24734, 7756, 24972],
   [101, 365, 82, 298, 298, 82, 361, 101, 338, 144, 460, 143, 143, 460, 144], [], ~c"\f"},
  {[1980, 10172, 22140, 25983, 11116, 6500, 30788, 5172, 18740, 8239, 24, 16875, 24967, 735, 9604,
    16836, 17152],
   [25907, 46228, 19968, 7424, 123396, 118793, 112951, 98366, 31786, 129952, 123720, 127208, 130974,
    8376, 8376], [], [14]},
  {[19591, 18951, 632, 14023, 883, 13066, 12628],
   [96, 11, 11, 96, 72, 62, 7, 72, 29, 20, 21, 18, 105, 110, 108], [], [2]},
  {[899, 258, 495, 1418, 1167, 1703, 1703, 1167, 1418, 495, 258, 899, 722, 284, 284, 658, 899],
   [16128, 68659, 123373, 98227, 16528, 19584, 30, 29580, 24204, 131059, 89761], [6], []},
  {[115, 15, 37, 88, 68, 68, 88], ~c"OPI)6`p", [5], []},
  {[4128, 20521, 10128, 10326, 8166, 6048, 7398, 20431, 16118, 18505, 24601, 774, 13488],
   [2092, 1557, 6609, 888, 1521, 1458, 1442, 1521, 888, 6609, 1557, 2092, 882, 882, 2092], [],
   ~c"\r"},
  {~c"\v\bOO\b\v]5.62.5", [1600, 63, 109, 8146, 1659, 5790, 5857], [3], []},
  {[70, 115, 52, 470, 102, 462, 84, 484, 62, 444, 467, 127, 127, 465, 444, 62, 484],
   [10957, 10957, 114297, 54199, 58878, 2486, 98231, 113010, 32888], [], [1]},
  {[198, 306, 463, 310, 204, 315, 219, 27, 217, 216, 216, 217, 27],
   [3712, 5470, 5470, 2688, 2815, 1535, 5888, 7905, 1267], ~c"\n", []},
  {[71371, 104223, 104221, 71371, 8422, 31421, 31421, 8422, 71371],
   [481, 192, 12, 30, 493, 12, 481, 493, 192, 319, 307, 30, 204, 493, 222, 435, 493], [6], []},
  {[13279, 13278, 13719, 19445, 8600, 26086, 518, 26199, 3242, 2488, 2488],
   [168, 1896, 1792, 135, 300, 1688, 2019, 2023, 1704, 167, 1995, 1607, 1976, 1852, 1416], ~c"\n",
   []},
  {[1237, 2022, 1161, 1161, 2022, 1237, 1177, 1131, 2029, 79, 1946],
   [2045, 581, 581, 2037, 1646, 588, 1073, 415, 1638, 587, 1470], [3], []},
  {[111450, 7065, 54910, 54910, 7065, 111450, 127548, 25051, 61861, 61569, 102656, 53858, 127683,
    87229, 114432],
   [17175, 23421, 6638, 17381, 32639, 9217, 6147, 32525, 26321, 9446, 23180, 6474, 32642, 32642,
    6466, 23180, 9446], [3], []},
  {[20, 22, 436, 394, 359, 359, 394], [31, 25, 6, 22, 112, 9, 118, 47, 6], [5], []},
  {[100217, 100217, 46111, 64677, 64959, 18555, 64861, 131030, 388, 112431, 66318, 67525, 118470],
   [6191, 8041, 993, 1896, 1896, 993, 8043, 6191, 6526, 819, 6371, 7048, 7648, 7628, 1919, 1453,
    8138], [1], []},
  {[291, 1, 24, 28, 1, 291, 492], [67, 1, 1, 67, 24, 25, 9, 66, 102], [], [2]},
  {~c"2aa2\n}|\n2", [204, 493, 301, 30, 12, 307, 200], [2], []},
  {[3115, 4616, 3100, 4656, 4643, 1344, 167], [44, 80, 82, 44, 2, 1, 2, 77, 24, 112, 17, 69, 69],
   [], ~c"\f"},
  {[67339, 92194, 8007, 70176, 4382, 5406, 70176, 8007, 92194, 67339, 55372, 10833, 123746, 57569,
    57569],
   [26980, 23, 8279, 8271, 8080, 12504, 21152, 22956, 22180, 3, 4255, 10567, 1544, 17968, 5776,
    30436, 20651], [14], []},
  {[6424, 26178, 346, 6490, 23485, 15384, 14592, 9703, 26392, 23515, 32280, 32475, 15706, 32358,
    9471, 23320, 17254],
   [37355, 36732, 81146, 81146, 35708, 37355, 96147, 4772, 58045, 4621, 96758, 96758, 4621, 58045,
    4772], [], ~c"\v"},
  {[75457, 7450, 103542, 100685, 20575, 20575, 117069, 103542, 7450, 75457, 75457, 7450, 103542,
    117069, 20575],
   [22966, 6534, 1795, 16432, 14029, 10570, 28924, 16432, 10570, 16432, 24503, 4228, 14029, 12107,
    8071, ...], ~c"\n", []},
  {[114654, 1118, 92031, 101299, 101299, 92031, 1118, 114654, 31935, 80545, 20702, 1480, 17953,
    69836, 60269, ...],
   [96904, 78341, 18775, 84868, 66504, 78725, 118578, 96919, 96805, 78826, 118382, 31124, 130880,
    118637, ...], [4], []},
  {[14474, 14474, 17870, 27951, 39, 7069, 240, 31399, 31655, 240, 7069],
   [396, 1676, 1581, 1709, 384, 45, 421, 1855, 274, 222, 51, 1953, 493, ...], [1], []},
  {[36, 36, 84, 53, 75, 28, 32, 126, 125, 125, 126, 36, 28, ...],
   [5362, 27129, 6901, 1782, 31485, 1170, 3171], [1], []},
  {[4259, 8068, 7, 8168, 4551, 6595, 1584, 4292, 84],
   [442, 168, 164, 164, 184, 442, 59, 292, 5, 32, 211, ...], [], ~c"\f"},
  {[130987, 86, 74905, 93, 126, 56186, 81145, 81094, 23097, 81025, 124915, ...],
   [20924, 16916, 16980, 20924, 17386, 17386, 20924, 16980, 16916, 20924, ...], [], [5]},
  {[38804, 125056, 92872, 151, 1196, 129732, 62279], [50, 99, 51, 51, 67, 50, 68, 83, 65, ...], [],
   [16]},
  {[54, 11, 393, 54, 127, 127, 54, 393, 11, ...],
   [1056, 1057, 388, 5069, 5071, 3510, 5066, 7130, ...], [5], []},
  {[391, 2025, 404, 2039, 188, 1629, 1605, 1894, ...],
   [44902, 44902, 123750, 127129, 44866, 45628, 31078, ...], [], [1]},
  {[1658, 1655, 26, 2019, 1637, 1649, 1655, ...], [446, 444, 34, 34, 444, 446, ...], [], [3]},
  {[365, 1438, 1069, 780, 1216, 1664, ...], [14332, 2892, 27071, 10003, 17863, ...], [14], []},
  {[7917, 64, 436, 297, 7982, ...], [70857, 70889, 70889, 70857, ...], [], [2]},
  {[7224, 12736, 21104, 27923, ...], [32323, 42255, 121795, ...], [5], []},
  {[203, 313, 1753, ...], [5527, 5527, ...], [], [...]},
  {[41, 73, ...], [685, ...], [], ...},
  {[116426, ...], [...], ...},
  {[...], ...},
  {...},
  ...
]

Part 1

Enum.map(mirrors, fn {_, _, row, col} ->
  List.first(col, 0) + List.first(row, 0) * 100
end)
|> Enum.sum()
40006

Part 2

defmodule Day13.Part2 do
  import Bitwise

  def alternatives(list, a, n) do
    l = length(list)

    list =
      for i <- 0..n,
          d = bsl(1, i),
          j <- 0..l,
          desmudged = List.update_at(list, j, &amp;bxor(&amp;1, d)),
          v <- Day13.find_axes(desmudged),
          v not in a,
          do: v

    Enum.dedup(list)
  end
end
{:module, Day13.Part2, <<70, 79, 82, 49, 0, 0, 11, ...>>, {:alternatives, 3}}
mirrors
|> Enum.with_index()
|> Enum.map(fn {{rows, cols, row, col}, _idx} ->
  row = List.first(Day13.Part2.alternatives(rows, row, length(cols)), 0)
  col = List.first(Day13.Part2.alternatives(cols, col, length(rows)), 0)

  row * 100 + col
end)
|> Enum.sum()
28627
Back