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