From 89015b843418b045c777dc20ca3cc3f052e7b9d2 Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <marcin.j.chrzanowski@gmail.com>
Date: Fri, 25 Dec 2020 15:33:34 +0100
Subject: Add day 16

---
 16/b.rb | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 76 insertions(+)
 create mode 100644 16/b.rb

(limited to '16/b.rb')

diff --git a/16/b.rb b/16/b.rb
new file mode 100644
index 0000000..d981c02
--- /dev/null
+++ b/16/b.rb
@@ -0,0 +1,76 @@
+require 'set'
+
+sections = File.read('input.txt').split "\n\n"
+
+fields = sections[0].split "\n"
+my_ticket_line = sections[1].split("\n")[1]
+my_ticket = my_ticket_line.split(',').map {|n| n.to_i}
+ticket_lines = sections[2].split("\n")
+tickets = ticket_lines.slice(1, ticket_lines.size).map {|t| t.split(',').map {|n| n.to_i}}
+
+valid_values = {}
+valid_all = {}
+
+fields.each do |field|
+  f, range1, range2 = field.split(/: | or /)
+  valid_values[f] = []
+  [range1, range2].each do |range|
+    from, to = range.split('-').map {|n| n.to_i}
+    valid_values[f].push (from..to)
+    (from..to).each do |n|
+      valid_all[n] = true
+    end
+  end
+end
+
+candidates = []
+my_ticket.each do
+  candidates.push(Set.new valid_values.keys())
+end
+
+tickets = tickets.filter do |ticket|
+  ticket.all? { |n| valid_all[n] }
+end
+
+tickets.each do |ticket|
+  ticket.each_with_index do |n, i|
+    valid_values.each do |field, valid|
+      if !(valid[0].include?(n) || valid[1].include?(n))
+        candidates[i].delete(field)
+      end
+    end
+  end
+end
+
+decided = Set.new
+mapping = {}
+changed = true
+while changed
+  changed = false
+  new_decided = candidates.find do |c|
+    if c.size == 1
+      f = c.to_a[0]
+      !decided.member? f
+    else
+      false
+    end 
+  end
+  if new_decided
+    index = candidates.find_index new_decided
+    field = new_decided.to_a[0]
+    decided.add field
+    mapping[field] = index
+    changed = true
+    candidates.each do |c|
+      c.delete(field)
+    end
+  end
+end
+
+product = 1
+mapping.each do |field, index|
+  if field =~ /departure/
+    product *= my_ticket[index]
+  end
+end
+puts product
-- 
cgit v1.2.3