Advent of Code in Go: #15

2 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

Today we are faced with duelling generators. Both generators are generating numbers using a formula and there is a judge deciding if the numbers match. Each time they match a counter is incremented. My task is to calculate the counter for my input.

The generators both work on the same principle. To create its next value, a generator will take the previous value it produced, multiply it by a factor (generator A uses 16807; generator B uses 48271), and then keep the remainder of dividing that resulting product by 2147483647. That final remainder is the value it produces next.

To calculate each generator’s first value, it instead uses a specific starting value as its “previous value” (as listed in your puzzle input).

In part 2 of the puzzle adds a criteria to the generated number:

In the interest of trying to align a little better, the generators get more picky about the numbers they actually give to the judge.

They still generate values in the same way, but now they only hand a value to the judge when it meets their criteria:

Generator A looks for values that are multiples of 4. Generator B looks for values that are multiples of 8.

The function to perform the calculation is quite simple. Multiply the previous value times the factor and then modulo 2147483647. If the result modulo criteria returns 0, it is a viable candidate.

func generateNext(factor int, previous int, criteria int) int {
	res := previous
	for {
		res = res * factor % 2147483647

		if res%criteria == 0 {
			return res
		}
	}
}

In order to be a good match, the lower 16 bits need to match. This is done with some masking, namely 0xffff or 65535.

func match(genA, genB int) bool {
	return genA&65535 == genB&65535
}

The solve is straightforward; loop over the amount of iterations, calling the generators and matching their result.

func solve(factorA, startA, critA, factorB, startB, critB, iters int) (part1 int, err error) {
	a, b := startA, startB
	for i := 0; i < iters; i++ {
		a = generateNext(factorA, a, critA)
		b = generateNext(factorB, b, critB)
		//fmt.Printf("%15d\t%15d\n", a, b)
		if match(a, b) {
			part1++
		}
	}
	return
}

Further work

There is a good possiblity to use channels here. That will be a good learning experience. I added it to my todo list.

Tags: , ,

Updated: