Advent of Code in Go: #6

4 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

The debugger is trying to figure out a problem with the memory reallocation routine. Whenever the bits are redistributed the system ends up in a loop. We are to try and find the loop and notify the debugger of the step it occurs in.

Lets take a look at an example:

The banks start with 0, 2, 7, and 0 blocks. The third bank has the most blocks, so it is chosen for redistribution.
Starting with the next bank (the fourth bank) and then continuing to the first bank, the second bank, and so on, the 7 blocks are spread out over the memory banks. The fourth, first, and second banks get two blocks each, and the third bank gets one back. The final result looks like this: 2 4 1 2.
Next, the second bank is chosen because it contains the most blocks (four). Because there are four memory banks, each gets one block. The result is: 3 1 2 3.
Now, there is a tie between the first and fourth memory banks, both of which have three blocks. The first bank wins the tie, and its three blocks are distributed evenly over the other three banks, leaving it with none: 0 2 3 4.
The fourth bank is chosen, and its four blocks are distributed such that each of the four banks receives one: 1 3 4 1.
The third bank is chosen, and the same thing happens: 2 4 1 2.

Having to keep track of the history seems like a pain; we need to have a dynamic array and append the current sequence to it and then compare the next sequence with all of history to determine a loop.

How do we find the highest value in an array, most notably the location at which it resides?

// return the index of the max in the array
// lowest index will win with tie
func maxIntArray(v []int) (m int) {
	if len(v) > 0 {
		m = 0
	}
	for i := 1; i < len(v); i++ {
		if v[i] > v[m] {
			m = i
		}
	}
	return
}

Then lets figure out how to cycle blocks in the bank. Given the location of the highest value, store that in a variable for redistribution, when set the value of that cell to 0. Start walking over the array, wrapping around where needed, and add 1 to the current value.

func cycleBlocks(state []int) []int {
	highest := maxIntArray(state)
	redist := state[highest]
	state[highest] = 0

	index := highest + 1
	for i := redist; i > 0; i-- {
		if index > len(state)-1 {
			index = 0
		}
		state[index]++
		index++
	}
	return state
}

When we have a list of such states we need to compare past to the present to determine a loop. Here I learned about reflect.DeepEqual() to compare the values of 2 arrays (slices) to eachother. If you use != you will get the message slice can only be compared to nil, which is totally not what we want.

func historyRepeats(history [][]int, present []int) bool {
	for _, past := range history {
		if reflect.DeepEqual(past, present) {
			return true
		}
	}
	return false
}

Now we can implement our first solve. The algorithm is messy and timeconsuming due to the constant iteration of history and the need to copy() the arrays all the time. I found that if you use := to assign the array to a new value it is done by reference, so on the next cycle the values in history were changed. Good lesson right there!

func solve(blocks string) int {
	fields := strings.Fields(blocks)

	history := [][]int{}
	state := make([]int, len(fields))

	for i, v := range fields {
		state[i] = atoi(v)
	}

	recurse := false
	steps := 0
	for recurse == false {
		steps++
		past := make([]int, len(state))
		copy(past, state)
		history = append(history, past)

		next := cycleBlocks(state)
		if historyRepeats(history, next) {
			recurse = true
		}
	}
	return steps
}

In the second part of the puzzle the debugger would like to know how long the loop is after you hit the recursion. So how many steps after the first occurence it takes to get back to the exact same state. So I added a section when historyRepeats() that just simply cycles blocks until it hits the same one again.

func solve2(blocks string) int {
	fields := strings.Fields(blocks)

	history := [][]int{}
	state := make([]int, len(fields))

	for i, v := range fields {
		state[i] = atoi(v)
	}

	recurse := false
	steps := 0
	for recurse == false {
		past := make([]int, len(state))
		copy(past, state)
		history = append(history, past)

		next := cycleBlocks(state)
		if historyRepeats(history, next) {

			target := make([]int, len(next))
			copy(target, next)
			next = cycleBlocks(next)
			steps++

			for !reflect.DeepEqual(target, next) {
				next = cycleBlocks(next)
				steps++
			}

			recurse = true
		}
	}
	return steps
}

The algorithm is messy and dirt slow, but it does provide the correct answers.

Tags: , ,

Updated: