2021/day16.livemd at master · hauleth.dev/advent-of-code

this repo has no description
advent-of-code / 2021 / day16.livemd
at master 17 kB view raw
  1<!-- vim:set ft=markdown: -->
  2
  3<!-- livebook:{"persist_outputs":true} -->
  4
  5# Day 16
  6
  7## Section
  8
  9```elixir
 10defmodule Day16 do
 11  defmodule Packet do
 12    defstruct [:version, :type, :value]
 13  end
 14
 15  def decode(<<version::3, 4::3, rest::bitstring>>) do
 16    {value, rest} = literal(rest, 0)
 17
 18    {%Packet{type: 4, version: version, value: value}, rest}
 19  end
 20
 21  def decode(<<version::3, type::3, 0::1, length::15, rest::bitstring>>) do
 22    <<subpackets::bitstring-size(length), rest::bitstring>> = rest
 23
 24    {%Packet{type: type, version: version, value: decode_all(subpackets)}, rest}
 25  end
 26
 27  def decode(<<version::3, type::3, 1::1, length::11, rest::bitstring>>) do
 28    {value, rest} = Enum.map_reduce(1..length, rest, fn _, acc -> decode(acc) end)
 29
 30    {%Packet{type: type, version: version, value: value}, rest}
 31  end
 32
 33  def decode_all(input) do
 34    case decode(input) do
 35      {packet, <<>>} -> [packet]
 36      {packet, rest} -> [packet | decode_all(rest)]
 37    end
 38  end
 39
 40  defp literal(<<1::1, bits::4, rest::bitstring>>, acc) do
 41    literal(rest, acc * 0x10 + bits)
 42  end
 43
 44  defp literal(<<0::1, bits::4, rest::bitstring>>, acc) do
 45    {acc * 0x10 + bits, rest}
 46  end
 47end
 48
 49input =
 50  File.read!("day16.txt")
 51  |> String.trim()
 52  |> Base.decode16!()
 53  |> Day16.decode()
 54  |> elem(0)
 55```
 56
 57```output
 58%Day16.Packet{
 59  type: 0,
 60  value: [
 61    %Day16.Packet{
 62      type: 1,
 63      value: [
 64        %Day16.Packet{type: 4, value: 20, version: 6},
 65        %Day16.Packet{
 66          type: 6,
 67          value: [
 68            %Day16.Packet{type: 4, value: 14747, version: 1},
 69            %Day16.Packet{type: 4, value: 14747, version: 6}
 70          ],
 71          version: 2
 72        }
 73      ],
 74      version: 1
 75    },
 76    %Day16.Packet{
 77      type: 3,
 78      value: [
 79        %Day16.Packet{type: 4, value: 15, version: 5},
 80        %Day16.Packet{type: 4, value: 10, version: 6}
 81      ],
 82      version: 7
 83    },
 84    %Day16.Packet{
 85      type: 1,
 86      value: [
 87        %Day16.Packet{
 88          type: 7,
 89          value: [
 90            %Day16.Packet{type: 4, value: 2184, version: 1},
 91            %Day16.Packet{type: 4, value: 130250, version: 6}
 92          ],
 93          version: 6
 94        },
 95        %Day16.Packet{type: 4, value: 5442981, version: 4}
 96      ],
 97      version: 6
 98    },
 99    %Day16.Packet{type: 4, value: 8281083, version: 0},
100    %Day16.Packet{
101      type: 2,
102      value: [
103        %Day16.Packet{type: 4, value: 102, version: 5},
104        %Day16.Packet{type: 4, value: 647125, version: 7}
105      ],
106      version: 1
107    },
108    %Day16.Packet{
109      type: 1,
110      value: [
111        %Day16.Packet{type: 4, value: 178, version: 1},
112        %Day16.Packet{type: 4, value: 176, version: 6}
113      ],
114      version: 0
115    },
116    %Day16.Packet{
117      type: 1,
118      value: [
119        %Day16.Packet{
120          type: 6,
121          value: [
122            %Day16.Packet{
123              type: 0,
124              value: [
125                %Day16.Packet{type: 4, value: 13, version: 1},
126                %Day16.Packet{type: 4, value: 8, version: 4},
127                %Day16.Packet{type: 4, value: 4, version: 3}
128              ],
129              version: 2
130            },
131            %Day16.Packet{
132              type: 0,
133              value: [
134                %Day16.Packet{type: 4, value: 7, version: 7},
135                %Day16.Packet{type: 4, value: 11, version: 3},
136                %Day16.Packet{type: 4, value: 14, version: 2}
137              ],
138              version: 4
139            }
140          ],
141          version: 7
142        },
143        %Day16.Packet{type: 4, value: 2724, version: 0}
144      ],
145      version: 1
146    },
147    %Day16.Packet{type: 4, value: 9, version: 4},
148    %Day16.Packet{
149      type: 1,
150      value: [
151        %Day16.Packet{
152          type: 5,
153          value: [
154            %Day16.Packet{type: 4, value: 7240238, version: 2},
155            %Day16.Packet{type: 4, value: 233, version: 7}
156          ],
157          version: 1
158        },
159        %Day16.Packet{type: 4, value: 37, version: 6}
160      ],
161      version: 4
162    },
163    %Day16.Packet{type: 2, value: [%Day16.Packet{type: 4, value: 2, version: 5}], version: 5},
164    %Day16.Packet{type: 4, value: 53749, version: 4},
165    %Day16.Packet{type: 4, value: 11, version: 3},
166    %Day16.Packet{
167      type: 1,
168      value: [
169        %Day16.Packet{type: 4, value: 382979, version: 4},
170        %Day16.Packet{
171          type: 5,
172          value: [
173            %Day16.Packet{
174              type: 0,
175              value: [
176                %Day16.Packet{type: 4, value: 15, version: 1},
177                %Day16.Packet{type: 4, value: 10, version: 0},
178                %Day16.Packet{type: 4, value: 2, version: 6}
179              ],
180              version: 5
181            },
182            %Day16.Packet{
183              type: 0,
184              value: [
185                %Day16.Packet{type: 4, value: 4, version: 7},
186                %Day16.Packet{type: 4, value: 7, version: 4},
187                %Day16.Packet{type: 4, value: 2, version: 5}
188              ],
189              version: 1
190            }
191          ],
192          version: 6
193        }
194      ],
195      version: 2
196    },
197    %Day16.Packet{type: 4, value: 21251, version: 1},
198    %Day16.Packet{
199      type: 1,
200      value: [
201        %Day16.Packet{type: 4, value: 163, version: 6},
202        %Day16.Packet{
203          type: 5,
204          value: [
205            %Day16.Packet{type: 4, value: 59, version: 3},
206            %Day16.Packet{type: 4, value: 836848134220, version: 1}
207          ],
208          version: 6
209        }
210      ],
211      version: 2
212    },
213    %Day16.Packet{
214      type: 2,
215      value: [
216        %Day16.Packet{
217          type: 0,
218          value: [
219            %Day16.Packet{
220              type: 0,
221              value: [
222                %Day16.Packet{
223                  type: 2,
224                  value: [
225                    %Day16.Packet{
226                      type: 2,
227                      value: [
228                        %Day16.Packet{
229                          type: 0,
230                          value: [
231                            %Day16.Packet{
232                              type: 3,
233                              value: [
234                                %Day16.Packet{
235                                  type: 2,
236                                  value: [
237                                    %Day16.Packet{
238                                      type: 2,
239                                      value: [
240                                        %Day16.Packet{
241                                          type: 3,
242                                          value: [%Day16.Packet{type: 0, value: [...], ...}],
243                                          version: 0
244                                        }
245                                      ],
246                                      version: 1
247                                    }
248                                  ],
249                                  version: 1
250                                }
251                              ],
252                              version: 7
253                            }
254                          ],
255                          version: 0
256                        }
257                      ],
258                      version: 6
259                    }
260                  ],
261                  version: 2
262                }
263              ],
264              version: 2
265            }
266          ],
267          version: 6
268        }
269      ],
270      version: 7
271    },
272    %Day16.Packet{type: 1, value: [%Day16.Packet{type: 4, value: 44, version: 4}], version: 7},
273    %Day16.Packet{
274      type: 1,
275      value: [
276        %Day16.Packet{type: 4, value: 255, version: 2},
277        %Day16.Packet{type: 4, value: 91, version: 5},
278        %Day16.Packet{type: 4, value: 176, version: 5},
279        %Day16.Packet{type: 4, value: 23, version: 1}
280      ],
281      version: 7
282    },
283    %Day16.Packet{
284      type: 3,
285      value: [
286        %Day16.Packet{type: 4, value: 11520, version: 4},
287        %Day16.Packet{type: 4, value: 6069, version: 0},
288        %Day16.Packet{type: 4, value: 1089149511401, version: 4},
289        %Day16.Packet{type: 4, value: 158, version: 2},
290        %Day16.Packet{type: 4, value: 620605, version: 0}
291      ],
292      version: 2
293    },
294    %Day16.Packet{
295      type: 0,
296      value: [
297        %Day16.Packet{type: 4, value: 62788, version: 7},
298        %Day16.Packet{type: 4, value: 9410622, version: 2},
299        %Day16.Packet{type: 4, value: 15912821, version: 4}
300      ],
301      version: 4
302    },
303    %Day16.Packet{
304      type: 1,
305      value: [
306        %Day16.Packet{type: 4, value: 22416, version: 5},
307        %Day16.Packet{
308          type: 5,
309          value: [
310            %Day16.Packet{type: 4, value: 246, version: 1},
311            %Day16.Packet{type: 4, value: 246, version: 4}
312          ],
313          version: 2
314        }
315      ],
316      version: 0
317    },
318    %Day16.Packet{type: 3, value: [%Day16.Packet{type: 4, value: 13008601, version: 5}], version: 0},
319    %Day16.Packet{
320      type: 0,
321      value: [
322        %Day16.Packet{
323          type: 1,
324          value: [
325            %Day16.Packet{type: 4, value: 3, version: 4},
326            %Day16.Packet{type: 4, value: 14, version: 1},
327            %Day16.Packet{type: 4, value: 5, version: 0}
328          ],
329          version: 5
330        },
331        %Day16.Packet{
332          type: 1,
333          value: [
334            %Day16.Packet{type: 4, value: 2, version: 1},
335            %Day16.Packet{type: 4, value: 14, version: 1},
336            %Day16.Packet{type: 4, value: 10, version: 1}
337          ],
338          version: 6
339        },
340        %Day16.Packet{
341          type: 1,
342          value: [
343            %Day16.Packet{type: 4, value: 8, version: 3},
344            %Day16.Packet{type: 4, value: 6, version: 6},
345            %Day16.Packet{type: 4, value: 11, version: 0}
346          ],
347          version: 1
348        }
349      ],
350      version: 5
351    },
352    %Day16.Packet{
353      type: 1,
354      value: [
355        %Day16.Packet{type: 4, value: 32940592237, version: 2},
356        %Day16.Packet{
357          type: 5,
358          value: [
359            %Day16.Packet{type: 4, value: 100, version: 1},
360            %Day16.Packet{type: 4, value: 1393232728, version: 2}
361          ],
362          version: 2
363        }
364      ],
365      version: 0
366    },
367    %Day16.Packet{type: 4, value: 89, version: 3},
368    %Day16.Packet{
369      type: 2,
370      value: [
371        %Day16.Packet{type: 4, value: 204, version: 6},
372        %Day16.Packet{type: 4, value: 260321821, version: 2},
373        %Day16.Packet{type: 4, value: 225241983, version: 6}
374      ],
375      version: 0
376    },
377    %Day16.Packet{
378      type: 0,
379      value: [
380        %Day16.Packet{type: 4, value: 960899, version: 3},
381        %Day16.Packet{type: 4, value: 58997, version: 5},
382        %Day16.Packet{type: 4, value: 54940, version: 6},
383        %Day16.Packet{type: 4, value: 10974, version: 2},
384        %Day16.Packet{type: 4, value: 882043, version: 2}
385      ],
386      version: 0
387    },
388    %Day16.Packet{
389      type: 1,
390      value: [
391        %Day16.Packet{
392          type: 6,
393          value: [
394            %Day16.Packet{type: 4, value: 35633017255, version: 4},
395            %Day16.Packet{type: 4, value: 35633017255, version: 2}
396          ],
397          version: 3
398        },
399        %Day16.Packet{type: 4, value: 1359, version: 6}
400      ],
401      version: 6
402    },
403    %Day16.Packet{
404      type: 1,
405      value: [
406        %Day16.Packet{type: 4, value: 92, version: 4},
407        %Day16.Packet{type: 4, value: 38, version: 3},
408        %Day16.Packet{type: 4, value: 160, version: 5},
409        %Day16.Packet{type: 4, value: 111, version: 1},
410        %Day16.Packet{type: 4, value: 64, version: 4}
411      ],
412      version: 4
413    },
414    %Day16.Packet{
415      type: 0,
416      value: [
417        %Day16.Packet{type: 4, value: 2541, version: 3},
418        %Day16.Packet{type: 4, value: 263947, version: 6},
419        %Day16.Packet{type: 4, value: 7686705, version: 5},
420        %Day16.Packet{type: 4, value: 31, version: 4}
421      ],
422      version: 2
423    },
424    %Day16.Packet{
425      type: 1,
426      value: [
427        %Day16.Packet{
428          type: 6,
429          value: [
430            %Day16.Packet{type: 4, value: 3193865, version: 1},
431            %Day16.Packet{type: 4, value: 20223, version: 7}
432          ],
433          version: 2
434        },
435        %Day16.Packet{type: 4, value: 9328522, version: 5}
436      ],
437      version: 0
438    },
439    %Day16.Packet{
440      type: 2,
441      value: [
442        %Day16.Packet{type: 4, value: 5, version: 4},
443        %Day16.Packet{type: 4, value: 7, version: 3},
444        %Day16.Packet{type: 4, value: 179420284, version: 4},
445        %Day16.Packet{type: 4, value: 19890, version: 1},
446        %Day16.Packet{type: 4, value: 2655, version: 0}
447      ],
448      version: 7
449    },
450    %Day16.Packet{
451      type: 1,
452      value: [
453        %Day16.Packet{type: 4, value: 862089, version: 1},
454        %Day16.Packet{
455          type: 6,
456          value: [
457            %Day16.Packet{type: 4, value: 248, version: 3},
458            %Day16.Packet{type: 4, value: 3286, version: 5}
459          ],
460          version: 3
461        }
462      ],
463      version: 3
464    },
465    %Day16.Packet{
466      type: 1,
467      value: [
468        %Day16.Packet{type: 4, value: 93, version: 6},
469        %Day16.Packet{
470          type: 5,
471          value: [
472            %Day16.Packet{type: 4, value: 4269, version: 6},
473            %Day16.Packet{type: 4, value: 240, version: 3}
474          ],
475          version: 4
476        }
477      ],
478      version: 5
479    },
480    %Day16.Packet{
481      type: 3,
482      value: [
483        %Day16.Packet{type: 4, value: 2938, version: 6},
484        %Day16.Packet{type: 4, value: 3, version: 6},
485        %Day16.Packet{type: 4, value: 211, version: 7}
486      ],
487      version: 3
488    },
489    %Day16.Packet{
490      type: 1,
491      value: [
492        %Day16.Packet{
493          type: 7,
494          value: [
495            %Day16.Packet{type: 4, value: 159, version: 0},
496            %Day16.Packet{type: 4, value: 159, version: 5}
497          ],
498          version: 0
499        },
500        %Day16.Packet{type: 4, value: 28, version: 1}
501      ],
502      version: 4
503    },
504    %Day16.Packet{type: 4, value: 84, version: 4},
505    %Day16.Packet{
506      type: 1,
507      value: [
508        %Day16.Packet{type: 4, value: 235, version: 4},
509        %Day16.Packet{
510          type: 6,
511          value: [
512            %Day16.Packet{type: 0, value: [%Day16.Packet{...}, ...], version: 4},
513            %Day16.Packet{type: 0, value: [...], ...}
514          ],
515          version: 3
516        }
517      ],
518      version: 6
519    },
520    %Day16.Packet{type: 4, value: 1425, version: 4},
521    %Day16.Packet{
522      type: 1,
523      value: [
524        %Day16.Packet{
525          type: 7,
526          value: [%Day16.Packet{type: 0, value: [...], ...}, %Day16.Packet{type: 0, ...}],
527          version: 5
528        },
529        %Day16.Packet{type: 4, value: 13, version: 2}
530      ],
531      version: 2
532    },
533    %Day16.Packet{type: 0, value: [%Day16.Packet{type: 4, value: 3121, version: 6}], version: 5},
534    %Day16.Packet{
535      type: 1,
536      value: [
537        %Day16.Packet{type: 4, value: 51, version: 2},
538        %Day16.Packet{type: 4, value: 61, ...},
539        %Day16.Packet{type: 4, ...}
540      ],
541      version: 4
542    },
543    %Day16.Packet{
544      type: 1,
545      value: [%Day16.Packet{type: 4, value: 1393, ...}, %Day16.Packet{type: 5, ...}],
546      version: 3
547    },
548    %Day16.Packet{type: 1, value: [%Day16.Packet{type: 7, ...}, %Day16.Packet{...}], version: 3},
549    %Day16.Packet{type: 1, value: [%Day16.Packet{...}, ...], version: 7},
550    %Day16.Packet{type: 3, value: [...], ...},
551    %Day16.Packet{type: 2, ...},
552    %Day16.Packet{...},
553    ...
554  ],
555  version: 3
556}
557```
558
559## Task 1
560
561```elixir
562defmodule Day16.Task1 do
563  alias Day16.Packet
564
565  def sum(%Packet{type: 4, version: version}), do: version
566
567  def sum(%Packet{version: version, value: value}) do
568    Enum.reduce(value, version, &(sum(&1) + &2))
569  end
570end
571
572Day16.Task1.sum(input)
573```
574
575```output
576949
577```
578
579## Task 2
580
581```elixir
582defmodule Day16.Task2 do
583  alias Day16.Packet
584
585  def evaluate(%Packet{type: 0} = packet), do: reduce(packet, 0, &+/2)
586  def evaluate(%Packet{type: 1} = packet), do: reduce(packet, 1, &*/2)
587  def evaluate(%Packet{type: 2} = packet), do: reduce(packet, :inf, &min/2)
588  def evaluate(%Packet{type: 3} = packet), do: reduce(packet, 0, &max/2)
589
590  def evaluate(%Packet{type: 4, value: value}), do: value
591
592  def evaluate(%Packet{type: 5} = packet), do: compare(packet, &>/2)
593  def evaluate(%Packet{type: 6} = packet), do: compare(packet, &</2)
594  def evaluate(%Packet{type: 7} = packet), do: compare(packet, &==/2)
595
596  defp reduce(%Packet{value: value}, initial, op) do
597    Enum.reduce(value, initial, &op.(evaluate(&1), &2))
598  end
599
600  defp compare(%Packet{value: [a, b]}, op) do
601    if op.(evaluate(a), evaluate(b)), do: 1, else: 0
602  end
603end
604
605Day16.Task2.evaluate(input)
606```
607
608```output
6091114600142730
610```