Discussion on: Advent of Code 2020 Solution Megathread - Day 16: Ticket Translation

rules, yours, nearby = File.read('input.txt').split(/\n\n/)

def ticket_values(nearby)
   nearby.split("\n")[1..]
end

def category_values(rules)
  rules.split("\n").each_with_object({}) do |line, categories|
    next if line.empty?

    category, values = line.chomp.split(': ')

    categories[category] = values
      .split(' or ')
      .map { |range| range.split('-').map(&:to_i) }
      .map { |(from, to)| (from..to) }
  end
end

def invalid?(value, ranges)
  ranges.none? { |range| range.cover?(value) }
end

def parse_ticket(ticket)
  ticket.chomp.split(',').map(&:to_i)
end

def valid_tickets(tickets, categories)
  ranges = categories.values.flat_map(&:itself)

  tickets.map do |ticket|
    values = parse_ticket(ticket)

    next values if values.none? { |value| invalid?(value, ranges) }
  end.compact
end

your_ticket = parse_ticket(yours.split("\n").last)

categories = category_values(rules)
tickets = ticket_values(nearby)
valids = valid_tickets(tickets, categories) + [your_ticket]

# This transposes the tickets from [ticket, ticket, ticket] to
# [column, column, column]. Makes it much easier to check all the values
# in a certain column, and is much faster than to skip over many values
# in many tickets to achieve the same _enumeration_.
transpose_tickets = valids.transpose

# For each column, find which categories would be applicable. This is done
# by seeing which categories' ranges satisfy _all_ values in a column.
category_options = transpose_tickets.map do |col_values|
  categories.select do |category, ranges|
    col_values.none? { |value| invalid?(value, ranges) }
  end.map(&:first)
end

# Each category now has 1 or more options. This entire function can be
# optimised, because all input data will generate options of size 1, 2, 3 ... n
# which means that the logic to find which category can be assigned is
# much simpler than actually counting options and removing them once
# they've been chosen.
#
# naive  0.000000   0.000000   0.000000 (  0.000074)
#  sort  0.000000   0.000000   0.000000 (  0.000035)
#
# But I like this more general purpose (naive) solution better.

=begin
column_categories = []

categories.length.times do
  index = category_options.find_index { |options| options.length === 1 }
  category = category_options[index].first

  category_options.each do |options|
    options.delete(category)
  end

  column_categories[index] = category
end
=end

# Here is the optimised (sort) solution
column_categories = category
  .sort { |a, b| a.length - b.length }
  .each_with_object([]) do |options, result|
    result << (options - result).first
  end
end

your_ticket_with_categories = column_categories.zip(your_ticket).to_h
departure_fields = your_ticket_with_categories.select { |k,_| k.start_with?('departure') }

puts departure_fields
puts departure_fields.values.inject(&:*)