# Advent of Code 2016, Day 24: Air Duct Spelunking

## Part A

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.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)

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)
``````

## Part B

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)