day16notes.txt

# Part 1

Ah, binary protocol decoding, nice!

Thinking of the primitives I'm going to need. Would a `get-bit` that
returns the next bit from the input be sufficient?

Or should I load an entire line's worth of data in a buffer, and then
carve sub-buffers from that?

Oh, the input contains a single line!

I'm going to assume that padding bits only occur at the end of the
outermost packet for now. The text hints at this:

> The three unlabeled 0 bits at the end are extra due to the hexadecimal
> representation and should be ignored.

I think I'm going to try with `get-bit`. How should it indicate the end of
input? Returning `ff` should be OK; in any case if all goes well we should
never request a bit past the end, I think. I'll just add a breakpoint there.

I wonder if literal values can be numbers longer than16 bits… Interestingly,
if there are longer numbers and my 16-bit storage overflows, it shouldn't
matter for part 1.

Note that my input is 1398 bytes long.

If there is indeed no extra padding inside packets, I should be able to
ignore type 0 length, right? Oh no, because I don't know how many packets
to parse inside.

On the other hand, part 1 only asks me to sum up version numbers, so I don't
actually need to respect the hierarchy. I'll go ahead and consider operator
packets done after their length, which should be equivalent.

Ah, but then I won't know when to stop reading, of course. Hmm, so I really
need a stack of open packets. Let's just recurse for now.

Done in 107 minutes, yay.

# Part 2

As expected, operators now have functions. This should be quite straightforward
to implement, the only wrinkle being how to separate sub-packet enumeration
(by length or by count) from the operation itself.

Oh, and hopefully we won't overflow. Let's just dump the hierarchy of my input
to see if I have to expect anything.

Versions can be completely skipped over for part 2.

Here's my complete tree:

  +              | 42188 + 27726 + …
   *             | 0
    <            | 0
     58459
     42678
    56547     
   *             | 0
    <            | 0
     +           | 36
      13
      15
      8
     +           | 18
      6
      9
      3
    24725
   *
    =
     1598
     1058
    36758
   *
    <
     +
      9
      15
      14
     +
      2
      15
      4
    110
   M
    88
   M
    26623
    58753
    130
   m
    31859
    30294
    15
    22255
    74
   *
    21
    111
    248
    120
   154
   M
    10
    9
    1319
    597
   +
    +
     +
      M
       +
        M
         m
          +
           M
            M
             m
              m
               *
                *
                 +
                  m
                   *
                    m
                     *
                      m
                       46691
   *
    172
    203
    201
   12
   *
    150
    4
    246
    156
    161
   *
    235
    66
   *
    >
     +
      14
      4
      5
     +
      8
      10
      14
    59423
   14
   *
    55319
    >
     25
     41065
   +
    119
    19890
    31921
    39323
    22863
   *
    30372
    >
     62287
     29811
   238
   +             | 27726
    27726
   6
   *
    >
     3888
     3888
    2783
   +
    *
     11
     5
     3
    *
     15
     8
     13
    *
     6
     12
     9
   *
    38
    <
     80
     15627
   M             | 42188
    42188
    1462
   m
    5337
   m
    13
    117
    2
   *
    17345
    =
     +
      13
      11
      8
     +
      2
      14
      6
   M             | 64111
    10838
    64111
    20723
    8
    12119
   40843
   191
   3
   m
    30
    3155
   +
    7
    33
   +
    55676
    50399
    75
    13987
   *
    1697
    <
     56166
     87
   *            | 0
    63239
    >           | 0
     30147
     45376
   +
    34387
    11
    4819
   *
    49
   259
   1917
   *
    57015
    >
     1798
     568
   *
    +
     15
     8
     4
    +
     5
     7
     14
    +
     10
     14
     7
   m
    220
    2504
    34369
    1363
   *
    >
     10391
     10391
    61360
   *
    47053
    <
     12326
     1
   *
    58973
    =
     96
     200
   *
    =
     36216
     36216
    5
   *
    57249
    >
     +
      11
      5
      12
     +
      10
      9
      6
   *
    <
     3132
     3132
    5043
   *
    158
    <
     16633
     16633

The largest literal is 64111, but it is used in a max operator, so it doesn't immediately overflow.
Likewise, the next largest is 63239, which is immediately multiplied by zero. It almost looks
as if the input has been constructed so that intermediate results would fit in 16 bits unsigned
integers… alas, at least the top-level sum overflows since it includes 42188 and 27726.

Looks like I'll have to implement a 64-bit integer stack.

"Your answer is too low"…

I just spent a few minutes reimplementing the evaluator in awk+dc to have confirmation:

 $ ./uxnrun.sh day16.tal  <(echo D8005AC2A8F0) |awk 'BEGIN { print "[f] sf [1+]
     so [0*] sz [1+]so [ sa sb 0 la lb <o ]s<  [ sa sb 0 la lb >o ]s> [ sa sb 0 la
     lb =o ]s= [ * ]s* [ + ]s+ [r]sr [ sa sb la lb la lb >r sZ ]sM [ sa sb la lb la
     lb <r sZ ]sm";} /\|/{printf "[%s\n]P\n", $0; op=substr($0,1,1); if(op=="#"){}
     else if(op!=" "){print "l" op "x";}else{print substr($0,1,22);}; print
     "f"}'|dc 2>&1

  Loaded day16.rom

                      5 | 5
  5
                     15 | 5 15
  15
  5
  <                     | 1
  1 

Running on my full input, `dc` gives the exact same (wrong) answer as my code. This is
frustrating.

But I just realized how stupid I've been earlier. "It almost looks as if the
input has been constructed so that intermediate results would fit in 16 bits
unsigned integers", indeed… of course if I truncate the integers as I read them,
it's no surprise that none will be above 65535!

This should be a relatively quick fix.

Here's the (hopefully) correct tree:

  +
   *
    <
     58459
     1025718
    56547
   *
    <
     +
      13
      15
      8
     +
      6
      9
      3
    24725
   *
    =
     1598
     1058
    9342870
   *
    <
     +
      9
      15
      14
     +
      2
      15
      4
    110
   M
    88
   M
    550911
    58753
    130
   m
    1184267379
    30294
    15
    22255
    74
   *
    21
    111
    248
    120
   154
   M
    10
    9
    1319
    597
   +
    +
     +
      M
       +
        M
         m
          +
           M
            M
             m
              m
               *
                *
                 +
                  m
                   *
                    m
                     *
                      m
                       46691
   *
    172
    203
    201
   12
   *
    150
    4
    246
    156
    161
   *
    235
    66
   *
    >
     +
      14
      4
      5
     +
      8
      10
      14
    2975066143
   14
   *
    62398191639
    >
     25
     237673
   +
    119
    19890
    13925553
    32725178779
    219471
   *
    882340
    >
     62287
     57243825267
   238
   +
    552014
   6
   *
    >
     3888
     3888
    2783
   +
    *
     11
     5
     3
    *
     15
     8
     13
    *
     6
     12
     9
   *
    38
    <
     80
     15627
   M
    1737543754956
    1462
   m
    5337
   m
    13
    117
    2
   *
    9782209
    =
     +
      13
      11
      8
     +
      2
      14
      6
   M
    207446
    2357871
    20723
    8
    36509658967
   43384020875
   191
   3
   m
    30
    3091795027
   +
    7
    33
   +
    150395260
    121095391
    75
    13987
   *
    1697
    <
     231267174
     87
   *
    158787303175
    >
     554435
     45376
   +
    523233691219
    11
    201427
   *
    49
   259
   1917
   *
    57015
    >
     246023942
     568
   *
    +
     15
     8
     4
    +
     5
     7
     14
    +
     10
     14
     7
   m
    220
    2504
    362049
    1363
   *
    >
     640297111
     640297111
    61360
   *
    102283213
    <
     12326
     1
   *
    58973
    =
     96
     200
   *
    =
     36216
     36216
    5
   *
    199221153
    >
     +
      11
      5
      12
     +
      10
      9
      6
   *
    <
     3132
     3132
    37819315
   *
    158
    <
     17013692973305
     17013692973305

Plenty of non-16-bit values here!

Running the computation again thankfully gives the right answer.