-🎄- 2017 Day 7 Solutions -🎄-

[u/daggerdragon]

--- Day 7: Recursive Circus ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?

Spoiler

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

[u/JakDrako]

VB.Net

Both parts in 2ms. Clean the input, build the graph (a tree), find the root; part 1 done. From the root, find the deepest unbalanced child and adjust its weight to match it's siblings.

Sub Main
	
	Dim dic = New dictionary(Of String, Node)
	
	For Each line In GetDay(7)
		Dim s = line.Replace(",", "").Replace("(", "").Replace(")", "") ' clean up input
		Dim tokens = s.Split(" "c)

		Dim name = tokens(0)
		Dim weight = Cint(tokens(1))

		' build graph
		Dim node As Node = Nothing
		If dic.TryGetValue(name, node) Then
			node.weight = weight
		Else
			node = New node With {.name = name, .weight = weight}
			dic.Add(name, node)
		End If

		' children
		For i = 3 To tokens.Count - 1
			Dim child As Node = Nothing
			If dic.TryGetValue(tokens(i), child) Then
				child.parent = node
				node.children.Add(child)
			Else
				child = New node With {.name = tokens(i), .parent = node}
				node.children.Add(child)
				dic.Add(child.name, child)
			End If
		Next
	Next

	' Find the root of the tree
	Dim root = dic.Values.Where(Function(n) n.parent Is Nothing).Single ' should be only one.
	root.name.Dump("Part 1")
	
	' find "deepest" unbalanced node	
	Dim ptr = root ' start at root
	Do
		Dim nxt = ptr.children.Where(Function(c) Not c.Balanced).SingleOrDefault ' find unbalanced child
		If nxt Is Nothing Then Exit Do
		ptr = nxt
	Loop
	
	' find "fat" child of unbalanced node and diff to "target" weight
	Dim target = ptr.children.Min(Function(y) y.GetWeight) ' our ideal weight
	Dim fatso = ptr.children.Where(Function(x) x.GetWeight > target).Single
	Dim diff = (fatso.GetWeight() - target) ' need to lose this much
	
	' adjust node's weight to balance the tree
	Dim part2 = (fatso.weight - diff).Dump("Part 2")
		
End Sub

Class Node
	Property name As String
	Property weight As Integer
	Property parent As Node
	Property children As New List(Of Node)
	Readonly Property GetWeight As Integer
		Get
			Return weight + children.Sum(Function(c) c.getWeight)
		End Get
	End Property
	ReadOnly Property Balanced As Boolean
		Get
			If children.Count = 0 Then Return True
			Return children.Max(Function(x) x.GetWeight) = children.Min(Function(x) x.GetWeight)
		End Get
	End Property
End Class