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>
```

PythonRepo 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.## 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 atopological sortingprocess.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 :]

PythonYay, 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

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

## 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.

## 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 sectionsMy 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.

RustI 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

Echoing everyone else's calls that this was a fun one. It was also by

farmy most egregious abuse of LINQ thus far.C### Part 1

## Part 2

## Helpers

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

entirelyaccomplished by LINQ one-liners.RubyThis 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.## 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.

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

Repo link

## day16.hs

## AoC.hs (utility functions)

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

## Part 2 diff

ElixirStill 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

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 thenfigure 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

## Output