advent_of_code_santa_claus_route_planning.rb

#!/usr/bin/env ruby

require 'set'

$places   = Set[]
$distance = Hash.new(Float::INFINITY)

for distance in DATA
  /^(?<from>\w+) to (?<to>\w+) = (?<distance>\d+)/ =~ distance
  $places << from << to
  $distance[ [ from, from ] ] = Float::INFINITY
  $distance[ [ to, to ] ]     = Float::INFINITY
  $distance[ [ to, from ] ]   = distance.to_f
  $distance[ [ from, to ] ]   = distance.to_f
end

results = $places.to_a.permutation.map { |tour|
  # Get back to where we started: tour.push tour.first
  [
    tour,
    tour.each_cons(2).inject(0.0) { |d, (from, to)| d + $distance[ [ from, to ] ] }
  ]
}.sort_by(&:last)
shortest_distance = results.first.last
optimal_results = results.select { |r| r.last <= shortest_distance }
for ((optimal_tour, tour_distance), i) in optimal_results.each_with_index
  puts "#{i + 1}. Optimal tour #{optimal_tour * ?→} has length #{tour_distance}."
end

__END__
AlphaCentauri to Snowdin = 66
AlphaCentauri to Tambi = 28
AlphaCentauri to Faerun = 60
AlphaCentauri to Norrath = 34
AlphaCentauri to Straylight = 34
AlphaCentauri to Tristram = 3
AlphaCentauri to Arbre = 108
Snowdin to Tambi = 22
Snowdin to Faerun = 12
Snowdin to Norrath = 91
Snowdin to Straylight = 121
Snowdin to Tristram = 111
Snowdin to Arbre = 71
Tambi to Faerun = 39
Tambi to Norrath = 113
Tambi to Straylight = 130
Tambi to Tristram = 35
Tambi to Arbre = 40
Faerun to Norrath = 63
Faerun to Straylight = 21
Faerun to Tristram = 57
Faerun to Arbre = 83
Norrath to Straylight = 9
Norrath to Tristram = 50
Norrath to Arbre = 60
Straylight to Tristram = 27
Straylight to Arbre = 81
Tristram to Arbre = 90