Advent of Code in Go: #9

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

We continue our journey. We find a stream of characters that is treaserous to pass. We need to figure out the number of groups in the stream based on some simple rulse.

The characters represent groups - sequences that begin with { and end with }. Within a group, there are zero or more other things, separated by commas either another group or garbage Since groups can contain other groups, a } only closes the most-recently-opened unclosed group - that is, they are nestable. Your puzzle input represents a single, large group which itself contains many smaller ones.

Sometimes, instead of a group, you will find garbage. Garbage begins with < and ends with >. Between those angle brackets, almost any character can appear, including { and }. Within garbage, < has no special meaning.

In a futile attempt to clean up the garbage, some program has canceled some of the characters within it using !: inside garbage, any character that comes after ! should be ignored, including <, >, and even another !.

These rules are simple enough. In a real scenario you would use a Reader I guess, but for now we can just proces the string from our input file.

Our goal is to determine the score of all the groups:

Your goal is to find the total score for all groups in your input. Each group is assigned a score which is one more than the score of the group that immediately contains it. (The outermost group gets a score of 1.)

Lets setup our testcases first. I learned about table driven tests yesterday. Basically we can just create a slice of structs inside a testcase, then we don’t need to redefine it every time.

func TestSolve(t *testing.T) {
	tests := []struct {
		stream string
		score  int
	}{
		// stream, score
		{"{}", 1},
		{"{ { {} } }", 6},
		{"{ {},{} }", 5},
		{"{ { {},{},{ {} } } }", 16},
		{"{<a>,<a>,<a>,<a>}", 1},
		{"{ {<ab>},{<ab>},{<ab>},{<ab>} }", 9},
		{"{ {<!!>},{<!!>},{<!!>},{<!!>} }", 9},
		{"{ {<a!>},{<a!>},{<a!>},{<ab>} }", 3},
	}
	for _, test := range tests {
		answer, _, err := solve(test.stream)
		if err != nil {
			t.Error("Received an error: ", err)
			continue
		}

		if answer != test.score {
			t.Error(
				"Expected", test.score,
				"Got", answer)
		}
	}

With the testcases ready I start writing my solve. I actually ended up having the function return 3 values, first the score, second the amount of garbage (part 2 of the puzzle) and third an error. Processing the stream with so few conditions is relatively simple. Keep track of the current state (depth of groups, inside garbage or flagged as ignore) and then work over the conditions.

You can actually do away with the score array and just increment immediately, but I thought perhaps part 2 would be something like ‘what was the highest score found?’, but instead it was about garbage.

func solve(stream string) (ret int, gar int, err error) {
	depth := 0 // the score for the next group is +1
	garbage := false
	ignore := false

	scores := []int{}
	gscores := []int{}
	gcount := 0
	// In real world you would use a Reader I would think
	// There is a Json Stream Decoder that does...
	for i, c := range stream {
		cur := string(c)
		if ignore { // if ignore is true, ignore anything
			ignore = false
			continue
		} else if cur == "!" { // if the current thing is !, toggle ignore
			ignore = true
		} else if cur == "<" && !garbage {
			garbage = true
			continue
		} else if garbage && cur == ">" {
			// the garbage ends with a >
			garbage = false
			gscores = append(gscores, gcount)
			gcount = 0
			continue
		} else if garbage {
			// ignore the things in the garbage
			gcount++
			continue
		} else if cur == "{" {
			depth++
			scores = append(scores, depth)
		} else if cur == "}" {
			depth--
		} else if cur == "," {
			// ignore seperator
			continue
		} else {
			fmt.Println("No case to deal with", cur)
			return 0, 0, fmt.Errorf("Parse error at position %d character %s", i, cur)
		}
	}
	return sumArray(scores), sumArray(gscores), nil
}

Part 2 was relatively simple due to the full implementation of state tracking.

Now, you’re ready to remove the garbage.

To prove you’ve removed it, you need to count all of the characters within the garbage. The leading and trailing < and > don’t count, nor do any canceled characters or the ! doing the canceling.

In the solve I just keep track of the count of garbage and deal with it the same as normal scores. In my first attempt I found a small error in my garbage detection, but the testcase showed it to me quickly enough.

func TestGarbage(t *testing.T) {
	tests := []struct {
		stream string
		score  int
	}{
		// stream, score
		{"{}", 0},
		{"{<>}", 0},
		{"{<random characters>}", 17},
		{"{<<<<>}", 3},
		{"{<{!>}>}", 2},
		{"{<!!>}", 0},
		{"{<!!!>>}", 0},
		{"{<{o\"i!a,<{i<a>}", 10},
	}
	for _, test := range tests {
		_, answer, err := solve(test.stream)
		if err != nil {
			t.Error("Received an error: ", err)
			continue
		}

		if answer != test.score {
			t.Error(
				"Input", test.stream,
				"Expected", test.score,
				"Got", answer)
		}
	}
}

So, both cases answered with the same parsing routine. Nice.

VSCode and Git

Yesterday I was happy with VSCode, but turns out their Git support is actually lacking if you want to do more than just commit something. It does a push as well, but for this blog I push to multiple locations and that is not supported. Magit is so good compared to it.

Tags: , ,

Updated: