Mariel de la Garza
mcat's devblog

mcat's devblog

Advent of Code 2021: Day 3, part 2

Photo by Waldemar Brandt on Unsplash

Advent of Code 2021: Day 3, part 2

Mariel de la Garza's photo
Mariel de la Garza
·Dec 15, 2021·

11 min read

Table of contents

Each day of Advent of Code has 2 puzzles - you unlock the second one when you complete the first . The second puzzle picks up where the first left off, using the same input.

For this puzzle, I still need to figure out whether 0 or 1 occurs most often at a certain place in the strings, but this time I'm looking to match a certain criterion and filter out the strings that don't meet it. The original input array of 1000 strings gets whittled down until there's one left, and that one string is part of our answer. Similar to the first part, when we're done going through the input we'll have 2 strings representing binary numbers and to get our final answer we multiply their decimal values together.

Input and Parsing

Getting an array to work with is done exactly the same way it was done for part 1:

import fs from "fs";
import path from "path";

const __dirname = path.resolve();

const day03part2 = () => {
  const inputArray = fs
    .readFileSync(path.join(__dirname, "day-03-input.txt"), "utf-8")
    .split("\n")
    .filter((e) => e);

Now that we have the array of 1000 strings, we need to do something with them.

What's our plan?

This puzzle is for us to figure out the "life support rating" of our submarine - the elves had a submarine handy but apparently don't have this information conveniently displayed anywhere. The life support rating is the result of multiplying the "oxygen generator rating" by the "CO2 scrubber rating."

Finding the oxygen generator rating

To get the oxygen generator rating, we need to look at the first bit of each string and figure out whether there are more 1s or 0s. This is exactly how we started part 1 -

billy mays saying but wait there's more

After figuring out whether there are more 1s or 0s, we need to ditch any strings that don't have that value in the first bit position. If they appear an equal number of times, we keep the strings with a 1 at that position. Then, we move on to the next bit position - array[element][1] and repeat the process. We continue moving through each bit position and getting rid of strings that don't match what we're looking for until we have one string left. That string is our binary "oxygen generator rating". To store this value, I added let mostAnswer just under where we create the input array. This is similar to creating let gammaValue = [] in part 1. The name is a reference to looking for the value that appears the most number of times, but it could be named anything.

const day03part2 = () => {
  const inputArray = fs
    .readFileSync(path.join(__dirname, "day-03-input.txt"), "utf-8")
    .split("\n")
    .filter((e) => e);

  let mostAnswer;

Finding the CO2 scrubber rating

This process starts out the same as the first - looking at how many 1s or 0s are at each bit position in the array's strings and narrowing things down to one string. This time, we want to focus on whether 1 or 0 appeared the fewest number of times. We'll keep the strings that have that value in the bit position we're checking and move on to the next. If 1 and 0 appear an equal number of times, we keep the strings with a 0 at the position we're checking. When we're down to one string, that is our binary "CO2 scrubber rating". To store this value, I added let leastAnswer just under where we create the input array. This is similar to creating let epsilonValue = [] in part 1. The name is a reference to looking for the value that appears the least number of times.

const day03part2 = () => {
  const inputArray = fs
    .readFileSync(path.join(__dirname, "day-03-input.txt"), "utf-8")
    .split("\n")
    .filter((e) => e);

  let mostAnswer;
  let leastAnswer;

Finding the answer

We need to convert the oxygen generator rating and the CO2 scrubber rating from binary values to decimal values and multiply them together. The result is our answer - the "life support rating".

Finding the most common element

Setting up the function

Unlike part 1, we don't need to rearrange our input. We're just going to look at the input array as it is. We know we're going to need something to keep track of where we are in the string (which bit position), we're going to need a way to count how many 1s and 0s there are, a way to use the result to filter our input, and a way to start the whole process over. A code snippet is below, followed by an explanation

let findMostCommonElement = (input) => {
  let myInput = input;
  let key;
  let zero = 0;
  let one = 0;

Later on in our solution, we're going to update our input after filtering through it using our criterion. To do this, myInput creates a mutable copy of the original input that we can just keep resetting to a different value. key is a term borrowed from the part 1 solution, when we used an object - it was the value that appeared the most often, 0 or 1. I kept the name since its representation was already in my head, but it could be called "mostOftenCharacter" or "numberToFilterBy" or anything else. zero and one are what we will use as counters. Every time we see a 0, we'll add 1, every time we see 1, we'll add 1. At the end of our function, where we reset myInput, we'll also reset zero and one so they can be used to count again when we look at the next bit position.

The first loop

We know we need to keep track of where we are in the string we're looking at. We know our strings are each 12 characters long and that when we look at them, they behave a little like arrays. We can access the first character by looking at inputArray[string][0].

Using a for loop with this in mind gets us started:

let findMostCommonElement = (input) => {
  let myInput = input;
  let key;
  let zero = 0;
  let one = 0;

  for (let j = 0; j < 12; j++) {
    }

The second loop

Now we need a way to look at each string in our array, at each bit position. We know we can do this with another for loop, and by putting that one inside the first loop, we'll have the beginnings of what we want.

  let findMostCommonElement = (input) => {
    let myInput = input;
    let key;
    let zero = 0;
    let one = 0;

    // For each bit position, 1 through 12
    for (let j = 0; j < 12; j++) {

      // For each string while at that bit position
      for (let i = 0; i < myInput.length; i++) {
      }
    }

Inside the second loop

While we're looking at bit position j in each of our strings, we need to do something: count how many 1s and 0s we see.

Because the input is originally given as 1000 rows of 1s and 0s, I think of each string in our input array as a "row" of that input. To make things easier to follow for myself, I set row to be myInput[i], where myInput[i] is the string that we're looking at.

Then, looking at bit j of our row, we'll use our counters. If row[j] is 0, we increase the zero counter by 1. If row[j] is 1, we increase the one counter by one. After we look at each string at this bit position, we'll jump out of this loop and back into the j loop.

  for (let j = 0; j < 12; j++) {
    for (let i = 0; i < myInput.length; i++) {
      let row = myInput[i];

      if (row[j] == "0") {
        zero += 1;
      } else {
        one += 1;
      }

Inside the first loop

Back inside the j loop, we look at the counter totals. The i loop looked at each string at position j. Now, for this position, we want to know if there were more zeroes than ones. If yes, we'll set our key to 0. Otherwise - if there are more ones than zeroes, or if there are the same number of ones and zeroes - we will set the key to 1. Once we have our key, we filter our input array. We'll keep every row where the bit at position j is the same as our key. We take what we're keeping, set that to myInput, and then reset zero and one to 0.

After that, our first loop will move to the next j value, doing the entire process over again with our new myInput.

    for (let j = 0; j < 12; j++) {
      for (let i = 0; i < myInput.length; i++) {
        let row = myInput[i];

        if (row[j] == "0") {
          zero += 1;
        } else {
          one += 1;
        }
      }

      if (zero > one) {
        key = 0;
      } else {
        key = 1;
      }

      myInput = myInput.filter((element) => element[j] == key);
      zero = 0;
      one = 0;
    }

Because of the original input I happened to get, I didn't actually need to specify to stop resetting myInput when there's one string left. At j = 11 (the 12th character), it has one string, the filter catches it, and because there's no more increases for j, we exit the loop.

Returning mostAnswer

We know that the string we want is going to be the only element left in our myInput array, so we can grab it with myInput[0]. We set myAnswer to that value, and return it. That string is the binary representation of our oxygen generator rating. (We just need to remember to call the function to begin with and give it "input" to get started.) The complete function is below, with the function call below it.

let findMostCommonElement = (input) => {
    let myInput = input;
    let key;
    let zero = 0;
    let one = 0;

    for (let j = 0; j < 12; j++) {
      for (let i = 0; i < myInput.length; i++) {
        let row = myInput[i];

        if (row[j] == "0") {
          zero += 1;
        } else {
          one += 1;
        }
      }

      if (zero > one) {
        key = 0;
      } else {
        key = 1;
      }

      myInput = myInput.filter((element) => element[j] == key);
      zero = 0;
      one = 0;
    }

    mostAnswer = myInput[0];
    return mostAnswer;
  };

  findMostCommonElement(inputArray);

Finding the least common element

This function will actually be the same as our other function all the way through what to do with the zero and one counts. This time, if zero is less than or equal to one, we set the key to 0. Otherwise, we set the key to 1. This could be represented as if (zero > one) { key = 1 } else key = 0, but the way it's written is how I kept it straight working through this, so I'm leaving it.

  for (let j = 0; j < 12; j++) {
    for (let i = 0; i < myInput.length; i++) {
      let row = myInput[i];

      if (row[j] == "0") {
        zero += 1;
      } else one += 1;
    }

    if (zero < one) {
      key = 0;
    } else if (zero == one) {
      key = 0;
    } else key = 1;

Here, I actually did need to specify to only reset myInput when it has more than one element. I spent a long time wondering why I got "nothing" back ... it was because my filter was filtering out my answer. For my input, I have:

myLeastInput for j = 7 and key = 0
let input7 = [111000101110, 111000100110]

my least input for j = 8 and key 0
let input8 = [111000100110];

At j= 7, we've got two strings left. input7 is our filtered result. So we're taking those two strings and starting the process again at j = 8. At input7[0][8] and input7[1][8], we have a 1 and 0. Because we have the same number of 1s and 0s, our key is 0. When we run our filter, we'll keep the string that has a 0 at position j. That leaves us with input8, just one string.

When it starts the process over again, at j = 9, we are only looking at 111000100110. At position 9, we have a 1. Because we have fewer zeroes than ones (since we have no zeroes), our key is again 0. When we run our filter, we'll keep whatever has a 0 at j = 9. The string we're looking at has a 1 at j = 9, it gets thrown away annnnnd we get nothing.

SO. Here, we add if (myInput.length > 1) before running the filter. That way, when it gets down to one string, we're done and exit the loop. Like above, we set myInput[0] to leastAnswer and return leastAnswer. The complete function is below, with the function call just after it.

let findLeastCommonElement = (input) => {
    let myInput = input;
    let zero = 0;
    let one = 0;
    let key;

    for (let j = 0; j < 12; j++) {
      for (let i = 0; i < myInput.length; i++) {
        let row = myInput[i];

        if (row[j] == "0") {
          zero += 1;
        } else one += 1;
      }

      if (zero < one) {
        key = 0;
      } else if (zero == one) {
        key = 0;
      } else key = 1;

      if (myInput.length > 1) {
        myInput = myInput.filter((element) => element[j] == key);
        zero = 0;
        one = 0;
      }
    }
    leastAnswer = myInput[0];
    return leastAnswer;
  };

  findLeastCommonElement(inputArray);

Decimal values and the final answer

As we did with part 1, we use parseInt to get our decimal values, then we multiply them together, and then we're done!

  let mostDecimal = parseInt(mostAnswer, 2);
  let leastDecimal = parseInt(leastAnswer, 2);
  let answer = mostDecimal * leastDecimal;

  console.log(answer);
 
Share this