Advent of Code in Go: #10

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 snow is coming down for real this morning. About 10cm has fallen and so the puzzle will have to be done in between play times outside!

Today the computer asks us to do some hash computations. We are presented with a list of numbers and a fixed width array (256 items). The algorithm is illustrated with the following diagram and some text explaining it to the reader.

  4--5   pinch   4  5           4   1
 /    \  5,0,1  / \/ \  twist  / \ / \
3      0  -->  3      0  -->  3   X   0
 \    /         \ /\ /         \ / \ /
  2--1           2  1           2   5

To achieve this, begin with a list of numbers from 0 to 255, a current position which begins at 0 (the first element in the list), a skip size (which starts at 0), and a sequence of lengths (your puzzle input). Then, for each length:

Reverse the order of that length of elements in the list, starting with the element at the current position. Move the current position forward by that length plus the skip size. Increase the skip size by one.

The text goes on to explain the proces in more detail, you can read about it here.

So lets get started. The thing I notice first is the need to treat the list as a circular one. This means wrapping around, applying subsets over array boundaries etc. So I go and write some functions for that.

First lets get a wrapped around slice from the array.

func getWrappedSlice(pos int, step int, seq []int) []int {
	target := make([]int, step)

	for i := range target {
		t := pos + i

		if t >= len(seq) {
			t = t % len(seq)
		}

		target[i] = seq[t]
	}
	return target
}

Next we need to apply the reversed subsection over the original array again. I found no reference in the documentation, so I wrote another function.

func applySlice(pos int, modified []int, seq []int) {
	for i := range modified {
		t := pos + i

		if t >= len(seq) {
			t = t % len(seq)
		}

		seq[t] = modified[i]
	}
}

When we have the slices we need to reverse them. That too seems to not be supported out of the box. Perhaps an interface needs to be created for it? I just wrote a function to do it for me.

func reverseInts(input []int) []int {
	if len(input) == 0 {
		return input
	}
	return append(reverseInts(input[1:]), input[0])
}

On to our actual solve. First I setup my array to hold the hash according to spec (seq). Then for the number of iterations (added due to part 2), I step over the input, grabbing the slice, reversing it and subsequently applying it to the sequence. I return the sequence itself.

func solve(steps []int, length int, iterations int) (ret []int, err error) {
	seq := make([]int, length)
	for i := range seq {
		seq[i] = i
	}

	pos := 0
	skip := 0

	for i := 0; i < iterations; i++ {
		for _, s := range steps {
			hashable := getWrappedSlice(pos, s, seq)

			reversed := reverseInts(hashable)
			applySlice(pos, reversed, seq)

			pos = pos + s + skip
			if pos >= len(seq) {
				pos = pos % len(seq)
			}
			skip++
		}
	}
	return seq, nil
}

I use this to find the answer to the question: “what do you get when you multiply the first 2 elements?”.

func TestInput(t *testing.T) {
	input, _ := readLines("input.txt")
	s := strings.Split(input[0], ",")
	steps := make([]int, len(s))
	for i, v := range s {
		steps[i] = atoi(v)
	}

	answer, _ := solve(steps, 256, 1)

	if (answer[0] * answer[1]) != 23715 {
		t.Error("Got:", answer)
	}
}

For part 2 of the puzzle we need to subtly change the input, not as a list of integers, but as the ASCII value of each character. This threw me of a little bit as I misread the statement and went on a wild goosechase with runes and other character math :s. It sorted itself out.

I just take the input and then take the int value of the 2nd value from range on a string, this turns out to be the ASCII value already. Then I add the known sequence from the puzzle text. Finally I just create the same step array as I used before.

The key difference from before is that the solve needs 64 iterations. Hence I added the iterations to the solve function.

func getState2Steps(input string) []int {
	ints := []int{}
	for _, v := range input {
		ints = append(ints, int(v))
	}
	steps := append(ints, 17, 31, 73, 47, 23)
	intSteps := make([]int, len(steps))
	for i, v := range steps {
		intSteps[i] = int(v)
	}
	return intSteps
}

func getSteps(filename string) []int {
	lines, _ := readLines(filename)

	return getState2Steps(lines[0])
}

With the hash returned from solve, also known as a sparse hash, we need to create a dense hash. This is done by xor-ing the values in each bucket (size 16). The the output is a hex string, which we can create using fmt.Sprintf.

func generateKnot(sparse []int) string {
	knot := make([]int, 16)
	for i := 0; i < 255; i += 16 {
		for j := 0; j < 16; j++ {
			knot[i/16] ^= sparse[i+j]
		}
	}

	hex := ""
	for _, element := range knot {
		hex += fmt.Sprintf("%.02x", element)
	}
	return hex
}

I tie this all together in the last testcase.

func TestInput2(t *testing.T) {
	steps := getSteps("input.txt")

	sparse, _ := solve(steps, 256, 64)
	result := generateKnot(sparse)

	if result != "541dc3180fd4b72881e39cf925a50253" {
		t.Error(
			"Expected", "541dc3180fd4b72881e39cf925a50253",
			"Got", result)
	}
}

All done.

Tags: , ,

Updated: