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

pInt :: Parser Int
pInt = read <$> many1 digit

type Range = (Int,Int)

pRange :: Parser Range
pRange = do
  l <- pInt 
  char '-'
  u <- pInt
  pure (l,u)

pRanges :: Parser (Range, Range)
pRanges = do
  lower <- pRange
  spaces
  string "or"
  spaces
  upper <- pRange
  pure (lower, upper)

pField :: Parser (String, (Range,Range))
pField = do 
  cs <- many (noneOf ":")
  char ':' 
  spaces
  r <- pRanges
  pure (cs, r)

pInts :: Parser [Int]
pInts = sepBy1 pInt (char ',')

pParse :: Parser a -> String -> a
pParse p source =
  case parse p "" source of
    Right e -> e
    _ -> error "Parsing error"

withinRange :: Range -> Int -> Bool
withinRange (l,u) v = l <= v && v <= u

inRange :: Int -> (Range, Range)  -> Bool
inRange v (r,r') = withinRange r v || withinRange r' v

rules :: Int -> [(String, (Range,Range))] -> Bool
rules v = any (inRange v . snd)

errorRate rs = foldr aux 0
    where
      aux v er | rules v rs = er
               | otherwise  = v + er

removeInValid rs = filter ((==) 0 . errorRate rs)

classify []         _ = []
classify ((s,r):rs) vs | all (`inRange` r) vs = s : classify rs vs  
                       | otherwise            = classify rs vs

main = do
  is <- readFile "day16_input" <&> lines
  -- parse fields, myticket, and nearby tickets
  let cs = map (pParse pField) (takeWhile (/= "") is)
  let myTicket = pParse pInts (head . tail $ dropWhile (/= "your ticket:") is) 
  let nb = map (pParse pInts) (tail $ dropWhile (/= "nearby tickets:") is) 

  -- part 1
  print (sum $ map (errorRate cs) nb)

  -- part 2
  let vs = removeInValid cs nb
      fields = sortOn (length . snd) (zip [0..] (map (classify cs) $ transpose vs) )
      (o,m) = span (\(_, fs) -> length fs == 1) fields
      ones = S.fromList . concatMap snd $ o

      fields' = o ++ snd
              (foldl'
                (\ (ones, xs) (i, rs)
                    -> let rs' = filter (not . (`S.member` ones)) rs
                       in (S.insert (head rs') ones, (i, rs') : xs))
                (ones, []) m)

      depart = foldr (\i r -> (myTicket !! fst i) * r) 
                     1 (filter (isPrefixOf "departure" . concat . snd) fields')
  print depart

const fs = require("fs")
let data = fs.readFileSync("input.txt","utf8"),
rules = data.match(/(.|\n)+(?=\n\syour ticket:)/i)[0].split("\n"),
valids = new Set();
rules.forEach(e => {
  e.match(/\d+-\d+/gi).forEach(e => {
     for (let i = Number(e.match(/\d+/i));i <= Number(e.match(/(?<=\d+-)\d+/)[0]);i++) {
     valids.add(i)
     }
  })
})
let nearbytickets = data.match(/(?<=ts:\n)(.|\n)+/)[0].split("\n");
let invalids = [];
for (let i = 0,n=nearbytickets.length;i < n; i++) {
  let theticket = nearbytickets[i].split(",").map(e=>Number(e));
  for (let j = 0,o=theticket.length; j < o; j++) {
  let isvalid = valids.has(theticket[j]);
  if (!isvalid) invalids.push(theticket[j])

  }
}
if (invalids.length) console.log(invalids.reduce((a,e) => a+e))
else console.log(0)

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(&:*)

use std::collections::{HashMap, HashSet};
use std::ops::RangeInclusive;
use parser::*;

// --- model

#[derive(Debug, Eq, PartialEq)]
struct Ranges(Vec<RangeInclusive<i64>>);

type FieldRanges = HashMap<String, Ranges>;
type Ticket = Vec<i64>;

#[derive(Debug, Eq, PartialEq)]
struct TicketData {
    field_ranges: FieldRanges,
    your_ticket: Ticket,
    nearby_tickets: Vec<Ticket>
}

impl Ranges {
    fn contains(&self, value: &i64) -> bool {
        self.0.iter().any(|r| r.contains(value))
    }
}

impl TicketData {
    fn is_invalid_value_for_field(&self, value: &i64, field: &str) -> bool {
        self.field_ranges.get(field)
            .map(|r| !r.contains(value))
            .unwrap()
    }

    fn is_invalid_value_for_any_field(&self, value: &i64) -> bool {
        self.field_ranges.values().all(|r| !r.contains(value))
    }

    fn ticket_errors(&self, ticket: &Ticket) -> i64 {
        ticket.iter()
            .filter(|value| self.is_invalid_value_for_any_field(value))
            .sum()
    }

    fn ticket_has_invalid_fields(&self, ticket: &Ticket) -> bool {
        ticket.iter().any(|value| self.is_invalid_value_for_any_field(value))
    }

    fn ticket_scanning_error_rate(&self) -> i64 {
        self.nearby_tickets.iter()
            .map(|ticket| self.ticket_errors(ticket))
            .sum()
    }

    fn valid_tickets<'a>(&'a self) -> impl Iterator<Item = &'a Ticket> + 'a {
        self.nearby_tickets.iter()
            .filter(move |ticket| !self.ticket_has_invalid_fields(ticket))
    }

    fn find_field_indices(&self) -> HashMap<String, usize> {
        let mut matcher = FieldMatcher::new(self);

        self.valid_tickets().for_each(|ticket| {
            matcher.eliminate_indices_for_ticket(
                ticket,
                |value, field_name| self.is_invalid_value_for_field(value, field_name)
            );
        });


        while !matcher.is_fully_determined() {
            matcher.eliminate_determined_indices();
        }

        matcher.flatten()
    }
}

struct FieldMatcher {
    ordered_fields: Vec<String>,
    possible_indices: HashMap<String, HashSet<usize>>
}

impl FieldMatcher {
    fn new(ticket_data: &TicketData) -> Self {
        let mut ordered_fields: Vec<String> = ticket_data.field_ranges.keys().cloned().collect();
        ordered_fields.sort();

        let all_indices: HashSet<usize> = (0..ticket_data.your_ticket.len()).collect();

        let possible_indices: HashMap<String, HashSet<usize>> = ticket_data.field_ranges.iter()
            .map(|(name, _)| (name.clone(), all_indices.clone()))
            .collect();

        FieldMatcher {
            ordered_fields,
            possible_indices
        }
    }

    fn eliminate_indices_for_ticket<F>(&mut self, ticket: &Ticket, is_invalid: F)
        where F: Fn(&i64, &str) -> bool
    {
        ticket.iter().enumerate()
            .for_each(|(index, value)| {
                self.possible_indices.iter_mut().for_each(|(field_name, indices)| {
                    if is_invalid(value, field_name) {
                        indices.remove(&index);
                    }
                })
            })
    }

    fn eliminate_determined_indices(&mut self) {
        let determined: HashSet<usize> =
            self.possible_indices.values()
                .filter(|ns| ns.len() == 1)
                .flat_map(|ns| ns.iter().cloned())
                .collect();

        self.possible_indices.values_mut()
            .filter(|ns| ns.len() > 1)
            .for_each(|ns| *ns = ns.difference(&determined).cloned().collect());
    }

    fn is_fully_determined(&self) -> bool {
        self.possible_indices.values().all(|ns| ns.len() == 1)
    }

    fn flatten(&self) -> HashMap<String, usize> {
        self.possible_indices.iter()
            .map(|(name, ns)| (name.clone(), *ns.iter().next().unwrap()))
            .collect()
    }

    fn debug(&self) {
        self.ordered_fields.iter().for_each(|f| {
            let mut ns: Vec<&usize> = self.possible_indices.get(f).unwrap().iter().collect();
            ns.sort();
            println!("{:20} -> {:?}", f, ns);
        });
        println!();
    }   
}


// --- parser

fn parse_input(input: &str) -> ParseResult<TicketData> {
    let range = pair(
        left(integer, match_literal("-")),
        integer,
        |min, max| (min..=max)
    );

    let ranges = range
        .sep_by(whitespace_wrap(match_literal("or")))
        .map(|rs| Ranges(rs));

    let field_name = one_or_more(any_char.pred(|c| *c != ':'))
        .map(|cs| cs.iter().collect());

    let field_range = tuple2(
        left(field_name, match_literal(":")),
        whitespace_wrap(ranges)
    );

    let csv = integer.sep_by(match_literal(","));

    let your_ticket = right(
        whitespace_wrap(match_literal("your ticket:")),
        csv.clone()
    );

    let nearby_tickets = right(
        whitespace_wrap(match_literal("nearby tickets:")),
        one_or_more(whitespace_wrap(csv))
    );

    let ticket_data = tuple3(one_or_more(field_range), your_ticket, nearby_tickets)
        .map(|(field_ranges, your_ticket, nearby_tickets)| TicketData {
            field_ranges: field_ranges.into_iter().collect(),
            your_ticket,
            nearby_tickets
        });

    ticket_data.parse(input)
}

// --- problems

fn part1(ticket_data: &TicketData) -> i64 {
    ticket_data.ticket_scanning_error_rate()
}

fn part2(ticket_data: &TicketData) -> i64 {
    let indices = ticket_data.find_field_indices();

    let values: Vec<&i64> = indices.iter()
        .filter(|(name, _)| name.starts_with("departure"))
        .map(|(_, index)| ticket_data.your_ticket.get(*index).unwrap())
        .collect();

    assert_eq!(values.len(), 6);

    values.into_iter().product()
}

fn main() {
    let input = std::fs::read_to_string("./input.txt").unwrap();
    let ticket_data = parse_input(&input).unwrap().1;

    println!("part 1 {:?}", part1(&ticket_data));
    println!("part 2 {:?}", part2(&ticket_data));
}


#[cfg(test)]
#[macro_use] extern crate maplit;

#[cfg(test)]
mod tests {
    use super::*;

    fn sample_data() -> TicketData {
        TicketData {
            field_ranges: hashmap![
                "class".to_string() => Ranges(vec![1..=3, 5..=7]),
                "row".to_string() => Ranges(vec![6..=11, 33..=44]),
                "seat".to_string() => Ranges(vec![13..=40, 45..=50])
            ],
            your_ticket: vec![7, 1, 14],
            nearby_tickets: vec![
                vec![7 ,3, 47],
                vec![40, 4, 50],
                vec![55, 2, 20],
                vec![38, 6, 12]
            ]
        }
    }

    #[test]
    fn test_parser() {
        let ticket_data = parse_input(
            "class: 1-3 or 5-7
             row: 6-11 or 33-44
             seat: 13-40 or 45-50

             your ticket:
             7,1,14

             nearby tickets:
             7,3,47
             40,4,50
             55,2,20
             38,6,12"
        );

        assert_eq!(ticket_data, Ok(("", sample_data())));
    }

    #[test]
    fn test_ticket_scanning_error_rate() {
        assert_eq!(sample_data().ticket_scanning_error_rate(), 71);
    }

    #[test]
    fn test_find_field_indices() {
        let indices = sample_data().find_field_indices();
        assert_eq!(indices, hashmap![
            "row".to_string() => 0,
            "class".to_string() => 1,
            "seat".to_string() => 2
        ]);
    }
}

#[derive(Hash, Eq, PartialEq)]
struct Field {
    name: String,
    range_1: (usize, usize),
    range_2: (usize, usize),
}

#[aoc(day16, part1)]
fn sum_invalid_tickets(input: &(Vec<Field>, Vec<usize>, Vec<Vec<usize>>)) -> usize {
    let mut sum = 0;
    for vec in &input.2 {
        for &v in vec {
            if input.0.iter().all(|f| f.is_invalid_number(&v)) {
                sum += v;
            }
        }
    }
    sum
}

#[aoc(day16, part2)]
fn departure_products(input: &(Vec<Field>, Vec<usize>, Vec<Vec<usize>>)) -> usize {
    let valid_tickets: Vec<&Vec<usize>> = input
        .2
        .iter()
        .filter(|&vec| {
            !vec.iter()
                .any(|v| input.0.iter().all(|f| f.is_invalid_number(&v)))
        })
        .collect();
    let mut field_translation = HashMap::new();
    let mut translated_fields = HashSet::new();
    while field_translation.len() < input.0.len() {
        for f in input.0.iter() {
            if translated_fields.contains(f) {
                continue;
            }
            let mut matched = false;
            let mut matched_more = false;
            let mut column = 0;
            for j in 0..input.0.len() {
                if field_translation.contains_key(&j) {
                    continue;
                }
                if !valid_tickets.iter().any(|vec| f.is_invalid_number(&vec[j])) {
                    if matched {
                        matched_more = true;
                        break;
                    }
                    matched = true;
                    column = j;
                }
            }
            if matched && !matched_more {
                field_translation.insert(column, f);
                translated_fields.insert(f);
            }
        }
    }

    input
        .1
        .iter()
        .enumerate()
        .filter(|(i, v)| field_translation[i].name.contains("departure"))
        .map(|(i, v)| v)
        .product()
}

{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE TupleSections #-}
module Main where

import Data.List
import Data.Maybe
import qualified Data.Text as T
import Data.Char
import Debug.Trace
import Data.Bifunctor as Bf



data Field = Field String [Int -> Bool]
type Ticket = [Int]
type TicketWId = [(Int, Int)]

--------------------- Part 1 -----------------
solve_1 :: [Int -> Bool] -> [Ticket] -> Int
solve_1 fs =
   foldr ((+) . foldl (\acc n -> if any (\f -> f n) fs then acc else acc+n) 0) 0 


--------------------- Part 2 -----------------
-- Discards the invalid fields from part 1
discardInvalid :: [Int -> Bool] -> [Ticket] -> [Ticket]
discardInvalid fs = filter (all (\x -> any (\f -> f x) fs))

-- Finds which id's a field can be, for a specific ticket
findValidIdForField :: [Int -> Bool] -> TicketWId -> [Int]
findValidIdForField [f1, f2] = 
  map fst . filter (\(i,n) -> f1 n || f2 n)

-- Removes valid id's from a field in case another ticket invalidated that id
removeInvalidIds :: (Field, [Int]) -> TicketWId -> (Field, [Int])
removeInvalidIds (fl@(Field n fs), xs) ticket = 
  (fl, xs `intersect` findValidIdForField fs ticket)

-- Finds the valid id's for a field
findTicketFields :: [(Field, [Int])] -> TicketWId -> [(Field, [Int])]
findTicketFields fields ticket = map (`removeInvalidIds` ticket) fields

-- findFields maps each field to which id's they can go to
findFields :: [(Field, [Int])] -> [TicketWId] -> [(String, [Int])]
findFields fls ts = map (\(Field n _, i) -> (n,i)) $ foldl findTicketFields fls ts

-- assignFields will whittle down the id's that a field can go to, 
-- until all fields have been assigned an id.
assignFields :: [(String, [Int])] -> [(String, Int)]
assignFields fields = 
  reduce sorted
  where sorted = sortBy (\(_, xs) (_,ys) -> compare (length xs) (length ys)) fields
        reduce :: [(String, [Int])] -> [(String, Int)]
        reduce [] = []
        reduce ((n,[x]):xs) = (n,x) : reduce (map (Bf.second (filter (/= x))) xs)


-- multiplyDeparture finds the final answer.
multiplyDeparture :: TicketWId -> [(String, Int)] -> Int
multiplyDeparture myticket fields = 
  product $ map snd $ filter (\(i,v) -> i `elem` depFields) myticket
  where depFields = map snd $ filter (\(n,_) -> "departure" `isPrefixOf` n) fields

solve_2 :: [Field] -> Ticket -> [Ticket] -> Int 
solve_2 fieldreqs myticket tickets = 
  let valids = discardInvalid (concatMap (\(Field _ fs) -> fs) fieldreqs) tickets
      withId = map (zip [0..]) valids :: [TicketWId]
      reqsWIds = map (, [0..length (head valids) -1]) fieldreqs :: [(Field, [Int])]

  in multiplyDeparture (zip [0..] myticket) $ assignFields $ findFields reqsWIds withId



--------------------- Main & parsing -----------------

parseTicket :: T.Text -> [Int]
parseTicket = map ((read :: String -> Int) . T.unpack) . T.splitOn ","

parseFieldReq :: T.Text -> Field
parseFieldReq s = 
  Field (T.unpack name) reqF
  where (name, rest) = T.span (/= ':') s
        reqs = T.splitOn " or " $ T.drop 2 rest
        reqF = map 
          (\s -> let [l,u] = T.splitOn "-" s in \n -> n >= read (T.unpack l) && n <= read (T.unpack u)) reqs

parse :: [T.Text] -> ([Field], Ticket, [Ticket])
parse ss = 
  (map parseFieldReq fields, myticket, othertickets)
  where (fields, rest) = span (/= "") ss
        myticket = parseTicket $ rest !! 2
        othertickets = map parseTicket $ drop 5 rest


main :: IO ()
main = do 
  (fieldreqs, myticket, tickets) <- parse . T.lines . T.pack <$> readFile "input.txt"

  print $ solve_1 (concatMap (\(Field _ fs) -> fs) fieldreqs) tickets
  print $ solve_2 fieldreqs myticket tickets

#include "Day16.h"

#include <stdbool.h>
#include <stdio.h>
#include <string.h>

#include "parsing.h"

typedef struct {
  char name[25];
  int min1;
  int max1;
  int min2;
  int max2;
} Field;

/// A field line is of the pattern:
/// <name>: <min1>-<max1> or <min2>-<max2>
Field parse_field_line(char* line) {
  Field f = {{0}, 0, 0, 0, 0};
  char* name = strtok(line, ":");
  char* min1 = strtok(NULL, "-");
  char* max1 = strtok(NULL, " ");
  strtok(NULL, " ");
  char* min2 = strtok(NULL, "-");
  char* max2 = strtok(NULL, "\n");
  strcpy(f.name, name);
  f.min1 = atoi(min1);
  f.max1 = atoi(max1);
  f.min2 = atoi(min2);
  f.max2 = atoi(max2);
  return f;
}

Field* parse_fields(FILE* fp, int* count) {
  *count = count_lines_until_blank(fp);
  Field* fields = (Field*)malloc(sizeof(Field) * *count);

  char line[100];
  for (int i = 0; i < *count; i++) {
    memset(line, 0, 100);
    fgets(line, 100, fp);
    fields[i] = parse_field_line(line);
  }
  return fields;
}

int* parse_my_values(FILE* fp, int field_count) {
  int* my_values = (int*)malloc(sizeof(int) * field_count);
  for (int i = 0; i < field_count; i++) {
    fscanf(fp, "%d", &my_values[i]);
    getc(fp);
  }
  return my_values;
}

int** parse_tickets(FILE* fp, int field_count, int* row_count) {
  size_t pos = ftell(fp);
  *row_count = count_lines(fp);
  fseek(fp, pos, SEEK_SET);

  int** rows = (int**)malloc(sizeof(int*) * *row_count);
  for (int i = 0; i < *row_count; i++) {
    rows[i] = (int*)malloc(sizeof(int) * field_count);
    for (int j = 0; j < field_count; j++) {
      fscanf(fp, "%d", &rows[i][j]);
      getc(fp);
    }
  }
  return rows;
}

/// Decides if a value is valid in at least one field.
static bool is_valid(int value, Field* fields, int field_count) {
  for (int i = 0; i < field_count; i++) {
    Field f = fields[i];
    if ((f.min1 <= value && f.max1 >= value) || (f.min2 <= value && f.max2 >= value)) {
      return true;
    }
  }
  return false;
}

/// Shifts the file pointer cursor forward n lines.
void consume_lines(FILE* fp, int n) {
  int newlines = 0;
  char c;
  while (newlines < n) {
    c = getc(fp);
    if (c == '\n') {
      newlines++;
    }
  }
}

/// Add up all of the invalid numbers from the nearby tickets.
int part1(const char* filename) {
  FILE* fp;
  fp = fopen(filename, "r");
  if (fp == NULL) {
    printf("Could not open file.\n");
    exit(EXIT_FAILURE);
  }

  // Parse the file
  int field_count;
  Field* fields = parse_fields(fp, &field_count);
  consume_lines(fp, 5);
  int row_count;
  int** values = parse_tickets(fp, field_count, &row_count);

  // Add up all of the invalid values on each nearby ticket
  int total = 0;
  for (int i = 0; i < row_count; i++) {
    for (int j = 0; j < field_count; j++) {
      if (!is_valid(values[i][j], fields, field_count)) {
        total += values[i][j];
      }
    }
  }

  // Clean up and return
  fclose(fp);
  free(fields);
  for (int i = 0; i < row_count; i++) free(values[i]);
  free(values);

  return total;
}

/// Returns true if a ticket contains any invalid numbers
bool contains_invalid(int* numbers, Field* fields, int field_count) {
  for (int i = 0; i < field_count; i++) {
    if (!is_valid(numbers[i], fields, field_count)) return true;
  }
  return false;
}

void drop_invalid_tickets(int** tickets, int row_count, Field* fields, int field_count) {
  // Drop any nearby tickets with any invalid numbers
  for (int i = 0; i < row_count; i++) {
    if (contains_invalid(tickets[i], fields, field_count)) {
      free(tickets[i]);
      tickets[i] = NULL;
    }
  }
}

/// Creates a boolean grid where the rows represent fields and the
/// columns represent columns on a ticket.  A `true` represents that
/// that column could still possibly be represented by that field's rules
/// and all tickets so far have adhered to that field's rules in that
/// column.
bool** create_possibility_grid(int field_count) {
  bool** possibilities = (bool**)malloc(sizeof(bool*) * field_count);
    for (int i = 0; i < field_count; i++) {
      possibilities[i] = (bool*)malloc(sizeof(bool) * field_count);
      for (int j = 0; j < field_count; j++) {
        possibilities[i][j] = true;
      }
    }
  return possibilities;
}

/// Prune down the possibility values.  If a ticket has a value in
/// a column that breaks a rule, that rule can't apply to that column
/// for any ticket.
void rule_out_possibilities(bool** possibilities,
  int** tickets, int row_count, Field* fields, int field_count) {

  for (int i = 0; i < row_count; i++) {
    if (tickets[i] == NULL) continue;
    for (int j = 0; j < field_count; j++) {
      for (int k = 0; k < field_count; k++) {
        Field f = fields[k];
        int val = tickets[i][j];
        possibilities[k][j] &= ((f.min1 <= val && f.max1 >= val) ||
                                (f.min2 <= val && f.max2 >= val));
      }
    }
  }
}

/// Count the number of `true` cells in a row.
int count_possibles(bool** possibilities, int row, int field_count) {
  int count = 0;
  for (int i = 0; i < field_count; i++) {
    if (possibilities[row][i]) count++;
  }
  return count;
}

/// Find the one (and there will be only one) column index where the
/// cell in that row is `true`.
int find_possible(bool** possibilities, int row, int field_count) {
  for (int i = 0; i < field_count; i++) {
    if (possibilities[row][i]) return i;
  }
  return -1;
}

/// Find the one row (and there will always be exactly one) that
/// only has one column still true.  Assign that column to that field
/// and remove that as a possibility from all other fields.
void assign_decided_field(int* assignments, int field_count, bool** possibilities) {
  for (int row = 0; row < field_count; row++) {
    if (count_possibles(possibilities, row, field_count) != 1) {
      continue;
    }

    int col = find_possible(possibilities, row, field_count);
    assignments[row] = col;

    // Set all other rows to false for this column
    for (int k = 0; k < field_count; k++) {
      possibilities[k][col] = false;
    }

    return;  
  }
  printf("Couldn't find a decided row.\n");
  exit(EXIT_FAILURE);
}

/// Discover which fields go to which columns on the ticket by process
/// of elimination.  Multiply any values on my own ticket together
/// if the associated field starts with 'departure'
long part2(const char* filename) {
  FILE* fp;
  fp = fopen(filename, "r");
  if (fp == NULL) {
    printf("Could not open file.\n");
    exit(EXIT_FAILURE);
  }

  // Parse file
  int field_count;
  Field* fields = parse_fields(fp, &field_count);
  consume_lines(fp, 2);
  int* my_values = parse_my_values(fp, field_count);
  consume_lines(fp, 2);
  int row_count;
  int** tickets = parse_tickets(fp, field_count, &row_count);

  // Preprocess tickets and possibilities
  drop_invalid_tickets(tickets, row_count, fields, field_count);

  bool** possible_fields = create_possibility_grid(field_count);
  rule_out_possibilities(possible_fields, tickets, row_count, fields, field_count);

  // Narrow down and assign columns by process of elimination.
  // Assumes there will always be exactly one row each iteration
  // With only one possible assignment.
  int assignments[field_count];
  for (int i = 0; i < field_count; i++) {
    assign_decided_field(assignments, field_count, possible_fields);
  }

  // Product up the departure columns
  long total = 1;
  for (int i = 0; i < field_count; i++) {
    if (strncmp(fields[i].name, "departure", 9) == 0) {
      total *= my_values[assignments[i]];
    }
  }

  // Clean up and return.
  fclose(fp);
  free(fields);
  for (int i = 0; i < field_count; i++) free(possible_fields[i]);
  free(possible_fields);
  for (int i = 0; i < row_count; i++) free(tickets[i]);
  free(tickets);
  free(my_values);

  return total;
}

int day16() {
  printf("====== Day 16 ======\n");
  printf("Part 1: %d\n", part1("data/day16.txt"));
  printf("Part 2: %ld\n", part2("data/day16.txt"));
  return EXIT_SUCCESS;
}