Advent of Code in Go: #7

3 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

There is a tower of processes, each proces is holding a disc with upon it even more towers, with even more discs. We are tasked with finding the root element.

As this is a learning journey for me, I chose to dive into structs this time. A graph is a great thing to figure out with structs and pointers, so I immediately thought of the following struct:

type node struct {
	name      string
	weight    int
	parent    *node
	childeren []*node
}

This serves as a good startingpoint for a nice graph. The node without a parent pointer will be the root of our tree. Given the description I figure that the second part will have to do with the weights of the nodes, so that should be a good starting point again.

So, as before, lets read the input into an array. I’ll create a registry using a map with node pointers and then we’ll traverse that to find the one without a parent pointer.

func solve() (string, map[string]*node) {
	lines, err := readLines("input.txt")
	if err != nil {
		panic("Could not read input")
	}

	registry := make(map[string]*node)

	for _, v := range lines {
		proces(v, registry)
	}

	//	fmt.Println(registry)
	for _, v := range registry {
		if v.parent == nil {
			return v.name, registry
		}
	}

	return "", registry
}

The processing is quite straightforward. Split the string and use array slices to parse the weight indicator. If the value is not in the map, due to map[key] returning a false value for ok (an extremely useful way to utilize the multi value return), I will create a new node. Then, if available, I will loop over the children and create nodes for them in the registry and in the children array.

In the end I assign the updated object back to the map.

func proces(n string, reg map[string]*node) {
	e := strings.Fields(n)

	root := e[0]
	weight := atoi(e[1][1 : len(e[1])-1])
	children := []*node{}

	self, ok := reg[root]
	if !ok {
		self = &node{root, weight, nil, children}
	}

	for i := 3; i < len(e); i++ {
		name := strings.Replace(e[i], ",", "", 1)
		child, ok := reg[name]

		if ok { // found an existing entry, update parent
			child.parent = self
			reg[name] = child
		} else { // no entry exists, create new node
			child = &node{name, -1, self, []*node{}}
			reg[name] = child
		}
		children = append(children, child)
	}

	self.weight = weight
	self.childeren = children
	reg[root] = self
}

Part 2 is a bit hard and I actually got stuck in it. I need to figure out what discs are not in balance and provide the corrected value to balance them out again. Using the balanced method on the node I was able to find the guilty party, the disc that is unbalanced, but I ran into problems when I tried to find the child that was causing it. I ended up doing it in my head and providing the answer. Probably a good nights sleep will help a lot here.

In order to find unbalance I push the values into a map, if there is more then 1 entry, the inbalance is cause in one of the children. In my case it was the difference between 1060 and 1051, 9. So subtracting that from the weight 655 gave me the value.

func (n *node) balanced() (int, error) {
	children := n.childeren

	weight := n.weight
	disc := make(map[int]int)

	for _, c := range children {
		sum, err := c.balanced()
		if err != nil {
			return sum, errors.New(c.name)
		}
		weight += sum
		disc[sum]++
	}

	if len(disc) > 1 {
		for i, v := range disc {
			if v == 1 {
				fmt.Println("Guilty party: ", i)
				// now subtract 1051 from 1060, which is 9
				// subtract 9 from 655 (its weight)
			}
		}
	}

	return weight, nil

}

Debugging in Emacs

Compared to Clojure the debugging in Go, using Emacs, is non-existant. There is some GUD integration with Delve, but it seriously lacks usability as far as I can see now.

I quickly tried VSCode with its Go extension and it provides a much nicer solution to this problem. It also installed quite a lot of extra packages to support itself, so maybe there is more to be had?

Tags: , ,

Updated: