Advent of Code in Go: #14

3 minute read

In this series I explore the Advent of Code, or AoC for short, with the Go programming language. Every day, as real life permits, I will be solving a puzzle from the series. I will document each day with a solution in Go and a walkthrough of the code.

You can find the previous walkthroughs here.

The puzzle

In the computer we now run into a disk fragmentation problem. We need to help the program figure out what sectors of the disk are actually used and which are not. In a twist we are again confronted with the knot hash from puzzle 10. The below explanation shows how we will fill a 128x128 grid based on our input hash.

The hash inputs are a key string (your puzzle input), a dash, and a number from 0 to 127 corresponding to the row. For example, if your key string were flqrgnkx, then the first row would be given by the bits of the knot hash of flqrgnkx-0, the second row from the bits of the knot hash of flqrgnkx-1, and so on until the last row, flqrgnkx-127.

The output of a knot hash is traditionally represented by 32 hexadecimal digits; each of these digits correspond to 4 bits, for a total of 4 * 32 = 128 bits. To convert to bits, turn each hexadecimal digit to its equivalent binary value, high-bit first: 0 becomes 0000, 1 becomes 0001, e becomes 1110, f becomes 1111, and so on; a hash that begins with a0c2017… in hexadecimal would begin with 10100000110000100000000101110000… in binary.

Continuing this process, the first 8 rows and columns for key flqrgnkx appear as follows, using # to denote used squares, and . to denote free ones:

##.#.#..-->
.#.#.#.#   
....#.#.   
#.#.##.#   
.##.#...   
##..#..#   
.#...#..   
##.#.##.-->
|      |   
V      V   

For each row I can calculate a knot hash and then, using bits.OnesCount8(), I can count the number of bits used in each byte. To populate the grid I convert the byte to its binary using fmt.Sprintf("%08b", b). This gives the string version that we can iterate over and toggle the used flag in the grid.

func fillGrid(row []bool, countUsed *int, input string) {
	index := 0
	for _, b := range knotHash(input) {
		*countUsed += bits.OnesCount8(b)
		for _, bit := range fmt.Sprintf("%08b", b) {
			if bit == '1' {
				fmt.Println(index)
				row[index] = true
			}
			index++
		}
	}
}

Part 2 of the puzzle asks to identify the connected cells as groups. The table from the example would be converted to groups using the following layout. As long as the cells are connected (except diagonally) they belong to the same group.

11.2.3..-->
.1.2.3.4   
....5.6.   
7.8.55.9   
.88.5...   
88..5..8   
.8...8..   
88.8.88.-->
|      |   
V      V   

The approach I chose is to take a cell, then visit all adjacent cells and toggle their used state to false. This allows me to clean out those cells for future visits. In the end I should be left with the count of cells that originate a group of cells.

First, lets loop over the grid/row and visit each individual cell, trying to spread out that cell to adjacent cells. Incrementing each time a spread has finished.

func regions(grid [][]bool) (count int) {
	for i, row := range grid {
		for j, used := range row {
			if used {
				spread(i, j, grid)
				count++
			}
		}
	}
	return
}

Spreading a cell is simple, just recursively spread to each neighbor.

func spread(row int, cell int, grid [][]bool) {
	// bounds check
	if row < 0 || row >= len(grid) || cell < 0 || cell >= len(grid[row]) {
		return
	}
	if grid[row][cell] {
		// Mark the cell so that future spreads do not count it
		grid[row][cell] = false
		spread(row-1, cell, grid) // up
		spread(row+1, cell, grid) // down
		spread(row, cell-1, grid) //left
		spread(row, cell+1, grid) // right
	}
}

The solve itself collects these values and returns values for part 1 and 2.

func solve(input string) (usedGrid int, regionCount int, err error) {
	grid := make([][]bool, 128)

	for i := 0; i < 128; i++ {
		grid[i] = make([]bool, 128)

		fillGrid(grid[i], &usedGrid, fmt.Sprintf("%s-%d", input, i))
	}

	regionCount = regions(grid)

	return
}

Other works

In the Reddit forums I found another Golanger that took pretty much the same approach. I actually borrowed the idea of passing the usedGrid as a pointer from that. He went as far as using goroutines to solve it, which made it intersting reading how he did it. It is also a very good example of using sync.WaitGroup to sync multiple goroutines

Perhaps there is a future place to use goroutines.

Tags: , ,

Updated: