Advent of Code 2021 Day 9

Try the simulator

The task at hand

Solve for X where

X = a combination of individual counts

1. Sum of risk levels of each low point
2. Product of the size of the three largest basins

Input is

• A multi-line string

It represents

• A 100x100 square area
• Each location is a number between 0-9
• Each number represents an altitude

Part 1: Rounds 1 and 2

I solved this part of the challenge on the day it was released.

In 50 lines of code, my original algorithm looked something like this:

Setup:
  Split the file's contents into an array of strings
    Split each string into an array of characters
      Convert each character into a number 0-9

Create an array to collect low points

Sub-routine to record a low point:
  Add the current number to the array of low points, only if:
    The minimum number among a list of numbers...
    ...is equal to the number at the current location...
    ...and the number in the last location...
    ...of the sorted and reversed list of numbers...
    ...is the number at the current location

For each row in the grid
  For each cell in the row
    Through a series of nested if..else if..else clauses...
    ...call the sub-routine, passing in the appropriate amount of arguments, each referencing the correct adjacent cell values

For each value in the collection of low points
  Update the value to itself plus one
For each value in the incremented collection of low points
  Add the value to an accumulating sum of all previous values

Return the final sum

Round 2: Now only 10 lines of code!

Same setup: process input file into a 2D array of numbers

Set risk level to 0

For each row in the grid
  For each cell in the row
    If the value in the cell is less than...
    ...the minimum number in a list of 2-4 numbers...
    ...resulting from a starting array of four relative coordinates (up one, left one, right one, down one)...
    ...updated to contain the values in each of the cells referenced by those relative coordinates...
    ...filtered to remove undefined values attained by references to cells that are out of boundary
      Increment risk level by the current cell's value plus one

Return risk level

Here's a visual description

Feeling invigorated after refactoring Part 1's code

• I put into practice a slew of new coding tricks I learned from studying other solvers' code in prior challenges
• I resolved a silly mistake in my code that failed to omit cell values that were less than their adjacent cells' values
• I felt proud of the conciseness and eloquence of my code, especially as compared to Round 1

Part 2: Round 1

When it was originally released, I didn't even attempt to solve part 2.

That's because I was unable to understand what was happening in the example diagrams.

This time around - with careful analysis, and perhaps an improved eye for interpreting puzzle instructions - I understood how the size of each basin was determined.

Two ways to solve

1. Use Find in my browser with the query 9 and my eyes to identify the largest basins and tally the sizes manually
2. Write an algorithm that tallies each basin size after processing the entire grid area

Obviously, I felt motivated to solve it via #2.

Defining what the algorithm should return

21   AA 
39   A

Given the input on the left, the algorithm should find a basin of size 3

219   AA   
399   A 
996     B  

Given the input above, the algorithm should two basins: one of size 3, another of size 1

89876995   A BBB  C 
93987896    D BBB C
54598939   DDD B E 
95999123    D   EEE
89891019   F G EEE

Given the input above, the algorithm should seven basins with sizes: 1,7,2,5,7,1,1

9299999    A      
9193939    A A A
9012349    AAAAA
9101999    AAA
9912329     AAAA
9999939        A

Given the input above, the algorithm should find a basin of size 17

And, of course, the example provided:

2199943210  AA   BBBBB
3987894921  A CCC B BB
9856789892   CCCCC D B
8767896789  CCCCC DDD
9899965678   C   DDDDD

Given the input above, the algorithm should four basins with sizes: 3,9,9,14

Describing how this algorithm should work

Create a unique set to track visited locations
Create an empty list to track basin sizes
For each row in the grid
  For each cell in the row
    If the cell's value is not 9, and its coordinates are not in the list of traversed cells:
      * For each of 2-4 cells above, left, right and below it:
        If the cell's value is 9:
          Return the locations visited along the way to this cell
        Else if the cell's value is 1 higher or lower than the source cell's value:
          Continue at * with the current list of visited locations
    Add to the list of basins:
      The size of the unique set of visited locations in the basin that this cell resides
For each size in basins
  Sort the list of basins from largest to smallest
    Extract the largest three values
      Return the product of all three values

Delight, then disappointment

• Running my algorithm on each of the samples above produces the correct output: it found each basin and determined the size correctly
• Sadly, when I ran my algorithm on my input, the answer it generated was too low
• To diagnose, I searched for a large-looking basin in my output. I found one at the bottom. I counted the values. I ran my algorithm. I found a problem.

UPDATED: Then extreme delight!

I solved it later the same day! See my revised notes below to learn how I stumbled upon - and resolved - my algorithm's error.

A summary of my journey through this challenge

• I solved Part 1 a while ago
• At that time, I didn't understand Part 2 enough to even attempt it
• Now, I solved Part 1 with an algorithm 1/5 the original's size!
• I actually understand what's happening in Part 2
• I wrote an algorithm that generates the correct answer on several small example data sets
• I discovered an example basin that my algorithm doesn't properly compute, in case I ever want to come back and meticulously debug it

My reflection from before solving Part 2:

It's a bummer that I couldn't solve Part 2.

I'm definitely proud of how much progress and practice this challenge offered me.

Now, it's time to move on.

Part 2: Round 2

• I came back later the same day to investigate how my algorithm processed that basin
• I discovered a new truth about the numbers in the grid: they may not always change by 1 from cell to cell
• I removed parts of my code that were overly conditional
• I generated the correct answer for Part 2!
• Bonus: I made another simulator to show the low points and basins for any valid grid

My reflection from after solving Part 2:

Just kidding!

It turns out, I couldn't let this puzzle go unsolved.

Luckily, with a simple logging statement, I could see which locations my algorithm started from.

Upon reviewing the first unexpected starting location, I noticed it was a difference of 2 from each of its adjacent cells.

I assumed there was only ever a difference of 1.

I removed that condition from my code.

Viola! My algorithm now calculated the correct - larger - sizes of each basin...and thus determined the correct product of the three largest basins

What a huge relief, fantastic sense of closure, and an incredibly rewarding personal achievement!

Bonus for code golf fans: my final code for both solutions is only 40 lines.

Next!