<!-- livebook:{"persist_outputs":true} -->

# Day 07

```elixir
Mix.install([:kino_aoc])
```

## Section

<!-- livebook:{"attrs":"eyJhc3NpZ25fdG8iOiJwdXp6bGVfaW5wdXQiLCJkYXkiOiI3Iiwic2Vzc2lvbl9zZWNyZXQiOiJBRFZFTlRfT0ZfQ09ERV9TRVNTSU9OIiwieWVhciI6IjIwMjQifQ","chunks":null,"kind":"Elixir.KinoAOC.HelperCell","livebook_object":"smart_cell"} -->

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

<!-- livebook:{"output":true} -->

```
{:ok,
 "644197722674: 5 9 46 99 1 5 9 2 22 6 74\n3424919: 67 51 7 561 358\n7160145: 9 9 7 4 8 3 91 2 3 3 5 731\n1133404163: 231 3 49 2 32 128 36\n198444: 9 77 90 347 308 46 3\n258135: 7 61 68 6 249 6\n10677865: 864 7 4 1 9 4 7 7 1 5 367\n1134: 54 7 3\n28760910: 1 6 627 9 752 831\n6740: 82 236 356 10\n983873830: 977 6 267 606 830\n101904: 5 71 29 2 264\n8536122: 5 3 7 388 120\n818217: 8 27 21 484 92 5 214\n9221: 219 23 270 18 5\n216699547: 2 24 46 9 1 55 6 61 9 88\n19040: 434 4 5 2 41 713 28 54\n113740483608: 52 951 38 417 23 17\n1837300: 627 46 5 1 91 6 6 4\n21564: 6 143 330 9 5 9\n100992468: 4 4 2 9 7 69 3 24 92 8 6 8\n522672: 5 226 7 5\n72660535: 181 857 70 5 2 4 1 11\n1553455: 57 842 4 650 374 79\n177565304: 177 5 6 530 7\n123464883: 65 67 315 7 2 45\n162378: 47 799 75 702 74 3\n75882558: 4 4 9 3 8 7 5 29 5 4 57 5\n15486: 5 771 6 1 2 2 8 8 8 8 2 4\n195018949: 237 9 76 61 19 95 4 9 9\n120067914: 12 7 1 282 9 17 7 2 7 79\n10625355: 6 16 906 3 533\n714034: 2 3 60 7 7 90 325 9\n147283595568: 3 311 33 3 57 822 8 93\n2316922: 8 26 41 831 2 94\n182954295: 438 22 56 5 993 4\n17143497694679: 73 169 33 1 4 71 6 79\n758512003463: 3 2 790 700 4 2 2 34 63\n4146569285: 280 8 9 5 6 7 68 4 9 1 2 5\n31770235539495: 589 8 9 1 1 95 3 63 492\n2140548: 7 6 1 4 3 4 8 929 1 3 8 12\n12113461: 291 3 50 772 17 5 2 2\n9197820380208: 1 58 583 110 58 207\n1539915: 88 340 19 5 689\n198635345304: 19 711 980 6 44 341\n43172: 426 8 4 318 1 1 439 3 5\n53202: 5 3 7 1 4 79 62 6 6\n999074: 1 4 221 5 9 71\n107010: 2 1 29 410 3\n1207: 8 600 5 9 567 17 1\n963: 56 902 7\n3661: 87 42 4 3\n55680: 8 7 2 58 8 4\n1443280: 1 33 16 68 39 592\n11791444132: 954 3 412 412 9\n40408: 8 8 513 70 19\n895: 45 9 784 52 8\n3630590257: 5 787 5 98 113 94 57\n1219939: 9 5 183 9 3\n7243377: 1 231 8 2 1 36 6 5 795 3\n10281688290: 728 359 69 874 8 45\n52129140: 78 1 7 407 547 5 2 4 5\n844925: 778 18 78 6 8\n1517768001: 56 213 629 27 17\n1586: 26 1 18 35 9\n897822305: 10 89 7 8 222 55 52\n307677984: 38 946 58 79 2\n11629377: 7 10 83 82 37 548 6 79\n5706366: 203 30 937 6 1 26\n545930: 1 8 696 5 770\n21436: 57 94 4 4 1\n601219587: 2 5 1 2 1 1 4 1 1 912 327\n1210568: 5 3 9 86 1 1 98 2 8 97 6 8\n163672: 311 939 4 1 130 522\n816: 3 9 7 9 5 25 84 186 56\n413330: 71 9 181 504 50\n275151204: 5 8 9 8 4 3 433 1 5 6 7 3\n5565: 47 19 8 7 1 276\n5528836: 1 552 789 9 936\n30771: 42 81 5 12 9\n113510: 99 58 723\n2552925934889: 802 8 795 54 8 372 4 6\n13201: 45 124 77 31 159\n720468: 17 6 92 4 7\n22380384159: 7 8 166 29 159 1 3 2 8 2\n45770: 4 41 765 2 3\n32957: 4 28 886 71\n5110126: 6 173 214 66 8\n1762745: 982 227 3 3 27 3 6 5\n130796643: 131 32 1 5 5 624\n78364255: 8 9 694 57 7 253\n844276: 8 42 224 792 1\n362023: 9 25 594 5 5 40 87 103\n1291399844: 5 6 1 9 39 1 73 9 6 44\n228417920: 25 37 71 9 26 794 8 4\n40050828: 3 27 763 6 9 9 5 1 9 12\n116627652: 7 4 7 1 446 8 4 5 2 4 75 6\n2516095717: 7 385 8 43 59 8 5 46\n655270872: 9 2 8 159 89 2 9 3 89 95\n35298709: 6 41 170 3 2 422 97\n558606: 4 6 5 74 6 53 7 7 100 1 5\n96911: 5 9 75 6 9 665 2 7 9 2 7 8\n429735: 7 72 58 6 9\n9402: 3 453 9 86 920 1 7 88 6\n2948456: 69 251 9 68 456\n254061: 603 70 2 6 789\n27948: 485 575 322 262 17\n90873: 58 49 8 27 31 31 725\n6444009: 5 6 195 7 6 33 13\n17255343: 78 867 42 3 85\n144630242: 490 2 39 11 7 4 39 86 1\n444869: 4 7 8 878 5 479\n253242155: 42 203 6 7 234 57\n1823338: 2 414 9 487 4 6\n25234118: 91 683 58 7 1\n642484013: 917 822 4 6 1 7 9 1 2\n10018629: 99 944 235 99 628\n52518012: 663 80 8 5 99\n52968775714: 217 3 8 2 3 2 9 6 9 9 94 6\n7014: 1 666 9 933 8 70\n1210591: 39 8 40 97 31\n61925382: 366 648 1 1 9 837 29\n1392623100: 92 3 6 6 8 18 8 815 990\n146952: 66 53 92 6 677 43\n16148106: 41 31 9 5 4 39\n972134: 4 36 905 3 28 9 75 54 3\n1699: 9 7 94 2\n38915712: 66 83 4 3 296 2 1\n24871732: 71 178 3 656 148\n1016303031: 229 634 7 499 532\n553520: 7 3 7 22 69\n588423590: 2 1 9 143 8 3 6 923 1 3 4\n8360806312: 1 3 9 850 24 7 857 5 7 5\n462718: 4 6 26 93 26\n21935424: 280 60 96 2 4 2 84\n885836: 8 850 4 5 2 27 704 58 9\n797703006: 1 3 1 8 9 4 9 495 3 7 60 6\n7714822: 2 4 757 959 3 25\n233319196: 881 27 45 10 4 979\n451620568437: 170 6 57 4 9 5 56 8 439\n2836062720: 7 88 111 9 6 6 2 4 3 8 3 2\n81217110: 827 98 9 501 2\n21081: 6 3 41 6 3 1 6 324 8 5 8\n861: 7 7 2 " <> ...}
```

```elixir
#puzzle_input =
  """
  190: 10 19
  3267: 81 40 27
  83: 17 5
  156: 15 6
  7290: 6 8 6 15
  161011: 16 10 13
  192: 17 8 14
  21037: 9 7 18 13
  292: 11 6 16 20
  """

equations =
  puzzle_input
  |> String.split("\n", trim: true)
  |> Enum.map(fn row ->
    {target, ": " <> rest} = Integer.parse(row)

    values =
      rest
      |> String.split()
      |> Enum.map(&String.to_integer/1)

    {target, values}
  end)
```

<!-- livebook:{"output":true} -->

```
warning: code block contains unused literal "190: 10 19\n3267: 81 40 27\n83: 17 5\n156: 15 6\n7290: 6 8 6 15\n161011: 16 10 13\n192: 17 8 14\n21037: 9 7 18 13\n292: 11 6 16 20\n" (remove the literal or assign it to _ to avoid warnings)
└─ Workspace/hauleth/advent-of-code/2024/day07.livemd#cell:7pxlqq2wa3oqdwfr:1

```

<!-- livebook:{"output":true} -->

```
[
  {644197722674, [5, 9, 46, 99, 1, 5, 9, 2, 22, 6, 74]},
  {3424919, [67, 51, 7, 561, 358]},
  {7160145, [9, 9, 7, 4, 8, 3, 91, 2, 3, 3, 5, 731]},
  {1133404163, [231, 3, 49, 2, 32, 128, 36]},
  {198444, [9, 77, 90, 347, 308, 46, 3]},
  {258135, [7, 61, 68, 6, 249, 6]},
  {10677865, [864, 7, 4, 1, 9, 4, 7, 7, 1, 5, 367]},
  {1134, [54, 7, 3]},
  {28760910, [1, 6, 627, 9, 752, 831]},
  {6740, [82, 236, 356, 10]},
  {983873830, [977, 6, 267, 606, 830]},
  {101904, [5, 71, 29, 2, 264]},
  {8536122, [5, 3, 7, 388, 120]},
  {818217, [8, 27, 21, 484, 92, 5, 214]},
  {9221, [219, 23, 270, 18, 5]},
  {216699547, [2, 24, 46, 9, 1, 55, 6, 61, 9, 88]},
  {19040, [434, 4, 5, 2, 41, 713, 28, 54]},
  {113740483608, [52, 951, 38, 417, 23, 17]},
  {1837300, [627, 46, 5, 1, 91, 6, 6, 4]},
  {21564, [6, 143, 330, 9, 5, 9]},
  {100992468, [4, 4, 2, 9, 7, 69, 3, 24, 92, 8, 6, 8]},
  {522672, [5, 226, 7, 5]},
  {72660535, [181, 857, 70, 5, 2, 4, 1, 11]},
  {1553455, [57, 842, 4, 650, 374, 79]},
  {177565304, [177, 5, 6, 530, 7]},
  {123464883, [65, 67, 315, 7, 2, 45]},
  {162378, [47, 799, 75, 702, 74, 3]},
  {75882558, [4, 4, 9, 3, 8, 7, 5, 29, 5, 4, 57, 5]},
  {15486, [5, 771, 6, 1, 2, 2, 8, 8, 8, 8, 2, 4]},
  {195018949, [237, 9, 76, 61, 19, 95, 4, 9, 9]},
  {120067914, [12, 7, 1, 282, 9, 17, 7, 2, 7, 79]},
  {10625355, [6, 16, 906, 3, 533]},
  {714034, [2, 3, 60, 7, 7, 90, 325, 9]},
  {147283595568, [3, 311, 33, 3, 57, 822, 8, 93]},
  {2316922, [8, 26, 41, 831, 2, 94]},
  {182954295, [438, 22, 56, 5, 993, 4]},
  {17143497694679, [73, 169, 33, 1, 4, 71, 6, 79]},
  {758512003463, [3, 2, 790, 700, 4, 2, 2, 34, 63]},
  {4146569285, [280, 8, 9, 5, 6, 7, 68, 4, 9, ...]},
  {31770235539495, [589, 8, 9, 1, 1, 95, 3, 63, ...]},
  {2140548, [7, 6, 1, 4, 3, 4, 8, ...]},
  {12113461, [291, 3, 50, 772, 17, 5, ...]},
  {9197820380208, [1, 58, 583, 110, 58, ...]},
  {1539915, [88, 340, 19, 5, ...]},
  {198635345304, [19, 711, 980, ...]},
  {43172, [426, 8, ...]},
  {53202, [5, ...]},
  {999074, [...]},
  {107010, ...},
  {...},
  ...
]
```

## Part 1

```elixir
defmodule Eq.P1 do
  def possible?(0, []), do: true
  def possible?(a, [a]), do: true
  def possible?(0, [_ | _]), do: false
  def possible?(_, []), do: false
  def possible?(a, _) when a < 0, do: false

  def possible?(a, [b | rest]) when rem(a, b) == 0 do
    possible?(div(a, b), rest) or possible?(a - b, rest)
  end

  def possible?(a, [b | rest]), do: possible?(a - b, rest)
end
```

<!-- livebook:{"output":true} -->

```
{:module, Eq.P1, <<70, 79, 82, 49, 0, 0, 8, ...>>, {:possible?, 2}}
```

```elixir
equations
|> Enum.filter(fn {target, vals} ->
  Eq.P1.possible?(target, Enum.reverse(vals))
end)
|> Enum.reduce(0, &(elem(&1, 0) + &2))
```

<!-- livebook:{"output":true} -->

```
3119088655389
```

## Part 2

```elixir
defmodule Eq.P2 do
  def possible?(a, [hd | rest]), do: possible?(a, hd, rest)

  defp possible?(a, a, []), do: true
  defp possible?(_, _, []), do: false
  defp possible?(a, b, _) when b > a, do: false

  defp possible?(target, curr, [a | rest]) do
    possible?(target, concat(curr, a), rest) or
      possible?(target, curr * a, rest) or
      possible?(target, curr + a, rest)
  end

  defp concat(a, b), do: a * l10(b) + b

  defp l10(n) when n >= 100, do: 1000
  defp l10(n) when n >= 10, do: 100
  defp l10(_), do: 10
end
```

<!-- livebook:{"output":true} -->

```
{:module, Eq.P2, <<70, 79, 82, 49, 0, 0, 9, ...>>, {:l10, 1}}
```

```elixir
equations
|> Task.async_stream(
  fn {target, vals} ->
    if Eq.P2.possible?(target, vals), do: target, else: 0
  end,
  ordered: false
)
|> Enum.reduce(0, fn {:ok, val}, acc -> val + acc end)
```

<!-- livebook:{"output":true} -->

```
264184041398847
```

<!-- livebook:{"offset":9317,"stamp":{"token":"XCP.DCDL30p1jz3L9vRDdQ5EJLc3r7y1DTsVhQ3GXFK_huvoEXqgYu2TTOfTq8AFYpt5W6fEIo4MvfrnHttbqS-z4SjRkT7WM09v09mZ_FeyqstWzLMCK_oNqhrrdwPPv5BG_8c","version":2}} -->