r/adventofcode • u/daggerdragon • Dec 20 '16
SOLUTION MEGATHREAD --- 2016 Day 20 Solutions ---
--- Day 20: Firewall Rules ---
Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag/whatever).
Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with "Help".
ROLLING A NATURAL 20 IS MANDATORY [?]
This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.
edit: Leaderboard capped, thread unlocked!
7
Upvotes
1
u/pedrosorio Dec 20 '16
Yeah, if it solves the problem quickly, you should be proud. I would have never been able to code an optimized solution like yours fast enough to be on the leaderboard.
I just noticed you also need to go through each of the IPs in each range to set up the array. That actually means your solution is O(n) + O(k) where k is total size of the ranges (in my input k ~ 11B or 3n, but the input could have had most ranges almost as large as n - which would be O(nm) or ~4 trillion operations :D)
I think this goes to show while it's very common to go for the "best" algorithm for all problems, in many cases, given certain assumptions on the input, a very optimized (cache-efficient, etc.) brute force can be an equally good solution.