AoC day7
Today’s puzzles were about bags which contain a certain amount of other bags (and so on) based on the rules from the input. The first one asks for the amount of different bags in which our -shiny gold- one is contained. The second one asks for the count of bags the own contains.
Abstraction
Let’s say each bag is a node and each rule is an edge with the count as edge-value. Then this problem can be converted into a graph theory one. Since this puzzle is solvable it can be assumed that the graph has no circles. Furthermore it can be assumed that this graph is a tree starting with the own bag -shiny gold- as root. Bags which contain no further one are the leaves. All other graphs not related to this tree (if any) are irrelevant and can be ignored.
This tree can be traversed for both puzzles recursively with an ordinary depth search. Below is an implementation of a depth search finding a node in a given tree.
type Node []string
type Tree map[string]Node
func depthSearch(current, goal string, tree Tree) bool {
if current == goal {
return true
}
for subNode, _ := range tree[current] {
if depthSearch(subNode, goal, tree) {
return true
}
}
return false
}
In this simplified depth search, a tree maps nodes name to a node. A node is a list of all related sub nodes identified by node names.
type Node []string
type Tree map[string]Node
The signature takes the current- such as the goal node name and the tree itself returning if the goal has been reached.
func depthSearch(current, goal string, tree Tree) bool
The abort condition of this recursion is satisfied if the goal has been reached. One can move this condition to the sub node loop. But imo it is code style to put it at the very first showing any reader when this recursion ends such as preventing errors leading to stack overflows.
if current == goal {
return true
}
To go in depth, the loop iterates over all sub nodes and calls itself for each
one. On reaching the goal the search immediately returns true and arises from
the depth. If the goal hasn’t been reached a search terminates if a node hasn’t any further sub nodes.
for subNode, _ := range tree[current] {
if depthSearch(subNode, goal, tree) {
return true
}
}
return false
Puzzle 1 - Find node
It should be counted how many nodes contain our -shiny gold- bag. This can be accomplished by searching it in each unique node and round the times it could be found.
found := 0
for name, _ := range tree {
if depthSearch(name, "shiny gold", tree) {
found++
}
}
The code from the last section can be used directly for the search.
Puzzle 2 - Count payload
In this puzzle, each bag has various amounts of sub nodes. Those amounts are not relevant for the search itself and called payload from here.
In contrast to the abstraction the below function is more a graph traversal than a search. Since the payload of all nodes is needed to calculate the total count of bags, the whole tree has to be traversed.
type Node map[string]int
type Tree map[string]Node
func DepthSearch(current string, tree Tree) int {
total := 1
for subNode, count := range tree[current] {
total += count * DepthSearch(subNode, tree)
}
return total
}
Each node is now a mapping from sub node names to its payload. A tree is still a mapping from node name to node.
type Node map[string]int
type Tree map[string]Node
No goal is necessary anymore since all nodes have to be visited and the search returns the total amount based on the given calculation from AoC.
func DepthSearch(current string, tree Tree) int
Initially, the total amount of sub bags is set to one in order to return the count for the current bag itself. This is also the reason why the final count is off by one. For example: A tree only containing our -shiny bag- has a count of zero and not the count of contained bags.
total := 1
Using the payload and the return value of the depth search, the amount of all bags inside one sub bag can be calculated.
for subNode, count := range tree[current] {
total += count * DepthSearch(subNode, tree)
}
Finally return the calculated/found amount of bags. Note that the definition of
total and this return will be the only effective lines in leaves (nodes
without any sub nodes).
return total
PS: I need to find alternatives for ‘the’ beginning of sentences…