AoC 2021 day 16

#include <Arduino.h>
#include "types.h"

#define ADD 0
#define MULTIPLY 1
#define MIN 2
#define MAX 3
#define LITERAL 4
#define GREATER 5
#define LESS 6
#define EQUAL 7

long checksum = 0;
char operators[8][3] = {"+ ", "* ", "mn", "mx", "L ", "> ", "< ", "=="};

bool debugExp = false;
int printExp(char *c)
{
  return debugExp && Serial.priant(c);
}

bool debugTree = false;
int printTree(char *c, int indent, char *op)
{
  if (debugTree)
  {
    for (int i = 0; i < indent - 1; i++)
      Serial.print("|  ");
    Serial.print(op);
    Serial.print(".");
    Serial.println(c);
    return 1;
  }
  return 0;
}

// const char data[] PROGMEM = {"020D78804D397973DB5B934D9280CC9F43080286957D9F60923592619D3230047C0109763976295356007365B37539ADE687F333EA8469200B666F5DC84E80232FC2C91B8490041332EB4006C4759775933530052C0119FAA7CB6ED57B9BBFBDC153004B0024299B490E537AFE3DA069EC507800370980F96F924A4F1E0495F691259198031C95AEF587B85B254F49C27AA2640082490F4B0F9802B2CFDA0094D5FB5D626E32B16D300565398DC6AFF600A080371BA12C1900042A37C398490F67BDDB131802928F5A009080351DA1FC441006A3C46C82020084FC1BE07CEA298029A008CCF08E5ED4689FD73BAA4510C009981C20056E2E4FAACA36000A10600D45A8750CC8010989716A299002171E634439200B47001009C749C7591BD7D0431002A4A73029866200F1277D7D8570043123A976AD72FFBD9CC80501A00AE677F5A43D8DB54D5FDECB7C8DEB0C77F8683005FC0109FCE7C89252E72693370545007A29C5B832E017CFF3E6B262126E7298FA1CC4A072E0054F5FBECC06671FE7D2C802359B56A0040245924585400F40313580B9B10031C00A500354009100300081D50028C00C1002C005BA300204008200FB50033F70028001FE60053A7E93957E1D09940209B7195A56BCC75AE7F18D46E273882402CCD006A600084C1D8ED0E8401D8A90BE12CCF2F4C4ADA602013BC401B8C11360880021B1361E4511007609C7B8CA8002DC32200F3AC01698EE2FF8A2C95B42F2DBAEB48A401BC5802737F8460C537F8460CF3D953100625C5A7D766E9CB7A39D8820082F29A9C9C244D6529C589F8C693EA5CD0218043382126492AD732924022CE006AE200DC248471D00010986D17A3547F200CA340149EDC4F67B71399BAEF2A64024B78028200FC778311CC40188AF0DA194CF743CC014E4D5A5AFBB4A4F30C9AC435004E662BB3EF0"};
const char bitArray[] PROGMEM = {"000000100000110101111000100000000100110100111001011110010111001111011011010110111001001101001101100100101000000011001100100111110100001100001000000000101000011010010101011111011001111101100000100100100011010110010010011000011001110100110010001100000000010001111100000000010000100101110110001110010111011000101001010100110101011000000000011100110110010110110011011101010011100110101101111001101000011111110011001100111110101010000100011010010010000000001011011001100110111101011101110010000100111010000000001000110010111111000010110010010001101110000100100100000000010000010011001100101110101101000000000001101100010001110101100101110111010110010011001101010011000000000101001011000000000100011001111110101010011111001011011011101101010101111011100110111011111110111101110000010101001100000000010010110000000000100100001010011001101101001001000011100101001101111010111111100011110110100000011010011110110001010000011110000000000000110111000010011000000011111001011011111001001001001010010011110001111000000100100101011111011010010001001001011001000110011000000000110001110010010101101011101111010110000111101110000101101100100101010011110100100111000010011110101010001001100100000000001000001001001001000011110100101100001111100110000000001010110010110011111101101000000000100101001101010111111011010111010110001001101110001100101011000101101101001100000000010101100101001110011000110111000110101011111111011000000000101000001000000000110111000110111010000100101100000110010000000000000100001010100011011111000011100110000100100100001111011001111011110111011011000100110001100000000010100100101000111101011010000000001001000010000000001101010001110110100001111111000100010000010000000001101010001111000100011011001000001000000010000000001000010011111100000110111110000001111100111010100010100110000000001010011010000000001000110011001111000010001110010111101101010001101000100111111101011100111011101010100100010100010000110000000000100110011000000111000010000000000101011011100010111001001111101010101100101000110110000000000000101000010000011000000000110101000101101010000111010100001100110010000000000100001001100010010111000101101010001010011001000000000010000101110001111001100011010001000011100100100000000010110100011100000000000100000000100111000111010010011100011101011001000110111101011111010000010000110001000000000010101001001010011100110000001010011000011001100010000000001111000100100111011111010111110110000101011100000000010000110001001000111010100101110110101011010111001011111111101111011001110011001000000001010000000110100000000010101110011001110111111101011010010000111101100011011011010101001101010111111101111011001011011111001000110111101011000011000111011111111000011010000011000000000101111111000000000100001001111111001110011111001000100100100101001011100111001001101001001100110111000001010100010100000000011110100010100111000101101110000011001011100000000101111100111111110011111001101011001001100010000100100110111001110010100110001111101000011100110001001010000001110010111000000000010101001111010111111011111011001100000001100110011100011111111001111101001011001000000000100011010110011011010101101010000000000100000000100100010110010010010001011000010101000000000011110100000000110001001101011000000010111001101100010000000000110001110000000000101001010000000000110101010000000000100100010000000000110000000000001000000111010101000000000010100011000000000011000001000000000010110000000000010110111010001100000000001000000100000000001000001000000000111110110101000000000011001111110111000000000010100000000000000111111110011000000000010100111010011111101001001110010101011111100001110100001001100101000000001000001001101101110001100101011010010101101011110011000111010110101110011111110001100011010100011011100010011100111000100000100100000000101100110011010000000001101010011000000000000010000100110000011101100011101101000011101000010000000001110110001010100100001011111000010010110011001111001011110100110001001010110110100110000000100000000100111011110001000000000110111000110000010001001101100000100010000000000000100001101100010011011000011110010001010001000100000000011101100000100111000111101110001100101010000000000000101101110000110010001000000000111100111010110000000001011010011000111011100010111111111000101000101100100101011011010000101111001011011011101011101011010010001010010000000001101111000101100000000010011100110111111110000100011000001100010100110111111110000100011000001100111100111101100101010011000100000000011000100101110001011010011111010111011001101110100111001011011110100011100111011000100000100000000010000010111100101001101010011100100111000010010001001101011001010010100111000101100010011111100011000110100100111110101001011100110100000010000110000000010000110011100000100001001001100100100100101010110101110011001010010010010000000010001011001110000000000110101011100010000000001101110000100100100001000111000111010000000000000001000010011000011011010001011110100011010101000111111100100000000011001010001101000000000101001001111011011100010011110110011110110111000100111001100110111010111011110010101001100100000000100100101101111000000000101000001000000000111111000111011110000011000100011100110001000000000110001000101011110000110110100001100101001100111101110100001111001100000000010100111001001101010110100101101011111011101101001010010011110011000011001001101011000100001101010000000001001110011001100010101110110011111011110000"};

//  const char bitArray[] PROGMEM = {"1100001000000000101101000000101010000010"};
//  char bitArray[((sizeof data / sizeof data[1])) *4] = {'\0'};
//  const char binary[16][5] = {"0000", "0001", "0010", "0011", "0100", "0101","0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110","1111"};
//  const String digits = "0123456789ABCDEF";

char *LL2Char(long long input)
{
  if (input == 0)
    return "0\0";

  static char result[21] = "";
  memset(&result[0], 0, sizeof(result));

  char temp[21] = "";
  char c;
  uint8_t base = 10;
  while (input)
  {
    int num = input % base;
    input /= base;
    c = '0' + num;

    sprintf(temp, "%c%s", c, result);
    strcpy(result, temp);
  }
  // strcat(result, "LL");
  return result;
}

long long char2LL(char *str, int size)
{
  long long result = 0LL;
  int bit = 0;

  for (int i = size - 1; i >= 0; i--)
    result += (long long)(str[i] - '0') << bit++;

  return result;
}

int char2Int(char *c)
{
  return strtol(c, NULL, 2);
}

long long processNumber(long long &value, long long v, int id, bool print = false)
{
  switch (id)
  {
  case ADD:
    print &&printExp(" + ");
    value += v;
    break;
  case MULTIPLY:
    print &&printExp(" * ");
    value *= v;
    break;
  case MIN:
    print &&printExp(", ");
    if (value == 0)
      value = INFINITY;
    value = min(value, v);
    break;
  case MAX:
    print &&printExp(", ");
    value = max(value, v);
    break;
  default:
    Serial.println(F("UNKNOWN OPERATOR ID"));
    break;
  }
}

packet partseData(int pointer, int indent, int print = 0);
packet partseData(int pointer, int indent, int print = 0)
{
  packet pack;

  indent++;
  int p = pointer;

  char version[4] = {'\0'};
  char id[4] = {'\0'};
  strncpy_P(version, bitArray + p, 3);
  strncpy_P(id, bitArray + p + 3, 3);
  p += 6;

  int idType = char2Int(id);
  checksum += char2Int(version);

  if (idType == LITERAL)
  {
    char val[64] = {"\0"};
    char num[5] = {"\0"};
    char closeBit[1] = "1";
    int size = 0;

    while (closeBit[0] == '1')
    {
      strncpy_P(closeBit, bitArray + p, 1);
      strncpy_P(num, bitArray + p + 1, 4);
      strcat(val, num);
      p += 5;
      size += 4;
    }
    pack.value = char2LL(val, size);

    if (print < 4)
      printExp(LL2Char(pack.value));
  }
  else
  {
    char lengthType[2]{'\0'};
    strncpy_P(lengthType, bitArray + p, 1);
    p++;
    int valueIndex = 0;

    long long values[2];
    long long value = 0LL;

    if (idType == MIN)
      printExp("min");
    if (idType == MAX)
      printExp("max");
    printExp("(");

    if (lengthType[0] == '0')
    {
      char subPacketsLength[16] = {"\0s"};
      memcpy_P(subPacketsLength, bitArray + p, 15);
      long subL = char2Int(subPacketsLength);
      p += 15;
      int end = p + subL;
      int round = 0;
      while (p < end)
      {
        round++;
        packet pck = partseData(p, indent, end > 2 ? 0:idType);
        p = pck.index;

        if (idType < 4)
        {
          if (round == 1 && idType == 1)
            value = 1;
          processNumber(value, pck.value, idType, p < end);
        }
        else
          values[valueIndex++] = pck.value;

        pack.value = value;
        if (p < end)
        {
          idType == 5 && printExp(" > ");
          idType == 6 && printExp(" < ");
          idType == 7 && printExp(" == ");
        }
      }
    }
    else if (lengthType[0] == '1')
    {
      char numSubPackets[12] = {"\0s"};
      memcpy_P(numSubPackets, bitArray + p, 11);
      long num = char2Int(numSubPackets);
      p += 11;
      for (size_t i = 0; i < num; i++)
      {
        packet pck = partseData(p, indent, num == 2 ? 0:idType);
        p = pck.index;

        if (idType < LITERAL)
        {
          if (i == 0 && idType == MULTIPLY)
            value = 1;
          processNumber(value, pck.value, idType, i < num - 1);
        }
        else
          values[valueIndex++] = pck.value;

        if (i < num - 1)
        {
          idType == 5 && printExp(" > ");
          idType == 6 && printExp(" < ");
          idType == 7 && printExp(" == ");
        }
        pack.value = value;
      }
    }

    if (idType == GREATER && values[0] > values[1])
      pack.value = 1LL;
    if (idType == LESS && values[0] < values[1])
      pack.value = 1LL;
    if (idType == EQUAL && values[0] == values[1])
      pack.value = 1LL;

    printExp(")");
  }

  pack.index = p;

  printTree(LL2Char(pack.value), indent, operators[idType]);

  return pack;
}

void setup()
{
  Serial.begin(9600);
  while (!Serial)
    ;

  Serial.println("START");
  long time = millis();
  // for (size_t i = 0; i < sizeof data / sizeof data[0]; i++)
  // {
  //    strcat(bitArray,binary[digits.indexOf( pgm_read_byte(data + i))]);
  // }
  //  Serial.println( bitArray );
  packet p = partseData(0, 0, true);
  debugExp && Serial.println();

  Serial.println("-----------------");
  Serial.println(checksum);
  Serial.println(LL2Char(p.value));
  Serial.println();
  Serial.println(millis() - time);
}

void loop()
{
}