AOC Day 9 2021
This is part of a greater series about solving advent of code with spreadsheets.
Part One
As always, read the problem text first.
In summary, part one asks to identify “low cells” in a grid. A low cell has a value less than all cells next to it. The output takes all low cells, changes them by adding 1, and sums.
Solving Part One
This solution requires multiple sheets.
Given a map of data0 …
| A1=6 | A1=2 | A1=3 |
| A1=7 | A1=4 | A1=5 |
| A1=6 | A1=5 | A1=9 |
| MAP |
|---|
(0) Each digit gets a cell via Python.
python3 -c '
import sys
print("\n"
.join([ ",".join(ln.strip())
for ln in sys.stdin ]))
' < data.txt | pbcopy
The first sheet finds low cells.
| A1= AND(MAP!A1 < MAP!B1, MAP!A1 < MAP!A2) |
B1= AND(MAP!B1 < MAP!C1, MAP!B1 < MAP!B2, MAP!B1 < A1) |
C1=AND( MAP!J1 < MAP!J2, MAP!J1 < I1) |
| A2=AND( MAP!A2 < MAP!B2, MAP!A2 < MAP!A3, MAP!A2 < MAP!A1) |
B2=AND( MAP!B2 < MAP!C2, MAP!B2 < MAP!B3, MAP!B2 < MAP!B1, MAP!B2 < MAP!A2) |
C2=AND( MAP!J2 < MAP!I2, MAP!J2 < MAP!J3, MAP!J2 < MAP!J1) |
| A3=AND( MAP!A5 < MAP!B5, MAP!A5 < MAP!A4) |
B3=AND( MAP!I5 < MAP!J5, MAP!I5 < MAP!I4, MAP!I5 < MAP!H5) |
C3=AND( MAP!J5 < MAP!I5, MAP!J5 < MAP!J4) |
| LOW1 |
|---|
This sheet adds one to each cell.
| A1=MAP!A1 + 1 | ← DRAG | ... |
| ↑ DRAG | ↑ DRAG | ... |
| ... | ... | ... |
| RISK |
|---|
A SUMIF combines these sheets.
| SUM | =SUMIF(LOW!A1:J5, RISK!A5:J5) |
|---|
How Part One Works
This is the second day using multiple sheets. Check out the first.
Part Two
Part two asks for basins. Basins are groups of cells all “flowing” to one low cell. If a cell has a value of 9, it does not flow. Otherwise, it belongs to exactly one basin2. The output is the multiplication of the three largest basins’s areas.
A flow isn’t defined. Maybe it means a path of values each lower than the previous. No plateaus (drawn below)!
999999
955549
999999
Solving Part Two
Borders of 9
Handcrafting 8 corner-case formulas is good for content. Part two is more complex. Boxing in the input with 9’s2 enables perfecting one inner equation.
Formulas
Here’s an example map with a border of 9’s.
| 9 | 9 | 9 | 9 |
| 9 | B2 | C2 | 9 |
| 9 | B3 | C3 | 9 |
| 9 | 9 | 9 | 9 |
| MAP |
|---|
The next sheet is the fabled single inner formula. Each cell displays the basin it belongs to. Cells …
- Are basinless (FALSE) if the value is 9.
- Use the basin name of a next-door cell of lower value.
- Or if it’s a low cell, create their own basin name.
| B2=IFS(MAP!B2 = 9,
FALSE, MAP!B2 > MAP!A2, A2, MAP!B2 > MAP!B1, B1, MAP!B2 > MAP!C2, C2, MAP!B2 > MAP!B3, B3, TRUE, COLUMN() + 100 * ROW()) |
← DRAG | ... | |
| ↑ DRAG | ↑ DRAG | ... | |
| BASIN |
|---|
The final sheet fetches basin’s names and areas.
| BASIN NAMES | A2=UNIQUE(FLATTEN3(BASIN!B2:D)) | ← SPILL |
|---|---|---|
| AREA | B2=COUNTIF( FLATTEN(BASIN!B$2:D), "="&A2) |
← SPILL |
These columns mark borders as one basin named “FALSE”. Throwing this out helps find the true three biggest basins.
| ISNT BORDER | C2=NOT(A2=FALSE) | ← DRAG |
|---|---|---|
| LARGEST | D2=LARGE(FILTER(B$2:B, C$2:C), 1) | |
| 2ND L | E2=LARGE(FILTER(B$2:B, C$2:C), 2) | |
| 3RD | F2=above but 3rd biggest | |
| OUT | G2=D2*E2*F2 |
How Part Two Works
Google Sheet’s Circular Reference Detection is Smart
| DATA | A2=1 |
|---|---|
| REF 1 | B2=A2+1 evaluates to 2 |
| REF OF REF 1 | C2=B2+1 evaluates to 3 |
Finding the evaluation order of a chain of cells is hard4. The Google Sheets team has performed a greater miracle: detecting circular references.
| A1=B1 => #REF! (Circular dependency detected.) |
| B1=A1 => #REF! |
This detection is careful. For example, these cells that reference one another work.
| A1=IF(FALSE, B1, 1) => 1 |
| B1=IF(FALSE, A1, 2) => 2 |
This restraint seems to be “dynamic”. For example, the following table errors out ONLY with no data. If there’s a value present in one of DATA1 or DATA2, NON EMPTY DATA 1 and 2 equal that value.
| DATA1 | A2 |
|---|---|
| DATA2 | B2 |
| NONEMPTY DATA1 | C2=IF(ISBLANK(A2), D2, A2) |
| NONEMPTY DATA2 | D2=IF(ISBLANK(B2), C2, B2) |
This is an incredible advantage. Google Sheets finds the individual basin cells that evaluate to a name. It then propagates the names out.
Related Works
I found another advent of coder. They were doing challenges at the other end of the tech stack. Check out their solution to this problem in TensorFlow.
You may be interested in the previous day's solution.