advent-of-code-2021-12-16.js

console.clear();

const DAY = 16;
const DEBUG = false;
const INPUT_URL = `https://adventofcode.com/2021/day/${DAY}/input`;

const testInput = `A0016C880162017C3686B18A3D4780`.trim();

const tests = {
  literal: () => {
    const parser = new Parser("D2FE28");
    const tree = parser.parse();

    console.assert(tree.version === 6, "expected version to be 6");
    console.assert(tree.typeId === 4, "expected typeId to be 4");
    console.assert(tree.data === 2021, "expected data to be 2021");
  },

  "operator / lengthType 0 / bit length": () => {
    const parser = new Parser("38006F45291200");
    const tree = parser.parse();

    console.assert(Array.isArray(tree.data));
    console.assert(tree.data.length === 2);
    console.assert(tree.data[0].version === 6);
    console.assert(tree.data[1].data === 20);
  },

  "operator / lengthType 1": () => {
    const parser = new Parser("EE00D40C823060");
    const tree = parser.parse();

    // too lazy to write assertions
  },

  "version sums": () => {
    const testCases = {
      "8A004A801A8002F478": 16,
      "620080001611562C8802118E34": 12,
      C0015000016115A2E0802F182340: 23,
      A0016C880162017C3686B18A3D4780: 31,
    };

    for (let [hexString, expectedSum] of Object.entries(testCases)) {
      const parser = new Parser(hexString);
      const tree = parser.parse();

      console.assert(
        sumVersions(tree) === expectedSum,
        'expected sum for hex "%s" to be "%s"',
        hexString,
        expectedSum
      );
    }
  },

  "operator evaluation": () => {
    const testCases = {
      C200B40A82: 3,
      "04005AC33890": 54,
      "880086C3E88112": 7,
      CE00C43D881120: 9,
      D8005AC2A8F0: 1,
      F600BC2D8F: 0,
      "9C005AC2F8F0": 0,
      "9C0141080250320F1802104A08": 1,
    };

    for (let [hexString, expectedResult] of Object.entries(testCases)) {
      const parser = new Parser(hexString);
      const tree = parser.parse();
      const actualResult = evaluate(tree);

      console.assert(
        actualResult === expectedResult,
        'expected result for hex "%s" to be %s (actual: %s)',
        hexString,
        expectedResult,
        actualResult
      );
    }
  },
};

function run(input) {
  const parser = new Parser(input);
  const tree = parser.parse();

  return {
    part1: sumVersions(tree),
    part2: evaluate(tree),
  };
}

function sumVersions(node) {
  if (!Array.isArray(node.data)) {
    return node.version;
  }

  return (
    node.version + node.data.reduce((sum, node) => sum + sumVersions(node), 0)
  );
}

function evaluate(node) {
  switch (node.typeId) {
    case 4:
      return node.data;

    case 0: // add
      return node.data.reduce((sum, node) => sum + evaluate(node), 0);

    case 1: // multiply
      return node.data.reduce((product, node) => product * evaluate(node), 1);

    case 2: // min
      return Math.min(...node.data.map(evaluate));

    case 3: // max
      return Math.max(...node.data.map(evaluate));

    case 5: // greater than
      console.assert(node.data.length === 2);
      return evaluate(node.data[0]) > evaluate(node.data[1]) ? 1 : 0;

    case 6: // less than
      console.assert(node.data.length === 2);
      return evaluate(node.data[0]) < evaluate(node.data[1]) ? 1 : 0;

    case 7: // equals
      console.assert(node.data.length === 2);
      return evaluate(node.data[0]) === evaluate(node.data[1]) ? 1 : 0;
  }

  throw new Error("unknown typeId: " + node.typeId);
}

class Parser {
  constructor(hexString) {
    this.reader = new BitStreamReader(Parser.hexStringToUint8Array(hexString));
  }

  parse() {
    const startOffset = this.reader.bitOffset;
    const version = this.reader.read(3);
    const typeId = this.reader.read(3);

    let data;
    if (typeId === 4) {
      data = this.parseLiteralValue();
    } else {
      data = this.parseOperator();
    }

    return {
      version,
      typeId,
      data,
      startOffset: startOffset,
      length: this.reader.bitOffset - startOffset,
    };
  }

  parseLiteralValue() {
    let res = 0;
    let lastHalfbyte;
    do {
      lastHalfbyte = !this.reader.read(1);
      // bitwise math only works with int32 numbers,
      // since there are larger numbers we need to use
      // the float64 default number type and replace bitwise ops
      // with regular arithmetic

      // res = res << 4 | this.reader.read(4);
      res = res * 16 + this.reader.read(4);
    } while (!lastHalfbyte);

    return res;
  }

  parseOperator() {
    const lengthTypeId = this.reader.read(1);
    let ret = [];
    if (lengthTypeId === 0) {
      const expectedLengthBits = this.reader.read(15);
      let bitsRead = 0;
      while (bitsRead < expectedLengthBits) {
        const packet = this.parse();
        bitsRead += packet.length;
        ret.push(packet);
      }
    } else {
      const numPackets = this.reader.read(11);
      for (let i = 0; i < numPackets; i++) {
        ret.push(this.parse());
      }
    }

    return ret;
  }

  static hexStringToUint8Array(hexString) {
    const bytes = new Uint8Array(Math.ceil(hexString.length / 2));

    for (let i = 0; i < hexString.length; i += 2) {
      bytes[i / 2] = Number(`0x${hexString.slice(i, i + 2).padEnd(2, "0")}`);
    }

    return bytes;
  }
}

class BitStreamReader {
  constructor(bytes) {
    this.bytes = bytes;
    this.bitOffset = 0;
  }

  readBit(bitOffset) {
    const b = this.bytes[Math.floor(bitOffset / 8)];

    return (b >> (7 - (bitOffset % 8))) & 1;
  }

  read(n) {
    let res = 0;

    for (let i = 0; i < n; i++) {
      const b = this.readBit(this.bitOffset + i);
      res |= b << (n - 1 - i);
    }
    this.bitOffset += n;

    return res;
  }
}

async function main() {
  console.group("tests");
  for (let [key, test] of Object.entries(tests)) {
    console.group("running test: " + key);
    test();
    console.groupEnd("running test: " + key);
  }
  console.groupEnd("tests");

  const input = DEBUG
    ? testInput
    : (await (await fetch(INPUT_URL)).text()).trim();

  const { part1, part2 } = run(input);
  logResult(1, part1);
  logResult(2, part2);
}

function logResult(part, result) {
  console.log(
    "%cpart %s result: %c%s",
    "font-size: 3em; font-weight: bold; color: #7a7",
    part,
    "font-size: 3em; font-weight: bold; color: #8f8",
    result
  );
}

main();