Advent of Code Day 23 was a classic graph problem entry of this year’s challenge. Lets figure it out!

---

The below is a guest post by the amazing Shraddha Agrawal.

---

Part 1

We are at a LAN party. The input is a list of connections between computers. Each line describes the connection between 2 computers. Consider the example kh-tc, this signifies that computers kh and tc are connected.

It is possible for a computer to be connected to many other computers. For the first part we need to find distinct set of 3 computers that are connected to each other. We need to find the count of such sets where atleast one computer has the name starting with a t.

Solution

We start of with creating a LAN map. The key will be all distinct computers in the input. The value will be another map, in which we will store computers which the key computer is connected to. We are using a map type in value to make searching O(1).

This can be created like below:

func getLANMap(input []string) map[string]map[string]struct{} {
	lanMap := make(map[string]map[string]struct{})

	for _, line := range input {
		comp1, comp2 := line[:2], line[3:]

		if _, ok := lanMap[comp1]; !ok {
			lanMap[comp1] = make(map[string]struct{})
		}

		if _, ok := lanMap[comp2]; !ok {
			lanMap[comp2] = make(map[string]struct{})
		}

		lanMap[comp1][comp2] = struct{}{}
		lanMap[comp2][comp1] = struct{}{}
	}
	return lanMap
}

Once, we have this, to find set of 3 interconnected computers we can simply loop over the above map. For each key, we can iterate over the values and check if they are interconnected as well. If yes, we add them to the result set.

func find3Connected(lanMap map[string]map[string]struct{}) map[lan]struct{} {
	result := make(map[lan]struct{})
	for key, value := range lanMap {
		if len(value) <= 1 {
			continue
		}

		for key2, _ := range value {
			for key3, _ := range value {
				if key2 == key3 {
					continue
				}

				if _, ok := lanMap[key2][key3]; ok {
					r := []string{key, key2, key3}
					sort.Strings(r)
					result[lan{r[0], r[1], r[2]}] = struct{}{}
				}
			}
		}
	}
	return result
}

Lastly, we need to get the count of sets where atleast one computer starts with a t :

func findT(input map[lan]struct{}) int {
	count := 0
	for key, _ := range input {
		if string(key.a[0]) == "t" || string(key.b[0]) == "t" || string(key.c[0]) == "t" {
			count++
		}
	}
	return count
}

This gives us the answer to part 1.

Part 2

Now instead of a set of 3 computers interconnected, we need to find the set with the maximum number of interconnected computers. The answer should be the alphabetical order of the computers in the largest set separated by commas.

Solution

Searching about this on the internet, I came across the Bron–Kerbosch algorithm. This is used to find set of vertices that are all interconnected. This is called cliques in graph theory.

Implementing the algorithm:

func BronKerbosch(currentClique []string, yetToConsider []string, alreadyConsidered []string, lanMap map[string]map[string]struct{}, cliques [][]string) [][]string {
	if len(yetToConsider) == 0 && len(alreadyConsidered) == 0 {
		cliques = append(cliques, append([]string{}, currentClique...))
		return cliques
	}

	for index := 0; index < len(yetToConsider); {
		node := yetToConsider[index]
		newYetToConsider := []string{}
		newAlreadyConsidered := []string{}

		for _, n := range yetToConsider {
			if _, ok := lanMap[node][n]; ok {
				newYetToConsider = append(newYetToConsider, n)
			}
		}

		for _, n := range alreadyConsidered {
			if _, ok := lanMap[node][n]; ok {
				newAlreadyConsidered = append(newAlreadyConsidered, n)
			}
		}

		cliques = BronKerbosch(append(currentClique, node), newYetToConsider, newAlreadyConsidered, lanMap, cliques)

		yetToConsider = append(yetToConsider[:index], yetToConsider[index+1:]...)
		alreadyConsidered = append(alreadyConsidered, node)
	}
	return cliques
}

Now, we can iterate over all the cliques found from the above algorithm to find the set of computers with the maximum length:

func findMaxCliques(lanMap map[string]map[string]struct{}) string {
	maxClique := []string{}
	allComputers := []string{}
	for key, _ := range lanMap {
		allComputers = append(allComputers, key)
	}
	cliques := BronKerbosch([]string{}, allComputers, []string{}, lanMap, [][]string{})
	for _, c := range cliques {
		if len(c) > len(maxClique) {
			maxClique = c
		}
	}
	sort.Strings(maxClique)
	return strings.Join(maxClique, ",")
}

And that gives us the answer to Part 2! You can find my final code here.

This was a fairly easy day and I learned a new algorithm! Graphs are one of my weaker data structures so I appreciate the puzzle for contextualising the usage of graphs and its gentle nudge to find the right algorithm to solve the second part.

How did you solve Day 23? I would love to compare notes and checkout your solution. Reach out to me on Twitter, Bluesky or on e-mail at contact[at]shraddhaag[dot]dev.