# Day 16: Ticket Translation

Join the Tildes private leaderboard! You can do that on this page, by entering join code `730956-de85ce0c`.

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace `python` with any of the "short names" listed in this page of supported languages):

``````<details>
<summary>Part 1</summary>

```python
```

</details>
``````

1. pnutzh4x0r
(edited )
Python Repo Link Part 1 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...

Python

Part 1

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

rules = {}

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

return rules

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():
nearby   = tickets[1:]
invalids = flatten(
find_invalid_fields(rules, ticket) for ticket in nearby
)

print(sum(invalids))

if __name__ == '__main__':
main()
``````
Part 2

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

rules = {}

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

return rules

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():
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()
``````
2. nothis
(edited )
Python Yay, no math! I think what took me the longest was a) doing all the regex-y stuff and b) figuring out my beautiful "departureSum" function didn't work because the solution wants the...

Python

Yay, no math! I think what took me the longest was a) doing all the regex-y stuff and b) figuring out my beautiful "departureSum" function didn't work because the solution wants the product, not the sum.

Part 1+2
``````import re

with open("input.txt") as inputFile:

# [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(

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)
``````
3. PapaNachos
That was fun! Unfortunately, I didn't get a chance to get to it until the morning after. Day 16 Part A – Python For this one I just do some regex to build a list of all possible valid numbers as I...

That was fun! Unfortunately, I didn't get a chance to get to it until the morning after.

Day 16 Part A – Python

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)
``````
Day 16 Part B – Python

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)

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

``````
Tips and Commentary
• 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.

4. wycy
Rust I don't really like my solution. It feels very messy but I also don't know how to clean it up. Lots of loops. Solution use std::env; use std::io::{prelude::*, BufReader}; use std::fs::File;...

Rust

I don't really like my solution. It feels very messy but I also don't know how to clean it up. Lots of loops.

Solution
``````use std::env;
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 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; }

}
}

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);
}
``````
5. JRandomHacker
Echoing everyone else's calls that this was a fun one. It was also by far my most egregious abuse of LINQ thus far. C# Part 1 public override string SolvePart1() { using (var fs = new...

Echoing everyone else's calls that this was a fun one. It was also by far my most egregious abuse of LINQ thus far.
C#

Part 1
``````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);
int.Parse(match.Groups[2].Value),
int.Parse(match.Groups[3].Value),
int.Parse(match.Groups[4].Value),
int.Parse(match.Groups[5].Value)));
}

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

var otherTickets = new List<List<int>>();
while ((line = fs.ReadLine()) != null)
{
}

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}";
}
}
``````
Part 2
``````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);
int.Parse(match.Groups[2].Value),
int.Parse(match.Groups[3].Value),
int.Parse(match.Groups[4].Value),
int.Parse(match.Groups[5].Value)));
}

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

var otherTickets = new List<List<int>>();
while ((line = fs.ReadLine()) != null)
{
}

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)))
{
}
}
}

//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();

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]];

}
}
``````
Helpers
``````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))
{
}
}

return ret;
}
}
``````
Commentary

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.

6. Crespyl
Ruby This one was fun, it always feels nice to watch the pieces clicking into place when running these constraint satisfaction puzzles. Part 1 I don't usually use bare enumerator/iterator objects...

Ruby

This one was fun, it always feels nice to watch the pieces clicking into place when running these constraint satisfaction puzzles.

Part 1 I don't usually use bare enumerator/iterator objects in ruby, but wanted to break out the parsing of each section of the input file. Not at all happy with the `rescue StopIteration` in there, but I wasn't quickly finding a good way to test if the enumerator had more values or not without handling that error. This could definitely be cleaner.
``````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

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

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

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
``````
Part 2 Lost a bunch of time in part 2 due to some kind of logic bug, but I did have the right approach. My solution worked for the sample input right away, but failed on the full input for a while, and I ended up thinking that there weren't any fields that could be narrowed down to a single possibility in the first pass.

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

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

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

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
``````
7. Lynx
(edited )
Haskell Yep, this one was fun. Unlike some of the previous ones, it was a breeze to implement in haskell. Repo link day16.hs {-# LANGUAGE NamedFieldPuns #-} module Day16 where import AoC import...

Yep, this one was fun. Unlike some of the previous ones, it was a breeze to implement in haskell.

day16.hs
``````{-# LANGUAGE NamedFieldPuns #-}

module Day16 where

import AoC

import Data.List
import Data.Maybe
import qualified Data.Set as S
import Data.Set (Set)

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 p = p <* char '\n'

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
char '-'
return (n1, n2)

parseTicket = readDecP `sepBy` char ','

parseInput = do
fields <- many1 \$ line parseField
line \$ string ""
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
``````
AoC.hs (utility functions)
``````module AoC
( (.:)
, enumerate
, oneCompleteResult
, splitOnEmptyLines
, runAoC
)
where

import Data.Function (on)
import Data.List (groupBy)

(.:) :: (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
``````
8. Gyrfalcon
Language: Julia Repository This one took a little longer than I had hoped, partly because I was overcomplicating the second part into a sudoku like mess, and partly because I took the shortcut of...

This one took a little longer than I had hoped, partly because I was overcomplicating the second part into a sudoku like mess, and partly because I took the shortcut of just returning the offending value in part 1. That meant that even though I had a working algorithm in part 2, I was passing in invalid data and getting confused when it didn't work out!

Part 1
``````function main()

input = []
open("Day16/input.txt") do fp
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()
``````
Part 2 diff
``````@@ -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()
``````
9. jzimbel
Elixir Still working on catching up after doing other things the past few days, but I had fun with this one so I thought I'd post it. TBQH it's messy and some functions/variables are in need of...

Elixir

Still working on catching up after doing other things the past few days, but I had fun with this one so I thought I'd post it. TBQH it's messy and some functions/variables are in need of renaming and documenting for it to make any sense, but... here you go lol. 💁‍♂️

Despite all of the nested iterations and the recursive `deduce/1` where I pare down the possible field labels one at a time, it runs pretty quickly: part 1 in 2ms, part 2 in 15ms.

Parts 1 and 2
``````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
``````
10. Bauke
Language: Rust. Repository. Main function (run harness). Fun! In part two it took me a minute to figure out I first had to calculate all of the possible combinations for the different columns and...

Fun! In part two it took me a minute to figure out I first had to calculate all of the possible combinations for the different columns and then figure out the unique ones, but I got there in the end.

Pretty happy this one finishes in about 10 milliseconds too, with how many numbers there are in the input I was expecting it to take a lot longer.

Solution
``````use std::collections::HashMap;

use crate::DayResult;

pub(crate) fn solve(data: String) -> DayResult {
let mut parts = data.trim().split("\n\n");
let mut ranges = vec![];

for line in parts.next().unwrap().lines() {
let name = &line[0..line.find(':').unwrap()];

let mut first_range = line
[line.find(':').unwrap() + 2..line.find(" or").unwrap()]
.split('-')
.map(str::parse::<usize>)
.map(Result::unwrap);

let first_range = first_range.next().unwrap()..=first_range.next().unwrap();

let mut second_range = line[line.find(" or ").unwrap() + 4..]
.split('-')
.map(str::parse::<usize>)
.map(Result::unwrap);

let second_range =
second_range.next().unwrap()..=second_range.next().unwrap();

ranges.push((name, first_range, second_range));
}

let my_ticket = parts
.next()
.unwrap()
.lines()
.nth(1)
.unwrap()
.split(',')
.map(str::parse::<_>)
.map(Result::unwrap)
.collect::<Vec<_>>();

let mut tickets = vec![];

// Skip the first line in the 3rd part, as it will say "nearby tickets:".
for line in parts.next().unwrap().lines().skip(1) {
tickets.push(
line
.split(',')
.map(str::parse::<usize>)
.map(Result::unwrap)
.collect::<Vec<_>>(),
);
}

let mut result_one = 0;
let mut valid_tickets = vec![my_ticket.clone()];

for ticket in &tickets {
let mut ticket_is_valid = true;

for field in ticket {
let field_is_invalid = ranges.iter().all(|(_, range_1, range_2)| {
!range_1.contains(field) && !range_2.contains(field)
});

if field_is_invalid {
result_one += field;
ticket_is_valid = false;
}
}

if ticket_is_valid {
valid_tickets.push(ticket.clone());
}
}

let mut possibilities = HashMap::new();
let ticket_length = my_ticket.len();

for (name, range_1, range_2) in ranges {
for index in 0..ticket_length {
let mut fields = valid_tickets
.iter()
.map(|tickets| tickets.get(index))
.map(Option::unwrap);

if fields.all(|field| range_1.contains(field) || range_2.contains(field))
{
let possibility = possibilities.entry(name).or_insert(vec![]);
possibility.push(index);
}
}
}

let mut possibilities = possibilities.into_iter().collect::<Vec<_>>();
possibilities.sort_by(|a, b| a.1.len().cmp(&b.1.len()));
let mut indices = HashMap::<usize, &str>::new();

for (name, possibilities) in possibilities {
'inner: for possibility in possibilities {
if indices.contains_key(&possibility) {
continue 'inner;
}

indices.insert(possibility, name);
}
}

let result_two = Some(
my_ticket
.iter()
.enumerate()
.filter_map(|(index, number)| {
if let Some(name) = indices.get(&index) {
if name.starts_with("departure") {
Some(number)
} else {
None
}
} else {
None
}
})
.product::<usize>()
.to_string(),
);

Ok((Some(result_one.to_string()), result_two))
}
``````
Output
``````🌟 Day 16  |
🎆 Part 1  | 26980
🎇 Part 2  | 3021381607403
🌠 Runtime | 10.71601ms
``````
1 vote