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 result = 0;
  42
  43         //literal
  44         if (packettype == 4) {
  45                 while (next(f) == 1)
  46                         result = result*16+bin2int(f, 4);
  47                 result = result*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                 //sum
  68                 if (packettype == 0) {
  69                         for (int i = 0; i<npackets; i++)
  70                                 result += packets[i];
  71                 //product
  72                 } else if (packettype == 1) {
  73                         result = 1;
  74                         for (int i = 0; i<npackets; i++)
  75                                 result *= packets[i];
  76                 //minimum
  77                 } else if (packettype == 2) {
  78                         result = ULONG_MAX;
  79                         for (int i = 0; i<npackets; i++)
  80                                 result = packets[i] < result ? packets[i] : result;
  81                 //maximum
  82                 } else if (packettype == 3) {
  83                         result = 0;
  84                         for (int i = 0; i<npackets; i++)
  85                                 result = packets[i] > result ? packets[i] : result;
  86                 //greater than
  87                 } else if (packettype == 5) {
  88                         result = packets[0] > packets[1];
  89                 //less than
  90                 } else if (packettype == 6) {
  91                         result = packets[0] < packets[1];
  92                 //equal to
  93                 } else if (packettype == 7) {
  94                         result = packets[0] == packets[1];
  95                 //unknown
  96                 } else {
  97                         fprintf(stderr, "unknown operator: %d\n", packettype);
  98                         exit(1);
  99                 }
 100         }
 101         return result;
 102 }
 103
 104 int main()
 105 {
 106         struct stream f = {.pos=0, .buf=""};
 107         printf("r: %lu\n", parse_packet(&f));
 108 }