Advent of Code 2021

Day 16 - Advent of Code 2021

Advent of Code 2021

The problem

Given a encoded message with different operator, our mission is to decode the message and perform theses operations to find the final answers

Initial thoughs

Oh boy this one is really hard for me, waking up at 6am and try to understand a long description of operator. I spent almost 1 hour trying to understand the example 😅.

So first things first, convert our heximal string to binary, lucky for us this is not a challenging task in JS

const hexToBin = (bin) => {
    let bin = "";
     for (let i=0;i<inp.length;i++) {
        bin += parseInt(inp[i],16).toString(2).padStart(4,'0');
     }
    return bin;
 }

The most important part of this function is padStart in order to have our result always have 4 bits, for example we would get 101 given 5 as input if we don't padStart, and it will mess up our calculation for the next parts.

Decoding input

Next step, we need to find the packet version which is the first 3 bit.

Then the next important information is the type of packet, by parsing following 3 bits

110100101111111000101000
VVVTTTAAAAABBBBBCCCCC

If the type is 4, then our input is a literal value, which mean it contains a number, we don't need to do any special to it.

If the type is not 4, we need to determinate the length type id by read the following bit

With length type 0, read following 15 bits to find the length of packet

With length type 1, read following 11 bits to find the number of sub-packets in this packet

With each packet we repeat the same decode process, so as you might guess, its recursive time


let versSum = 0;
const parsePacket = (str) => {
  versSum += parseInt(str.slice(0, 3), 2);
  const type = parseInt(str.slice(3, 6), 2);
  let packetLength;
  const values = [];

  if (type === 4) {
    // Literal case
    let currentPos = 6;
    let num = "";
    while (str[currentPos] === "1") {
      num += str.slice(currentPos + 1, currentPos + 5);

      // Skip 5 bits
      currentPos += 5;
    }
    // We found the last bit, concatenate to the final result
    num += str.slice(currentPos + 1, currentPos + 5);
    return [currentPos + 5, parseInt(num, 2)];
  } else {
    const lengthType = str[6];

    if (lengthType === "0") {
      // Find the length of packet
      const len = parseInt(str.slice(7, 22), 2);

      let count = 0;
      while (count < len) {
        const packet = parsePacket(str.slice(22 + count));
        count += packet[0];
        values.push(packet[1]);
      }
      packetLength = 22 + len;
    } else {
      const len = parseInt(str.slice(7, 18), 2);
      let count = 18;
      for (let i = 0; i < len; i++) {
        let packet = parsePacket(str.slice(count));
        count += packet[0];
        values.push(packet[1]);
      }
      packetLength = count;
    }

    switch (type) {
      case 0:
        return [packetLength, values.reduce((a, b) => a + b)];
      case 1:
        return [packetLength, values.reduce((a, b) => a * b)];
      case 2:
        return [packetLength, values.reduce((a, b) => Math.min(a, b))];
      case 3:
        return [packetLength, values.reduce((a, b) => Math.max(a, b))];
      case 5:
        return [packetLength, values[0] > values[1] ? 1 : 0];
      case 6:
        return [packetLength, values[0] < values[1] ? 1 : 0];
      case 7:
        return [packetLength, values[0] == values[1] ? 1 : 0];
    }
  }
};

The final code

And voilà, after 2 hours of debugging i finally got it. Not something i would proud of in term of readibility but for now i'm happy and we got correct answer for both parts 🍺 !

That's it for today, thank you for reading.