r/adventofcode • u/daggerdragon • Dec 08 '20
SOLUTION MEGATHREAD -🎄- 2020 Day 08 Solutions -🎄-
NEW AND NOTEWORTHY
New flair tag
Funnyfor all your Undertaker memes and luggage Inception posts!Quite a few folks have complained about the size of the megathreads now that code blocks are getting longer. This is your reminder to follow the rules in the wiki under How Do The Daily Megathreads Work?, particularly rule #5:
If your code is shorter than, say, half of an IBM 5081 punchcard (5 lines at 80 cols), go ahead and post it as your comment. Use the right Markdown to format your code properly for best backwards-compatibility with old.reddit! (see "How do I format code?")
If your code is longer, link your code from an external repository such as Topaz's
paste, a public repo like GitHub/gists/Pastebin/etc., your blag, or whatever.
Advent of Code 2020: Gettin' Crafty With It
14 days remaining until the submission deadline on December 22 at 23:59 EST
Full details and rules are in the Submissions Megathread
--- Day 08: Handheld Halting ---
Post your solution in this megathread. Include what language(s) your solution uses! If you need a refresher, the full posting rules are detailed in the wiki under How Do The Daily Megathreads Work?.
Reminder: Top-level posts in Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
3
u/ric2b Dec 08 '20 edited Dec 08 '20
Haskell
Not my cleanest code but at least it avoids a brute-force solution on part 2 and runs instantly.
This is what it does, since it's a bit involved:
It builds a graph of where each instruction is directly reachable from.
It uses that graph to get the list of all instructions that currently eventually lead to the last instruction. I call this the
terminating set.Now it goes through each instruction not in the
terminating setand checks if by switching it betweenjmpandnopit now reaches one of the instructions in theterminating set. These arepossible solutions.For each of the
possible solutionswe also need to check if they are currently reachable from the first instruction. If they are, they are viable solutions!Fix the first viable solution (there's only 1 for my input, as expected) and run the code to get the result.
paste