On Day 24 we have Travelling Salesman Problem. Well, maybe not exactly, but similar. In TSP you need to visit each city exactly once and here you can visit air ducts multiple times. Our input looks like this:
###########
#0.1.....2#
#.#######.#
#4.......3#
###########
We need to tell what is the fewest number of steps to visit every point with number at least once.
It is a graph problem again. We don’t need to care about all those points on the map. We should only care about distances between air ducts, those numbered nodes. And we need to calculate distances between every pair of nodes. We can use Floyd-Warshall algorithm to calculate such distances, but this algorithm has complexity O(n^3) where n is number of nodes. Our real input is thousands of all nodes and only 8 of those numbered nodes. I implemented it in the beginning, but it was taking way too long.
So what we can do instead is to use Breadth-First Search (BFS) and just run it for each pair of numbered nodes.
Finally we can use recursion to explore all possible solutions or in other words permutations of orders in which we will visit air ducts. And we will choose the shortest one. Here is the full solution:
def parse_input(filename)
data = File.readlines(filename, chomp: true).map { |line| line.split("") }
width = data[0].size
height = data.size
nodes = {}
points = []
data.each_with_index do |row, y|
row.each_with_index do |item, x|
next if item == "#"
nodes[[x, y]] = []
points[item.to_i] = [x, y] if item =~ /\d+/
end
end
nodes.each do |(x, y), neighbors|
candidates = [
[x + 1, y],
[x - 1, y],
[x, y + 1],
[x, y - 1]
]
candidates.each do |key|
if nodes[key]
neighbors.push(key)
end
end
end
[nodes, points]
end
def bfs(nodes, points, start)
queue = [[points[start], 0]]
visited = { points[start] => true }
paths = Array.new(points.size, Float::INFINITY)
paths[start] = 0
while !queue.empty?
current, time = queue.shift
if points.include?(current)
paths[points.index(current)] = time
end
return paths if paths.none? { |item| item == Float::INFINITY }
nodes[current].each do |neighbor|
if !visited[neighbor]
queue.push([neighbor, time + 1])
visited[neighbor] = true
end
end
end
end
nodes, points = parse_input("24.txt")
paths = (0...(points.size)).map do |index|
bfs(nodes, points, index)
end
def solve(paths, remaining = [], start = 0, total = 0)
return total if remaining.empty?
remaining.permutation(1).to_a.map do |(key)|
solve(paths, remaining - [key], key, total + paths[start][key])
end.min
end
puts solve(paths, (1...(points.size)).to_a)
In the second part we need to visit all air ducts and then return back to the beginning. We can just slightly modify our previous solve method and write this:
def solve(paths, remaining = [], start = 0, total = 0)
return total + paths[start][0] if remaining.empty?
remaining.permutation(1).to_a.map do |(key)|
solve(paths, remaining - [key], key, total + paths[start][key])
end.min
end
This time when returning the value we also add path from the last visited node to the first one.