Advent of Code 2021 in Julia – Day 3: Binary Diagnostic

11-minute read
In series: Advent of Code
Julia
Table of Contents

It’s getting interesting! Today’s problem got me stucked for a while – mainly because I didn’t read the question closely enough. For this excercise I work with matrices, which Julia handles really well.

Part 1

Show challenge - day 3, part 1

The submarine has been making some odd creaking noises, so you ask it to produce a diagnostic report just in case.

The diagnostic report (your puzzle input) consists of a list of binary numbers which, when decoded properly, can tell you many useful things about the conditions of the submarine. The first parameter to check is the power consumption.

You need to use the binary numbers in the diagnostic report to generate two new binary numbers (called the gamma rate and the epsilon rate). The power consumption can then be found by multiplying the gamma rate by the epsilon rate.

Each bit in the gamma rate can be determined by finding the most common bit in the corresponding position of all numbers in the diagnostic report. For example, given the following diagnostic report:

00100
11110
10110
10111
10101
01111
00111
11100
10000
11001
00010
01010

Considering only the first bit of each number, there are five 0 bits and seven 1 bits. Since the most common bit is 1, the first bit of the gamma rate is 1.

The most common second bit of the numbers in the diagnostic report is 0, so the second bit of the gamma rate is 0.

The most common value of the third, fourth, and fifth bits are 1, 1, and 0, respectively, and so the final three bits of the gamma rate are 110.

So, the gamma rate is the binary number 10110, or 22 in decimal.

The epsilon rate is calculated in a similar way; rather than use the most common bit, the least common bit from each position is used. So, the epsilon rate is 01001, or 9 in decimal. Multiplying the gamma rate (22) by the epsilon rate (9) produces the power consumption, 198.

Use the binary numbers in your diagnostic report to calculate the gamma rate and epsilon rate, then multiply them together. What is the power consumption of the submarine? (Be sure to represent your answer in decimal, not binary.)

Here’s the provided input:

Show input - Day 3
000001100010
100111011010
001100011001
011010001010
011010101011
001001110101
100110001101
100010010011
011110000110
011000110110
011111111110
100111110011
110000100101
011010011111
001010011101
110110001010
101111110101
000010101101
111010111110
111110001110
100110111011
101011010101
001001000101
111101000100
001100000010
010001100101
001010011111
101010010100
100001110011
100000111010
100101010101
000000101000
011010100011
110100111110
010010011000
000101000010
001100011100
011101000000
010110111010
101101100100
000000010011
000101001111
011011100111
101111100101
101001101011
101100010100
001001110111
110011011110
111001101000
101101111111
001100110100
000001000111
000111101111
110101011100
010111011100
010011101000
100011101011
110000110011
110000100010
100101001110
011000001100
100000101110
101010110001
000111101110
011111101111
000000100010
101000010100
011000111001
001011001101
011111111111
100111000100
101010011010
001100100011
011101011110
011111100010
110111110011
111011111010
000101101011
001111011011
000011101000
000101111011
000010100110
111001000100
011110001111
010001011000
100010100100
100100111100
010010010101
001101110011
000000010000
000110001100
100110110111
001000100100
101010111010
000011101100
100000100001
011111110000
101001001111
100000111111
110111000111
111000010001
011011011111
110011011010
100011010101
011110010100
001001101010
100100111000
100110110011
010010111000
111011101111
111001101010
100000010011
011011101111
011100101011
110101011000
101111011110
100111000010
001110110101
111001111100
010000110111
011100001010
110111110101
011011100010
111101101000
101000000111
110000001001
001100101101
100111100010
000100010100
111101100110
101001010001
011000000001
010100100100
010001001000
010000010111
100011110001
000011100110
001001000001
000100001100
001001101111
001001100000
000111011100
100001010110
101010001110
010010101001
110010001100
101011101100
111000110111
100011010100
001110001101
101011011010
110101011010
011100010001
010011010011
001011111001
100011101100
011101100011
010000011111
011001101011
011110011100
001100011010
101100001110
011001111101
100101011111
011111100001
111001010111
010111000100
111110110111
100011011001
100000010000
111110111111
101111101011
110011010011
100001111110
101011011011
110111111110
101110101001
011100001100
000101011100
011010100111
110111011000
100110111100
111010001100
010010011111
000011010100
010111101111
111111000011
000111111010
000011111111
010010001010
100101110010
111110010100
111110000000
111110111110
110010100111
110011000010
001101010011
100100010001
101010110110
110110011100
111111001011
000011010001
010111011001
010100100010
010001101100
001101001110
010101000100
111010010010
000100100101
000011001001
011000110111
010111110111
011000100110
011110001110
011100111010
001111101100
100100001100
001100110101
011101111001
100001000000
110100001010
110111111000
010110010001
110010011101
101101011111
111111100110
101110001000
111100110100
110001111011
001011000011
011000000100
101100000001
001110000100
111110001111
100001001101
111111111011
101101110001
111001110111
100001101000
001100101001
000101000000
001011111011
000001011111
100000101011
101100000000
101110001001
110111111010
010000011000
110111100100
001100010011
111111100100
101011010100
101101001100
110110101001
011001101000
011101110001
010010010000
110001010101
110111110001
100011111110
110011111101
011111110110
110110101101
000010111000
111110011000
100111101110
101011000010
111101111000
001001110010
011000100101
011010100100
101111010001
111101101011
101110100110
011111100000
000101100001
110100100000
010011110111
001011010011
010001101111
100111110010
100111010001
110001111111
000110110011
000100000101
011111111001
110011100110
111011000110
100101101101
001111000010
001101011100
011001101111
101110111100
110011001110
011001011000
110010001001
000100000110
011101001000
100111010111
000101010000
011110110110
010110111001
111110100101
100100011010
111011100110
100111010000
011111100111
101010100001
110001101110
000101000001
010011011100
111101011111
101001100111
011101111000
100001100111
110011001001
011101000111
000011011100
100111001001
001001101100
101101111101
100100001111
111100111011
010011000001
000101010101
000100100010
100001011100
110011100010
010110011010
001110100001
001110111011
101110100111
011101101110
110100101110
111101110010
001001110110
100011010111
111110101100
011100111101
001010000100
000111001111
110101010110
101010101011
011101011000
111000111010
000010011001
011010111101
000111111101
000010111101
111011000000
111100001100
110101111111
000111011000
010010001111
100011101000
110100010001
110101001111
100011100100
000010111100
011010010011
111001000010
101010101111
110100101010
001100101011
001111101011
000011100111
111011001001
110110000010
010000010011
010110110010
110100100101
001101110101
001011001011
010100100000
000010000000
110110011101
101001100011
010111000001
001111100111
110111111101
011010100000
011011110101
011110100001
010100110001
100000000101
010011101111
101111110111
101000100100
011010101001
010000000110
110011110111
010011011011
101101101111
001111011101
100111101111
000111000101
100100101010
011110011110
010011101110
000000100110
010100110101
101101010100
101001000010
111000000110
010001000000
000100010110
110101101001
010010111110
010011100001
001011111111
111001101001
111100001110
101110010101
111101111011
110011010000
111101011011
111100101101
111010100110
111000001011
011011001011
000000010010
100100000000
110011111001
010000101000
111010110100
010101101011
111111001111
010101001110
101110111011
011101111010
101110110011
000110111101
111100011100
000010101001
000011011010
100010011100
000110100001
101001111110
000010100010
001110000000
100011100110
010011110110
110000111000
010110001110
110001100011
001010000011
101001010000
101110110100
111010000100
111011011001
000100001011
011010001101
011000101000
011101011100
110111110100
101000000010
101000100011
011101110011
011100011010
001010001111
001011101011
100001010010
111110111101
110000010001
011001010101
100100101000
110000000111
001111110101
101000010010
011110111100
101111111000
000011101101
110001100110
001111011000
000011000100
001101000010
011111111000
011111001010
000110000010
010000010110
101111000010
001101111101
101011101010
101110110010
001000000111
100000101001
011111110010
011001100100
011010010111
001010110011
001001011010
000111000001
000111000000
011000001111
010001001101
001100010110
010100000011
110110110100
011100000100
101111000101
110101010010
001110010111
110000011010
000110100000
111101000011
000100011100
010010100010
000000010001
110001111101
100011001101
010011110011
000101010001
110111101001
110010000011
100100000101
100001010101
111111111110
100011101101
100100100011
110000001111
010101001010
101000111000
010010011100
110011101001
011101011111
011111001011
111110011100
010001111111
100011110100
010000001101
100111111100
101000101011
110110101011
110101001100
101010110010
110110100011
001001010001
011110010000
000001111111
101010101000
010001111101
100110101111
100101000011
001010110010
001111001100
100101011100
111001000101
010100100101
100010101101
100101110001
101000100010
110101111110
111100110110
100101100100
001000001100
010011110001
011100101000
101111101010
100101100001
000110000000
001001001111
001111100000
111110001011
011110011010
111001100110
000010100000
010110110001
100111001101
111101010110
110001010100
110110100000
011100000011
100101110111
000001000011
100100100110
111100000010
100110110100
000101111110
001110100110
010101110100
111010110101
000001100111
100010001101
101011011111
010011111101
101010011111
000011111000
110001100000
100010111011
010111101011
010100101011
100010001110
111100000100
101011101110
000101100011
100000111000
110011001010
000001110011
000111010100
111110110100
100101011001
110010010001
010100111101
111100100000
101000110000
011101111111
001101111111
001001000110
000001100110
110100101000
001111000000
111101100010
100111001011
001001100101
100000001001
101010100101
010001000010
111100000000
001100010101
101111111101
110100010100
101000100101
111001010000
011001000100
011110011011
101100010011
100100110111
111100101011
011100100110
000111001001
111101101001
001111101111
101111111001
101100110101
101000011000
100100011111
101011001011
001101111001
111010011100
001011000001
100011001110
101101010010
111000101010
101101100110
101111010100
101011000100
100111111010
110110001011
100101001001
110001101100
010000100000
110100010010
101011110001
001000011010
001011110000
101111010110
000101110111
110111110000
101110001100
111010110001
010001110001
100010001000
001001000111
100010110010
000011100101
111111000111
010010001110
011011011110
111110100011
101111111111
000010011111
010101011101
101101011011
001111010111
001010010100
101010111001
010110111111
000110111110
001101101100
011000101001
110011000001
100111001010
001101011010
100000100111
110100010111
100000111001
100011011111
010111100011
110111000010
011110101001
010110101000
011110111110
110000110001
100100001010
011111001000
110110110010
011000101011
000000000010
000010000100
110000000011
011111101101
011000101101
110011101110
000000001001
101001110010
101101000001
011011001111
110010010010
000100101011
010111010001
111101000110
111010111111
111001010100
011010110101
001001000010
011001000010
000000101101
010000111110
010011100101
100111000110
111111001100
101100100110
011110100110
001110101101
001101001000
111111011000
011100100000
001000011001
001001111111
111010011011
001001111101
101000110110
100000111101
001011000110
100010010010
101010011001
101010110011
101010110000
000001000110
001101110110
010010011011
101111110000
011110001011
001011111100
111011111111
101101010111
000001010101
010110101111
111100000001
010101100010
101111010011
010001011010
011100101101
111100101010
001100111001
001101000111
011010111010
010011100000
110000011001
111101100101
010111101110
011110001010
011101000100
011000110011
110111001000
011000001001
010111111001
111001110010
110110110000
000100110000
101011110110
111000011010
011001110100
100011101001
111010110110
000110100010
011101010110
001100111010
010010101101
000101110011
100000000010
100111100011
101110111000
100001111011
001111001000
000110010110
010001110101
111100010011
100000010101
111111111101
000001001100
100111111110
111100110001
111000100011
110101100110
000101010100
010000001001
011010000011
011011011000
101100011010
101001001011
000010110111
101111000111
100101010001
001111011001
000010111111
010001010100
011110101111
001110101010
010000001100
011011101011
100111110100
101101100101
101101000011
111110101111
110010110110
100011000101
011011110011
101010101100
001101000001
100010111010
100101011101
101011000001
101100000011
001011000100
000011100000
010110001011
000111111100
111011000011
110100111001
001110001110
001010100001
110111111001
011011101110
010100010000
101011111000
010001100001
000001010111
110011101010
001110111110
011101110110
010110001000
110101111010
100101100000
000100111001
110110111010
111010010101
110111111100
010101010111
100001011110
010101001001
001101011101
011100100100
010001110111
100111001100
101010111011
100000111110
101111011011
011110110001
000100000100
010111100100
110101010111
101101101011
110101101010
001010000111
111001111111
100100011001
101111010000
110111011010
110001110101
011100001001
001111100011
000100010111
100110010011
011110011001
010110001111
011111011010
111011111000
011110111101
000001000100
111000010000
010010000101
011100100111
110001001000
110100111111
100000010110
110111100011
101001110100
001001011001
010011100111
101001010011
101000001101
000100001111
111111011111
000101001010
011011010010
101010000101
001101001010
000001100001
010010110100
010011000010
111110011111
010011111011
111100010111
000000010100
110011011111
000100110100
011001000101
010110100011
100011010011
010111001110
100101010000
001001010110
110000001000
101111110001
101101001101
010100000100
100101111010
001111011010
101110011111
110000010111
100011011110
000000100111
010111010111
100001011011
101001011010
001111001111
110101100001
010010011101
010010101011
111100111111
000110110000
000100100110
100100111001
011100101001
110011100000
100111111001
101011110100
001010101001
011111010110
110010110100
111101011000
100110011000
100100001000
010111100001
111001110011
100110100011
011000011001
000000000100
000010110010
011010111000
010111010000
011000100010
100110011100
101110011000
001100100010
010100111100
001101101010
110111100001
101110010000
000000110100
111010000001
010011001001
000010001100
001001101101
010010000011
011111100110
111010000101
110101110000
010011001100
100101111111
000010001110
111100001011
111100110111
110101000100
000111110111
011100011101
110011101101
000101100111
101100101100
111110101000
000110101011
010110011110
000000111000
100000000100
110101101000
101011100101
101111000000
110111000001
010001100110
110010010100
111011010111
101110011110
111100110000
001101110010
010010100001
000111100110
010000110000
001011010000
110011010100

Here’s my solution:

diagnostic = split.(split(strip(input), "\n"), "")
diagnostic = [parse(Int, diagnostic[i][j])
              for i in 1:length(diagnostic),
                  j in 1:length(diagnostic[1])]

nrow, width = size(diagnostic)

γ =  sum(diagnostic, dims=1) .> nrow/2
ϵ = .!γ
γ = sum([γ[i] * 2^(width - i) for i in 1:width])
ϵ = sum([ϵ[i] * 2^(width - i) for i in 1:width])

out = γ * ϵ
print(out)

I’m flexing Julia’s unicode support here. Using symbol like ϵ and γ in variable names makes the code much nicer to look at!

Part 2

Show challenge - day 3, part 2

Next, you should verify the life support rating, which can be determined by multiplying the oxygen generator rating by the co2 scrubber rating.

Both the oxygen generator rating and the co2 scrubber rating are values that can be found in your diagnostic report - finding them is the tricky part. Both values are located using a similar process that involves filtering out values until only one remains. Before searching for either rating value, start with the full list of binary numbers from your diagnostic report and consider just the first bit of those numbers. Then:

  • Keep only numbers selected by the bit criteria for the type of rating value for which you are searching. Discard numbers which do not match the bit criteria.
  • If you only have one number left, stop; this is the rating value for which you are searching.
  • Otherwise, repeat the process, considering the next bit to the right.

The bit criteria depends on which type of rating value you want to find:

  • To find oxygen generator rating, determine the most common value (0 or 1) in the current bit position, and keep only numbers with that bit in that position. If 0 and 1 are equally common, keep values with a 1 in the position being considered.
  • To find co2 scrubber rating, determine the least common value (0 or 1) in the current bit position, and keep only numbers with that bit in that position. If 0 and 1 are equally common, keep values with a 0 in the position being considered.

For example, to determine the oxygen generator rating value using the same example diagnostic report from above:

  • Start with all 12 numbers and consider only the first bit of each number. There are more 1 bits (7) than 0 bits (5), so keep only the 7 numbers with a 1 in the first position: 11110, 10110, 10111, 10101, 11100, 10000, and 11001.
  • Then, consider the second bit of the 7 remaining numbers: there are more 0 bits (4) than 1 bits (3), so keep only the 4 numbers with a 0 in the second position: 10110, 10111, 10101, and 10000.
  • In the third position, three of the four numbers have a 1, so keep those three: 10110, 10111, and 10101.
  • In the fourth position, two of the three numbers have a 1, so keep those two: 10110 and 10111.
  • In the fifth position, there are an equal number of 0 bits and 1 bits (one each). So, to find the oxygen generator rating, keep the number with a 1 in that position: 10111.
  • As there is only one number left, stop; the oxygen generator rating is 10111, or 23 in decimal.

Then, to determine the co2 scrubber rating value from the same example above:

  • Start again with all 12 numbers and consider only the first bit of each number. There are fewer 0 bits (5) than 1 bits (7), so keep only the 5 numbers with a 0 in the first position: 00100, 01111, 00111, 00010, and 01010.
  • Then, consider the second bit of the 5 remaining numbers: there are fewer 1 bits (2) than 0 bits (3), so keep only the 2 numbers with a 1 in the second position: 01111 and 01010.
  • In the third position, there are an equal number of 0 bits and 1 bits (one each). So, to find the co2 scrubber rating, keep the number with a 0 in that position: 01010.
  • As there is only one number left, stop; the co2 scrubber rating is 01010, or 10 in decimal.

Finally, to find the life support rating, multiply the oxygen generator rating (23) by the co2 scrubber rating (10) to get 230.

Use the binary numbers in your diagnostic report to calculate the oxygen generator rating and co2 scrubber rating, then multiply them together. What is the life support rating of the submarine? (Be sure to represent your answer in decimal, not binary.)

Here’s the solution:

diagnostic = split.(split(strip(input), "\n"), "")
diagnostic = [parse(Int, diagnostic[i][j])
              for i in 1:length(diagnostic),
                  j in 1:length(diagnostic[1])]

function life_support(x::Matrix, f::Function)
    nrow, width = size(x)
    for pos in 1:width
        if nrow == 1
            break
        end
        x = x[x[:, pos] .== f(sum(x[:, pos]), nrow/2),:]
        nrow, width = size(x)
    end
    return sum([x[i] * 2^(width - i) for i in 1:width])
end

out = life_support(diagnostic, >=) * life_support(diagnostic, <)
print(out)

It’s a fun little excercise, to generalize the two algorithms to compute the two components of the answer as a function taking another function as a parameter (>= and < in this case)