Advent of Code in Go: #1

6 minute read

December is here again! That means that this years’ Advent of Code has started. This year I am taking the opportunity to learn Go to solve the puzzles.

Why Go?

Go recently turned 8 and to celebrate there is a great blog post that details the growth in popularity.

I have learned quite a lot of different languages over my carreer. I started with Basic 2.0, moved on to Pascal, Delphi, Perl (Yeah!) C and C++, erlang, Java and eventually Clojure. The last 2, where I spent most of the last 2 decades require the Java Virtual Machine in order to run.

Go has not additional dependencies once it is compiled, so I think it is a language that is quite handy to have in my toolbelt. In order to learn a language I always start with trying to solve some problems.

Advent of Code

The Advent of Code is a yearly puzzle challenge. Each day of december, until christmas, a new puzzle is exposed. So each day of december I can solve something new using Go.

Realistically I will not be able to code every single day, so some puzzles will be done a little later, but nevertheless it will be a very fun time thinking and hacking. This year every day will yield 2 puzzles, so to solve the challenge for a day you need to actually solve 2 puzzles.

Day 1 part 1

This post is about the puzzles of the first day. You, the player, are transported to a computer to fix the printer. Santa needs to have his naughty or nice list out of the darn thing! The first challenge is to solve a captcha that opens the door.

The captcha requires you to review a sequence of digits (your puzzle input) and find the sum of all digits that match the next digit in the list. The list is circular, so the digit after the last digit is the first digit in the list.

Each puzzle is given some sample input that I can base my testcases on. For this puzzle the samples are:

  • 1122 produces a sum of 3 (1 + 2) because the first digit (1) matches the second digit and the third digit (2) matches the fourth digit.
  • 1111 produces 4 because each digit (all 1) matches the next.
  • 1234 produces 0 because no digit matches the next.
  • 91212129 produces 9 because the only digit that matches the next one is the last digit, 9.

Ok, so first thing to learn is “how to convert a character to an integer”. In low level languages this is done by calling atoi, but that seems to be missing. I did find the strconv package that “implements conversions to and from string representations of basic data types”. That is exactly what I need, so I set out to use strconv.Atoi. The function uses the output, error pattern and thus we need to capture both and do some error handling. I wrapped it into my own atoi function.

func atoi(s string) int {
        i, err := strconv.Atoi(s)
        if err != nil {
                log.Fatalf("Atoi conversion failed: %s", err)
        }
        return i
}

Now for my first attempt. In the tutorial I learned that you can pass functions as a closure. That allows me to continually call the function over the values of the array, compare the current value to the previous one and then add the value if it matches.

func summer() func(int) int {
	sum := 0
	previous := 10
	return func(x int) int {
		if (x == previous) {
			sum += x
		}
		previous = x
		return sum
	}
}

In the main function I create the closure, call the clojure for every digit in the string, that I convert with atoi. Finally I need to check the last/first entries to deal with the circularity.

s := summer()
result := 0

for _, r := range target {
	result = s(atoi(string(r)))
}

if target[0] == target[len(target) - 1] {
	result += atoi(string(target[0]))
}

fmt.Printf("Result: %d\n", result)

Great! The answer is correct! On to the second part of the puzzle.

Day 1 part 2

Now, instead of considering the next digit, it wants you to consider the digit halfway around the circular list. That is, if your list contains 10 items, only include a digit in your sum if the digit 10/2 = 5 steps forward matches it. Fortunately, your list has an even number of elements.

The sample data changes to:

  • 1212 produces 6: the list contains 4 items, and all four digits match the digit 2 items ahead.
  • 1221 produces 0, because every comparison is between a 1 and a 2.
  • 123425 produces 4, because both 2s match each other, but no other digit has a match.
  • 123123 produces 12.
  • 12131415 produces 4.

Well, thats a bummer! It doesn’t really fit in my current solution, so back to the drawingboard!

The string that we need to process should be converted to an array of digits I believe, so next up is “how to use an array” and “how to loop over a string”. Surprisingly the range function is very flexible and allows to loop over a list/string and it not only returns the index of the loop, but also the value. The multi value assignment here assigns the index and value and I use that to populate my array of integers.

func convertInput(s string) []int {
	output := make([]int, len(s))

	for i, e := range s {
		output[i] = atoi(string(e))
	}

	return output
}

Now, lets first setup some testing functions to validate our new solution. The built in testing library seems to be quite simple. I created a struct called testpair to hold the sample data, the expected result and the offset to deal with the new conditions given.

type testpair struct {
        values string
        result int
	offset int
}

var tests = []testpair{
        { "1122", 3, 1 },
        { "1111", 4, 1 },
        { "1234", 0, 1 },
        { "91212129", 9, 1 },
        { "1212", 6, int(len("1212")/2) },
        { "1221", 0, int(len("1221")/2) },
        { "123425", 4, int(len("123425")/2) },
        { "123123", 12, int(len("123123")/2) },
        { "12131415", 4, int(len("12131415")/2) },
	
}

Time to create a testcase! The convention is to use Test* as a function name with the signature (t *testing.T). Again I use range to loop over every single testpair I defined and then I call my new function (not yet written) called pincode. If something does not come out right I use t.Error to signal the error.

func TestPincode(t *testing.T) {
        for _, pair := range tests {
                pin := pincode(pair.offset, pair.values)
                if pin != pair.result {
                        t.Error(
                                "For", pair.values,
                                "expected", pair.result,
                                "got", pin,
                        )
                }
        }
}

Lets attack this problem again, but then with both cases in mind. All we need to do is to loop over the array and take the current element and the element at the given offset. The only challenge here is when the index of the offsetted element exceeds the array length. With a modulo (%) I will get the value of the index in range. Basically this operation will tell you what is left over when you subtract the length of the array. In this case you could also use a subtraction, but then you need more if statements.

This little piece of code actually solves both the first and the second puzzle.

func pincode(offset int, input string) int {
	digits := convertInput(input)
	pin := 0

	// Loop over the digits in the input
	for i := 0; i < len(digits); i++ {
		// Grab the digit to compare to
		target := (i + offset) % len(digits)
		// If the yare the same, add the digit to the pin
		if digits[i] == digits[target] {
			pin += digits[i]
		}
	}
	
	return pin
}

So, what did I learn today? 1) how to write some basic Go code, 2) arrays, 3) range and 4) string conversions.

Emacs and Go

In my emacs I installed go-mode.el (M-x package-install RET go-mode). This package integrates nicely with flycheck-mode.

For now I only used the basic syntax highlighting and formatting features and Flycheck to highlight errors. I wonder if it can do more, but already it was a pleasant experience.

Tags: , ,

Updated: