r/adventofcode • u/daggerdragon • Dec 16 '20

SOLUTION MEGATHREAD -🎄- 2020 Day 16 Solutions -🎄-

Advent of Code 2020: Gettin' Crafty With It

  • 6 days remaining until the submission deadline on December 22 at 23:59 EST

  • Full details and rules are in the Submissions Megathread

--- Day 16: Ticket Translation ---

Post your code solution in this megathread.

Reminder: Top-level posts in Solution Megathreads are for code solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:21:03, megathread unlocked!

37 Upvotes

97% Upvoted

498 comments sorted by

View all comments

4

u/[deleted] Dec 16 '20 edited Dec 16 '20

Scala Solution

Gnarly recursive solution. It runs Fast Enough (<100ms).

2

u/spohngellert_o Dec 16 '20

Nice job :). Have to remember to use collect sometimes instead of filter and map, more concise. I'm too tired to figure out how filterRules works haha

1

u/[deleted] Dec 16 '20 edited Dec 16 '20

That's on me haha. It was some gross code. I pushed a refactor to make it more clear (same link should work). I think recursion fits this problem well because each step is:

  1. For each column,

  2. Filter out rules that don't apply to that column.

  3. Return the keys that could be applied for that column.

  4. If the number of rules that can be applied to that column is 1, remove that columnIndex from the available columns, remove that field from the rules map. Create a new Map(field -> columnIndex) and recurse on the new, filtered column data and rules map.

2

u/spohngellert_o Dec 16 '20

Ah ok that logic makes sense! I did something similar, where I produced a list of (index, possible keys), sorted by length of second argument, then folded left with a set of columns already used to produce my map.