1. Mathias Kools
2. Advent of Code 2021 in Spreadsheets
3. AOC Day 3 2021

AOC Day 3 2021

This is part of a greater series about solving advent of code with spreadsheets.

Foreword

There was a lot of repetitive work in this challenge. Easy enough in sheets but not easy on readers. Particularly on the number of bits …

• The author’s examples use 5.
• The challenge input used 12.
• The written solution will demo 3.

Part One

As always, read the problem text first. In summary, the input is a list of binary numbers (of the same length). The goal is to find, for each binary place, the most and least common values.

The number gamma uses the common bits. The number epsilon uses the least common bits.

Finally, multiply gamma by epsilon.

Solving Part One

Input parsing is boring and repetitive. Skip!⁰

Data is ready as the following columns.

DATA BIT 0	B2 (e.g 1)	...
BIT 1	C2 (e.g 0)	...
2	D2 (e.g 1)	...

Each individual gamma bit is calculated like the following.

GAMMA BIT 0	H2 = ROUND(AVERAGE(B2:B))
BIT 1	I2 = ROUND(AVERAGE(C2:C))
2	J2 = repeat ↓

All those bits become a number like this.

GAMMA	H4 = BIN2DEC(CONCATENATE(H2:J2))
EPSILON	I4 = (2^4 - 1) - H4
OUTPUT	J4 = H4 * I4

How Part One Works

Most of the cleverness is with binary.

AVERAGE

First, why is the AVERAGE rounded the most common value?

A is the count of 1s. Z is the count of 0s.

The average equals …

• = (1A + 0Z) / (A + Z)
• = A / (A + Z)

Case by case analysis shows …¹

• If A > Z then …
  • A + Z < A + A = 2A
  • With the average gives A / (A + Z) > A / (A + A) = 1/2.
  • The average is greater than 1/2 and will round to 1.
• If A < Z then …
  • Flipping inequality signs gives A / (A + Z) < A / (A + A) = 1/2
  • The average is less than 1/2 and will round to 0.

We ignore the particular case that A = Z. The author didn’t provide guidance on ties. And in fact no inputs need tie-breaking.

BIN2DEC Limitations

The function BIN2DEC converts binary to decimal. It is particular about input …

• It expects a signed² binary string.
• The string can contain at most 10 digits.

The second condition is a problem. The demo uses 3 bits, but the challenge input uses 12.

The solution is to convert to decimal in pieces.

• Get the first 6 bits with LEFT.
• Get the second 6 bits with RIGHT.
• Convert the halves and combine the results.
  • 2^6 * BIN2DEC(LEFT(range, 6)) +
BIN2DEC(RIGHT(range, 6))

Epsilon From Gamma

This solution uses trickery to calculate epsilon. A single cell flips the bits of gamma. When 0 and 1 are the only options this works to get the less common value.

To flip bits in binary use subtraction. This subtraction is converted into decimal.

  11111  →   (2^6 - 1)
- gamma     -    gamma
-------     ----------

Part Two

Part two requires much more effort.

In summary the objective is still to get two bitstrings

• One of them is called oxygen.
• The second is called carbon.

Instead of building these however, the twist is that they’re already in the input.

Each desired number requires multiple passes and filters on the input.

• These passes happen at each bit position.
• These passes keep occurring until only one line of input remains (not necessarily at the final position).

In an extreme attempt to be concise, only the solution for oxygen will be shown. The solution for carbon requires only sign switches and replacing some 1s with 0s.

For oxygen …

• Each pass selects lines of input using the most common value in that bit position.
• If there are tie breaks, the “most common value” is 1.

The final output is the multiplication of oxygen and carbon of course.

Solving Part Two

The same data table is used with slightly different coordinates. This change is necessary for a new row later. Additionally, the column the bits come from is included.

DATA	A1	...
DATA BIT 0	B4 (e.g 1)	...
BIT 1	C4 (e.g 0)	...
2	D4 (e.g 1)	...

For each bit there is a column …

• Calculating the most common bit of all lines left.
• With repeating formulas checking if the input has that most common bit.

1 MORE COMMON	GC BIT	pass
G1 = SUM(B4:B) >=COUNT(B4:B)/2	G2 = IF(G1,1,0)	1	G4 = B4=G$2	rep →
H1 = SUMIF(G4:G,"=TRUE",C4:C) >=COUNTIF(G4:G,"=TRUE")/2	repeat ↓	2	H4 = AND(B4,C3=H$2)	rep →
repeat ↓	repeat ↓	rep ↓	repeat ↓	rep ↘

Finally, there is a cell finding what binary number passes the most checks.

PASSES	L4 = COUNTIF(G4:I4,"=TRUE")
OXYGEN STR	M4 = INDEX(A4:A, MATCH(MAX(L4:L),L4:L,0))

Converting that oxygen binary number to decimal is left out.

How Part Two Works

SUM >= COUNT/2

Comparing SUM(B4:B) to COUNT(B3:B)/2 is a slight re-working of AVERAGE in part 1⁴. SUM becomes SUMIF on the second pass to prevent summing across rows already filtered out.

Why not FILTER

The FILTER function⁵ could power alternative solutions. This function takes a range and returns a range matching a criteria.

Here’s a sample. The list starts at 3 values: 1, 5, and 10.

• After the first FILTER the list is 5 and 10.
• After the second one the list is just 5.

DATA	A2 = 1	5	10
> 4	B2 = A2>4 => FALSE	TRUE	TRUE
FILTER > 4	C2 = FILTER(A2:A, B2:B) => 5	10
< 6	D2 = C2 < 6 => TRUE	FALSE
FILTER < 6	E2 = FILTER(C2:C, D2:D) => 5

Ultimately, FILTER wasn’t the right fit.

The Famous Duo INDEX and MATCH

In the spreadsheet world there might not be a better duo than INDEX and MATCH.

• MATCH gives the row number a “match” occurs at (the third parameter adjusts what “match” means).
• INDEX gives the value in a range at that row.

Combined they allow you to look up cells by a different column⁶. For programming folk if you were writing a SQL statement to SELECT one row …

• MATCH gives you WHERE functionality on one column
• INDEX gives you SELECT functionality on one column

Unpacking this formula M4 = INDEX(A4:A, MATCH(MAX(L4:L), L4:L, 0)) …

• MAX(L4:L) returns the maximum number in the range L4:L.
• MATCH(MAX(L4:L), L4:L, 0) then returns the row (relative to the range) that maximum value is at.
• INDEX(A4:A, MATCH(MAX(L4:L), L4:L, 0)) is a lookup for what input in the range A4:A created this maximum value.

You may be interested in the previous or next day's solution.