advent-2016-24.rb

# Strategy:
# 1. Find location of each number
# 2. For each combination of 2 numbers, find the distance between them in the graph. Use BFS because I'm lazy
# 3. Brute force the shortest path that goes through each of the 7 numbers.
#   - For each permutation of 7 numbers that begins with 0, sum up the distances for each hop.
#   - E.g. [0, 2, 5, ...] == distance(0, 2) + distance(2, 5) + ...
#   - Find min distance among all permutations

require "byebug"
input = File.read("input.txt").lines.map(&:strip).map(&:chars)
@input = input

PART_TWO = true

digits = (0..7).to_a.map(&:to_s)
digit_locations = {}

# Find digit locations
input.each_with_index do |row, i|
  row.each_with_index do |val, j|
    if digits.include?(val)
      digit_locations[val] = [i, j]
    end
  end
end

distance_between_digits = {}

# For each combination of 2 digits, BFS the distance between them.
digits.each do |a|
  digits.each do |b|
    next if a == b

    to_visit = [[digit_locations[a][0], digit_locations[a][1], 0]]
    visited = {}

    until to_visit.empty?
      i, j, depth = to_visit.shift
      if visited[[i,j]]
        next
      end

      visited[[i,j]] = true

      if @input.dig(i,j) == b
        distance_between_digits[[a,b]] = depth
        break
      end

      unless @input.dig(i, j) == "." || digits.include?(@input.dig(i,j))
        next
      end

      to_visit << [i-1, j, depth + 1] if i > 0
      to_visit << [i+1, j, depth + 1]
      to_visit << [i, j-1, depth + 1] if j > 0
      to_visit << [i, j+1, depth + 1]
    end

    if !distance_between_digits[[a,b]]
      puts "ACK WE COULDN'T FIND #{a} and #{b}"
    end
  end
end

# For each permutation, sum up the total route cost and save the min
# Part 2 includes a final hop from the last point back to "0".
min = Float::INFINITY
digits.permutation.each do |permutation|
  next unless permutation[0] == "0"

  val = distance_between_digits[[permutation[0], permutation[1]]] + distance_between_digits[[permutation[1], permutation[2]]] + distance_between_digits[[permutation[2], permutation[3]]] + distance_between_digits[[permutation[3], permutation[4]]] + distance_between_digits[[permutation[4], permutation[5]]] + distance_between_digits[[permutation[5], permutation[6]]] + distance_between_digits[[permutation[6], permutation[7]]]
  val += distance_between_digits[[permutation[7], permutation[0]]] if PART_TWO

  min = [min, val].min
end

puts min