advent-code-2021-day-16.js

function toDec(num) {
  return parseInt(num, 2);
}

/**
 *
 * @param {string} input
 * @returns {[number, number]}
 */
function read(input, start, length) {
  let next = start + length;
  return [toDec(input.substring(start, next)), next];
}

function run(original) {
  const parsers = {
    v: (input, index) => {
      const [num, next] = read(input, index, 3);
      return [num, next];
    },
    t: (input, index) => {
      const [num, next] = read(input, index, 3);
      return [num, next];
    },
    // parse next packet
    packet: (input, index) => {
      let next = index;
      let packet = null;

      if (
        input.length > next + 6 &&
        Array.from(input.substring(next)).some((c) => c !== "0")
      ) {
        let val = null;
        let v = null;
        let t = null;
        [v, next] = parsers.v(input, next);
        [t, next] = parsers.t(input, next);

        // next packet is a literal
        if (t === 4) {
          [val, next] = parsers.literalBody(input, next);
        } else {
          // next packet is a operator
          [val, next] = parsers.operatorBody(input, next);
        }
        packet = {
          v,
          t,
          val,
        };
      } else {
        next = input.length;
      }
      return [packet, next];
    },
    packets: (input, index = 0, max = Number.MAX_SAFE_INTEGER) => {
      let packets = [];
      let next = index;
      while (next < input.length && max > 0) {
        max--;
        let packet = null;
        [packet, next] = parsers.packet(input, next);
        if (packet) {
          packets.push(packet);
        } else {
          break;
        }
      }
      return [packets, next];
    },
    // Heading is skipped
    literalBody: (input, index) => {
      let res = "";
      let next = index;
      while (true) {
        let curr = next;
        next += 5;
        res += input.substring(curr + 1, next);
        if (input[curr] === "0") {
          break;
        }
      }
      return [toDec(res), next];
    },
    operatorBody: (input, index) => {
      let next = index;
      let is15 = input[next++] === "0";
      if (is15) {
        let length;
        [length, next] = read(input, next, 15);
        let substring = input.substring(next, next + length);
        [packets] = parsers.packets(substring);
        return [packets, next + length];
      } else {
        let num;
        [num, next] = read(input, next, 11);
        [packets, next] = parsers.packets(input, next, num);
        return [packets, next];
      }
    },
  };
  return parsers.packets(original);
}

function walk(root, cb) {
  if (Array.isArray(root)) {
    root.forEach((item) => walk(item, cb));
  } else {
    cb(root);
    if (root.val) {
      walk(root.val, cb);
    }
  }
}

// run("110100101111111000101000");
// run("00111000000000000110111101000101001010010001001000000000");
// run("11101110000000001101010000001100100000100011000001100000");

const util = require("util");

function fromHex(input) {
  return Array.from(input).reduce(
    (acc, curr) => acc + parseInt(curr, 16).toString(2).padStart(4, 0),
    ""
  );
}
function sum(input) {
  const [tree] = run(fromHex(input))[0];
  console.log(tree);

  function step(node) {
    if (node.t === 0) {
      return node.val.reduce((acc, curr) => acc + step(curr), 0);
    }
    if (node.t === 1) {
      return node.val.reduce((acc, curr) => acc * step(curr), 1);
    }
    if (node.t === 2) {
      return node.val.reduce(
        (acc, curr) => Math.min(acc, step(curr)),
        Number.MAX_SAFE_INTEGER
      );
    }
    if (node.t === 3) {
      return node.val.reduce((acc, curr) => Math.max(acc, step(curr)), 0);
    }

    if (node.t === 4) {
      return node.val;
    }

    if (node.t === 5) {
      return step(node.val[0]) > step(node.val[1]) ? 1 : 0;
    }

    if (node.t === 6) {
      return step(node.val[0]) < step(node.val[1]) ? 1 : 0;
    }

    if (node.t === 7) {
      return step(node.val[0]) === step(node.val[1]) ? 1 : 0;
    }
  }

  console.log(step(tree));
}

sum("C200B40A82");
sum("04005AC33890");
sum("880086C3E88112");
sum("CE00C43D881120");
sum("D8005AC2A8F0");
sum("F600BC2D8F");
sum("9C005AC2F8F0");
sum("9C0141080250320F1802104A08");


sum(
  "E20D41802B2984BD00540010F82D09E35880350D61A41D3004E5611E585F40159ED7AD7C90CF6BD6BE49C802DEB00525272CC1927752698693DA7C70029C0081002140096028C5400F6023C9C00D601ED88070070030005C2201448400E400F40400C400A50801E20004C1000809D14700B67676EE661137ADC64FF2BBAD745B3F2D69026335E92A0053533D78932A9DFE23AC7858C028920A973785338832CFA200F47C81D2BBBC7F9A9E1802FE00ACBA44F4D1E775DDC19C8054D93B7E72DBE7006AA200C41A8510980010D8731720CB80132918319804738AB3A8D3E773C4A4015A498E680292B1852E753E2B29D97F0DE6008CB3D4D031802D2853400D24DEAE0137AB8210051D24EB600844B95C56781B3004F002B99D8F635379EDE273AF26972D4A5610BA51004C12D1E25D802F32313239377B37100105343327E8031802B801AA00021D07231C2F10076184668693AC6600BCD83E8025231D752E5ADE311008A4EA092754596C6789727F069F99A4645008247D2579388DCF53558AE4B76B257200AAB80107947E94789FE76E36402868803F0D62743F00043A1646288800084C3F8971308032996A2BD8023292DF8BE467BB3790047F2572EF004A699E6164C013A007C62848DE91CC6DB459B6B40087E530AB31EE633BD23180393CBF36333038E011CBCE73C6FB098F4956112C98864EA1C2801D2D0F319802D60088002190620E479100622E4358952D84510074C0188CF0923410021F1CE1146E3006E3FC578EE600A4B6C4B002449C97E92449C97E92459796EB4FF874400A9A16100A26CEA6D0E5E5EC8841C9B8FE37109C99818023A00A4FD8BA531586BB8B1DC9AE080293B6972B7FA444285CC00AE492BC910C1697B5BDD8425409700562F471201186C0120004322B42489A200D4138A71AA796D00374978FE07B2314E99BFB6E909678A0"
);