2020-12-16 - Ticket Translation
(original .ipynb)
Day 16 is about numbers present on flight tickets. In the input (mine is here) you're given a set of ticket fields and the valid numbers they can have, your own ticket (a bunch of comma-separated integers) and a list of nearby tickets (many lines of comma-separated integers). You don't know which fields correspond to which part of the ticket. Part 1 involves applying some validation to input to find tickets which don't satisfy ANY rules, and returning the sum of their values. Part 2 obviously involves trying to map the ticket fields to the index they have in the comma-separated list of ticket numbers, finding the ones relating to the "departure" fields in your own ticket and multiplying them together.
test_input_str = """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"""
puzzle_input_str = open("puzzle_input/day16.txt", "r").read()
def parse_range(range_str):
start_str, end_str = range_str.split("-")
return (int(start_str), int(end_str))
def parse_rule(rule_str):
name, ranges_str = rule_str.split(": ")
ranges = [parse_range(range_str) for range_str in ranges_str.split(" or ")]
return (name, ranges)
def within_range(value, ranges):
for r_lower, r_upper in ranges:
if r_lower <= value and value <= r_upper:
return True
return False
def matching_rules(v, rules):
return [name for name, ranges in rules if within_range(v, ranges)]
def sum_invalid_fields(ticket, rules):
return sum(
v
for v
in ticket
if len(matching_rules(v, rules)) == 0
)
def parse_input(input_str):
rules_str, my_ticket_str, nearby_tickets_str = input_str.split("\n\n")
rules = [parse_rule(rule_str) for rule_str in rules_str.split("\n")]
my_ticket = [ int(s) for s in my_ticket_str.split("\n")[1].split(",")]
all_nearby_tickets = [
[ int(s) for s in ticket_str.split(",")]
for ticket_str
in nearby_tickets_str.split("\n")[1:]
]
return rules, my_ticket, all_nearby_tickets
def ticket_scanning_error_rate(input_str):
rules, my_ticket, all_nearby_tickets = parse_input(input_str)
return sum(
sum_invalid_fields(ticket, rules)
for ticket
in all_nearby_tickets
)
assert 71 == ticket_scanning_error_rate(test_input_str)
ticket_scanning_error_rate(puzzle_input_str)
19240
from collections import defaultdict
def all_rules_found(rules, possible_rule_indices):
return all(
len(possible_rule_indices[rule]) == 1
for rule, ranges
in rules
)
# I have no idea what to call this function, for an hour or so it was "blorp_rule"
# maybe should instead be two functions, come to think of it...
def comb_tickets_with_rule(ranges, possible_rule_indices, tickets):
if len(possible_rule_indices) == 1:
return list(possible_rule_indices)[0], []
to_eliminate = set()
for ticket in tickets:
for i in possible_rule_indices:
if not within_range(ticket[i], ranges):
to_eliminate.add(i)
return None, to_eliminate
def find_rule_indices(input_str):
rules, my_ticket, all_nearby_tickets = parse_input(input_str)
# validate the tickets
nearby_tickets = [ticket for ticket in all_nearby_tickets if sum_invalid_fields(ticket, rules) == 0]
# now the ugly stuff - start assuming all indices are possible for a given column
# and comb through it, removing invalid ones or ones which have been identified
# elsewhere
possible_rule_indices = defaultdict(lambda: set(range(len(my_ticket))))
while not all_rules_found(rules, possible_rule_indices):
for name, ranges in rules:
definite_match, to_eliminate = comb_tickets_with_rule(ranges, possible_rule_indices[name], nearby_tickets)
if definite_match != None:
for rule in possible_rule_indices:
if definite_match in possible_rule_indices[rule]:
if rule != name:
possible_rule_indices[rule].remove(definite_match)
possible_rule_indices[name] = set([definite_match])
elif len(to_eliminate) > 0:
for rule_index in to_eliminate:
possible_rule_indices[name].remove(rule_index)
rule_indices = {
rule:possible_rule_indices[rule].pop()
for rule
in possible_rule_indices
}
return my_ticket, rule_indices
test_input_str_2 = """class: 0-1 or 4-19
row: 0-5 or 8-19
seat: 0-13 or 16-19
your ticket:
11,12,13
nearby tickets:
3,9,18
15,1,5
5,14,9"""
# Based on the nearby tickets in the above example,
# - the first position must be row
# - the second position must be class
# - the third position must be seat
_, test_indices = find_rule_indices(test_input_str_2)
assert 0 == test_indices["row"]
assert 1 == test_indices["class"]
assert 2 == test_indices["seat"]
# departure location: 32-174 or 190-967
# departure station: 50-580 or 588-960
# departure platform: 35-595 or 621-972
# departure track: 41-85 or 104-962
# departure date: 39-293 or 299-964
# departure time: 44-192 or 215-962
departure_fields = [
"departure location",
"departure station",
"departure platform",
"departure track",
"departure date",
"departure time"
]
my_ticket, puzzle_indices = find_rule_indices(puzzle_input_str)
from functools import reduce
reduce(lambda x,y:x*y, [my_ticket[puzzle_indices[df]] for df in departure_fields])
21095351239483