require_relative 'util'
require 'set'

# --- Day 24: Electromagnetic Moat ---

# The CPU itself is a large, black building surrounded by a bottomless
# pit. Enormous metal tubes extend outward from the side of the
# building at regular intervals and descend down into the
# void. There's no way to cross, but you need to get inside.

# No way, of course, other than building a bridge out of the magnetic
# components strewn about nearby.

# Each component has two ports, one on each end. The ports come in all
# different types, and only matching types can be connected. You take
# an inventory of the components by their port types (your puzzle
# input). Each port is identified by the number of pins it uses; more
# pins mean a stronger connection for your bridge. A 3/7 component,
# for example, has a type-3 port on one side, and a type-7 port on the
# other.

# Your side of the pit is metallic; a perfect surface to connect a
# magnetic, zero-pin port. Because of this, the first port you use
# must be of type 0. It doesn't matter what type of port you end with;
# your goal is just to make the bridge as strong as possible.

# The strength of a bridge is the sum of the port types in each
# component. For example, if your bridge is made of components `0/3`,
# `3/7`, and `7/4`, your bridge has a strength of `0+3 + 3+7 + 7+4 =
# 24`.

# For example, suppose you had the following components:

#     0/2
#     2/2
#     2/3
#     3/4
#     3/5
#     0/1
#     10/1
#     9/10

# With them, you could make the following valid bridges:

# - 0/1
# - 0/1--10/1
# - 0/1--10/1--9/10
# - 0/2
# - 0/2--2/3
# - 0/2--2/3--3/4
# - 0/2--2/3--3/5
# - 0/2--2/2
# - 0/2--2/2--2/3
# - 0/2--2/2--2/3--3/4
# - 0/2--2/2--2/3--3/5

# (Note how, as shown by `10/1`, order of ports within a component
# doesn't matter. However, you may only use each port on a component
# once.)

# Of these bridges, the strongest one is `0/1--10/1--9/10`; it has a
# strength of `0+1 + 1+10 + 10+9 = 31`.

# What is the strength of the strongest bridge you can make with the
# components you have available?

def parse(input)
  input.split("\n").map do |line|
    from, to = line.split('/')
    [from.to_i, to.to_i]
  end
end

def bridge_strength(bridge)
  bridge.map(&:sum).sum
end

def bridge_each(components, starter, result = nil, value = 0, &block)
  pool = components.clone.delete(starter)
  result ||= [starter]
  yield(result)
  other = starter[0] == value ? starter[1] : starter[0]
  pool.each do |link|
    next unless link.include?(other)
    bridge_each(pool, link, result + [link], other, &block)
  end
end

def strongest_bridge(input)
  components = Set.new(parse(input))
  starters = components.select { |c| c[0].zero? }
  max = 0
  starters.each do |starter|
    bridge_each(components, starter) do |bridge|
      score = bridge_strength(bridge)
      max = score if score > max
    end
  end
  max
end

def easy(input)
  strongest_bridge(input)
end

test_input = "0/2\n2/2\n2/3\n3/4\n3/5\n0/1\n10/1\n9/10"
input = File.open('24.txt') { |f| f.read.chomp }

assert(easy(test_input) == 31)
puts "easy(input): #{easy(input)}"

# --- Part Two ---

# The bridge you've built isn't long enough; you can't jump the rest
# of the way.

# In the example above, there are two longest bridges:

# - 0/2--2/2--2/3--3/4
# - 0/2--2/2--2/3--3/5

# Of them, the one which uses the 3/5 component is stronger; its
# strength is `0+2 + 2+2 + 2+3 + 3+5 = 19`.

# What is the strength of the longest bridge you can make? If you can
# make multiple bridges of the longest length, pick the strongest one.

def longest_bridges(input)
  components = Set.new(parse(input))
  starters = components.select { |c| c[0].zero? }
  longest = []
  max = 0
  starters.each do |starter|
    bridge_each(components, starter) do |bridge|
      longest = [] if bridge.length > max
      longest << bridge if bridge.length >= max
      max = bridge.length if bridge.length > max
    end
  end
  longest
end

def hard(input)
  longest = longest_bridges(input)
  longest.map { |bridge| bridge_strength(bridge) }.max
end

assert(hard(test_input) == 19)
puts "hard(input): #{hard(input)}"