Advent of Code 2021 Day 3 Part 1 in Google Sheets

2022-09-07 • 5 min read

In this article I will explain how I solved Day 3 Part 1 of Advent of Code 2021 in Google Sheets using a single formula.

Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like. People use them as a speed contest, interview prep, company training, university coursework, practice problems, or to challenge each other. Read more...

In this puzzle we are given an input in the following form:

And we are asked to find the gamma rate, the epsilon rate, multiply them together and convert the result to base10.

The gamma and epsilon rates are defined as being respectively the most and least common bits in the corresponding positions of each number. In the example above, the gamma rate is 10110 and the epsilon rate is 01001.

* The full problem can be found here.

Generic Formula

=ARRAYFORMULA(
  PRODUCT(
    MMULT(
      TRANSPOSE(
        IF(
          MMULT(
            TRANSPOSE(SPLIT(REGEXREPLACE(INPUT,"(.)","$1❄️"),"❄️")),
            SEQUENCE(ROWS(INPUT),1,1,0))>(ROWS(INPUT)/2),
          {1,0},
          {0,1})*
        2^SEQUENCE(LENGTH,1,LENGTH-1,-1)),
      SEQUENCE(LENGTH,1,1,0))))

INPUT: Range containing the puzzle input.
LENGTH: Integer specifying the amount of bits each number in the puzzle input contains. In our case it's 5 for the test input and 12 for the final input.

So the generic formula for the final input can be rewritten as:

=ARRAYFORMULA(
  PRODUCT(
    MMULT(
      TRANSPOSE(
        IF(
          MMULT(
            TRANSPOSE(SPLIT(REGEXREPLACE(INPUT,"(.)","$1❄️"),"❄️")),
            SEQUENCE(ROWS(INPUT),1,1,0))>(ROWS(INPUT)/2),
          {1,0},
          {0,1})*
        2^SEQUENCE(12,1,11,-1)),
      SEQUENCE(12,1,1,0))))

Warning

When copying and pasting the puzzle input into the spreadsheet, make sure that the range is formatted as plain text, otherwise the leading zeros will be removed and the formula won't return the correct output.

Explanation

Step 1 - Distribute each digit into its own cell

The first step is to distribute every digit into its own cell. This is done by inserting a placeholder character after every digit and splitting by it.

I will be using a snowflake ❄️ as the placeholder character.

=ARRAYFORMULA(SPLIT(REGEXREPLACE(A2:A13,"(.)","$1❄️"),"❄️"))

Step 2 - Sum the corresponding digits

The second step consists of summing all the corresponding bits from left to right, which will tell us the amount of 1s of each bit of our input.

An array formula column-by-column sum can be done with a matrix multiplication.

First matrix

The first matrix is the transposed distributed input generated with

=ARRAYFORMULA(TRANSPOSE(SPLIT(REGEXREPLACE(A2:A13,"(.)","$1❄️"),"❄️")))

Second matrix

The second matrix is a sequence of twelve 1s generated with

=SEQUENCE(12,1,1,0)

Now we enter these two matrices as arguments of MMULT(). The resulting matrix will have the number of rows of the first matrix (5) and the number of columns of the second matrix (1) and it will tell us the sum of 1s of each column of our input.

=ARRAYFORMULA(MMULT(TRANSPOSE(SPLIT(REGEXREPLACE(A2:A13,"(.)","$1❄️"),"❄️")),SEQUENCE(12,1,1,0)))

Step 3 - Determine the Gamma and Epsilon rates

We will use the information from the previous step to determine whether each bit of the gamma and epsilon rates is 1 or 0.

This can be done with the following IF statements:

Gamma rate

If the sum of 1s is greater than the size of the input divided by two, return 1, otherwise return 0.

=ARRAYFORMULA(IF(MMULT(TRANSPOSE(SPLIT(REGEXREPLACE(A2:A13,"(.)","$1❄️"),"❄️")),SEQUENCE(12,1,1,0))>6,1,0))

Epsilon rate

If the sum of 1s is greater than the size of the input divided by two, return 0, otherwise return 1.

=ARRAYFORMULA(IF(MMULT(TRANSPOSE(SPLIT(REGEXREPLACE(A2:A13,"(.)","$1❄️"),"❄️")),SEQUENCE(12,1,1,0))>6,0,1))

The way Google Sheets deals with array functions allows us to reduce the two formulas above into a single one by using {curly brackets arrays} in the return fields of our IF statement.

=ARRAYFORMULA(IF(MMULT(TRANSPOSE(SPLIT(REGEXREPLACE(A2:A13,"(.)","$1❄️"),"❄️")),SEQUENCE(12,1,1,0))>6,{1,0},{0,1}))

Step 4 - Convert the Gamma and Epsilon rates to base10

Now that we know the gamma and epsilon rates, we have to convert them to base10. The most intuitive approach to this step would be to use the BIN2DEC() function, a function specifically designed to convert binary numbers to decimal. But while this can be done on the test input, it cannot be done on the final input as the function comes with the limitation of only allowing conversions up to 10 bits and our final input is 12 bits long.

So the approach we take is to convert them in the standard way. We take our previous formula and multiply it by 2^SEQUENCE(5,1,4,-1), the latter returns the following: 2^4=16; 2^3=8; 2^2=4; 2^1=2; 2^0=1 which multiplied by our binary gamma and epsilon rates it gives us the corresponding decimal value of each digit.

=ARRAYFORMULA(IF(MMULT(TRANSPOSE(SPLIT(REGEXREPLACE(A2:A13,"(.)","$1❄️"),"❄️")),SEQUENCE(12,1,1,0))>6,{1,0},{0,1})*2^SEQUENCE(5,1,4,-1))

We then add these numbers together by performing another matrix multiplication similar to the one in the second step.

=ARRAYFORMULA(MMULT(TRANSPOSE(IF(MMULT(TRANSPOSE(SPLIT(REGEXREPLACE(A2:A13,"(.)","$1❄️"),"❄️")),SEQUENCE(12,1,1,0))>6,{1,0},{0,1})*2^SEQUENCE(5,1,4,-1)),SEQUENCE(5,1,1,0)))

Step 5 - Multiply the Gamma and Epsilon rates together

Now that we have the corresponding decimal values of the gamma and epsilon rates, the final step is to multiply them together. This is easily done with the PRODUCT() function.

=ARRAYFORMULA(PRODUCT(MMULT(TRANSPOSE(IF(MMULT(TRANSPOSE(SPLIT(REGEXREPLACE(A2:A13,"(.)","$1❄️"),"❄️")),SEQUENCE(12,1,1,0))>6,{1,0},{0,1})*2^SEQUENCE(5,1,4,-1)),SEQUENCE(5,1,1,0))))

That's all. Thanks for reading.

Go to Generic Formula

Previous Post Next Post