Part 1
Take a grid of input and move a ‘beam’ down through the grid, based on an entry point and ‘splitters’ which split the beam in two.
Solution
Similar to day 4, we have a grid of squares and we need to transform the grid in some way and then calculate a number from it.
Our only data structure is a representation of a square, from which the grid will be built. We also need a function to populate the struct based on a single character of input. To make testing and debugging easier, we will also write a function to print out the data structure, i.e. the inverse of population.
const (
UNKNOWN = -1
EMPTY = iota
BEAM_ENTRY
BEAM
SPLITTER
)
type Square struct {
contents int
}
func getSquare(input string) Square {
square := Square{}
switch input {
case ".":
square.contents = EMPTY
case "S":
square.contents = BEAM_ENTRY
case "|":
square.contents = BEAM
case "^":
square.contents = SPLITTER
default:
square.contents = UNKNOWN
}
return square
}
func printSquare(square Square) string {
output := ""
switch square.contents {
case EMPTY:
output = "."
case BEAM_ENTRY:
output = "S"
case BEAM:
output = "|"
case SPLITTER:
output = "^"
}
return output
}Each row or line in the grid needs to be populated as a slice of Squares. Initially I wrote the following:
func getLine(input string) []Square {
line := []Square{}
input = strings.Trim(input, "\n")
squareCharacters := strings.Split(input, "")
for sc := range squareCharacters {
square := getSquare(squareCharacters[sc])
if square.contents != UNKNOWN {
line = append(line, square)
}
}
return line
}
func printLine(line []Square) string {
output := ""
for lineIndex := range line {
output += printSquare(line[lineIndex])
}
return output
}However, Go suggested “using string += string in a loop is inefficient” in printLine because strings are immutable, as I was creating a new string in each iteration and making more work for the allocator and garbage collector. In this puzzle the inefficiency is unlikely to be important, because the size of input is known and small, though it could be an issue with larger or more complex inputs. I generally assume that the compiler knows more than me though - it has after all been written by experts - so I decided to rewrite the function using strings.Builder, which doesn’t return the immutable string until the end.
func printLine(line []Square) string {
var sb strings.Builder
for lineIndex := range line {
sb.WriteString(printSquare(line[lineIndex]))
}
return sb.String()
}Now that we can populate a square and line, we need a final pair of functions to populate and print the grid:
func getGrid(input string) [][]Square {
grid := [][]Square{}
lines := strings.Split(input, "\n")
for lineIndex := range lines {
if len(lines[lineIndex]) > 0 {
grid = append(grid, getLine(lines[lineIndex]))
}
}
return grid
}
func printGrid(grid [][]Square) string {
var sb strings.Builder
for row := range grid {
sb.WriteString(printLine(grid[row]))
sb.WriteString("\n")
}
return sb.String()
}Next we come to the puzzle itself - how do we work out how many times the beam splits? We will break this down into three parts:
- Move the beam once - this allows us to test each move rather than just the end result.
- Move the beam to the exit point - this is where we need to get to.
- Count the number of splits - the final answer.
To move the beam once, we need to take the grid and find the last row which contains either a beam or the beam entry point. If this is the last row in the grid, we can return false to indicate that no more moves as possible, otherwise we need to update the next row as follows:
- If the column on the next row under a beam is empty, place a beam there.
- If the column on the next row under a bean is a splitter, place a beam either side.
As we only store a single item of content for each square, it does not matter if a multiple beams are split into the same square - all we care about is if there is at least one beam.
func moveBeam(grid [][]Square) bool {
// Find current beam row - 0 is the default
currentBeamRow := 0
for row := range grid {
for column := range grid[row] {
if grid[row][column].contents == BEAM || grid[row][column].contents == BEAM_ENTRY {
currentBeamRow = row
}
}
}
// If we are not on the last row of the grid, move down one
// otherwise return false and do not modify the grid
if currentBeamRow < len(grid)-1 {
nextBeamRow := currentBeamRow + 1
for column := range grid[currentBeamRow] {
if grid[currentBeamRow][column].contents == BEAM || grid[currentBeamRow][column].contents == BEAM_ENTRY {
switch grid[nextBeamRow][column].contents {
case EMPTY:
grid[nextBeamRow][column].contents = BEAM
case SPLITTER:
if column > 0 {
grid[nextBeamRow][column-1].contents = BEAM
}
if column < len(grid[nextBeamRow])-1 {
grid[nextBeamRow][column+1].contents = BEAM
}
}
}
}
return true
} else {
return false
}
}We can now use moveBeam to write a function that moves the beam all the way to the exit. This is straightforward, as all we need to do is call moveBeam until it returns false, which we can do with a for loop with an empty body.
func moveBeamToExit(grid [][]Square) {
for moveBeam(grid) {
}
}Finally, we need a function to count the number of times the beam has split. First we move the beam to the exit, then we find all the splitters with a beam directly above them, i.e. at the same column position and row position - 1.
func countBeamSplits(grid [][]Square) int {
beamSplits := 0
moveBeamToExit(grid)
// Find all the splitters with a beam directly above them
for row := 1; row < len(grid); row++ {
for column := range grid[row] {
if grid[row][column].contents == SPLITTER && grid[row-1][column].contents == BEAM {
beamSplits++
}
}
}
return beamSplits
}Part 2
Overall thoughts
Part 1 was quite easy, given that I’m now familiar with converting to/from grids.