50 lines
1.3 KiB
Crystal
50 lines
1.3 KiB
Crystal
orbits = File.read("day6.txt").lines.map(&.chomp)
|
|
indirect = {} of String => Set(String)
|
|
direct = {} of String => Set(String)
|
|
edges_from = {} of String => Set(String)
|
|
orbits.each do |orbit|
|
|
big, small = orbit.split(")")
|
|
direct[big] ||= Set(String).new
|
|
direct[big] << small
|
|
(edges_from[big] ||= Set(String).new) << small
|
|
(edges_from[small] ||= Set(String).new) << big
|
|
end
|
|
|
|
def compute_indirect(direct, indirect, for, current)
|
|
indirect[for] ||= Set(String).new
|
|
indirect[for] << current unless current == for
|
|
return unless direct.has_key? current
|
|
direct[current].each do |n|
|
|
compute_indirect(direct, indirect, for, n)
|
|
end
|
|
end
|
|
|
|
direct.each_key do |k|
|
|
compute_indirect(direct, indirect, k, k)
|
|
end
|
|
|
|
total_direct = direct.values.map(&.size).sum
|
|
total_indirect = indirect.values.map(&.size).sum
|
|
puts total_indirect
|
|
|
|
start = "YOU"
|
|
dest = "SAN"
|
|
visited = Set(String).new
|
|
distances = { start => 0 }
|
|
queue = Set { start }
|
|
length = 0
|
|
loop do
|
|
next_node = queue.min_by { |e| distances.fetch(e, 1000000) }
|
|
queue.delete next_node
|
|
|
|
break if next_node == dest
|
|
next if visited.includes? next_node
|
|
visited << next_node
|
|
|
|
edges_from[next_node].each do |neighbor|
|
|
distances[neighbor] ||= distances[next_node] + 1
|
|
queue << neighbor
|
|
end
|
|
end
|
|
puts distances[dest]-2
|
|
|