16b.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <limits.h>
   4
   5 char *hex2bin[] =
   6         { ['0'] = "0000", ['1'] = "0001", ['2'] = "0010", ['3'] = "0011"
   7         , ['4'] = "0100", ['5'] = "0101", ['6'] = "0110", ['7'] = "0111"
   8         , ['8'] = "1000", ['9'] = "1001", ['A'] = "1010", ['B'] = "1011"
   9         , ['C'] = "1100", ['D'] = "1101", ['E'] = "1110", ['F'] = "1111"
  10         , ['\n'] = "0000"};
  11
  12 struct stream { int pos; char *buf; };
  13
  14 int next(struct stream *f)
  15 {
  16         int r;
  17         if (*f->buf == '\0')
  18                 f->buf = hex2bin[r];
  19         r =*(f->buf++) == '1' ? 1 : 0;
  20         f->pos++;
  21         return r;
  22 }
  23
  24 unsigned long bin2int(struct stream *f, int n)
  25 {
  26         unsigned long r = 0;
  27         for (int i = 0; i<n; i++)
  28                 r = 2*r+next(f);
  29         return r;
  30 }
  31
  32 unsigned long parse_packet(struct stream *f)
  33 {
  34         int packetversion  __attribute__((unused)) = bin2int(f, 3);
  35         int packettype = bin2int(f, 3);
  36         unsigned long r = 0;
  37
  38         //literal
  39         if (packettype == 4) {
  40                 while (next(f) == 1)
  41                         r = r*16+bin2int(f, 4);
  42                 r = r*16+bin2int(f, 4);
  43         //operator
  44         } else {
  45                 int lengthtypeid = next(f);
  46                 unsigned long packets[100] = {0};
  47                 int npackets = 0;
  48
  49                 //number of bits
  50                 if (lengthtypeid == 0) {
  51                         int lengthsubpackets = bin2int(f, 15);
  52                         int oldpos = f->pos;
  53                         while (f->pos - oldpos < lengthsubpackets)
  54                                 packets[npackets++] = parse_packet(f);
  55                 //number of packets
  56                 } else {
  57                         npackets = bin2int(f, 11);
  58                         for (int i = 0; i<npackets; i++)
  59                                 packets[i] = parse_packet(f);
  60                 }
  61
  62                 if (packettype == 0) {        //sum
  63                         for (int i = 0; i<npackets; i++)
  64                                 r += packets[i];
  65                 } else if (packettype == 1) { //product
  66                         r = 1;
  67                         for (int i = 0; i<npackets; i++)
  68                                 r *= packets[i];
  69                 } else if (packettype == 2) { //minimum
  70                         r = ULONG_MAX;
  71                         for (int i = 0; i<npackets; i++)
  72                                 r = packets[i] < r ? packets[i] : r;
  73                 } else if (packettype == 3) { //maximum
  74                         for (int i = 0; i<npackets; i++)
  75                                 r = packets[i] > r ? packets[i] : r;
  76                 } else if (packettype == 5) { //greater than
  77                         r = packets[0] > packets[1];
  78                 } else if (packettype == 6) { //less than
  79                         r = packets[0] < packets[1];
  80                 } else if (packettype == 7) { //equal to
  81                         r = packets[0] == packets[1];
  82                 }
  83         }
  84         return r;
  85 }
  86
  87 int main()
  88 {
  89         struct stream f = {.pos=0, .buf=""};
  90         printf("%lu\n", parse_packet(&f));
  91 }