Advent of Code in Go: #8

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

So, the first week of december was all about fiddling around with numbers and characters. You would think we would ease into the more complex things step by step right? No! This time the CPU asks us to create an interpreter from scratch to figure out what all these operations are going to do with the registers.

Back in the day, I am talking Pascal days, I wrote my fair share of interpreters. But that was such a long time ago… today I went and wrote a simple one in Go.

The input will be an expression such as b inc 5 if a > 1 where the operation inc can only be done of register b if the condition a > 1 is true.

To get started we will need a place to hold our registers.

var registers = make(map[string]int)

we’ll also create a helper to clear out the registers so that we can run multiple testcases after eachother (figured out this after giving a wrong answer)

func clearRegisters() {
	for k := range registers {
		registers[k] = 0
	}
}

Next we will need to parse the expression into its components for us to proces.

type exp struct {
	reg         string
	instruction string
	value       int

	lhs     string
	operand string
	rhs     int
}

Now lets parse the string expression into its components. I am not doing any error handling here, as I expect the input to be valid. Normally this part would be much more complex. If you are interested in writing parsers, take a look at the Antlr project, it can generate parsers from a definition of the language.

// parse a string into an expression
// b inc 5 if a > 1
// b, inc, 5, a, >, 1
func parse(instruction string) exp {
	tokens := strings.Fields(instruction)

	return exp{
		// b inc 5
		tokens[0], tokens[1], atoi(tokens[2]),
		// a > 1
		tokens[4], tokens[5], atoi(tokens[6]),
	}
}

Next I need something to take the condition part of the expression and tell me if it is true or not. The first time using the switch statement in Go.

func condition(expr exp) bool {
	lhsVal := registers[expr.lhs]
	truth := false
	switch expr.operand {
	case ">":
		truth = lhsVal > expr.rhs
		break
	case "<":
		truth = lhsVal < expr.rhs
		break
	case ">=":
		truth = lhsVal >= expr.rhs
		break
	case "<=":
		truth = lhsVal <= expr.rhs
		break
	case "==":
		truth = lhsVal == expr.rhs
		break
	case "!=":
		truth = lhsVal != expr.rhs
		break
	default:
		fmt.Println("UNKNOWN operaand:", expr.operand)
	}
	return truth
}

Now that I can know if the condition is true I can actually apply the operations to the registers. Again using the switch statement on the operand to change the register value.

func apply(expr exp) {
	if condition(expr) {
		regVal := registers[expr.reg]
		switch expr.instruction {
		case "inc":
			regVal += expr.value
			break
		case "dec":
			regVal -= expr.value
			break
		default:
			fmt.Println("UNKNOWN instruction:", expr)
		}
		registers[expr.reg] = regVal
	}
}

Almost done. The puzzle wants to know what the highest value is in the registers at the end of the run. So lets take our maxIntArray() function and rewrite it to a maxIntMap() version.

func maxIntMap(m map[string]int) (max int) {
	for _, v := range m {
		if v > max {
			max = v
		}
	}
	return
}

The solve is now a matter of applying each line of the file and the using maxIntMap() to grab the highest value.

func solve(filename string) (ret int, err error) {
	lines, err := readLines(filename)

	for _, v := range lines {
		expr := parse(v)

		apply(expr)
	}

	return maxIntMap(registers), nil
}

And then, part 2. I am feeling confident because I have create a proper interpreter for this problem. So, whatever it asks, I am ready…

It wants to know the highest value ever witnessed during execution. Well that is quite simple (after reading the question correctly). On the processing of each line, take a look at the highest value in the register and keep track of it.

I first read the question wrong and resorted to math.Abs to find the highest positive/negative number, but the testcase was very helpful in pointing out I was being silly.

func solve2(filename string) (ret int, err error) {
	lines, err := readLines(filename)

	highest := 0
	for _, v := range lines {
		expr := parse(v)

		apply(expr)

		curHighest := maxIntMap(registers)
		if curHighest > highest {
			highest = curHighest
		}
	}

	return highest, nil
}

Writing code in VSCode

As I explained yesterday I was not very happy with the debugging facilities in Emacs, so I tried VSCode. I figured, as it is a month of experimentation I might as well give VSCode a try as well.

So far the editing experience is quite nice. I am trying to figure out the keyboard shortcuts and the editing nicities, but both the Go editing as well as Markdown (what I am writing this text in) is good enough for me.

The debugging facilities are top notch for Go projects, which is nice! It also does Git quite nicely (not as nice as Magit though!).

For editing I prefer the Zen mode as it has very little extras going on, just like I use my Emacs.

Tags: , ,

Updated: