Day 16: Ticket Translation

The first part was relatively straightforward and I got to bust out the handy dandy itertools package to flatten nested lists. I stored the rules as a table where each field corresponded to a list of ranges that can be checked to determine if the field values are valid. I used this table to basically find all the invalid nearby tickets by checking if any values did not fit into any of the ranges specified by the field rules.

import itertools
import re
import sys

# Functions

def read_rules():
    rules = {}

    while line := sys.stdin.readline().strip():
        field, ranges = line.split(':', 1)
        rules[field]  = [
            (int(s), int(e)) for s, e in re.findall(r'(\d+)-(\d+)', ranges)
        ]

    return rules

def read_tickets():
    return [
        [int(f) for f in l.split(',')] for l in sys.stdin if ',' in l
    ]

def flatten(iterable):
    return list(itertools.chain.from_iterable(iterable))

def find_invalid_fields(rules, ticket):
    all_ranges = flatten(rules.values())

    for value in ticket:
        if not any(s <= value <= e for s, e in all_ranges):
            yield value

# Main Execution

def main():
    rules    = read_rules()
    tickets  = read_tickets()
    nearby   = tickets[1:]
    invalids = flatten(
        find_invalid_fields(rules, ticket) for ticket in nearby
    )

    print(sum(invalids))

if __name__ == '__main__':
    main()

The second part took me a lot longer mainly because I forgot to include my own ticket (the first ticket) when considering which fields corresponded to which index, and because I didn't realize that multiple fields could satisify different columns. That is, a column like "row" could work for indices say 1, 4, and 5. Originally, I just picked the first index that worked, but that then left certain indices unmatched.

To fix this, I had two phases: first I scanned the tickets and rules to determine which indices could work for which rules. I did this in my find_matches function which returns a table that contains a list of indices that are valid for each field. Next, in my find_fields function, I determined the exact mapping of field to index by finding all the fields with a single index match, storing that in my mapping, and then removing that index from all the other fields. Eventually, this narrows down the indices each field could serve until I got an exact mapping of field to index. This is very similar to topological sort and I had actually done a problem quite similar to this in year's past. Once I saw that the initial match had a single field with only one index, I knew I had to apply a topological sorting process.

Once I had this table, then I just needed to filter out the departure values and multiply them. I must admit, I tried pretty hard in using as many list comprehensions and functional programming techniques here... I think it's mostly readable :]

import functools
import itertools
import operator
import re
import sys

# Functions

def read_rules():
    rules = {}

    while line := sys.stdin.readline().strip():
        field, ranges = line.split(':', 1)
        rules[field]  = [(int(start), int(end)) for start, end in re.findall(r'(\d+)-(\d+)', ranges)]

    return rules

def read_tickets():
    return [[int(field) for field in line.split(',')] for line in sys.stdin if ',' in line]

def flatten(iterable):
    return itertools.chain.from_iterable(iterable)

def is_ticket_valid(rules, ticket):
    return all(any(s <= v <= e for s, e in flatten(rules.values())) for v in ticket)

def find_matches(rules, tickets):
    matches = {}
    
    for field, ranges in rules.items():
        matches[field] = [ 
            index for index in range(len(tickets[0])) if all(
                any(s <= ticket[index] <= e for s, e in ranges) for ticket in tickets
            )
        ]

    return matches

def find_fields(matches):
    fields = {}

    while matches:
        singles = [(field, indices[0]) for field, indices in matches.items() if len(indices) == 1]

        for field, index in singles:
            fields[index] = field
            for f in matches:
                matches[f].remove(index)
            del matches[field]

    return fields

# Main Execution

def main():
    rules    = read_rules()
    tickets  = read_tickets()
    valids   = [ticket for ticket in tickets if is_ticket_valid(rules, ticket)]

    matches  = find_matches(rules, valids)
    fields   = find_fields(matches)

    values   = [value for index, value in enumerate(tickets[0]) if fields[index].startswith('departure')]
    result   = functools.reduce(operator.mul, values, 1)

    print(result)

if __name__ == '__main__':
    main()

import re

with open("input.txt") as inputFile:
    tickedData = inputFile.read()

# [lower limit 1, upper limit 1, lower limit 2, upper limit 2, rule name]
rules = [[int(rule[1]), int(rule[2]), int(rule[3]), int(rule[4]), rule[0]]
         for rule in re.findall(r'([a-z| ]+)\: (\d+)\-(\d+) or (\d+)\-(\d+)', tickedData)]

myTicket = [int(number) for number in re.findall(
    r'your ticket\:\n(.+)\n', tickedData)[0].split(",")]

nearbyTickets = [list(map(int, numbers.split(",")))
                 for numbers in re.findall(r'nearby tickets\:\n(.+)',
                                           tickedData, re.DOTALL)[0].split("\n")]


def validate(tickets, myTicket, rules):
    invalidNumbers = []
    validTickets = []

    for ticket in tickets:
        ticketValid = True
        for number in ticket:
            numberValid = False
            for rule in rules:
                if (number >= rule[0] and number <= rule[1]) or (number >= rule[2] and number <= rule[3]):
                    numberValid = True
                    break
            if not numberValid:
                invalidNumbers.append(number)
                ticketValid = False
                break
        if ticketValid:
            validTickets.append(ticket)
    print("Scanning error rate:", sum(invalidNumbers))
    validTickets.append(myTicket)
    return validTickets


def findPositions(tickets, rules):
    fieldPossibilities = {}
    for rule in rules:
        fieldPossibilities[rule[4]] = ["?"] * len(rules)

    for ticket in tickets:
        for pos in range(0, len(ticket)):
            for rule in rules:
                if not ((ticket[pos] >= rule[0] and ticket[pos] <= rule[1]) or (ticket[pos] >= rule[2] and ticket[pos] <= rule[3])):
                    # this rule's field name can't be at pos!
                    fieldPossibilities[rule[4]][pos] = "."

    positions = {}
    while len(positions) < len(rules):
        for field in fieldPossibilities:
            if fieldPossibilities[field].count("?") == 1:
                # only one possible position for this field name!
                index = fieldPossibilities[field].index("?")
                positions[field] = index
                for f in fieldPossibilities:
                    # invalidate others for this position by marking them "."
                    fieldPossibilities[f][index] = "."
    return positions


def departureProduct(positions, myTicket):
    departureProduct = 1
    for posName in positions:
        if "departure" in posName:
            departureProduct *= myTicket[positions[posName]]
    print("Product of all departure fields:", departureProduct)


validTickets = validate(nearbyTickets, myTicket, rules)
positions = findPositions(validTickets, rules)
departureProduct(positions, myTicket)

For this one I just do some regex to build a list of all possible valid numbers as I read in the rules. Then I compare each ticket against the full list of all valid numbers, keeping track of the error scanning rate as it goes

import re
#data = test_data
data = input_data
fields, my_ticket, nearby_tickets = data.split('\n\n')

valid_nums = []
pattern = re.compile('(\d+)-(\d+) or (\d+)-(\d+)')
for row in fields.split('\n'):
    matches = pattern.search(row)
    valid_nums = valid_nums + list(range(int(matches.group(1)),int(matches.group(2))+1))
    valid_nums = valid_nums + list(range(int(matches.group(3)),int(matches.group(4))+1))
valid_nums = list(set(valid_nums))

error_scanning_rate = 0
for row in nearby_tickets.split('\n')[1:]:
    vals = map(int,row.split(','))
    for val in vals:
        if val in valid_nums:
            pass
        else:
            error_scanning_rate = error_scanning_rate + val
print(error_scanning_rate)

Part B was a fair bit more complicated.

First I adjusted my regex a bit to grab the field data, I probably should have done this in part A, but whatever.

Then I assigned a big grid (dictionary full of lists) called 'unknown fields' to help me track what all the possibilities could be.

Then I pass through all the data, eliminating any errors or impossibilities from my grid.

Finally, I continue looping through my unknown data and checking particular field is down to one possibility. If it is, then I declare it known and remove it as a possibility from other areas. Which hopefully will reduce at least one other combination down to one. I keep doing that until I have everything locked in, at which point I calculate the answer.

My removal and validation process are definitely not as clean and efficient as I would like them to be, but they work well enough for a data set of this size. I'm still somewhat ashamed of my loopy mess.

import re
#data = test_data
data = input_data
fields, my_ticket, nearby_tickets = data.split('\n\n')

valid_nums = []
pattern = re.compile('(.+): (\d+)-(\d+) or (\d+)-(\d+)')
field_info = {}
for index,row in enumerate(fields.split('\n')):
    matches = pattern.search(row)
    valid_vals = []
    valid_vals = valid_vals + list(range(int(matches.group(2)),int(matches.group(3))+1))
    valid_vals = valid_vals + list(range(int(matches.group(4)),int(matches.group(5))+1))
    field_info[matches.group(1)] = list(set(valid_vals))
    valid_nums = valid_nums + valid_vals
valid_nums = list(set(valid_nums))

valid_tickets = []
my_ticket = my_ticket.split('\n')[1:]
for row in my_ticket + nearby_tickets.split('\n')[1:]:
    vals = list(map(int,row.split(',')))
    valid = True
    for val in vals:
        if val in valid_nums:
            pass
        else:
            valid = False
    if valid:
        valid_tickets.append(vals)
unknown_fields = {}
known_fields = {}
field_list = field_info.keys()
for field in range(len(field_list)):
    unknown_fields[field] = list(field_list)

for row in valid_tickets:
    for index, val in enumerate(row):
        for field in unknown_fields[index]:
            if val in field_info[field]:
                pass
            else:
                unknown_fields[index].remove(field)
count = 0
while len(unknown_fields) > 0 and count < 100:
    count = count + 1
    for field in unknown_fields.keys():
        if len(unknown_fields[field]) == 1:
            known_fields[field] = unknown_fields[field][0]
    for field in known_fields.values():
        for field_list in unknown_fields.values():
            if field in field_list:
                field_list.remove(field)
    for key in known_fields.keys():
        if key in unknown_fields.keys():
            unknown_fields.pop(key)

answer = 1
my_ticket = list(map(int,my_ticket[0].split(',')))
for key in known_fields.keys():
    if 'departure' in known_fields[key]:
        answer = answer * my_ticket[key]
        
print(answer)

• Don't forget that the ranges are inclusive. You might make an off-by-1 error if you're not careful

• Parsing the data in the first place might be difficult, if you separate it by looking for \n\n that will help you identify the groups of data so that you can deal with the different sections

• My test data was too small of a group to fully validate my algorithm. It might be necessary to move to the full data set earlier than you normally would so that you can have more entries to work with

• Depending on what your real data looks like, you'll likely need to use the process of elimination. Once you know that a field must be a certain thing, then you know that other fields AREN'T that thing.

use std::env;
use std::io::{prelude::*, BufReader};
use std::fs::File;
use std::collections::HashMap;

extern crate regex;
use regex::Regex;

#[macro_use]
extern crate text_io;

#[derive(Debug, Clone)]
struct TicketField {
    name: String,
    range1: (u64,u64),
    range2: (u64,u64),
    possible_pos: Vec<bool>,
}
impl From<&String> for TicketField {
    fn from(input: &String) -> Self {
        // departure station: 28-106 or 130-969
        let name: String;
        let mut range1: (u64,u64) = (0,0);
        let mut range2: (u64,u64) = (0,0);
        scan!(input.bytes() => "{}: {}-{} or {}-{}", name, range1.0, range1.1, range2.0, range2.1);
        Self {
            name: name,
            range1: range1,
            range2: range2,
            possible_pos: Vec::new(),
        }
    }
}
impl TicketField {
    pub fn validate(&self, value: u64) -> bool {
        (self.range1.0..=self.range1.1).contains(&value) || (self.range2.0..=self.range2.1).contains(&value)
    }
}

#[derive(Debug, Clone)]
struct Ticket {
    fields: Vec<u64>,
    valid: bool,
}
impl From<&String> for Ticket {
    fn from(input: &String) -> Self {
        Self {
            fields: input.split(",").map(|x| x.parse::<u64>().unwrap()).collect::<Vec<_>>(),
            valid: true,
        }
    }
}

fn day16(input: &str) {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);

    let input: Vec<String> = match reader.lines().collect() {
        Err(err) => panic!("Unknown error reading input: {}", err),
        Ok(result) => result,
    };

    // Process input
    let mut fields: Vec<TicketField> = Vec::new();
    let mut tickets: Vec<Ticket> = Vec::new();

    let re_field = Regex::new(r"^[\w ]+: [\d]+\-[\d]+ or [\d]+\-[\d]+$").unwrap();
    let re_ticket = Regex::new(r"^([\d]+,)+[\d]+$").unwrap();
    for line in input {
        if re_field.is_match(&line) {
            fields.push(TicketField::from(&line));
        } else if re_ticket.is_match(&line) {
            tickets.push(Ticket::from(&line));
        }
    }

    // Part 1
    let mut part1 = 0;
    for ticket in &mut tickets {
        for val in &ticket.fields {
            if fields.iter().map(|f| f.validate(*val)).filter(|f| f == &true).count() == 0 {
                part1 += val;
                ticket.valid = false;
            }
        }
    }
    println!("Part 1: {}", part1); // 26009

    // Part 2
    let tickets = tickets.iter().filter(|t| t.valid).collect::<Vec<_>>();
    let num_fields = fields.len();
    let my_ticket = tickets.get(0).unwrap();

    // Build array of bools to track possible field positions
    for field in &mut fields { field.possible_pos = vec![true; num_fields]; }

    // Rule out certain field positions
    for field in &mut fields {
        for ticket in &tickets {
            for (ix,val) in ticket.fields.iter().enumerate() {
                if !field.validate(*val) {
                    field.possible_pos[ix] = false;
                }
            }
        }
    }

    // Narrow down one field at a time
    let mut order: HashMap<usize,String> = HashMap::new();
    while order.len() != num_fields {
        for i in 0..num_fields {
            if fields[i].possible_pos.iter().filter(|&x| *x == true).count() != 1 { continue; }
            let ix = fields[i].possible_pos.iter().position(|&x| x == true).unwrap();
            order.insert(ix, fields[i].name.clone());
            for f_other in &mut fields { f_other.possible_pos[ix] = false; }
            
        }
    }

    // Calculate part 2 answer
    let part2 = my_ticket
        .fields
        .iter()
        .enumerate()
        .map(|(i,x)| 
            match order.get(&i).unwrap().split_ascii_whitespace().next().unwrap() {
                "departure" => x,
                _ => &1u64,
            })
        .product::<u64>();

    println!("Part 2: {}", part2); // 589685618167

}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    day16(&filename);
}

public override string SolvePart1()
{
	using (var fs = new StreamReader(Inputs.Year2020.Inputs2020.Input16))
	{
		string line;
		var re = new Regex("(.*): (\\d*)-(\\d*) or (\\d*)-(\\d*)");
		var rules = new List<TicketRule>();
		while ((line = fs.ReadLine()) != string.Empty)
		{
			var match = re.Match(line);
			rules.Add(new TicketRule(match.Groups[1].Value,
				int.Parse(match.Groups[2].Value),
				int.Parse(match.Groups[3].Value),
				int.Parse(match.Groups[4].Value),
				int.Parse(match.Groups[5].Value)));
		}

		fs.ReadLine();
		var myTicket = fs.ReadLine().Split(',').Select(s => int.Parse(s)).ToList();

		fs.ReadLine();
		fs.ReadLine();
		var otherTickets = new List<List<int>>();
		while ((line = fs.ReadLine()) != null)
		{
			otherTickets.Add(line.Split(',').Select(s => int.Parse(s)).ToList());
		}

		var totalInvalid = otherTickets.Sum(ticket => ticket.Select(i => new Tuple<int, bool>(i, rules.Any(r => r.IsValid(i)))).Where(ib => !ib.Item2).Sum(ib => ib.Item1));

		return $"Total error rate is {totalInvalid}";
	}
}

public override string SolvePart2()
{
	using (var fs = new StreamReader(Inputs.Year2020.Inputs2020.Input16))
	{
		string line;
		var re = new Regex("(.*): (\\d*)-(\\d*) or (\\d*)-(\\d*)");
		var rules = new List<TicketRule>();
		while ((line = fs.ReadLine()) != string.Empty)
		{
			var match = re.Match(line);
			rules.Add(new TicketRule(match.Groups[1].Value,
				int.Parse(match.Groups[2].Value),
				int.Parse(match.Groups[3].Value),
				int.Parse(match.Groups[4].Value),
				int.Parse(match.Groups[5].Value)));
		}

		fs.ReadLine();
		var myTicket = fs.ReadLine().Split(',').Select(s => int.Parse(s)).ToList();

		fs.ReadLine();
		fs.ReadLine();
		var otherTickets = new List<List<int>>();
		while ((line = fs.ReadLine()) != null)
		{
			otherTickets.Add(line.Split(',').Select(s => int.Parse(s)).ToList());
		}

		var validTickets = otherTickets.Where(ticket => ticket.All(i => rules.Any(r => r.IsValid(i)))).ToList();
		var fieldDatas = new List<int>[20];
		for(int i = 0; i < fieldDatas.Length; i++)
		{
			fieldDatas[i] = validTickets.Select(ticket => ticket[i]).ToList();
		}

		//Search for matching rule
		//Map list of rules -> list of fields
		var fieldMapCandidates = new List<Tuple<List<int>, int>>();
		for(int i = 0; i < fieldDatas.Length; i++)
		{
			var matches = new List<int>();
			for(int j = 0; j < rules.Count(); j++)
			{
				if (fieldDatas[i].All(f => rules[j].IsValid(f)))
				{
					matches.Add(j);
				}
			}
			fieldMapCandidates.Add(Tuple.Create(matches, i));
		}

		//Rules -> fields
		var confirmedRules = new Dictionary<int, int>();

		while (fieldMapCandidates.Count() > 0)
		{
			var singles = fieldMapCandidates.Where(fmc => fmc.Item1.Count == 1).ToList();
			fieldMapCandidates.RemoveAll(fmc => singles.Any(s => s.Item2 == fmc.Item2));
			foreach (var pair in singles)
			{
				var rule = pair.Item1.Single();
				confirmedRules.Add(rule, pair.Item2);

				for (int i = 0; i < fieldMapCandidates.Count; i++)
				{
					fieldMapCandidates[i] = Tuple.Create(fieldMapCandidates[i].Item1.Where(r => r != rule).ToList(), fieldMapCandidates[i].Item2);
				}

			}
		}

		long answer = (long)myTicket[confirmedRules[0]] * (long)myTicket[confirmedRules[1]] * (long)myTicket[confirmedRules[2]] * (long)myTicket[confirmedRules[3]] * (long)myTicket[confirmedRules[4]] * (long)myTicket[confirmedRules[5]];

		return $"Final ticket answer is {answer}";
	}
}

public class TicketRule
{
	public string Name { get; set; }
	public Tuple<int, int> Rule1 { get; set; }
	public Tuple<int, int> Rule2 { get; set; }

	public TicketRule(string name, int start1, int end1, int start2, int end2)
	{
		Name = name;
		Rule1 = Tuple.Create(start1, end1);
		Rule2 = Tuple.Create(start2, end2);
	}

	public bool IsValid(int toCheck)
	{
		return (toCheck >= Rule1.Item1 && toCheck <= Rule1.Item2) || (toCheck >= Rule2.Item1 && toCheck <= Rule2.Item2);
	}

	public List<int> GetInvalids(List<int> toCheck)
	{
		var ret = new List<int>();
		foreach (var i in toCheck)
		{
			if (!(i >= Rule1.Item1 && i <= Rule1.Item2) || !(i >= Rule2.Item1 && i <= Rule2.Item2))
			{
				ret.Add(i);
			}
		}

		return ret;
	}
}

There's some overkill here, for certain, and this is probably #1 on my list of "puzzles to revisit and architect a cleaner solution".

I don't know whether to be proud or horrified about the LINQ one-liner at the end of Part 1. I'd bet there are a decent number of AoC puzzles that could be entirely accomplished by LINQ one-liners.

RULE_RE = /^([\w\s]+): (\d+-\d+) or (\d+-\d+)\n?$/

def parse_rule(line)
  binding.pry unless line.match?(RULE_RE)
  captures = line.match(RULE_RE).captures
  name = captures[0]
  r1 = captures[1].split('-').map(&:to_i)
  r2 = captures[2].split('-').map(&:to_i)
  return [name.to_sym, r1[0]..r1[1], r2[0]..r2[1]]
end

def compute_p1(input)
  lines = input.lines.enum_for

  # read rules
  rules = {}
  while (l = lines.next).strip.size > 0
    r = parse_rule(l)
    rules[r[0]] = r[1..]
  end

  # read my ticket
  l = lines.next until l.start_with?("your ticket:")
  my_ticket = lines.next.split(',').map(&:to_i)

  # read nearby tickets
  l = lines.next until l.start_with?("nearby tickets:")
  nearby_tickets = []
  begin
    while (l = lines.next.strip).size > 0
      nearby_tickets << l.split(',').map(&:to_i)
    end
  rescue StopIteration
  end

  # check each value in nearby_tickets for all rules
  invalid_values = []
  nearby_tickets.each do |ticket|
    ticket.each do |value|
      invalid_values << value unless rules.values.flatten.any? { |r| r.include?(value) }
    end
  end

  return invalid_values.sum
end

That had me thinking about how I might have to find a subset of possible field orders, and then brute force search through those, but instead I tried re-writing my first algorithm one more time and it worked!

The idea is to start with the set of "unknown" fields, and an array indicating which fields go in which position (initialized to all nil). We then iterate through each field (1-20) for all tickets (so we're examining the first field of ticket #1, then the first field of ticket #2, and so on, and then the second field of ticket #1, the second field of ticket #2, etc, on down the line), and compare against the fields/rules in the unknown set to find the set of rules that match that value for all tickets.

If there is only one field in that set, we know this must be the correct position for that field, and we add it to our known list in the correct position, and remove it from the unknown set. Repeat until the unknown set is empty.

def compute_p2(input, return_fields=nil)
  lines = input.lines.enum_for

  # read rules
  rules = {}
  while (l = lines.next).strip.size > 0
    r = parse_rule(l)
    rules[r[0]] = r[1..]
  end

  # read my ticket
  l = lines.next until l.start_with?("your ticket:")
  my_ticket = lines.next.split(',').map(&:to_i)

  # read nearby tickets
  l = lines.next until l.start_with?("nearby tickets:")
  nearby_tickets = []
  begin
    while (l = lines.next.strip).size > 0
      nearby_tickets << l.split(',').map(&:to_i)
    end
  rescue StopIteration
  end

  # check each value in each of nearby_tickets against all rules to find the valid tickets
  valid_tickets = nearby_tickets.filter do |ticket|
    ticket.all? { |value| rules.values.flatten.any? { |r| r.include?(value) } }
  end

  unknown_fields = Set.new(rules.keys)
  fields_order = Array.new(my_ticket.size)

  while unknown_fields.size > 0
    # look at the nth field in each ticket, and find the rule that matches all values
    my_ticket.size.times do |n|
      matching_rules = valid_tickets.map { _1[n] }.reduce(unknown_fields) do |set, value|
        set & unknown_fields.filter { |k| rules[k].any? { |r| r.include? value } }
      end
      if matching_rules.size == 1
        fields_order[n] = matching_rules.first
        unknown_fields -= [matching_rules.first]
      end
    end
  end

  binding.pry if unknown_fields.size > 0

  if return_fields.nil?
    return_fields = fields_order.filter { |f| f.to_s.start_with?("departure") }
  end

  return return_fields.reduce(1) { |product, field| product * my_ticket[fields_order.index(field)] }
end

{-# LANGUAGE NamedFieldPuns #-}

module Day16 where

import AoC

import Data.List
import Data.Maybe
import qualified Data.Set as S
import Data.Set (Set)
import Text.ParserCombinators.ReadP
import Text.Read.Lex

data Field = Field { name :: String
                   , valids :: Set Int
                   } deriving (Show)

type Ticket = [Int]

data Input = Input { fields :: [Field]
                   , myTicket :: Ticket
                   , otherTickets :: [Ticket]
                   } deriving (Show)

line :: ReadP a -> ReadP a
line p = p <* char '\n'

parseField :: ReadP Field
parseField = do
    name <- many1 $ satisfy (/=':')
    string ": "
    ranges <- parseRange `sepBy` string " or "
    let valids = S.fromList . concat . map (uncurry enumFromTo) $ ranges
    return $ Field { name, valids }
    where parseRange = do
            n1 <- readDecP
            char '-'
            n2 <- readDecP
            return (n1, n2)

parseTicket :: ReadP Ticket
parseTicket = readDecP `sepBy` char ','

parseInput :: ReadP Input
parseInput = do
    fields <- many1 $ line parseField
    line $ string ""
    line $ string "your ticket:"
    myTicket <- line parseTicket
    line $ string ""
    line $ string "nearby tickets:"
    otherTickets <- many1 $ line parseTicket
    return $ Input {fields, myTicket, otherTickets }

matchesAnyField :: [Field] -> Int -> Bool
matchesAnyField fields n = any (n `S.member`) . map valids $ fields

iterateUntilDone :: (a -> Maybe a) -> a -> a
iterateUntilDone f x = case f x of
                         Just x' -> iterateUntilDone f x'
                         Nothing -> x

data Resolve a = Resolved a | Choice (Set a) deriving (Show)

resolve :: Ord a => [[a]] -> Maybe [a]
resolve = sequence . map fromResolved . iterateUntilDone resolve' . map (Choice . S.fromList)
    where fromResolved (Resolved x) = Just x
          fromResolved _ = Nothing

findSingletonChoice :: [Resolve a] -> Maybe (a, [Resolve a])
findSingletonChoice (c@(Choice s):xs) | S.size s == 1 = let [x] = S.elems s
                                                        in Just (x, Resolved x:xs)
                                      | otherwise = (fmap.fmap) (c:) $ findSingletonChoice xs
findSingletonChoice (x:xs) = (fmap.fmap) (x:) $ findSingletonChoice xs
findSingletonChoice _ = Nothing

resolve' :: Ord a => [Resolve a] -> Maybe [Resolve a]
resolve' xs = do
    (x, xs') <- findSingletonChoice xs
    return $ map (dropChoice x) xs'
    where dropChoice x (Choice s) = Choice (S.delete x s)
          dropChoice _ r = r

part1 :: Input -> Int
part1 Input { fields, otherTickets } = sum . filter (not . matchesAnyField fields) . concat $ otherTickets

part2 :: Input -> Int
part2 Input { fields, myTicket, otherTickets } = product departureValues
    where validTickets = filter (all $ matchesAnyField fields) otherTickets
          columns = transpose validTickets
          fieldNames = fromJust . resolve . map findPossibleFields $ columns
          departureIndices = findIndices ("departure" `isPrefixOf`) fieldNames
          departureValues = map (myTicket !!) departureIndices
          findPossibleFields col = map name . filter (\field -> all (`S.member` valids field) col) $ fields

main = runAoC (fromJust . oneCompleteResult parseInput) part1 part2

module AoC
    ( (.:)
    , enumerate
    , oneCompleteResult
    , splitOnEmptyLines
    , runAoC
    )
where

import Data.Function (on)
import Data.List (groupBy)
import Text.ParserCombinators.ReadP

(.:) :: (c -> d) -> (a -> b -> c) -> a -> b -> d
f .: g = (f .) . g
infixl 8 .:

enumerate :: Enum i => i -> [a] -> [(i, a)]
enumerate _ [] = []
enumerate i (x:xs) = (i, x) : enumerate (succ i) xs

oneCompleteResult :: ReadP a -> String -> Maybe a
oneCompleteResult p s = case readP_to_S (p <* eof) s of
                          [(x, "")] -> Just x
                          _ -> Nothing

splitOnEmptyLines :: String -> [[String]]
splitOnEmptyLines = filter (not . any null) . groupBy ((==) `on` null) . lines

runAoC :: (Show r1, Show r2) => (String -> i) -> (i -> r1) -> (i -> r2) -> IO ()
runAoC inputTransform part1 part2 = do
    contents <- inputTransform <$> getContents
    print $ part1 contents
    print $ part2 contents

function main()

    input = []
    open("Day16/input.txt") do fp
        input = split(readchomp(fp), "\n\n")
    end

    input_fields = split.(split(input[1], '\n'), ": ")
    fields = Dict()
    for field in input_fields
        values = split.(split(field[2], " or "), '-')
        fields[field[1]] = parse.(Int, [values[1][1], values[1][2],
                                        values[2][1], values[2][2]])
    end
    
    my_ticket = split.(split(input[2], '\n')[2], ',')
    my_ticket = [parse(Int, val) for val in my_ticket]
    
    nearby_tickets = split.(split(input[3], '\n')[2:end], ',')
    nearby_tickets = [[parse(Int, val) for val in ticket] for ticket in nearby_tickets]

    error_rate = 0
    for ticket in nearby_tickets
        error_rate += basic_validation(ticket, fields)
    end

    println(error_rate)

end

function basic_validation(ticket, fields)
    for value in ticket
        valid = false
        for bounds in values(fields)
            if (bounds[1] <= value <= bounds[2]) || (bounds[3] <= value <= bounds[4])
                valid = true
            end
        end
        if !valid
            return value
        end
    end
    return 0
end

main()

@@ -21,11 +21,23 @@ function main()
 
     error_rate = 0
     for ticket in nearby_tickets
-        error_rate += basic_validation(ticket, fields)
+        error_rate += basic_validation(ticket, fields)[1]
     end
 
     println(error_rate)
 
+    for idx in length(nearby_tickets):-1:1
+        if basic_validation(nearby_tickets[idx], fields)[2]
+            deleteat!(nearby_tickets, idx)
+        end
+    end
+
+    ordered_fields = find_fields(nearby_tickets, fields)
+
+    departure_fields = [value for (key, value) in ordered_fields if startswith(key, "departure")]
+
+    println(prod(my_ticket[departure_fields]))
+
 end
 
 function basic_validation(ticket, fields)
@@ -37,10 +49,46 @@ function basic_validation(ticket, fields)
             end
         end
         if !valid
-            return value
+            return (value, true)
+        end
+    end
+    return (0, false)
+end
+
+function find_fields(tickets, fields)
+    field_order = Dict()
+    possibilities = Dict()
+    for (name, bounds) in fields
+        for row in 1:length(tickets[1])
+            values = [ticket[row] for ticket in tickets]
+            if all(((bounds[1] .<= values) .& (values .<= bounds[2]))
+                    .| ((bounds[3] .<= values) .& (values .<= bounds[4])))
+                if name in keys(possibilities)
+                    push!(possibilities[name], row)
+                else
+                    possibilities[name] = Set([row])
+                end
+            end
         end
     end
-    return 0
+
+    while true
+        
+        singletons = [name for (name, value) in possibilities if length(value) == 1]
+        single_val = possibilities[singletons[1]]
+        delete!(possibilities, singletons[1])
+        field_order[singletons[1]] = collect(single_val)[1]
+
+        if length(possibilities) < 1
+            break
+        end
+
+        for key in collect(keys(possibilities))
+            setdiff!(possibilities[key], single_val)
+        end
+    end
+
+    return field_order
 end
 
 main()

defmodule AdventOfCode.Day16 do
  def part1(args) do
    {rules, _, nearby_tickets} = parse_input(args)

    nearby_tickets
    |> Enum.flat_map(&invalid_values(&1, rules))
    |> Enum.sum()
  end

  def part2(args) do
    {rules, my_ticket, nearby_tickets} = parse_input(args)

    nearby_tickets
    |> Enum.reject(&invalid_ticket?(&1, rules))
    |> assign_fields(rules)
    |> Enum.zip(my_ticket)
    |> Enum.filter(fn {field, _} -> String.starts_with?(field, "departure") end)
    |> Enum.map(&elem(&1, 1))
    |> Enum.reduce(1, &Kernel.*/2)
  end

  defp parse_input(input) do
    [rules, my_ticket, nearby_tickets] =
      input
      |> String.trim()
      |> String.split("\n\n", trim: true)

    {parse_rules(rules), parse_my_ticket(my_ticket), parse_nearby_tickets(nearby_tickets)}
  end

  defp parse_rules(rules) do
    rules
    |> String.split("\n")
    |> Enum.map(&parse_rule/1)
  end

  defp parse_rule(rule) do
    [field | bounds] =
      Regex.run(~r|([^:]+): (\d+)-(\d+) or (\d+)-(\d+)|, rule, capture: :all_but_first)

    [l1, r1, l2, r2] = Enum.map(bounds, &String.to_integer/1)

    validator = fn n -> n in l1..r1 or n in l2..r2 end

    {field, validator}
  end

  defp parse_my_ticket(my_ticket) do
    my_ticket
    |> String.split("\n")
    |> Enum.at(1)
    |> parse_ticket()
  end

  defp parse_nearby_tickets(nearby_tickets) do
    nearby_tickets
    |> String.split("\n")
    |> Enum.drop(1)
    |> Enum.map(&parse_ticket/1)
  end

  defp parse_ticket(ticket) do
    ticket
    |> String.split(",")
    |> Enum.map(&String.to_integer/1)
  end

  defp invalid_values(ticket, rules) do
    Enum.filter(ticket, &invalid_value?(&1, rules))
  end

  defp invalid_ticket?(ticket, rules) do
    Enum.any?(ticket, &invalid_value?(&1, rules))
  end

  defp invalid_value?(value, rules) do
    Enum.all?(rules, fn {_, validator} -> not validator.(value) end)
  end

  defp assign_fields(tickets, rules) do
    tickets
    |> columnize()
    |> list_valid_fields(rules)
    |> deduce()
  end

  defp columnize([ticket | tickets]) do
    acc = Enum.map(ticket, &[&1])

    Enum.reduce(tickets, acc, fn ticket, acc ->
      acc
      |> Enum.zip(ticket)
      |> Enum.map(fn {values, value} -> [value | values] end)
    end)
  end

  defp list_valid_fields(field_values, rules) do
    field_values
    |> Enum.map(fn values ->
      rules
      |> Enum.filter(fn {_, validator} -> Enum.all?(values, &validator.(&1)) end)
      |> Enum.map(&elem(&1, 0))
    end)
  end

  defp deduce(valid_fields) do
    case Enum.find(valid_fields, &match?([_], &1)) do
      nil ->
        valid_fields

      [resolved] ->
        valid_fields
        |> Enum.map(fn
          [^resolved] -> resolved
          fields when is_list(fields) -> fields -- [resolved]
          field -> field
        end)
        |> deduce()
    end
  end
end