-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathProgram.fs
88 lines (70 loc) · 2.39 KB
/
Program.fs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
module Day07
open System.IO
type Node =
{ Name: string
Weight: int
Children: string list }
type TreeNode =
{ Name: string
Weight: int
Children: TreeNode list }
let parse (line: string): Node =
let parseLeaf (leaf: string): Node =
let parts = leaf.Split(" ")
let weight = parts.[1].Trim('(', ')')
{ Name = parts.[0]
Weight = int weight
Children = [] }
let parts = line.Split(" -> ")
if Array.length parts < 2 then
parseLeaf parts.[0]
else
let node = parseLeaf parts.[0]
{ node with
Children = parts.[1].Split(", ") |> Array.toList }
let findRootNode (input: Node list): Node =
let hasNoParent (item: Node) =
List.forall (fun (node: Node) -> not (List.contains item.Name node.Children)) input
List.find hasNoParent input
let rec buildTree (input: Node list) (root: Node): TreeNode =
let findNodeByName name =
List.find (fun (node: Node) -> node.Name = name) input
let children =
root.Children
|> List.map findNodeByName
|> List.map (buildTree input)
{ Name = root.Name
Weight = root.Weight
Children = children }
let rec calculateTotalWeight (tree: TreeNode) =
tree.Weight
+ List.sumBy calculateTotalWeight tree.Children
let rec findUnbalancedNode (tree: TreeNode): int option =
let children =
tree.Children
|> List.map (fun node -> (node, calculateTotalWeight node))
let totalWeights = children |> List.map (fun (_, w) -> w)
let (correctTotalWeight, _) =
totalWeights
|> List.countBy id
|> List.filter (fun (_, count) -> count > 1)
|> List.head
children
// Find a child that has a different weight
|> List.tryFind (fun (_, w) -> w <> correctTotalWeight)
|> Option.bind (fun (outlier, totalWeight) ->
// If the outlier has children with different weights, recurse
findUnbalancedNode outlier
// Otherwise, this node is wrong
|> Option.orElse (Some(outlier.Weight + correctTotalWeight - totalWeight)))
[<EntryPoint>]
let main argv =
let input =
File.ReadLines("input.txt")
|> Seq.map parse
|> Seq.toList
let rootNode = findRootNode input
printfn "Part one: %s" rootNode.Name
let tree = buildTree input rootNode
findUnbalancedNode tree |> printfn "Part two: %A"
0