Notice: If you have coding experience, I highly recommend to try and solve the puzzle in a language you already know. It's a lot of fun and you'll be able to focus on Go more later on.

Did you know the internet is a series of pipes? No? Well, today’s problem is all about pipes. Go read the problem description, it’s a fun one. Go on, I’ll wait here until you’re ready.

Good, you’re back! Let’s get started. On the agenda for today: reusing your code.

Today’s problem is a rather easy graph problem: we get a set of edges that make up multiple, disconnected graphs. Find the number of nodes in the graph that contains node “0”. Modelling your data is always a good place to start. In this case, the input file describes a set of edges of the graph: program A is connected to program B,C and D. Let’s create a new datastructure EdgeSet in our collection package from day 4. Each program in the map is connected to the program in the corresponding slice. While the input file has numerical id’s for the programs, the problem description doesn’t give us any indication we need to use the actual int value. We’re not bothering with the parsing and will just use the id’s as strings.

type EdgeSet map[string][]string

Ok, so using this datastructure, we want to separate the programs into multiple disconnected sets. In our day 4 solution, we already created a datastructure to hold a set of strings, the StringSet. We can create a function with this signature to create the disconnected sets:

func (es EdgeSet) NodeSets() []StringSet {
}

Think about the implementation for a moment, while we put our focus on the main program for a moment. You may be wondering why we’re computing all the disconnected program sets, while part A of the problem description only asks about the set that contains “0”. It’s got something to do with part B: find the total number of disconnected sets. Because we’ve put all the hard datastructure & algorithmic work into the collection package, the main program becomes fairly simple:

package main

import (
	"fmt"
	"os"

	"github.com/blackskad/adventofcode/collection"
)

func Solve() {
	if len(os.Args) < 2 {
		fmt.Println("Missing input file name.")
		os.Exit(1)
	}

	pipes := collection.NewEdgeSetFromFile(os.Args[1])

	sets := pipes.NodeSets()
	for _, set := range sets {
		if set.Contains("0") {
			fmt.Println("Part A:", len(set))
			break
		}
	}
	fmt.Println("Part B:", len(sets))
}

There are a couple of things to note:

• The function NewEdgeSetFromFile loads the edges from the input file, similarly to the load function of previous solutions. There’s no new magic going on there, it just returns a collection.EdgeSet object.
• Go’s compiler is really smart, it can infer the types of all the variables without additional hints from our side. It knows pipes is an collection.EdgeSet and that the NodeSets method returns sets as a slice of collection.StringSet objects. That means we can keep our code light. While we’re using the types from the collection package, we never actually mention the types. it makes the code really easy to read and understand.

Easy, right? Time to shift our focus back to the NodeSets method. The algorithm is quite easy: Loop over all the programs, when the program is not yet in an existing set, create a new set and add the linked programs recursively.

// Recursively add all programs that are linked to the origin program to the set.
func (es EdgeSet) buildNodeSet(set StringSet, origin string) {
	for _, d := range es[origin] {
		if set.Put(d) {
			es.buildNodeSet(set, d)
		}
	}
}

func (es EdgeSet) NodeSets() []StringSet {
	sets := []StringSet{}

	for o := range es {
		found := false
		for _, s := range sets {
			if s.Contains(o) {
				found = true
				break
			}
		}
		if !found {
			newset := NewStringSet()
			newset.Put(o)

			es.buildNodeSet(newset, o)
			sets = append(sets, newset)
		}
	}
	return sets
}

That’s it! The full solution is available in my github repository. See you all tomorrow!