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.