Smoke Basin - Advent of Code 2021 Day 9

 

Tokyo Skytree

Todays' Advent of Code problem requires us to find the lowest points in a height map and also to figure out the size of the basin surrounding the lowest points

Understanding the problem

The input consists of a 2D array with numbers from 0 to 9.  

For the first part we are required to find the point that is lower than all its adjacent neighboring points.

For the second part we are required to find the encompassing basin. Each basin is bounded by 9

Solving it

I've been solving the past few problems in Python, and decided to give GoLang a try this time around. My experience in Go is very limited and this solution comes courtesy of multiple open tabs of Go searches in Google 

The entire source code can be found here -

https://github.com/jasoncoelho/adventOfCode2021/blob/main/9/run.go

In order to solve the first part we need to iterate over all the elements in the 2D array and determine if it is less than all adjacent cells. The key aspect of this solution is the following function that checks the adjacent neighbors

func isLowPoint(row int, col int, twoDArray [][]string) bool {

	var curCell = getCellVal(row, col, twoDArray)

	// check neighbors to determine if this is a low point
	// only need to compare adjacent locations
	if curCell < getCellVal(row-1, col, twoDArray) &&
           curCell < getCellVal(row, col-1, twoDArray) && 
           curCell < getCellVal(row, col+1, twoDArray) &&
           curCell < getCellVal(row+1, col, twoDArray) {
		return true
	}

	return false
}

I haven't shown it here, but it is also possible to slightly optimize the iteration by skipping cells in the iteration after discovering a low point.

The second part requires a recursive function that expands upon the low point by visiting all adjacent neighbors until we reach a cell containing 9.We mark all visited neighbors so that we don't count them more than once and end up in an infinite recursion. These steps are implemented in the following function -

func getBasinSize(row int, col int, twoDArray [][]string) int {

	var cellVal int = getCellVal(row, col, twoDArray)

	if cellVal >= 9 || cellVal == -1 {
	    return 0
	}

	twoDArray[row][col] = strconv.Itoa(-1) // mark cell visited

	var northVal = getBasinSize(row-1, col, twoDArray)
	var southVal = getBasinSize(row+1, col, twoDArray)
	var eastVal = getBasinSize(row, col+1, twoDArray)
	var westVal = getBasinSize(row, col-1, twoDArray)

	return 1 + northVal + southVal + eastVal + westVal
}