phpdev.uk: Advent of Code

2022 Day 8

Posted on Dec 8, 2022

Part 1

Problem

From a grid of trees (with heights), count the trees that are visible from outside the grid.

General solution

First we need to design our data structures. A grid is perhaps most easily represented as a 2 dimensional array, both from a conceptual perspective and also it is likely to be efficient because requests will have locality of reference (we will often be looking at values near to each other).

The data we need to store about trees are:

  • Position on the grid: This will be covered by the indexes on the grid array.
  • Height of the tree: A single digit unsigned integer (a negative height would be nonsensical).

We could also store whether the tree is visible from outside the grid, or we can calculate this on the fly. However, at this point we don’t know what part 2 of the problem will be, so we should create a data structure to represent a tree in case we need to expand on it later.

Solution: Go

First of all, we need to define our data structure for a tree, because the grid will consist of trees:

type Tree struct {
    Height  int
    Visible bool
}

We then need to create the grid. We have two choices here:

  • Slice: Slices can grow and shrink dynamically, so we could build a slice of slices (for 2 dimensions) as we read in the file.
  • Array: Array sizes are fixed at point of creation.

In theory an array might be more efficient, as we only need to allocate memory for it once (since we know the size). However, this would mean reading in the file first to find out the two dimensions (number of rows and number of digits in each row). In Go, array sizes must also be an expression that can be computed at compile time - unlike other languages where a run time expression is permitted (even C allows this, although C11 removed the requirement to support variable length arrays). So we will have to fall back on slices.

Fortunately in Go slices are easy to define, as they are backed by an array and therefore the syntax is similar:

grid := [][]Tree{}

Populating the grid is straightforward - each line in the file is a row, and each digit within the line is a column. As this is a grid, we can assume that the number of columns is equal for each row. Reading in a file line by line is something we have done many times, and extracting each character (which we have to convert to an integer) is also straightforward using strings.Split with the empty string as the separator (as with previous solutions, we don’t need to worry about the difference between characters and UTF-8 sequences).

scanner := bufio.NewScanner(os.Stdin)

// Read in each line and convert into grid structure
for scanner.Scan() {
    line := strings.TrimSpace(scanner.Text())

    // Only process line if we have content, as we may have an
    // empty line at the end of the file
    if len(line) > 0 {
        gridRow := []Tree{}
        trees := strings.Split(line, "")

        for t := range trees {
            height, _ := strconv.Atoi(trees[t])

            tree := Tree{
                Height:  height,
                Visible: false,
            }

            gridRow = append(gridRow, tree)
        }

        grid = append(grid, gridRow)
    }
}

Now that we have the grid setup, we need to process each tree and mark it as visible. This is a straightforward two level loop (rows and columns) to get each tree, and then we need to check if there is a clear line of shorter trees between the current tree and the side of the grid.

The generic way to check for a clear line of shorter trees is to count the shorter trees between the current tree and each side of the grid. If the number of shorter trees is equal to the number of trees, the current tree is visible. For example, to check all the trees to the left of the current tree:

if !grid[row][column].Visible {
    leftTreeTotalCount := row
    leftTreeShorterCount := 0

    for leftRow := 0; leftRow < row; leftRow++ {
        if grid[leftRow][column].Height < grid[row][column].Height {
            leftTreeShorterCount++
        }
    }

    if leftTreeShorterCount == leftTreeTotalCount {
        grid[row][column].Visible = true
    }
}

We check whether the tree is already visible before looking at other trees, because a tree is visible if it can be seen from anywhere outside of the grid. If a tree is visible from multiple locations (e.g. the tree at the top left of the grid), we only mark it as visible once.

We can also add a special case for trees at the edge of the grid, which by definition will always be visible:

if row == 0 || row == gridRows-1 || column == 0 || column == gridColumns-1 {
    grid[row][column].Visible = true
}

This is literally an edge case.

Finally, we iterate over the grid and count the number of visible trees:

visibleTreeCount := 0

for row := range grid {
    for column := range grid[row] {
        if grid[row][column].Visible {
            visibleTreeCount++
        }
    }
}

We could have kept a count as we marked trees as visible, but separating the two steps allows flexibility if part 2 changes one part of the process.

Complete solution:

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	type Tree struct {
		Height  int
		Visible bool
	}

	grid := [][]Tree{}

	scanner := bufio.NewScanner(os.Stdin)

	// Read in each line and convert into grid structure
	for scanner.Scan() {
		line := strings.TrimSpace(scanner.Text())

		// Only process line if we have content - may have an empty line at the end of the file
		if len(line) > 0 {
			gridRow := []Tree{}
			trees := strings.Split(line, "")

			for t := range trees {
				height, _ := strconv.Atoi(trees[t])

				tree := Tree{
					Height:  height,
					Visible: false,
				}

				gridRow = append(gridRow, tree)
			}

			grid = append(grid, gridRow)
		}
	}

	gridRows := len(grid)
	gridColumns := len(grid[0])

	// Scan the grid and mark trees as visible
	for row := range grid {
		for column := range grid[row] {
			// If the tree is at the edge of the grid, it is always visible
			if row == 0 || row == gridRows-1 || column == 0 || column == gridColumns-1 {
				grid[row][column].Visible = true
			} else {
				// Tree is not at the edge of the grid, so we need to check all trees
				// to the left, right, up, and down
				// We can stop once a tree is visible from any direction

				// Left
				if !grid[row][column].Visible {
					leftTreeTotalCount := row
					leftTreeShorterCount := 0

					for leftRow := 0; leftRow < row; leftRow++ {
						if grid[leftRow][column].Height < grid[row][column].Height {
							leftTreeShorterCount++
						}
					}

					if leftTreeShorterCount == leftTreeTotalCount {
						grid[row][column].Visible = true
					}
				}

				// Right
				if !grid[row][column].Visible {
					rightTreeTotalCount := (gridRows - 1) - row
					rightTreeShorterCount := 0

					for rightRow := gridRows - 1; rightRow > row; rightRow-- {
						if grid[rightRow][column].Height < grid[row][column].Height {
							rightTreeShorterCount++
						}
					}

					if rightTreeShorterCount == rightTreeTotalCount {
						grid[row][column].Visible = true
					}
				}

				// Up
				if !grid[row][column].Visible {
					upTreeTotalCount := column
					upTreeShorterCount := 0

					for upColumn := 0; upColumn < column; upColumn++ {
						if grid[row][upColumn].Height < grid[row][column].Height {
							upTreeShorterCount++
						}
					}

					if upTreeShorterCount == upTreeTotalCount {
						grid[row][column].Visible = true
					}
				}

				// Down
				if !grid[row][column].Visible {
					downTreeTotalCount := (gridColumns - 1) - column
					downTreeShorterCount := 0

					for downColumn := gridColumns - 1; downColumn > column; downColumn-- {
						if grid[row][downColumn].Height < grid[row][column].Height {
							downTreeShorterCount++
						}

						if downTreeShorterCount == downTreeTotalCount {
							grid[row][column].Visible = true
						}
					}
				}
			}
		}
	}

	// Scan the grid and count visible trees
	// We could have done this in the previous step, but we are keeping the
	// two operations (mark and count) separate in case part 2 requires
	// different processing
	visibleTreeCount := 0

	for row := range grid {
		for column := range grid[row] {
			if grid[row][column].Visible {
				visibleTreeCount++
			}
		}
	}

	fmt.Println(visibleTreeCount)
}

Part 2

Problem

For each tree in the grid, count the number of trees in each direction (left, right, up, and down) until we reach one of the following:

  1. A tree which is the same height or taller than the current tree.
  2. The edge of the grid.

Count the number of trees, including the tree which caused us to stop. This is the viewing distance is that direction. Calculate the product of the viewing distances for each tree (the scenic score), then find the tree with the highest product.

General solution

Creating the grid will be the same as part 1, however our logic for processing the grid will be different. We will move outwards from each tree in each direction (instead of inwards from the edges of the grid), but we will stop as soon as we have found a tree the same height or taller, or have reached the edge of the grid.

Solution: Go

First of all, we need to add a scenic score field to our tree struct, and we can also remove the visible field because it is no longer required:

type Tree struct {
    Height      int
    scenicScore int
}

Our processing of the input into the grid structure is the same as before. We do not need to set a default value for the scenic score, as Go will automatically initialise int fields as 0.

Once we have the grid, we need to examine each tree and calculate its viewing distances, and then its scenic score. To calculate the viewing distance on the left:

leftViewingDistance := 0

// Left
for leftRow, leftHigherTreeFound := row-1, false; leftRow >= 0 && !leftHigherTreeFound; leftRow-- {
    if grid[leftRow][column].Height >= grid[row][column].Height {
        leftHigherTreeFound = true
    }

    leftViewingDistance++
}

We start from the tree next to the current tree, then work outwards until we find a tree which is taller, or when we reach the edge (row 0) - whichever comes first.

As before, we can handle trees at the edge of the grid as a special case. They will always have a scenic score of zero, since at least one of their viewing distances will be zero, and the product of a set of numbers including zero will always be zero.

if row == 0 || row == gridRows-1 || column == 0 || column == gridColumns-1 {
    grid[row][column].scenicScore = 0
}

Strictly speaking, we do not need to set the scenic score, as it will already have a score of zero because of the default initialisation, however explicitly setting the score here makes our intention clearer.

Finding the highest scenic score is straightforward, as we iterate over the grid and check each score against the current highest score:

highestScenicScore := 0

for row := range grid {
    for column := range grid[row] {
        if grid[row][column].scenicScore > highestScenicScore {
            highestScenicScore = grid[row][column].scenicScore
        }
    }
}

Full solution:

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	type Tree struct {
		Height      int
		scenicScore int
	}

	grid := [][]Tree{}

	scanner := bufio.NewScanner(os.Stdin)

	// Read in each line and convert into grid structure
	for scanner.Scan() {
		line := strings.TrimSpace(scanner.Text())

		// Only process line if we have content - may have an empty line at the end of the file
		if len(line) > 0 {
			gridRow := []Tree{}
			trees := strings.Split(line, "")

			for t := range trees {
				height, _ := strconv.Atoi(trees[t])

				tree := Tree{
					Height: height,
				}

				gridRow = append(gridRow, tree)
			}

			grid = append(grid, gridRow)
		}
	}

	gridRows := len(grid)
	gridColumns := len(grid[0])

	// Scan the grid and mark trees as visible
	for row := range grid {
		for column := range grid[row] {
			// If the tree is at the edge of the grid, it will always have
			// a scenic score of zero
			if row == 0 || row == gridRows-1 || column == 0 || column == gridColumns-1 {
				grid[row][column].scenicScore = 0
			} else {
				// Tree is not at the edge of the grid, so we need to check all trees
				// to the left, right, up, and down, moving outwards from the tree
				leftViewingDistance := 0
				rightViewingDistance := 0
				upViewingDistance := 0
				downViewingDistance := 0

				// Left
				for leftRow, leftHigherTreeFound := row-1, false; leftRow >= 0 && !leftHigherTreeFound; leftRow-- {
					if grid[leftRow][column].Height >= grid[row][column].Height {
						leftHigherTreeFound = true
					}

					leftViewingDistance++
				}

				// Right
				for rightRow, rightHigherTreeFound := row+1, false; rightRow < gridRows && !rightHigherTreeFound; rightRow++ {
					if grid[rightRow][column].Height >= grid[row][column].Height {
						rightHigherTreeFound = true
					}

					rightViewingDistance++
				}

				// Up
				for upColumn, upHigherTreeFound := column-1, false; upColumn >= 0 && !upHigherTreeFound; upColumn-- {
					if grid[row][upColumn].Height >= grid[row][column].Height {
						upHigherTreeFound = true
					}

					upViewingDistance++
				}

				// Down
				for downColumn, downHigherTreeFound := column+1, false; downColumn < gridColumns && !downHigherTreeFound; downColumn++ {
					if grid[row][downColumn].Height >= grid[row][column].Height {
						downHigherTreeFound = true
					}

					downViewingDistance++
				}

				// Calculate the scenic score as the product of viewing distances
				grid[row][column].scenicScore = leftViewingDistance * rightViewingDistance * upViewingDistance * downViewingDistance
			}
		}
	}

	// Scan the grid and find the highest scenic score
	// Start at zero since we know at least one tree will have this score
	highestScenicScore := 0

	for row := range grid {
		for column := range grid[row] {
			if grid[row][column].scenicScore > highestScenicScore {
				highestScenicScore = grid[row][column].scenicScore
			}
		}
	}

	fmt.Println(highestScenicScore)
}

Post-solution thoughts

In part 1, instead of counting the number of trees shorter than the current tree, we could halt as soon as we find a taller (or equal height) tree. This would have reduced the work required for part 2.

We could have worked outwards from each tree in part 1, which would have reduced the work in part 2. However, moving inwards made more sense in part 1, as we were trying to find the trees visible from outside the grid, so we were moving from the outside in. For part 2 we were looking out from a tree, so moving from the inside out.

As tree heights are a single digit, we could have used a smaller data type than int. uint8 would have sufficed, and would have made it clearer that heights cannot be negative. However, we would have needed to cast the result of each call to strconv.Atoi, because Go will not allow assignment from the int returned by that function to uint8 (although we ‘know’ that the int will always fit into a uint8, the Go compiler cannot work this out from the source code).