Mariel de la Garza
mcat's devblog

mcat's devblog

Advent of Code 2021: Day 3, part 1

Photo by Max Beck on Unsplash

Advent of Code 2021: Day 3, part 1

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

9 min read

Table of contents

  • Input and Parsing
  • What's our plan?
  • Organizing the input
  • Find the most common element
  • Finding the most common element in each array
  • Finding the least common elements
  • Getting the decimal values
  • The answer

Advent of Code is a neat thing that happens on the internet starting December 1. Every day through Christmas you get a fun puzzle and then you use whatever sort of programming thing you want to solve it. I'm using JavaScript because of course, but people have used the Shakespeare Programming Language, a TI- calculator, Python, Java, and Excel. The only point really is to learn things and have fun. (A leaderboard does exist, so if global competition is fun for you, you're covered.)

If you go to the Advent of Code page and click on "Events" in the top menu, you'll see a list of the years it's happened. Next to them, you'll see the number of gold stars you've gotten (if you're logged in). The puzzles come in two parts, and you get a gold star for solving each part.

I have obviously been a strong participant.

screen shot of advent of code events page

You can poke around and see the different problems that have been given for each day. Day 1 of 2020 had something to do with expense reports, and Day 1 of this year starts us off on a submarine. With elves. Why? Because they dropped the keys to Santa's sleigh in the ocean and now we have to find them, of course.

I recently finished Day 3 part 1 and I'm going to walk through what I did because understanding code I wrote more than 10 minutes ago can be a struggle.

moira rose asking "who wrote that"

Input and Parsing

Day 3 finds us still on our deep sea adventure with the elves and today we need to check the power consumption of our submarine. At the bottom of the puzzle is a link to the input to use to get the solution. I copy and paste my input into a .txt file in my editor because I am not one of the wizards who just solves the puzzle right there in the devtools console. Because of reasons, I don't check the input or puzzle text into version control, but know this day's input is just 1000 lines of binary numbers, each of which is 12 characters long.

After moving the input to a .txt file, I need to get it into a form I can use. Luckily using Node.js makes this pretty easy. (If you're new to Node, FreeCodeCamp has some exercises to get you started.) Below is the code snippet, and then the explanation.

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

const __dirname = path.resolve();

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

First, we import fs and path, which let us access and interact with our files. Those modules are then used to get what's inside our input text file. By specifying utf-8 as our encoding, the input will be loaded as a string. Then, using .split("\n") will break up that text at every new line, put the new pieces into an array, and return the array.

That last line? .filter((e) => e)? That's because my editor settings caused me to waste 5 hours debugging code that was actually working fine. On file saves, a new line is added to the end of the file. (Why it does isn't relevant here.) I forgot about that when I pasted the text from the browser so my array of input was ['000101', '000111', ''], leading to "undefined" showing up in my results later. That filter is going through the array and kicking out anything that's not true. Empty strings are falsy so they get dropped off. Once I figured out my problem I initially turned off the newline setting but I chose to update my code instead so I'd remember how to account for that in the future.

What's our plan?

The 1000 lines of text has been turned into an array with ... 1000 strings of equal length as elements, where each string is a series of 1s and 0s that represent a binary number. The length of each string - how many characters it has - is 12.

The first step toward our solution is to look at each character position of our strings and figure out which number (in this case, 0 or 1) appears most often. That number then becomes a character in what the puzzle calls our gammaValue. So, if we look at the first character of each input string and find that most of them start with 0, then 0 becomes the first character of our gammaValue. Moving to the second character of each input string, if the number we see the most is 1, that will become the next character of our gammaValue, making it 01, and so on through the 12th and final character. The final gammaValue will be a string of 1s and 0s that represents a binary number.

Once we have the gammaValue we need its inverse: we'll need to determine which character appears the least often at each position in our input strings and combine those together. That series of 1s and 0s becomes a binary number our puzzle calls the epsilon value. Then, we need to convert both the gammaValue and epsilonValue to decimal values and multiply those together. The result of that multiplication is the answer to our puzzle.

Organizing the input

Pretend that our input looks like this:

['101',
 '000',
 '010'
 '111'
 '101']

We know that we need to look at each 'column' to find the character that appears the most often. To be able to look through each "column", or each position in the strings of our input array, we need to split our input up again. Using the example input above, we want to turn that array of strings into:

['1, 0, 0, 1, 1']
['0, 0, 1, 1, 0']
['1, 0, 0, 1, 1']

Each of these new arrays represents one of the columns (or character positions) that we're going to be checking. This makes it easy to go over each character position and count up how many times the 0s and 1s appear. The code is below, followed by an explanation.

let arrays = [[], [], [], [], [], [], [], [], [], [], [], []];
for (let i = 0; i < input.length; i++) {
  for (let j = 0; j < arrays.length; j++) arrays[j].push(input[i][j]);
}

First, we create an empty array of empty arrays to hold each "column" of our input. Then, the outer for loop is going through each string of our input array. The inner for loop is going through every character in that string and adding each character to the corresponding empty array. So if our input string were "dinosaur" -> 'd' gets added to the first array, 'i' to the second, 'n' to the third, etc. When it's done, each of the 12 arrays represents each of the character positions of our input strings. The value that appears the most in each array will be added to our gammaValue.

Find the most common element

Looking through each array inside of arrays, we want to find the element ('0' or '1') that appears most often. If our first array is [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], when we're done with our initial tally, we'll have something like:

'0': 2
'1': 10

Since that looks like an object, with a key and a value, we should create one.

const findMostCommonElement = (array) => {
  let object = {};
};

Next we add a for loop that fills out our object keys and their values. We want to look at each element in the array (each '0' or '1') and if it isn't a key our object, we're going to add it and specify that it's now been seen once. If it is a key in the object, we're going to increase the number of times it's been seen by 1.

const findMostCommonElement = (array) => {
  let object = {};

  for (let i = 0; i < array.length; i++) {
    let element = array[i];
    if (object[element] == null) object[element] = 1;
    else object[element]++;
  }
};

This is what finally gives us our tally of {'0': 2, '1': 10}. Next we need to grab the bigger of those two values, find its key, and add that key to the gammaValue. We can actually find the biggest value with one line.

    let value = Math.max(...Object.values(object));

First, let's look inside the parentheses. ...Object.values(object) gives us the values of the object. Since our object is {'0': 2, '1': 10}, we'll get [2, 10]. Math.max looks at that [2, 10] and tells us which is larger. So the value we're getting back is 10.

In the next line, we're going to go backwards: look at the object and find the key that has the given value.

gammaValue.push(Object.keys(object).find((key) => object[key] === value));

There's not a given function to do this, so we use Object.keys().find() to look at each of the keys of our object and find something. (key) => object[key] === value says to find the key where its value equals the value we've specified above (with let value =).

The key we'll get back is 1, so that's what we're going to add to our gammaValue array.

Now we just need to do this 11 more times.

Finding the most common element in each array

Above, we created an array of arrays and named it arrays.

We need to pass each of its inner arrays to our function that figures out whether 0 or 1 appears most often and adds it to the gammaValue. Below, "element" represents one of the smaller arrays (because each is an element of arrays):

arrays.forEach((element) => findMostCommonElement(element));

Once this is done, we'll have checked each character position of our input strings and have our final gammaValue.

Finding the least common elements

Remember since our strings represent binary numbers, we're only working with 0s and 1s. If 0 occurred the most, that means 1 occurred the least. Knowing this, we don't need to go back through every piece of our original input, we just need to go back over our gammaValue. The opposite of that will be what our puzzle calls the epsilonValue.

const findEpsilonValue = (gammaValue) => {
  for (let i = 0; i < gammaValue.length; i++) {
    if (gammaValue[i] == 0) {
      epsilonValue.push("1");
    } else {
      epsilonValue.push("0");
    }
  }
};

findEpsilonValue(gammaValue);

Looking at each element of the gammaValue (remember we created an array), if it equals '0', we're going to push '1' onto our epsilonValue, otherwise (i.e., if it equals '1'), we're going to push '0' onto our 'epsilonValue`.

Getting the decimal values

Now, we have 2 arrays: the gammaValue and the epsilonValue. When we join the values of each array together, we'll have 2 strings that represent binary numbers. We need the decimal values of those to get our final answer. Luckily we have a function that will do this for us: parseInt will take a string value and the base of that string value and then give us back an integer in base 10.

  let gammaDecimal = parseInt(gammaValue.join(""), 2);
  let epsilonDecimal = parseInt(epsilonValue.join(""), 2);

The answer

Now, we can take the gammaDecimal, multiple it by the epsilonDecimal, and that is the answer to our puzzle.

carlton dancing

 
Share this