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         if (*f->buf == '\0')
  17                 f->buf = hex2bin[getchar()];
  18         int r = *(f->buf++) == '1' ? 1 : 0;
  19         f->pos++;
  20         return r;
  21 }
  22
  23 unsigned long bin2int(struct stream *f, int n)
  24 {
  25         unsigned long r = 0;
  26         for (int i = 0; i<n; i++)
  27                 r = 2*r+next(f);
  28         return r;
  29 }
  30
  31 unsigned long parse_packet(struct stream *f)
  32 {
  33         int packetversion  __attribute__((unused)) = bin2int(f, 3);
  34         int packettype = bin2int(f, 3);
  35         unsigned long r = 0;
  36
  37         //literal
  38         if (packettype == 4) {
  39                 while (next(f) == 1)
  40                         r = r*16+bin2int(f, 4);
  41                 r = r*16+bin2int(f, 4);
  42         //operator
  43         } else {
  44                 int lengthtypeid = next(f);
  45                 unsigned long packets[100] = {0};
  46                 int npackets = 0;
  47
  48                 //number of bits
  49                 if (lengthtypeid == 0) {
  50                         int lengthsubpackets = bin2int(f, 15);
  51                         int oldpos = f->pos;
  52                         while (f->pos - oldpos < lengthsubpackets)
  53                                 packets[npackets++] = parse_packet(f);
  54                 //number of packets
  55                 } else {
  56                         npackets = bin2int(f, 11);
  57                         for (int i = 0; i<npackets; i++)
  58                                 packets[i] = parse_packet(f);
  59                 }
  60
  61                 if (packettype == 0) {        //sum
  62                         for (int i = 0; i<npackets; i++)
  63                                 r += packets[i];
  64                 } else if (packettype == 1) { //product
  65                         r = 1;
  66                         for (int i = 0; i<npackets; i++)
  67                                 r *= packets[i];
  68                 } else if (packettype == 2) { //minimum
  69                         r = ULONG_MAX;
  70                         for (int i = 0; i<npackets; i++)
  71                                 r = packets[i] < r ? packets[i] : r;
  72                 } else if (packettype == 3) { //maximum
  73                         for (int i = 0; i<npackets; i++)
  74                                 r = packets[i] > r ? packets[i] : r;
  75                 } else if (packettype == 5) { //greater than
  76                         r = packets[0] > packets[1];
  77                 } else if (packettype == 6) { //less than
  78                         r = packets[0] < packets[1];
  79                 } else if (packettype == 7) { //equal to
  80                         r = packets[0] == packets[1];
  81                 }
  82         }
  83         return r;
  84 }
  85
  86 int main()
  87 {
  88         struct stream f = {.pos=0, .buf=""};
  89         printf("%lu\n", parse_packet(&f));
  90 }