DEV Community

loading...
Cover image for Advent of Code 2020 Solution Megathread - Day 16: Ticket Translation

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

rpalo profile image Ryan Palo ・1 min read

How are you doing? Making it OK? Keeping up? I'm starting to bog down a little, but switching to Python when I need to keep caught up has been helping.

The Puzzle

In today’s puzzle, we're planning ahead for our upcoming train trip. We've got a ticket with some numbers, and there are a bunch of fields that these numbers could belong to. We've got to validate our neighbor's tickets to make sure we're on the right track (eh? ehhh?) before we can validate our own.

The Leaderboards

As always, this is the spot where I’ll plug any leaderboard codes shared from the community.

Ryan's Leaderboard: 224198-25048a19
Enter fullscreen mode Exit fullscreen mode

If you want to generate your own leaderboard and signal boost it a little bit, send it to me either in a DEV message or in a comment on one of these posts and I'll add it to the list above.

Yesterday’s Languages

Updated 11:18PM 12/15/2020 PST.

Language Count
Rust 2
Haskell 2
Python 1
JavaScript 1
Ruby 1
COBOL 1

Merry Coding!

Discussion (8)

pic
Editor guide
Collapse
kudostoy0u profile image
Kudos Beluga • Edited

Part 1 JS solution, I've been hearing that Part 2 day 16 is a very hard part
😳, hope I'll be able to finish that


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)

Enter fullscreen mode Exit fullscreen mode
Collapse
bgaster profile image
Benedict Gaster

Here's my Haskell solution. It was farily easy today, compared to some of the others, and I took my time between part 1 and part 2, to walk the dog in what turned out to be a very wet and muddy time.

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
Enter fullscreen mode Exit fullscreen mode
Collapse
benwtrent profile image
Benjamin Trent

My rust impl. Pretty gross use of "exactly one match" boolean thrashing. But, I was in a hurry and didn't want to mess with it any longer :)

#[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()
}
Enter fullscreen mode Exit fullscreen mode
Collapse
cappe987 profile image
Casper

Today's Haskell solution, much longer than yesterday. The parsing was a bit annoying today, but not too bad. Part 1 was very easy. Part 2 was extremely tedious, but at least no performance issues today. I'm still pretty satisfied with my solution and it worked on the first try.

{-# 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
Enter fullscreen mode Exit fullscreen mode
Collapse
neilgall profile image
Neil Gall

Probably the hardest one so far this year. I was caught out in part 2 by using part 1''s solution - I was using an "error count" > 0 to find invalid tickets, but there's one record where the only invalid field has value zero, so the "error count" is zero. Fixed by changing it to the arguably clearer and definitely more efficient check that no fields are invalid.


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
        ]);
    }
}
Enter fullscreen mode Exit fullscreen mode
Collapse
sleeplessbyte profile image
Derk-Jan Karrenbeld • Edited

Today was a LOT of fun! I finished it quickly, but only was able to work on it just now. It's not a nice solution (unlike many other days where I took the time to OOP it up), but it works very well (sub 20ms) and I think isn't too bad to read.

Ruby:

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(&:*)
Enter fullscreen mode Exit fullscreen mode
Collapse
rpalo profile image
Ryan Palo Author

Whew! I think in any other language, this would have been a lot smaller and less verbose, but C made me work it all out loop by loop. It's so much code. My eyes are crossed.

But it works great! I got foiled right at the end by a "not big enough output type" bug that had my answer overflowing and becoming too small. And did a butt ton of debugging and going in the wrong direction before slapping my head and hitting a bunch of undos.

Anyways, I'm pretty happy about how it finally turned out. There were a lot of moving pieces and I think I handled them, if not algorithmically quickly, at least cleanly and readably. And it's still pretty fast.

Also, I love strtok. That is all.

#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;
}
Enter fullscreen mode Exit fullscreen mode
Collapse
thibpat profile image
Thibaut Patel

My JavaScript walkthrough: