11 votes

Day 16: Ticket Translation

Today's problem description: https://adventofcode.com/2020/day/16


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
Your code here.
```

</details>

9 comments

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

    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 field corresponded to a list of ranges that can be checked to determine if the field values are valid. I used this table to basically find all the invalid nearby tickets by checking if any values did not fit into any of the ranges specified by the field rules.

    import itertools
    import re
    import sys
    
    # Functions
    
    def read_rules():
        rules = {}
    
        while line := sys.stdin.readline().strip():
            field, ranges = line.split(':', 1)
            rules[field]  = [
                (int(s), int(e)) for s, e in re.findall(r'(\d+)-(\d+)', ranges)
            ]
    
        return rules
    
    def read_tickets():
        return [
            [int(f) for f in l.split(',')] for l in sys.stdin if ',' in l
        ]
    
    def flatten(iterable):
        return list(itertools.chain.from_iterable(iterable))
    
    def find_invalid_fields(rules, ticket):
        all_ranges = flatten(rules.values())
    
        for value in ticket:
            if not any(s <= value <= e for s, e in all_ranges):
                yield value
    
    # Main Execution
    
    def main():
        rules    = read_rules()
        tickets  = read_tickets()
        nearby   = tickets[1:]
        invalids = flatten(
            find_invalid_fields(rules, ticket) for ticket in nearby
        )
    
        print(sum(invalids))
    
    if __name__ == '__main__':
        main()
    
    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
    
    def read_rules():
        rules = {}
    
        while line := sys.stdin.readline().strip():
            field, ranges = line.split(':', 1)
            rules[field]  = [(int(start), int(end)) for start, end in re.findall(r'(\d+)-(\d+)', ranges)]
    
        return rules
    
    def read_tickets():
        return [[int(field) for field in line.split(',')] for line in sys.stdin if ',' in line]
    
    def flatten(iterable):
        return itertools.chain.from_iterable(iterable)
    
    def is_ticket_valid(rules, ticket):
        return all(any(s <= v <= e for s, e in flatten(rules.values())) for v in ticket)
    
    def find_matches(rules, tickets):
        matches = {}
        
        for field, ranges in rules.items():
            matches[field] = [ 
                index for index in range(len(tickets[0])) if all(
                    any(s <= ticket[index] <= e for s, e in ranges) for ticket in tickets
                )
            ]
    
        return matches
    
    def find_fields(matches):
        fields = {}
    
        while matches:
            singles = [(field, indices[0]) for field, indices in matches.items() if len(indices) == 1]
    
            for field, index in singles:
                fields[index] = field
                for f in matches:
                    matches[f].remove(index)
                del matches[field]
    
        return fields
    
    # Main Execution
    
    def main():
        rules    = read_rules()
        tickets  = read_tickets()
        valids   = [ticket for ticket in tickets if is_ticket_valid(rules, ticket)]
    
        matches  = find_matches(rules, valids)
        fields   = find_fields(matches)
    
        values   = [value for index, value in enumerate(tickets[0]) if fields[index].startswith('departure')]
        result   = functools.reduce(operator.mul, values, 1)
    
        print(result)
    
    if __name__ == '__main__':
        main()
    
    4 votes
  2. nothis
    (edited )
    Link
    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:
        tickedData = inputFile.read()
    
    # [lower limit 1, upper limit 1, lower limit 2, upper limit 2, rule name]
    rules = [[int(rule[1]), int(rule[2]), int(rule[3]), int(rule[4]), rule[0]]
             for rule in re.findall(r'([a-z| ]+)\: (\d+)\-(\d+) or (\d+)\-(\d+)', tickedData)]
    
    myTicket = [int(number) for number in re.findall(
        r'your ticket\:\n(.+)\n', tickedData)[0].split(",")]
    
    nearbyTickets = [list(map(int, numbers.split(",")))
                     for numbers in re.findall(r'nearby tickets\:\n(.+)',
                                               tickedData, re.DOTALL)[0].split("\n")]
    
    
    def validate(tickets, myTicket, rules):
        invalidNumbers = []
        validTickets = []
    
        for ticket in tickets:
            ticketValid = True
            for number in ticket:
                numberValid = False
                for rule in rules:
                    if (number >= rule[0] and number <= rule[1]) or (number >= rule[2] and number <= rule[3]):
                        numberValid = True
                        break
                if not numberValid:
                    invalidNumbers.append(number)
                    ticketValid = False
                    break
            if ticketValid:
                validTickets.append(ticket)
        print("Scanning error rate:", sum(invalidNumbers))
        validTickets.append(myTicket)
        return validTickets
    
    
    def findPositions(tickets, rules):
        fieldPossibilities = {}
        for rule in rules:
            fieldPossibilities[rule[4]] = ["?"] * len(rules)
    
        for ticket in tickets:
            for pos in range(0, len(ticket)):
                for rule in rules:
                    if not ((ticket[pos] >= rule[0] and ticket[pos] <= rule[1]) or (ticket[pos] >= rule[2] and ticket[pos] <= rule[3])):
                        # this rule's field name can't be at pos!
                        fieldPossibilities[rule[4]][pos] = "."
    
        positions = {}
        while len(positions) < len(rules):
            for field in fieldPossibilities:
                if fieldPossibilities[field].count("?") == 1:
                    # only one possible position for this field name!
                    index = fieldPossibilities[field].index("?")
                    positions[field] = index
                    for f in fieldPossibilities:
                        # invalidate others for this position by marking them "."
                        fieldPossibilities[f][index] = "."
        return positions
    
    
    def departureProduct(positions, myTicket):
        departureProduct = 1
        for posName in positions:
            if "departure" in posName:
                departureProduct *= myTicket[positions[posName]]
        print("Product of all departure fields:", departureProduct)
    
    
    validTickets = validate(nearbyTickets, myTicket, rules)
    positions = findPositions(validTickets, rules)
    departureProduct(positions, myTicket)
    
    4 votes
  3. PapaNachos
    Link
    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)
    
    answer = 1
    my_ticket = list(map(int,my_ticket[0].split(',')))
    for key in known_fields.keys():
        if 'departure' in known_fields[key]:
            answer = answer * my_ticket[key]
            
    print(answer)
    
    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 votes
  4. wycy
    Link
    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::io::{prelude::*, BufReader};
    use std::fs::File;
    use std::collections::HashMap;
    
    extern crate regex;
    use regex::Regex;
    
    #[macro_use]
    extern crate text_io;
    
    #[derive(Debug, Clone)]
    struct TicketField {
        name: String,
        range1: (u64,u64),
        range2: (u64,u64),
        possible_pos: Vec<bool>,
    }
    impl From<&String> for TicketField {
        fn from(input: &String) -> Self {
            // departure station: 28-106 or 130-969
            let name: String;
            let mut range1: (u64,u64) = (0,0);
            let mut range2: (u64,u64) = (0,0);
            scan!(input.bytes() => "{}: {}-{} or {}-{}", name, range1.0, range1.1, range2.0, range2.1);
            Self {
                name: name,
                range1: range1,
                range2: range2,
                possible_pos: Vec::new(),
            }
        }
    }
    impl TicketField {
        pub fn validate(&self, value: u64) -> bool {
            (self.range1.0..=self.range1.1).contains(&value) || (self.range2.0..=self.range2.1).contains(&value)
        }
    }
    
    #[derive(Debug, Clone)]
    struct Ticket {
        fields: Vec<u64>,
        valid: bool,
    }
    impl From<&String> for Ticket {
        fn from(input: &String) -> Self {
            Self {
                fields: input.split(",").map(|x| x.parse::<u64>().unwrap()).collect::<Vec<_>>(),
                valid: true,
            }
        }
    }
    
    fn day16(input: &str) {
        let file = File::open(input).expect("Input file not found.");
        let reader = BufReader::new(file);
    
        let input: Vec<String> = match reader.lines().collect() {
            Err(err) => panic!("Unknown error reading input: {}", err),
            Ok(result) => result,
        };
    
        // Process input
        let mut fields: Vec<TicketField> = Vec::new();
        let mut tickets: Vec<Ticket> = Vec::new();
    
        let re_field = Regex::new(r"^[\w ]+: [\d]+\-[\d]+ or [\d]+\-[\d]+$").unwrap();
        let re_ticket = Regex::new(r"^([\d]+,)+[\d]+$").unwrap();
        for line in input {
            if re_field.is_match(&line) {
                fields.push(TicketField::from(&line));
            } else if re_ticket.is_match(&line) {
                tickets.push(Ticket::from(&line));
            }
        }
    
        // Part 1
        let mut part1 = 0;
        for ticket in &mut tickets {
            for val in &ticket.fields {
                if fields.iter().map(|f| f.validate(*val)).filter(|f| f == &true).count() == 0 {
                    part1 += val;
                    ticket.valid = false;
                }
            }
        }
        println!("Part 1: {}", part1); // 26009
    
        // Part 2
        let tickets = tickets.iter().filter(|t| t.valid).collect::<Vec<_>>();
        let num_fields = fields.len();
        let my_ticket = tickets.get(0).unwrap();
    
        // Build array of bools to track possible field positions
        for field in &mut fields { field.possible_pos = vec![true; num_fields]; }
    
        // Rule out certain field positions
        for field in &mut fields {
            for ticket in &tickets {
                for (ix,val) in ticket.fields.iter().enumerate() {
                    if !field.validate(*val) {
                        field.possible_pos[ix] = false;
                    }
                }
            }
        }
    
        // Narrow down one field at a time
        let mut order: HashMap<usize,String> = HashMap::new();
        while order.len() != num_fields {
            for i in 0..num_fields {
                if fields[i].possible_pos.iter().filter(|&x| *x == true).count() != 1 { continue; }
                let ix = fields[i].possible_pos.iter().position(|&x| x == true).unwrap();
                order.insert(ix, fields[i].name.clone());
                for f_other in &mut fields { f_other.possible_pos[ix] = false; }
                
            }
        }
    
        // Calculate part 2 answer
        let part2 = my_ticket
            .fields
            .iter()
            .enumerate()
            .map(|(i,x)| 
                match order.get(&i).unwrap().split_ascii_whitespace().next().unwrap() {
                    "departure" => x,
                    _ => &1u64,
                })
            .product::<u64>();
    
        println!("Part 2: {}", part2); // 589685618167
    
    }
    
    fn main() {
        let args: Vec<String> = env::args().collect();
        let filename = &args[1];
        day16(&filename);
    }
    
    4 votes
  5. JRandomHacker
    Link
    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);
    			rules.Add(new TicketRule(match.Groups[1].Value,
    				int.Parse(match.Groups[2].Value),
    				int.Parse(match.Groups[3].Value),
    				int.Parse(match.Groups[4].Value),
    				int.Parse(match.Groups[5].Value)));
    		}
    
    		fs.ReadLine();
    		var myTicket = fs.ReadLine().Split(',').Select(s => int.Parse(s)).ToList();
    
    		fs.ReadLine();
    		fs.ReadLine();
    		var otherTickets = new List<List<int>>();
    		while ((line = fs.ReadLine()) != null)
    		{
    			otherTickets.Add(line.Split(',').Select(s => int.Parse(s)).ToList());
    		}
    
    		var totalInvalid = otherTickets.Sum(ticket => ticket.Select(i => new Tuple<int, bool>(i, rules.Any(r => r.IsValid(i)))).Where(ib => !ib.Item2).Sum(ib => ib.Item1));
    
    		return $"Total error rate is {totalInvalid}";
    	}
    }
    
    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);
    			rules.Add(new TicketRule(match.Groups[1].Value,
    				int.Parse(match.Groups[2].Value),
    				int.Parse(match.Groups[3].Value),
    				int.Parse(match.Groups[4].Value),
    				int.Parse(match.Groups[5].Value)));
    		}
    
    		fs.ReadLine();
    		var myTicket = fs.ReadLine().Split(',').Select(s => int.Parse(s)).ToList();
    
    		fs.ReadLine();
    		fs.ReadLine();
    		var otherTickets = new List<List<int>>();
    		while ((line = fs.ReadLine()) != null)
    		{
    			otherTickets.Add(line.Split(',').Select(s => int.Parse(s)).ToList());
    		}
    
    		var validTickets = otherTickets.Where(ticket => ticket.All(i => rules.Any(r => r.IsValid(i)))).ToList();
    		var fieldDatas = new List<int>[20];
    		for(int i = 0; i < fieldDatas.Length; i++)
    		{
    			fieldDatas[i] = validTickets.Select(ticket => ticket[i]).ToList();
    		}
    
    		//Search for matching rule
    		//Map list of rules -> list of fields
    		var fieldMapCandidates = new List<Tuple<List<int>, int>>();
    		for(int i = 0; i < fieldDatas.Length; i++)
    		{
    			var matches = new List<int>();
    			for(int j = 0; j < rules.Count(); j++)
    			{
    				if (fieldDatas[i].All(f => rules[j].IsValid(f)))
    				{
    					matches.Add(j);
    				}
    			}
    			fieldMapCandidates.Add(Tuple.Create(matches, i));
    		}
    
    		//Rules -> fields
    		var confirmedRules = new Dictionary<int, int>();
    
    		while (fieldMapCandidates.Count() > 0)
    		{
    			var singles = fieldMapCandidates.Where(fmc => fmc.Item1.Count == 1).ToList();
    			fieldMapCandidates.RemoveAll(fmc => singles.Any(s => s.Item2 == fmc.Item2));
    			foreach (var pair in singles)
    			{
    				var rule = pair.Item1.Single();
    				confirmedRules.Add(rule, pair.Item2);
    
    				for (int i = 0; i < fieldMapCandidates.Count; i++)
    				{
    					fieldMapCandidates[i] = Tuple.Create(fieldMapCandidates[i].Item1.Where(r => r != rule).ToList(), fieldMapCandidates[i].Item2);
    				}
    
    			}
    		}
    
    		long answer = (long)myTicket[confirmedRules[0]] * (long)myTicket[confirmedRules[1]] * (long)myTicket[confirmedRules[2]] * (long)myTicket[confirmedRules[3]] * (long)myTicket[confirmedRules[4]] * (long)myTicket[confirmedRules[5]];
    
    		return $"Final ticket answer is {answer}";
    	}
    }
    
    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))
    			{
    				ret.Add(i);
    			}
    		}
    
    		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.

    4 votes
  6. Crespyl
    Link
    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
    
      # read rules
      rules = {}
      while (l = lines.next).strip.size > 0
        r = parse_rule(l)
        rules[r[0]] = r[1..]
      end
    
      # read my ticket
      l = lines.next until l.start_with?("your ticket:")
      my_ticket = lines.next.split(',').map(&:to_i)
    
      # read nearby tickets
      l = lines.next until l.start_with?("nearby tickets:")
      nearby_tickets = []
      begin
        while (l = lines.next.strip).size > 0
          nearby_tickets << l.split(',').map(&:to_i)
        end
      rescue StopIteration
      end
    
      # check each value in nearby_tickets for all rules
      invalid_values = []
      nearby_tickets.each do |ticket|
        ticket.each do |value|
          invalid_values << value unless rules.values.flatten.any? { |r| r.include?(value) }
        end
      end
    
      return invalid_values.sum
    end
    
    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
    
      # read rules
      rules = {}
      while (l = lines.next).strip.size > 0
        r = parse_rule(l)
        rules[r[0]] = r[1..]
      end
    
      # read my ticket
      l = lines.next until l.start_with?("your ticket:")
      my_ticket = lines.next.split(',').map(&:to_i)
    
      # read nearby tickets
      l = lines.next until l.start_with?("nearby tickets:")
      nearby_tickets = []
      begin
        while (l = lines.next.strip).size > 0
          nearby_tickets << l.split(',').map(&:to_i)
        end
      rescue StopIteration
      end
    
      # check each value in each of nearby_tickets against all rules to find the valid tickets
      valid_tickets = nearby_tickets.filter do |ticket|
        ticket.all? { |value| rules.values.flatten.any? { |r| r.include?(value) } }
      end
    
      unknown_fields = Set.new(rules.keys)
      fields_order = Array.new(my_ticket.size)
    
      while unknown_fields.size > 0
        # look at the nth field in each ticket, and find the rule that matches all values
        my_ticket.size.times do |n|
          matching_rules = valid_tickets.map { _1[n] }.reduce(unknown_fields) do |set, value|
            set & unknown_fields.filter { |k| rules[k].any? { |r| r.include? value } }
          end
          if matching_rules.size == 1
            fields_order[n] = matching_rules.first
            unknown_fields -= [matching_rules.first]
          end
        end
      end
    
      binding.pry if unknown_fields.size > 0
    
      if return_fields.nil?
        return_fields = fields_order.filter { |f| f.to_s.start_with?("departure") }
      end
    
      return return_fields.reduce(1) { |product, field| product * my_ticket[fields_order.index(field)] }
    end
    
    3 votes
  7. Lynx
    (edited )
    Link
    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...

    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 Data.List
    import Data.Maybe
    import qualified Data.Set as S
    import Data.Set (Set)
    import Text.ParserCombinators.ReadP
    import Text.Read.Lex
    
    data Field = Field { name :: String
                       , valids :: Set Int
                       } deriving (Show)
    
    type Ticket = [Int]
    
    data Input = Input { fields :: [Field]
                       , myTicket :: Ticket
                       , otherTickets :: [Ticket]
                       } deriving (Show)
    
    line :: ReadP a -> ReadP a
    line p = p <* char '\n'
    
    parseField :: ReadP Field
    parseField = do
        name <- many1 $ satisfy (/=':')
        string ": "
        ranges <- parseRange `sepBy` string " or "
        let valids = S.fromList . concat . map (uncurry enumFromTo) $ ranges
        return $ Field { name, valids }
        where parseRange = do
                n1 <- readDecP
                char '-'
                n2 <- readDecP
                return (n1, n2)
    
    parseTicket :: ReadP Ticket
    parseTicket = readDecP `sepBy` char ','
    
    parseInput :: ReadP Input
    parseInput = do
        fields <- many1 $ line parseField
        line $ string ""
        line $ string "your ticket:"
        myTicket <- line parseTicket
        line $ string ""
        line $ string "nearby tickets:"
        otherTickets <- many1 $ line parseTicket
        return $ Input {fields, myTicket, otherTickets }
    
    matchesAnyField :: [Field] -> Int -> Bool
    matchesAnyField fields n = any (n `S.member`) . map valids $ fields
    
    iterateUntilDone :: (a -> Maybe a) -> a -> a
    iterateUntilDone f x = case f x of
                             Just x' -> iterateUntilDone f x'
                             Nothing -> x
    
    data Resolve a = Resolved a | Choice (Set a) deriving (Show)
    
    resolve :: Ord a => [[a]] -> Maybe [a]
    resolve = sequence . map fromResolved . iterateUntilDone resolve' . map (Choice . S.fromList)
        where fromResolved (Resolved x) = Just x
              fromResolved _ = Nothing
    
    findSingletonChoice :: [Resolve a] -> Maybe (a, [Resolve a])
    findSingletonChoice (c@(Choice s):xs) | S.size s == 1 = let [x] = S.elems s
                                                            in Just (x, Resolved x:xs)
                                          | otherwise = (fmap.fmap) (c:) $ findSingletonChoice xs
    findSingletonChoice (x:xs) = (fmap.fmap) (x:) $ findSingletonChoice xs
    findSingletonChoice _ = Nothing
    
    resolve' :: Ord a => [Resolve a] -> Maybe [Resolve a]
    resolve' xs = do
        (x, xs') <- findSingletonChoice xs
        return $ map (dropChoice x) xs'
        where dropChoice x (Choice s) = Choice (S.delete x s)
              dropChoice _ r = r
    
    part1 :: Input -> Int
    part1 Input { fields, otherTickets } = sum . filter (not . matchesAnyField fields) . concat $ otherTickets
    
    part2 :: Input -> Int
    part2 Input { fields, myTicket, otherTickets } = product departureValues
        where validTickets = filter (all $ matchesAnyField fields) otherTickets
              columns = transpose validTickets
              fieldNames = fromJust . resolve . map findPossibleFields $ columns
              departureIndices = findIndices ("departure" `isPrefixOf`) fieldNames
              departureValues = map (myTicket !!) departureIndices
              findPossibleFields col = map name . filter (\field -> all (`S.member` valids field) col) $ fields
    
    main = runAoC (fromJust . oneCompleteResult parseInput) part1 part2
    
    AoC.hs (utility functions)
    module AoC
        ( (.:)
        , enumerate
        , oneCompleteResult
        , splitOnEmptyLines
        , runAoC
        )
    where
    
    import Data.Function (on)
    import Data.List (groupBy)
    import Text.ParserCombinators.ReadP
    
    (.:) :: (c -> d) -> (a -> b -> c) -> a -> b -> d
    f .: g = (f .) . g
    infixl 8 .:
    
    enumerate :: Enum i => i -> [a] -> [(i, a)]
    enumerate _ [] = []
    enumerate i (x:xs) = (i, x) : enumerate (succ i) xs
    
    oneCompleteResult :: ReadP a -> String -> Maybe a
    oneCompleteResult p s = case readP_to_S (p <* eof) s of
                              [(x, "")] -> Just x
                              _ -> Nothing
    
    splitOnEmptyLines :: String -> [[String]]
    splitOnEmptyLines = filter (not . any null) . groupBy ((==) `on` null) . lines
    
    runAoC :: (Show r1, Show r2) => (String -> i) -> (i -> r1) -> (i -> r2) -> IO ()
    runAoC inputTransform part1 part2 = do
        contents <- inputTransform <$> getContents
        print $ part1 contents
        print $ part2 contents
    
    2 votes
  8. Gyrfalcon
    Link
    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
            input = split(readchomp(fp), "\n\n")
        end
    
        input_fields = split.(split(input[1], '\n'), ": ")
        fields = Dict()
        for field in input_fields
            values = split.(split(field[2], " or "), '-')
            fields[field[1]] = parse.(Int, [values[1][1], values[1][2],
                                            values[2][1], values[2][2]])
        end
        
        my_ticket = split.(split(input[2], '\n')[2], ',')
        my_ticket = [parse(Int, val) for val in my_ticket]
        
        nearby_tickets = split.(split(input[3], '\n')[2:end], ',')
        nearby_tickets = [[parse(Int, val) for val in ticket] for ticket in nearby_tickets]
    
        error_rate = 0
        for ticket in nearby_tickets
            error_rate += basic_validation(ticket, fields)
        end
    
        println(error_rate)
    
    end
    
    function basic_validation(ticket, fields)
        for value in ticket
            valid = false
            for bounds in values(fields)
                if (bounds[1] <= value <= bounds[2]) || (bounds[3] <= value <= bounds[4])
                    valid = true
                end
            end
            if !valid
                return value
            end
        end
        return 0
    end
    
    main()
    
    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()
    
    2 votes
  9. jzimbel
    Link
    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
    
    2 votes