Advent of Code 2021 Day 9 Part 1 in Google Sheets
2022-09-25 • 6 min read
In this article I will explain how I solved Day 9 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:
Where each number corresponds to the height of a particular location, 9 being the highest and 0 being the lowest a location can be.
And our goal is to:
- Find the low points, which are the locations that are lower than any of their adjacent locations.
- Find the risk levels by adding 1 to the height of the low points.
- Sum the risk levels.
* See the full problem for more context.
Generic Formula
=ARRAYFORMULA(SUM(LAMBDA(a,IF(
(a<SPLIT(REGEXREPLACE(LEFT(9&input,length),"(.)","$1❄️"),"❄️"))*
(a<SPLIT(REGEXREPLACE(RIGHT(input&9,length),"(.)","$1❄️"),"❄️"))*
(a<SPLIT(REGEXREPLACE(LEFT({REPT(9,length);ARRAY_CONSTRAIN(input&9,ROWS(input)-1,1)},length),"(.)","$1❄️"),"❄️"))*(a<SPLIT(REGEXREPLACE(LEFT({QUERY(input&9,"offset 1");REPT(9,length)},length),"(.)","$1❄️"),"❄️")),
a,))(SPLIT(REGEXREPLACE(LEFT(input&9,length),"(.)","$1❄️"),"❄️"))))
- input: The puzzle input.
- length: The length of each row of the puzzle input. In our case it's 10 for the test input and 100 for the final input.
So the generic formula for the final input can be rewritten as:
=ARRAYFORMULA(SUM(LAMBDA(a,IF(
(a<SPLIT(REGEXREPLACE(LEFT(9&input,100),"(.)","$1❄️"),"❄️"))*
(a<SPLIT(REGEXREPLACE(RIGHT(input&9,100),"(.)","$1❄️"),"❄️"))*
(a<SPLIT(REGEXREPLACE(LEFT({REPT(9,100);ARRAY_CONSTRAIN(input&9,ROWS(input)-1,1)},100),"(.)","$1❄️"),"❄️"))*(a<SPLIT(REGEXREPLACE(LEFT({QUERY(input&9,"offset 1");REPT(9,100)},100),"(.)","$1❄️"),"❄️")),
a+1,))(SPLIT(REGEXREPLACE(LEFT(input&9,100),"(.)","$1❄️"),"❄️"))))
Explanation
In order to find the low points we have to compare each location with all of its adjacent locations. Since we will be working with arrays and we will therefore be comparing one array with other four (one for each position: left, right, up, down), in order to avoid "Array arguments are of different size" errors, we need all of the arrays to be of the same size and with the given input it's not possible due to the inconsistency with the amount of adjacencies for each location: the locations at the corners have two adjacent locations, the locations at the edges have three adjacent locations and all the other ones have four.
So the first step we take is to normalize the adjacencies, that is, to manipulate the given input in a way that allows us to have the same amount of adjacent locations for each location. This is easily done by creating a border of 9s around the input.
The reason we create a border of 9s and not of 0s or 1s or any other number is because we will determine the low points by doing a bunch of less than comparisons and we don't want the border we created solely to prevent errors to interfere with the output. (There isn't any number from 0 to 9 that 9 is strictly less than).
Step 1 - Normalize the adjacencies by creating a border of 9s around the input
=ARRAYFORMULA({REPT(9,10+2);9&A1:A5&9;REPT(9,10+2)})
The REPT function takes an input and it repeats it n times. In this case it takes 9 and it repeats it 10+2 times, which is the amount of numbers in each row plus 2 to account for the newly created left and right borders.
Step 2 - Split each number into its own cell
Now that we have four adjacent locations for each location, we are almost done with the setup phase, we just have to split every digit into its own cell so we can operate on them independently.
This can be done by placing a placeholder character after each digit and splitting by it. I will be using a snowflake ❄ as the placeholder character.
=ARRAYFORMULA(SPLIT(REGEXREPLACE({REPT(9,10+2);9&A1:A5&9;REPT(9,10+2)},"(.)","$1❄"),"❄"))
Step 3 - Compare each location of the input with all of its adjacent locations
Normally, we would now be able to do the following less than comparisons with our current position c and the corresponding adjacent positions cv and ch:
- [cv,ch] < [cv,ch-1] (left)
- [cv,ch] < [cv,ch+1] (right)
- [cv,ch] < [cv+1,ch] (up)
- [cv,ch] < [cv-1,ch] (down)
cv and ch are respectively the vertical and horizontal coordinates of the current position.
The GIF below is a visual representation of the arrays we are comparing with yellow being our puzzle input.
However, the goal here is to solve the problem using a single formula without relying on any helper cells. So there are some additional steps we have to take.
Step 3.1 - Extract the left, right, up and down arrays
Extract each of the four arrays that we are going to use for the comparison by only referencing the puzzle input.
To extract each array individually we use the same technique adopted in Step 2 along with a combination of LEFT(), RIGHT(), ARRAY_CONSTRAIN() and QUERY(...,"offset X").
Formula to extract the puzzle input (Array 0):
=ARRAYFORMULA(SPLIT(REGEXREPLACE(A1:A5,"(.)","$1❄"),"❄"))
Formula to extract the left array (Array 1):
=ARRAYFORMULA(SPLIT(REGEXREPLACE(LEFT(9&A1:A5,10),"(.)","$1❄"),"❄"))
Formula to extract the right array (Array 2):
=ARRAYFORMULA(SPLIT(REGEXREPLACE(RIGHT(A1:A5&9,10),"(.)","$1❄"),"❄"))
Formula to extract the above array (Array 3):
=ARRAYFORMULA(SPLIT(REGEXREPLACE(RIGHT(ARRAY_CONSTRAIN({REPT(9,10);A1:A5},ROWS(A1:A5),1),10),"(.)","$1❄"),"❄"))
Formula to extract the below array (Array 4):
=ARRAYFORMULA(SPLIT(REGEXREPLACE(RIGHT(QUERY({A1:A5;REPT(9,10)},"offset 1"),10),"(.)","$1❄"),"❄"))
Step 3.2 - Perform the comparisons
We now have everything we need to perform the comparisons which we are going to do with the following IF statement:
=ARRAYFORMULA(IF(
(SPLIT(REGEXREPLACE(A1:A5,"(.)","$1❄"),"❄")<SPLIT(REGEXREPLACE(LEFT(9&A1:A5,10),"(.)","$1❄"),"❄"))*
(SPLIT(REGEXREPLACE(A1:A5,"(.)","$1❄"),"❄")<SPLIT(REGEXREPLACE(RIGHT(A1:A5&9,10),"(.)","$1❄"),"❄"))*
(SPLIT(REGEXREPLACE(A1:A5,"(.)","$1❄"),"❄")<SPLIT(REGEXREPLACE(RIGHT(ARRAY_CONSTRAIN({REPT(9,10);A1:A5},ROWS(A1:A5),1),10),"(.)","$1❄"),"❄"))*
(SPLIT(REGEXREPLACE(A1:A5,"(.)","$1❄"),"❄")<SPLIT(REGEXREPLACE(RIGHT(QUERY({A1:A5;REPT(9,10)},"offset 1"),10),"(.)","$1❄"),"❄")),
SPLIT(REGEXREPLACE(A1:A5,"(.)","$1❄"),"❄"),))
This may seem like a lot but it's actually very simple. All we are doing is checking if the puzzle input is lower than each one of its adjacent locations. If it is, return the puzzle input, if it's not, leave the cell blank.
The resulting array 1, 0, 5, 5 is a visual representation of the location of our low points.
Step 4 - Find the risk levels
We are almost done! In order to find the risk levels we just have to add 1 to each element of the resulting array of the previous step.
=ARRAYFORMULA(IF(
(SPLIT(REGEXREPLACE(A1:A5,"(.)","$1❄"),"❄")<SPLIT(REGEXREPLACE(LEFT(9&A1:A5,10),"(.)","$1❄"),"❄"))*
(SPLIT(REGEXREPLACE(A1:A5,"(.)","$1❄"),"❄")<SPLIT(REGEXREPLACE(RIGHT(A1:A5&9,10),"(.)","$1❄"),"❄"))*
(SPLIT(REGEXREPLACE(A1:A5,"(.)","$1❄"),"❄")<SPLIT(REGEXREPLACE(RIGHT(ARRAY_CONSTRAIN({REPT(9,10);A1:A5},ROWS(A1:A5),1),10),"(.)","$1❄"),"❄"))*
(SPLIT(REGEXREPLACE(A1:A5,"(.)","$1❄"),"❄")<SPLIT(REGEXREPLACE(RIGHT(QUERY({A1:A5;REPT(9,10)},"offset 1"),10),"(.)","$1❄"),"❄")),
SPLIT(REGEXREPLACE(A1:A5,"(.)","$1❄"),"❄")+1,))
Step 5 - Sum the risk levels
The final step is to sum the risk levels. This is easily done with the SUM function.
=ARRAYFORMULA(SUM(IF(
(SPLIT(REGEXREPLACE(A1:A5,"(.)","$1❄"),"❄")<SPLIT(REGEXREPLACE(LEFT(9&A1:A5,10),"(.)","$1❄"),"❄"))*
(SPLIT(REGEXREPLACE(A1:A5,"(.)","$1❄"),"❄")<SPLIT(REGEXREPLACE(RIGHT(A1:A5&9,10),"(.)","$1❄"),"❄"))*
(SPLIT(REGEXREPLACE(A1:A5,"(.)","$1❄"),"❄")<SPLIT(REGEXREPLACE(RIGHT(ARRAY_CONSTRAIN({REPT(9,10);A1:A5},ROWS(A1:A5),1),10),"(.)","$1❄"),"❄"))*
(SPLIT(REGEXREPLACE(A1:A5,"(.)","$1❄"),"❄")<SPLIT(REGEXREPLACE(RIGHT(QUERY({A1:A5;REPT(9,10)},"offset 1"),10),"(.)","$1❄"),"❄")),
SPLIT(REGEXREPLACE(A1:A5,"(.)","$1❄"),"❄")+1,)))
That's all. Thanks for reading.
Go to Generic formula