< up >
2020-12-07 18:35:56 +0100 CET

AoC day7

Todays 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 irelevant 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 returing 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 cound 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…