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

AOC Day 5 2021

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

Part One and Two

As always, read the problem text first. In summary, the input is a list of line segments made by two points. The goal is to count the number of points where at least two lines overlap.

The data uses some simplifications …

• Each line is horizontal, vertical, or diagonal (slope of 1 or -1)⁰.
• Everything happens on integer coordinates.
• Every line fits within a known square box.
  • The example has line segments between (0,0) and (10,10).
  • The challenge is mostly between (0,0) and (100, 100)¹.

Part one asks to count unique intersections of horizontal and vertical lines only. Part two removes that filter.

Solving Part One and Part Two

The solution makes a grid of numbers. This creates a picture like the author’s example². Each cell is a single point. Lines of 1’s represent a single line segment. 2 or more’s represent intersections. 0 replaces “."’s to depict empty points.

.......1..
..1....1..
..1....1..
.......1..
.112111211
..........
..........
..........
..........
222111....

The line segments are parsed into the following columns.

X1	D2	...
Y1	E2	...
X2	F2	...
Y2	G2	...

These 5 columns classify the type of line.

HORIZONTAL	H2 = E2=G2	repeat →
VERTICAL	I2 = D2=F2	repeat →
SLOPE	J2 = (G2 - E2)/(F2 - D2)	repeat →
BL TR DIAG	K2 = IFERROR(J2=1,FALSE)	repeat →
TL BR DIAG	L2 = IFERROR(J2=-1,FALSE)	repeat →

These 5 columns will help figure out if a line exists at a point or not.

MIN X	M2 = MIN(D2,F2)	repeat →
MAX X	N2 = MAX(D2,F2)	repeat →
MIN Y	O2 = MIN(E2,G2)	repeat →
MAX Y	P2 = MIN(E2,G2)	repeat →
Y INTERCEPT	Q2 = IFERROR( E2 - D2 * J2, "vertical")	repeat →

This table uses an x-offset defined by cell AA1. More on this later.

The cells of the map work like this. This includes the diagonal lines. To remove them for part one take away the last 2 terms of the sum.

AA1	AA2 = AA1	AA3 = AA2 + 1
0	AB2 = COUNTIFS($H$2:$H,"=TRUE", $M$2:$M,"<="&AB$1, $N$2:$N,">="&AB$1, $O$2:$O,"="&$AA2) + COUNTIFS($I$2:$I,"=TRUE", $M$2:$M,"="&AB$1, $O$2:$O,"<="&$AA2, $P$2:$P,">="&$AA2) + COUNTIFS($K$2:$K,"=TRUE", $M$2:$M,"<="&AB$1, $N$2:$N,">="&AB$1, $Q$2:$Q,"="&($AA2-AB$1)) + COUNTIFS($L$2:$L,"=TRUE", $M$2:$M,"<="&AB$1), $N$2:$N,">="&AB$1), $Q$2:$Q,"="&($AA2+AB$1))	repeat →

This cell counts the number of points where at least two lines intersect.

>=2 INTERSECTIONS

R2 = COUNTIF(AB2:AL, ">=2")

How Part One and Part Two Works

There are two new concepts at work here.

IFERROR

Errors in spreadsheets are poison. If one cell errors most uses of it will also error. For example, this table is full of errors.

DATA	A2 = 1/0 => #DIV/0!
USE1	B2 = A2 + 10 => #DIV/0!
USE2	C2 = A2=10 => #DIV/0!

IFERROR checks if the value is in error and returns a new value if so. This cleans out divide by 0’s from vertical line slopes.

Slices

The challenge had lines between (0,0) and (1000,1000). To recreate the author’s map each point requires a cell. This doesn’t scale well. The sheet would need 1,000,000 cells. When I tried a million cells the program froze.

Instead of all this, the sheet deals in “slices”. Each map cell is independent of other map cells and so it’s possible to “batch” maps³. I chose to deal in 50 columns by 1000 row slices. Each slice took about 20 seconds so I was through 20 of them in no time⁴.

Unpacking COUNTIFS

There are four COUNTIFS in each cell of the map. Each of them …

• Counts the number of line segments overlapping with the point.
• Belongs to a different type of line.

Two of these are worth unpacking.

The first formula is for horizontal lines. It has four criteria.

• This COUNTIFS($H$2:$H,"=TRUE", checks that the line is HORIZONTAL (column H).
• $M$2:$M,"<="&AB$1, checks that the x of the cell is within the line’s MINX (column M).⁵
• $N$2:$N,">="&AB$1, checks that the x is within the line’s MAXX(column N).
• $O$2:$O,"="&$AA2 checks the y of the cell is equal to the line’s y (column O is MINY).

The second formula is for diagonals with a slope of 1. It too uses four criteria.

• COUNTIFS($K$2:$K,"=TRUE", is familiar. It checks if the line is a BL-TR DIAG (column K).
• $M$2:$M,"<="&AB$1), and $N$2:$N,">="&AB$1, are repeats as well. This checks min’s and max’s on x.
• $Q$2:$Q,"="&($AA2-AB$1) is the special sauce. This checks if a line with a slope of 1 intersected the cell if it would have the same y intercept.

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