Follow

Follow

# Advent of Code 2021: Day 3

Cristiana Man
Â·Dec 3, 2021Â·

This blog post is third in the Advent of Code 2021 series and shows a JavaScript-based solution to the problem described in Day 3.

All solutions are in this GitHub repository.

## Solving Part One

The input file consists of binary numbers on separate lines. We must find the so-called gamma rate and epsilon rate, multiply them and return the resulting number in decimal format. Gamma rate is a binary number where each bit represents the most common bit in its position among all given numbers. Similarly, the epsilon rate contains the least common bit for each position.

We can break this problem into smaller tasks:

• read lines from the input file
• find how many bits each number has
• find the most common bit for a given position
• find the least common bit for a given position
• concatenate found bits
• parse the binary string to decimal

### Read lines from the input file

I wrote about the `readInput` function in my Advent of Code: Day 1 blog post. If you haven't already, give it a read!

``````import { URL, fileURLToPath } from 'url'

const inputPath = fileURLToPath(new URL('./input.txt', import.meta.url))
``````

We can then get each line containing a binary number by splitting the input data using the new line character `\n`

``````const lines = data.split('\n')
``````

### Find how many bits each number has

One of the constraints of this problem is that each number is represented using the same number of bits. Thus, we can calculate the length of the first line to find how many bits each number has.

``````const numberOfBits = lines[0].length
``````

Now for each position, we must find the most and least common bits

``````for (let i = 0; i < numberOfBits; i++) {
// find most common bit for position i
// find least common bit for position i
}
``````

### Find the most common bit for a given position

We must iterate through each line and investigate the bit at the given position. To get the bit on a given position of a line we can use `line.charAt(index)`. We can then count the occurrences of `0` and `1` and compare them in the end to determine the most common bit.

``````const getMostCommonBit = (lines, index) => {
let occurenceOf0 = 0
let occurenceOf1 = 0
lines.forEach((line) => {
const bit = line.charAt(index)
if (bit === '0') {
occurenceOf0 += 1
} else {
occurenceOf1 += 1
}
})
return occurenceOf0 > occurenceOf1 ? '0' : '1'
}
``````

Since `occurenceOf0 > occurenceOf1` can be written `occurenceOf0 - occurenceOf1 > 0` we don't actually need the exact count of occurrences, only the difference. Thus, we can refactor the code like so:

``````const getMostCommonBit = (lines, index) => {
let occurenceDifference = 0
lines.forEach((line) => {
const bit = line.charAt(index)
if (bit === '0') {
occurenceDifference += 1
} else {
occurenceDifference -= 1
}
})
return occurenceDifference > 0 ? '0' : '1'
}
``````

### Find the least common bit for a given position

After finding the most common bit, we can determine the least common bit as the opposite. For example, if the most common bit is `0` we know the least common is `1` and vice versa.

``````const mostCommonBit = getMostCommonBit(lines, i)
const leastCommonBit = mostCommonBit === '0' ? '1' : '0'
``````

### Concatenate found bits

``````let gammaRate = ''
let epsilonRate = ''

for (let i = 0; i < numberOfBits; i++) {
const mostCommonBit = getMostCommonBit(lines, i)
gammaRate += mostCommonBit
epsilonRate += mostCommonBit === '0' ? '1' : '0'
}
``````

### Parse the binary string to decimal

After finding the `gammaRate` and `epsilonRate` we can parse them to decimal using the `parseInt` function.

``````parseInt(gammaRate, 2)
parseInt(epsilonRate, 2)
``````

You can see the final solution for part one my GitHub repository

## Solving Part Two

I suggest thoroughly reading and understanding the problem before reading further. To solve the second part of the challenge, we need to repeatedly filter the given binary numbers based on a bit criteria until there a single number is left. We must find the so-called oxygen generator rating (`oxygenRate`) and the CO2 scrubber rating (`co2Rate`) using this filtering method.

There are a few steps to solve the challenge:

• find the bit criteria for `oxygenRate` and `co2Rate`
• filter numbers until there is a single item left
• parse the binary string to decimal

### Find the bit criteria

The bit criteria for `oxygenRate` is the most common bit in position X among filtered numbers, where X starts at 0 and increases each filtering round. Similarly, the bit criteria for `co2Rate` is the least common bit.

We can reuse the `getMostCommonBit` function created for part one, but with changes to accommodate the additional rule - if there is an equal number of bits, the criteria should default to `1` for `oxygenRate` and `0` for `co2Rate`.

``````const getOccurenceDifference = (lines, index) => {
let occurenceDifference = 0
lines.forEach((line) => {
const bit = line.split('')[index]
if (bit === '0') {
occurenceDifference += 1
} else {
occurenceDifference -= 1
}
})
return occurenceDifference
}
``````

The `getOccurenceDifference` returns a positive number if `0` is most common, a negative number if `1` is most common or `0` if both bits are equally common. Thus, the bit criteria for `oxygenRate` is defined as follows and represents the most common bit or if both bits are equally common defaults to `1`.

``````getOccurenceDifference(oxygenRates, index) > 0 ? '0' : '1'
``````

The bit criteria for `co2Rate` represents the least common bit or if both bits are equally common defaults to `0`.

``````getOccurenceDifference(co2Rates, index) > 0 ? '1' : '0'
``````

### Filter numbers until there is a single item left

The first filtering round starts with all lines for both `oxygenRates` and `co2Rates`. We can copy the lines representing the binary numbers into each corresponding array.

``````let oxygenRates = [...lines]
let co2Rates = [...lines]
``````

We repeatedly filter these numbers until there is a single item left. Each time we must increase the index of bit we compare with `criteriaBit`.

``````let index = 0
while (oxygenRates.length > 1) {
const bitCriteria = getOccurenceDifference(oxygenRates, index) > 0 ? '0' : '1'
oxygenRates = oxygenRates.filter((line) => line.charAt(index) === bitCriteria)
index++
}
``````

Similarly, we filter the `co2Rates`.

``````index = 0
while (co2Rates.length > 1) {
const bitCriteria = getOccurenceDifference(co2Rates, index) > 0 ? '1' : '0'
co2Rates = co2Rates.filter((line) => line.charAt(index) === bitCriteria)
index++
}
``````

### Parse the binary string to decimal

Finally, we can parse the first and only element in `oxygenRates` and `co2Rates` in the same manner we did for part one.

``````parseInt(oxygenRates[0], 2)
parseInt(co2Rates[0], 2)
``````

You can see the final solution for part two my GitHub repository

## Conclusion

Day 3 was about thoroughly reading the problem, understanding it and breaking it down into smaller parts. We processed strings representing binary numbers and relied on JavaScript functions like `parseInt(binaryString, 2)`, `String.charAt(index)`, `array.filter(condition)` to solve the challenges.

Â