Day 22

2024/day22.livemd

Łukasz Jan Niemier

@hauleth

advent-of-code

More notebooks

Day 22

Mix.install([:kino_aoc])

Section

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

{:ok,
 "4832674\n14802956\n7210529\n7709095\n6063251\n12294789\n15666951\n12074106\n15427686\n1214891\n15165649\n3609602\n10200989\n16451437\n10915511\n3479515\n173864\n1238342\n3381843\n14767788\n16088065\n15637051\n15981887\n15854806\n4988920\n7980791\n11263142\n8044640\n4572291\n328777\n11851557\n13706949\n16451719\n15991644\n14668984\n8852039\n1685443\n13814197\n14117797\n6281998\n12395020\n1681090\n16476099\n2171296\n10155667\n15490827\n6723206\n7272972\n1788575\n2950054\n10917267\n6862495\n8153949\n16559239\n8572595\n1821668\n3417901\n11375457\n3878450\n10863466\n10890116\n13055126\n7451580\n5815531\n8335506\n431487\n201975\n5841753\n11744013\n4498615\n9261071\n9953929\n4630027\n2227105\n6260342\n10375281\n3015284\n3789175\n15843612\n14432075\n14847622\n11501912\n9079366\n2550341\n6931972\n13371306\n9601571\n14504463\n6162939\n5361897\n14900517\n12748562\n7519640\n14694035\n5566950\n7688680\n13810532\n5654369\n10957671\n6886767\n13114128\n9355299\n14808826\n11001280\n4983663\n9915373\n3356476\n16519750\n15826279\n11122172\n12902904\n1010762\n16214923\n9519057\n15931832\n15664252\n12750269\n1110882\n7854151\n3509827\n10328167\n1494530\n8712493\n396534\n15995697\n7396815\n3419574\n14789278\n14099072\n15389372\n6910648\n649063\n3609071\n6004556\n5054128\n13730203\n3554012\n2766085\n7133343\n7566747\n1194302\n10446649\n1529903\n9036124\n11725198\n6479244\n10287711\n2219155\n2360315\n8169407\n7841353\n7486466\n15297309\n9336789\n7225072\n6248515\n16154198\n11100038\n8584563\n3753173\n7371112\n2481160\n10954049\n8009781\n7381801\n280810\n11001420\n14114713\n4242475\n1237360\n6496866\n15267044\n1880781\n8798544\n5033766\n5079684\n11633848\n16509688\n8226900\n15858455\n16041151\n5334220\n15421957\n2633967\n8343560\n14729378\n9702409\n5482505\n2041087\n9712582\n3430735\n10644043\n9195957\n1784419\n14046333\n2031279\n12766582\n12165573\n14207224\n14929506\n11436548\n13623882\n12370036\n7592923\n228169\n8988171\n6688080\n5492092\n8212636\n3736928\n15352784\n2612376\n14843761\n12308540\n8404032\n11632730\n4404470\n2599992\n6807809\n12044159\n9795957\n5307557\n13144362\n13941181\n9362743\n4957570\n9950852\n4069207\n699043\n13667685\n12869414\n5834836\n8434557\n13512362\n5446646\n16663243\n10059682\n231185\n14405863\n10532295\n13752653\n3266523\n12926376\n9013886\n15683001\n10524950\n325867\n15226063\n15175724\n15991383\n13961546\n15823957\n9310375\n5534565\n2674761\n13444598\n9915920\n1755544\n1429896\n14788650\n5453166\n10081466\n2149840\n16613385\n2519989\n7555351\n7295534\n12099546\n3223009\n2684428\n8436395\n5406395\n836225\n9962036\n2847179\n12880336\n13215841\n3498334\n5985622\n7700379\n5785351\n9938722\n15810882\n2349820\n906893\n2513825\n10432278\n13789913\n2913486\n9683268\n2862417\n4807276\n16264545\n6607564\n10222512\n2190055\n11839341\n2132714\n153996\n10874457\n12023939\n7748310\n13452955\n3246986\n2892967\n9561561\n3280827\n991231\n13105708\n16641479\n273523\n4832864\n13832855\n7903624\n13242917\n13379831\n9085055\n1473661\n11031255\n4126827\n12754058\n456062\n14316218\n6580848\n11147440\n1828704\n15262845\n557484\n2406569\n10393027\n3363996\n15821838\n16365523\n5566374\n3723957\n5186897\n501767\n10639559\n3256585\n2354615\n1888438\n11574106\n11798800\n12629659\n6316600\n3119025\n14801938\n7025953\n14949782\n7577552\n14785389\n8868837\n11642113\n14574465\n8689963\n16223594\n14705685\n16363438\n1393194\n5961465\n16603208\n8121071\n15143692\n7531645\n6777163\n8168251\n15905711\n2373414\n1269213\n2506356\n1080789\n2154403\n11578189\n6232867\n10065427\n15116084\n15449140\n12675436\n14126594\n8470014\n2106625\n12556109\n12771090\n1437370\n16145074\n6244539\n6832665\n13217078\n5152936\n15205635\n12092447\n15115231\n2112929\n13215959\n11124896\n14598714\n15256810\n9994507\n11687859\n11599901\n5330801\n13829820\n1720133\n11040068\n4351948\n9597919\n10673331\n6148104\n12360792\n9687192\n11668420\n10272257\n7823976\n6113203\n8827921\n5600165\n6950138\n9581746\n15917691\n6453798\n11788226\n15057269\n9639028\n5073513\n15459362\n14118507\n7979569\n4210224\n5726357\n10649449\n14645020\n3062620\n14613306\n13963982\n14770179\n15097265\n1789308\n12405157\n7360698\n6983540\n9752726\n8200080\n5784060\n13456865\n4677699\n3783161\n13650051\n9865655\n13066800\n1868022\n5855823\n15061710\n11742417\n2116233\n15002417\n904747\n9455335\n5203086\n704685\n902384\n15284593\n8328120\n13587250\n11550241\n10950646\n14876694\n11393724\n14576237\n898540\n8874901\n5548732\n11351523\n2315166\n9532824\n11462685\n1297628\n3862586\n16331382\n9291789\n2887008\n2582973\n4861709\n15301133\n8978897\n533818\n1565155\n3829639\n8438476\n11901529" <> ...}

inits =
  puzzle_input
  |> String.split("\n", trim: true)
  |> Enum.map(&amp;String.to_integer/1)

[4832674, 14802956, 7210529, 7709095, 6063251, 12294789, 15666951, 12074106, 15427686, 1214891,
 15165649, 3609602, 10200989, 16451437, 10915511, 3479515, 173864, 1238342, 3381843, 14767788,
 16088065, 15637051, 15981887, 15854806, 4988920, 7980791, 11263142, 8044640, 4572291, 328777,
 11851557, 13706949, 16451719, 15991644, 14668984, 8852039, 1685443, 13814197, 14117797, 6281998,
 12395020, 1681090, 16476099, 2171296, 10155667, 15490827, 6723206, 7272972, 1788575, 2950054, ...]

defmodule Buyer do
  def hash(number, rounds \\ 2000) do
    Enum.map_reduce(1..rounds//1, number, fn _, acc ->
      r = do_round(acc)
      {rem(r, 10), r}
    end)
  end

  defp do_round(num) do
    num = subround(num, num * 64)
    num = subround(num, div(num, 32))
    subround(num, num * 2048)
  end

  defp subround(a, b), do: rem(Bitwise.bxor(a, b), 16_777_216)

  def sequences(prices) do
    prices
    |> Enum.chunk_every(5, 1, :discard)
    |> Enum.reduce(%{}, fn seq, map ->
      Map.put_new(map, diffs(seq), List.last(seq))
    end)
  end

  defp diffs(vals) do
    vals
    |> Enum.chunk_every(2, 1, :discard)
    |> Enum.map(fn [a, b] -> b - a end)
    |> Integer.undigits(256)
  end
end

{:module, Buyer, <<70, 79, 82, 49, 0, 0, 13, ...>>, {:diffs, 1}}

hashes = Enum.map(inits, &amp;Buyer.hash(&amp;1))

[
  {[5, 9, 7, 9, 4, 6, 2, 9, 4, 3, 6, 5, 0, 6, 5, 7, 2, 7, 9, 7, 0, 2, 5, 8, 8, 2, 0, 8, 4, 8, 3, 1,
    4, 3, 3, 8, 0, 5, 2, 1, 2, 8, 6, 2, 2, 3, 6, 9, ...], 8186085},
  {[8, 6, 8, 8, 3, 4, 6, 9, 0, 1, 1, 5, 4, 9, 5, 4, 1, 2, 5, 2, 6, 7, 8, 7, 5, 4, 4, 2, 5, 6, 4, 6,
    2, 4, 5, 9, 5, 8, 5, 0, 6, 9, 3, 2, 3, 4, 4, ...], 16060909},
  {[6, 0, 5, 8, 8, 7, 3, 6, 0, 9, 1, 0, 7, 2, 7, 5, 6, 4, 0, 5, 4, 0, 1, 9, 6, 5, 7, 1, 7, 9, 9, 9,
    5, 6, 0, 7, 3, 0, 9, 4, 8, 4, 0, 2, 2, 7, ...], 3581487},
  {[6, 3, 1, 0, 2, 6, 8, 9, 1, 6, 7, 4, 5, 0, 9, 9, 8, 9, 1, 0, 6, 4, 9, 0, 1, 0, 9, 3, 0, 0, 9, 1,
    9, 6, 6, 7, 2, 1, 7, 2, 7, 3, 2, 7, 3, ...], 14331752},
  {[3, 5, 1, 7, 1, 4, 6, 0, 4, 9, 8, 3, 7, 3, 3, 2, 2, 9, 1, 3, 3, 4, 9, 2, 3, 2, 5, 6, 9, 4, 3, 8,
    1, 6, 7, 3, 8, 8, 7, 5, 3, 3, 2, 3, ...], 11096256},
  {[9, 5, 4, 8, 1, 3, 9, 8, 2, 6, 7, 9, 0, 8, 6, 3, 4, 8, 7, 0, 0, 2, 2, 7, 2, 2, 0, 9, 7, 4, 9, 5,
    7, 1, 3, 1, 7, 9, 3, 3, 6, 2, 4, ...], 8119288},
  {[3, 0, 8, 6, 0, 0, 3, 4, 2, 0, 0, 8, 7, 6, 3, 7, 5, 2, 4, 8, 4, 4, 5, 4, 8, 9, 2, 1, 6, 8, 3, 9,
    2, 8, 0, 5, 0, 9, 7, 2, 5, 9, ...], 4175670},
  {[9, 6, 3, 2, 9, 6, 8, 1, 7, 8, 0, 7, 2, 2, 0, 8, 6, 5, 5, 3, 9, 6, 5, 7, 1, 4, 6, 7, 9, 7, 2, 4,
    6, 2, 0, 2, 9, 7, 8, 0, 9, ...], 9128738},
  {[5, 8, 5, 2, 2, 9, 4, 4, 8, 8, 9, 9, 8, 3, 4, 9, 2, 2, 9, 1, 2, 2, 0, 8, 1, 2, 3, 4, 0, 4, 6, 4,
    3, 6, 8, 1, 9, 6, 1, 5, ...], 13899897},
  {[0, 9, 4, 3, 5, 9, 1, 2, 1, 1, 8, 1, 8, 8, 3, 8, 4, 4, 3, 7, 7, 2, 9, 8, 5, 8, 8, 4, 4, 8, 4, 0,
    5, 9, 7, 0, 3, 3, 6, ...], 12087848},
  {[5, 6, 7, 3, 2, 0, 5, 4, 8, 8, 2, 6, 8, 4, 9, 7, 2, 0, 9, 3, 4, 1, 3, 0, 6, 5, 2, 6, 4, 6, 9, 4,
    3, 9, 9, 9, 7, 2, ...], 11514818},
  {[0, 9, 7, 9, 2, 6, 4, 9, 7, 0, 3, 1, 6, 4, 3, 2, 0, 2, 8, 4, 7, 6, 7, 7, 1, 1, 5, 2, 6, 6, 1, 4,
    9, 5, 6, 9, 3, ...], 4150418},
  {[5, 5, 0, 8, 5, 6, 2, 7, 0, 5, 4, 2, 1, 0, 5, 6, 6, 3, 6, 2, 4, 3, 9, 4, 3, 0, 8, 0, 6, 7, 1, 8,
    0, 2, 7, 1, ...], 2679493},
  {[4, 0, 8, 1, 5, 9, 0, 3, 6, 0, 2, 8, 5, 7, 1, 1, 9, 1, 5, 1, 5, 0, 7, 3, 5, 5, 4, 3, 9, 4, 3, 9,
    6, 9, 6, ...], 84072},
  {[0, 5, 2, 6, 6, 4, 1, 2, 5, 2, 3, 8, 4, 1, 2, 4, 7, 5, 2, 7, 7, 0, 8, 0, 6, 0, 6, 3, 4, 3, 7, 0,
    5, 8, ...], 3938870},
  {[5, 5, 5, 5, 6, 0, 6, 9, 2, 0, 0, 5, 3, 0, 3, 3, 0, 7, 7, 0, 1, 5, 8, 8, 6, 5, 3, 3, 2, 5, 8, 8,
    8, ...], 15186439},
  {[5, 1, 6, 4, 5, 2, 2, 2, 0, 9, 6, 3, 2, 1, 5, 6, 2, 6, 0, 4, 2, 8, 9, 2, 8, 7, 8, 7, 9, 2, 5, 1,
    ...], 4224277},
  {[8, 7, 6, 6, 8, 0, 1, 8, 9, 1, 7, 5, 0, 6, 4, 4, 9, 2, 1, 6, 1, 5, 4, 1, 9, 9, 9, 4, 7, 3, 0,
    ...], 6637814},
  {[7, 4, 4, 8, 3, 9, 5, 6, 1, 1, 7, 4, 7, 2, 5, 3, 8, 5, 3, 4, 7, 7, 0, 0, 4, 1, 7, 1, 4, 5, ...],
   15335578},
  {[1, 3, 9, 5, 1, 4, 9, 6, 9, 0, 6, 7, 7, 5, 4, 8, 8, 4, 4, 0, 3, 0, 0, 2, 8, 8, 8, 7, 5, ...],
   14808063},
  {[3, 8, 6, 7, 8, 8, 1, 5, 4, 2, 3, 3, 6, 0, 4, 4, 6, 3, 6, 3, 5, 3, 3, 7, 4, 7, 1, 8, ...],
   2236221},
  {[4, 2, 4, 3, 0, 3, 6, 2, 7, 9, 6, 6, 9, 3, 2, 0, 1, 8, 1, 5, 7, 7, 3, 8, 8, 1, 9, ...], 9777274},
  {[8, 5, 1, 6, 9, 9, 1, 6, 3, 9, 9, 4, 5, 9, 4, 2, 8, 5, 7, 9, 2, 1, 6, 9, 0, 9, ...], 14777742},
  {[4, 6, 0, 4, 6, 3, 2, 3, 8, 0, 2, 3, 2, 2, 0, 7, 7, 4, 5, 8, 8, 2, 8, 9, 4, ...], 3528684},
  {[3, 6, 3, 3, 3, 2, 5, 2, 8, 8, 8, 0, 3, 1, 2, 2, 6, 2, 3, 1, 2, 6, 1, 9, ...], 15225220},
  {[2, 1, 2, 4, 0, 6, 0, 8, 6, 5, 9, 5, 1, 7, 1, 3, 9, 3, 2, 8, 5, 4, 8, ...], 4484251},
  {[1, 5, 9, 2, 0, 5, 7, 4, 6, 2, 3, 4, 7, 9, 9, 7, 9, 8, 3, 4, 2, 3, ...], 12505941},
  {[3, 2, 8, 0, 7, 6, 7, 8, 6, 2, 0, 4, 7, 6, 2, 8, 2, 7, 3, 0, 3, ...], 12324709},
  {[3, 6, 3, 2, 2, 5, 4, 5, 3, 2, 2, 8, 5, 8, 7, 6, 5, 9, 3, 0, ...], 12840916},
  {[7, 4, 1, 3, 5, 7, 1, 9, 4, 8, 2, 0, 2, 6, 7, 1, 7, 8, 4, ...], 13939301},
  {[0, 4, 4, 4, 6, 9, 8, 0, 2, 3, 9, 9, 4, 0, 6, 0, 4, 2, ...], 7392065},
  {[7, 8, 0, 0, 4, 1, 6, 1, 5, 9, 0, 3, 1, 4, 5, 8, 9, ...], 13395486},
  {[5, 5, 1, 7, 9, 8, 0, 1, 5, 5, 6, 2, 1, 6, 6, 5, ...], 14846825},
  {[4, 1, 5, 9, 7, 1, 3, 6, 6, 5, 8, 9, 1, 0, 7, ...], 15647415},
  {[5, 0, 0, 5, 4, 4, 9, 3, 4, 0, 4, 9, 0, 0, ...], 15491670},
  {[5, 3, 1, 3, 6, 7, 3, 2, 8, 6, 2, 5, 0, ...], 12602693},
  {[9, 6, 3, 2, 6, 3, 9, 6, 6, 5, 2, 6, ...], 16470307},
  {[8, 4, 3, 6, 0, 4, 0, 8, 5, 5, 9, ...], 10819101},
  {[0, 9, 4, 4, 6, 0, 2, 4, 0, 3, ...], 8658998},
  {[0, 2, 8, 3, 0, 4, 5, 0, 5, ...], 11616760},
  {[4, 8, 3, 5, 2, 8, 0, 8, ...], 4294043},
  {[8, 1, 0, 8, 2, 1, 0, ...], 11210309},
  {[5, 8, 6, 9, 6, 8, ...], 1113711},
  {[1, 6, 5, 5, 4, ...], 16530315},
  {[5, 1, 3, 9, ...], 8014000},
  {[7, 4, 5, ...], 13932057},
  {[8, 9, ...], 9987703},
  {[4, ...], 10745797},
  {[...], ...},
  {...},
  ...
]

Part 1

hashes
|> Enum.map(&amp;elem(&amp;1, 1))
|> Enum.sum()

13461553007

Part 2

hashes
|> Task.async_stream(
  fn {prices, _} -> Buyer.sequences(prices) end,
  ordered: false
)
|> Enum.reduce(%{}, fn {:ok, a}, b -> Map.merge(a, b, fn _k, v, k -> v + k end) end)
|> Enum.max_by(&amp;elem(&amp;1, 1))
|> elem(1)

Back