Advent of Code 2015, Day 9 – In Ruby

This is day 9 of 2015.

The first half of the puzzle

Every year, Santa manages to deliver all of his presents in a single night.

This year, however, he has some new locations to visit; his elves have provided him the distances between every pair of locations. He can start and end at any two (different) locations he wants, but he must visit each location exactly once. What is the shortest distance he can travel to achieve this?

For example, given the following distances:

London to Dublin = 464 London to Belfast = 518 Dublin to Belfast = 141

The possible routes are therefore:

Dublin -> London -> Belfast = 982 London -> Dublin -> Belfast = 605 London -> Belfast -> Dublin = 659 Dublin -> Belfast -> London = 659 Belfast -> Dublin -> London = 605 Belfast -> London -> Dublin = 982

The shortest of these is London -> Dublin -> Belfast = 605, and so the answer is 605 in this example.

What is the distance of the shortest route?

The solution:

#!/usr/bin/env ruby

distances = {}

ARGF.each_line(chomp: true).map(&:split).each do |x, _, y, _, d|
  distances[[x, y].sort] = d.to_i
end

results = distances.keys.flatten.uniq.permutation.map do |route|
  route.each_cons(2).reduce(0) do |s, x|
    s + distances[x.sort]
  end
end

puts "Distance of the shortest route: #{results.min}"

First, we parse the input: we split each line into words, and store the relevant ones (the two cities and the distance) in our hash. We sort the city names to make it easier to use the key for both directions.

Then, the meat of the problem:

Get a list of the cities: distances.keys.flatten.uniq. With the example data, it’d be ["London", "Dublin", "Belfast"]
Generate all permutations: .permutation. From above, it’d be

[
  ["London", "Dublin", "Belfast"],
  ["London", "Belfast", "Dublin"],
  ["Dublin", "London", "Belfast"],
  ["Dublin", "Belfast", "London"],
  ["Belfast", "London", "Dublin"],
  ["Belfast", "Dublin", "London"],
]

Transform each permutation to the distances of the given route by first generating the city pairs with .each_cons(2) (result for the first line: [["London", "Dublin"], ["Dublin", "Belfast"]]), then to the distances between the given cities ([464, 141]), then summing the elements (605).
In the end, the results array will be [605, 659, 982, 659, 982, 605], and we pick and print the minimum value, which is 605.

The second half of the puzzle

The next year, just to show off, Santa decides to take the route with the longest distance instead.

He can still start and end at any two (different) locations he wants, and he still must visit each location exactly once.

For example, given the distances above, the longest route would be 982 via (for example) Dublin -> London -> Belfast.

What is the distance of the longest route?

The solution:

#!/usr/bin/env ruby

distances = {}

ARGF.each_line(chomp: true).map(&:split).each do |x, _, y, _, d|
  distances[[x, y].sort] = d.to_i
end

results = distances.keys.flatten.uniq.permutation.map do |route|
  route.each_cons(2).reduce(0) do |s, x|
    s + distances[x.sort]
  end
end

puts "Distance of the shortest route: #{results.max}"

Easy: we simply change the .min in the last line to .max.

The code with my input text is available in the GitHub repo.

Thanks for reading! If you have any comments, additions, or corrections, feel free to reach me via e-mail.