Advent Of Code - Day 10

Again, a bit of breathing time with an easier one. Although, it can be difficult, if you go down the path of trying to do it via recursion.

Day 10 - Part 1

We have to match brackets. There can be a bit of a hassle if you go off on the wrong foot and try to implement it using recursion. But that works perfectly fine as well. But, there is a more elegant solution in which we just use a stack or try matching the last by updating it constantly. The stack is a heck of a lot easier. And considering part 2, it’s also more convenient.

Let’s see.. we parse our input, and then create a stack. In Go a stack is just simply a slice which we’ll manipulate like a stack.

stack := make([]rune, 0)

Why rune? Because we can iterate over strings which give runes.

What are we trying to do? In the basest form, we push characters onto the stack. If a new one comes around which is a closing character, we see if the last one was an opening character for that closing one. If it wasn’t there is an error. If it was, great, we popped it off of the stack so the next character can come along.

First, let’s create some maps which will hold some definitive values so we don’t have to search for anything.

var (
	openingForClosed = map[rune]rune{
		')': '(',
		']': '[',
		'}': '{',
		'>': '<',
	}
	openingDelimiters = map[rune]struct{}{
		'(': {},
		'[': {},
		'{': {},
		'<': {},
	}
	closingDelimiters = map[rune]struct{}{
		')': {},
		']': {},
		'}': {},
		'>': {},
	}
	points = map[rune]int{
		')': 3,
		']': 57,
		'}': 1197,
		'>': 25137,
	}
)

What have we here? We have the openingForClosed which we’ll use to see if the last character was an opening for our closing character. We have openingDelimiters which we’ll use to detect if we have an opening token. And closing, which is the same just for closings.

Then we have our main logic:

	score := 0
	for _, line := range input {
		stack := make([]rune, 0)
		var last rune
		for _, r := range line {
			// if it's an opening thing, push it in stack
			if _, ok := openingDelimiters[r]; ok {
				stack = append(stack, r)
			}
			// if it's a closing one, pop one if it's the opening of the previous one
			// we are good and we popped it.
			if _, ok := closingDelimiters[r]; ok {
				last, stack = stack[len(stack)-1], stack[:len(stack)-1]
				if last != openingForClosed[r] {
					score += points[r]
					break
				}
			}
		}
	}
	fmt.Println("Number of corrupter lines: ", score)

This is it. This is the whole thing, plus the score. We run this for our input and we are done.

Day 10 - Part 2

And of course, if you had a little insight and read the thing which said some of these lines are incomplete, your first thought was surely, that we’ll have to complete them. And indeed, we have to. So our code is actually there already.

We have to discard the ones that are corrupt. And then we’ll have to complete the closing ones. But guess what… After your inner loop completes, what remains in the stack are just the openings which don’t have any closings left.

For example the example contains this:

}}]])})] - 288957 total points.

What our stack will have are these:

[({([[{{

Which is exactly what that is just reversed. Now, the scoring goes like this:

): 1 point.
]: 2 points.
}: 3 points.
>: 4 points.

But the same goes for the opening ones too! They cost the same… Which means we just have to take what’s left in the stack, read it backwards, and score it.

	scores := make([]int, 0)
out:
	for _, line := range input {
		stack := make([]rune, 0)
		var last rune
		for _, r := range line {
			// if it's an opening thing, push it in stack
			if _, ok := openingDelimiters[r]; ok {
				stack = append(stack, r)
			}
			// if it's a closing one, pop one if it's the opening of the previous one
			// we are good and we popped it.
			if _, ok := closingDelimiters[r]; ok {
				last, stack = stack[len(stack)-1], stack[:len(stack)-1]
				if last != openingForClosed[r] {
					continue out // and this continue with a label to jump outside if the line is corrupt
				}
			}
		}
		// this is what changed
		score := 0
		for i := len(stack) - 1; i >= 0; i-- {
			score *= 5
			score += points[stack[i]]
		}
		scores = append(scores, score)
	}
	sort.Ints(scores) // sort and get the middle.
	fmt.Println("middle score: ", scores[len(scores)/2])
}

And that’s it, we have our end score.

Conclusion

We learned today to not over complicate things. If we don’t have an idea about what to do, just try fitting the problem into random data structures and see if something sparks an idea. Finding the right data structure sometimes solves 90% of the problems.

The repository for all my solutions for AOC 2021 can be found here.

Thank you for reading!

Gergely.