# Advent of Code 2017, Day 7: Recursive Circus

## Part A

On Day 7 we are building a tree which is described in the input file that looks like this:

``````pbga (66)
xhth (57)
ebii (61)
havc (66)
ktlj (57)
fwft (72) -> ktlj, cntj, xhth
qoyq (66)
padx (45) -> pbga, havc, qoyq
tknk (41) -> ugml, padx, fwft
jptl (61)
ugml (68) -> gyxo, ebii, jptl
gyxo (61)
cntj (57)
``````

On the left we have the name of any particular node and on the right we have its children. Our task is to output the name of the root node.

``````data = File.readlines("7.txt", chomp: true)
hash = {}

data.each do |line|
match = line.match(/(.+?) \((\d+)\)(?: -> (.+))?\$/)
name = match[1]
weight = match[2]
children = (match[3] || "").split(", ").map(&:strip)

hash[name] ||= "root"

children.each do |name|
hash[name] = "child"
end
end

hash.each do |key, value|
if value == "root"
puts key
break
end
end
``````

We are storing all nodes in `hash` hash. Node name is used as key and the value can be either `root` or `child`. If we first see a particular node we mark it as root node. When later the same name is again seen as a child we change it to child.

At the end we scan the whole hash and output the name of the node that is root. There should be just one.

## Part B

I will just leave my solution here:

``````data = File.readlines("7.txt", chomp: true)
hash = {}

data.each do |line|
match = line.match(/(.+?) \((\d+)\)(?: -> (.+))?\$/)
name = match[1]
weight = match[2].to_i
children = (match[3] || "").split(", ").map(&:strip)

hash[name] = {
weight: weight,
total: 0,
children: children
}
end

def weight(hash, name)
node = hash[name]

if node[:children].any?
node[:total] = node[:weight] + node[:children].map { |child| weight(hash, child) }.sum
else
node[:total] = node[:weight]
end

return node[:total]
end

weight(hash, "fbgguv")

current = "fbgguv"
difference = nil

while true
node = hash[current]

break if node[:children].empty?

weights = {}
counts = {}

node[:children].each do |child|
weight = hash[child][:total]
weights[child] = weight
counts[weight] ||= 0
counts[weight] += 1
end

unbalanced_weight = nil
balanced_weight = nil
counts.each do |weight, count|
if count == 1
unbalanced_weight = weight
else
balanced_weight = weight
end
end

unbalanced_child = nil
node[:children].each { |child| unbalanced_child = child if hash[child][:total] == unbalanced_weight }

difference ||= unbalanced_weight - balanced_weight

if unbalanced_weight.nil?
puts node[:weight] - difference
break
end

current = unbalanced_child
end
``````

The weird string is the answer for the first part.