Advent of Code in Go: #12

2 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

Today we are a plumber trying to figure out what programs are connected to eachother with pipes.

Programs in this village communicate using a fixed system of pipes. Messages are passed between programs using these pipes, but most programs aren’t connected to each other directly. Instead, programs pass messages between each other until the message reaches the intended recipient.

For some reason, though, some of these messages aren’t ever reaching their intended recipient, and the programs suspect that some pipes are missing. They would like you to investigate.

The input looks like this:

0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5

Part 1 of the puzzle asks how large the group of programs are that are directly and indirectly connected to process 0, part 2 wants to know how many other groups exist.

This is relatively easy done by first parsing the input strings, as I have done before in the previous puzzles, and then performing a Depth First Search over the children.

The DFS takes the graph that I construct from the input, the group of nodes that are part of the proces, where the Proces ID is the key and the value is a bool to indicate it was seen. The index is the current proces to look at. I set the index within the group to true and then iterate over the children of that proces. If the proces is already seen, ignore it.

Then simply call the connect function again with the updated variables.

func connect(graph [][]int, group map[int]bool, index int) {
	group[index] = true

	for _, node := range graph[index] {
		if !group[node] {
			connect(graph, group, node)
		}
	}
}

The main driver program is straightforward. The first part is simply calling connect on proces 0, then counting the items in group. For part 2 I loop over the graph until all processes are seen in group, counting as a seperate group each time we can call connect on an unseen group.

func solve(input []string) (part1 int, part2 int, err error) {
	graph := make([][]int, len(input))
	for _, v := range input {
		fields := strings.Fields(v)
		node := atoi(fields[0])
		children := make([]int, len(fields)-2)
		for i := 2; i < len(fields); i++ {
			children[i-2] = atoi(strings.Split(fields[i], ",")[0])
		}
		graph[node] = children

	}

	group := make(map[int]bool)

	connect(graph, group, 0)

	part1 = len(group)

	part2 = 1

	for len(group) < len(graph) {
		for index := range graph {
			if !group[index] {
				connect(graph, group, index)
				part2++
			}
		}
	}

	return
}

All done for today.

Tags: , ,

Updated: