-
Notifications
You must be signed in to change notification settings - Fork 0
/
day06.jl
69 lines (61 loc) · 1.54 KB
/
day06.jl
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
mutable struct Node
name::String
children::Array{Node,1}
parent::Union{Node,Nothing}
end
Node(name) = Node(name, [], nothing)
const Tree = Dict{String,Node}
function read_tree(filename::String)
open(filename, "r") do inputfile
T = Tree()
for line in eachline(inputfile)
edge = split(line, ")")
parent = get!(T, edge[1], Node(edge[1]))
child = get!(T, edge[2], Node(edge[2]))
push!(parent.children, child)
child.parent = parent
end
return T
end
end
function find_depth(T::Tree)
depth = Dict([(v, 0) for (v, _) in T])
Q = [T["COM"]]
while !isempty(Q)
v = pop!(Q)
for c in v.children
depth[c.name] = depth[v.name] + 1
pushfirst!(Q, c)
end
end
return depth
end
function find_common_ancestor(a::Node, b::Node, depth::Dict{String,Int})
depth_a = depth[a.name]
depth_b = depth[b.name]
while depth_a > depth_b
a = a.parent
depth_a -= 1
end
while depth_b > depth_a
b = b.parent
depth_b -= 1
end
while a != b
a = a.parent
b = b.parent
depth_a -= 1
depth_b -= 1
end
return a
end
function main()
T = read_tree("input06.txt")
depth = find_depth(T)
part1 = sum(values(depth))
println("PART 1: $(part1)")
a = find_common_ancestor(T["YOU"], T["SAN"], depth)
part2 = depth["YOU"] - depth[a.name] + depth["SAN"] - depth[a.name] - 2
println("PART 2: $(part2)")
end
main()