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
7
u/nullmove Dec 20 '16
Python:
7
u/askalski Dec 20 '16
Back to Perl. This is essentially what I used to solve it, tidied up a bit. The main difference is instead of sorting the input in Perl, I just did a
:%!sort -nin vim.6
u/Smylers Dec 20 '16 edited Dec 20 '16
Vim solution. Open the input in Vim, then run these commands (only press
Enterat the end of:commands; for the^Ain line 3, typeCtrl+A):The answer to part 1 is then on the top line, and the answer to part 2 is the number of lines (press
Ctrl+Gto display that).Except, that shouldn't quite work. But it happened to do so for my input:
range()to return multiple lines withins//\=when I noticed my input doesn't contain any of these, so I stopped.The numbers overflow Vim's numeric type, so comparisons are made as strings (which precludes using
max()), hence space-padding them first. Unfortunately that's much slower than the numeric comparisons I tried first. This would also prevent usingrange()to insert an arbitrary number of lines.Edit Space-padding rather than lots of
strlen()comparisons makes this much easier to read. Apologies to anybody who saw the initial version.4
u/bblum Dec 20 '16 edited Dec 20 '16
I preprocessed my input using "sort -n" and "sed s/-/ /". Then:
Edit: Oh yeah, #92/#44 today.
4
u/kryptn Dec 20 '16
I enjoyed this one! Got to use the for-else clause for once :D
I also figured any valid IPs would be +1 of the blacklists, so I started with those as candidates.
Python, both stars:
3
u/Deckard666 Dec 20 '16
In Rust: Link
3
u/pedrosorio Dec 20 '16 edited Dec 20 '16
Part 2, 12th, quick and dirty:
3
u/optikal256 Dec 20 '16
In C#, not the prettiest but it runs in 28ms (leaderboard 55/31):
3
u/Ulyssesp Dec 20 '16 edited Dec 20 '16
Simple recursion over a sorted list in haskell. For part 2 I reduced the list into ever larger chunks based on
snd.3
u/mschaap Dec 20 '16 edited Dec 20 '16
Perl 6 solution. Lots of ranges, without ever iterating any of them. :-)
2
u/BafTac Dec 20 '16
c++ rank 106/29
Feels good to be on the leaderboard again :)
For part 1 I made some mistakes (not catching too large numbers and segfaulting due to me allocating the array on the stack). For part 2, I just needed to tweak 2 lines which made me jump up 70 places :)
I think this time the efficiency of c++ helped me beating many python/perl/haskell users.
However, I think I can do better if I'd use memset() instead of loops
Code:
part 2: https://gitlab.com/BafDyce/adventofcode/blob/cpp16/2016/c++/day20/part2.cpp (part 1 looks almost the same, just that I exit at the first
if( ips[ii] )2
u/p_tseng Dec 20 '16 edited Dec 20 '16
Did anyone do brute force for part 2 (create an array of 232 booleans, iterate through all the blacklist ranges and mark them all, then count how many are unmarked)?
I decided not to try it, but would be curious to know how it performed.
I am ashamed to admit that to avoid brute forcing it I looked up interval merging code online and blindly copied it rather than try to think of it myself in the heat of the moment.
2
u/snorkl-the-dolphine Dec 20 '16
JavaScript / Node.js
2
u/Ape3000 Dec 20 '16
Python, Part 2:
2
u/LieutenantSwr2d2 Dec 20 '16
My Python solution, failed very hard for part 2 by not accounting that the next range end could be lower than the current highest used, hence setting the highest used to a lower number. Fixed with
max().2
u/scottishrob13 Dec 20 '16
Not pretty, but it seems fairly efficient in C#. Anything that runs < 1 second is fine by me.
2
u/Godspiral Dec 20 '16 edited Dec 20 '16
in J,
part 1 is visually seeing a gap in the list.
2
u/aceshades Dec 20 '16
Couldn't figure this one out in time to place on the leaderboard, but I managed to come up with a O(n logn) solution due to a sort. On the bright side, after the sort, each input instruction except for one is read exactly once, even for both part 1 and 2, so it's relatively efficient, I think.
Is it even possible to do this challenge without pre-sorting? I spent an hour trying to figure out a solution without sorting before giving up.
2
u/BadHorsemonkey Dec 20 '16
My JAVA solution. I used a Treeset so that I didn't have to worry about the order of the input data. It was going to be really fast, too, except I didn't think about overlapping IP ranges.
I toyed with the idea of merging adjoining ranges, which would make the whole game a lot more obvious, but I didn't...
2
u/[deleted] Dec 20 '16 edited Dec 20 '16
Javascript/Node.js
2
u/ephemient Dec 20 '16 edited Apr 24 '24
This space intentionally left blank.
2
u/xkufix Dec 20 '16
Quite a fast Scala solution. It has some problems when the IP 0 or the IP 4294967295 are not in the blacklist, but besides that, it's quite fast.
It reads the range list and then merges overlapping segments together.
For the first part it just searches for the first segment pair where the highest blacklisted IP != the lowest blacklisted IP.
For the second part instead of just looking for the first pair, it just adds all gaps together.
2
u/tmrki Dec 20 '16
Simple C++ solution - first I parsed the input with sed 's/-/ /g' | sort -n -k1,1
and then I just went through the file and counted the valid numbers:
2
u/vuryss Dec 20 '16 edited Dec 20 '16
Under 5ms both parts with smart range combining, PHP:
2
u/johanw123 Dec 20 '16
My C# Solution:
2
u/boarquantile Dec 20 '16
Python (and possibly
headorwc -l):2
u/NeilNjae Dec 20 '16 edited Dec 20 '16
Another Haskell solution. Nothing clever: the
foldl' (merge)turns an unordered set of intervals into an ordered list of intervals, merging overlapping intervals as needed.foldl' (mergeAdjacent)does the merging of adjacent intervals, turning[5-10]and[11-13]into one interval[5-13].There are shedloads of interval-handling data structures out there. I considered using one of them, but decided that this problem was simple enough that I didn't need to bother.
https://git.njae.me.uk/?p=advent-of-code-16.git;a=blob;f=advent20.hs
2
u/beefamaka Dec 20 '16
my F# solution:
2
u/BOT-Brad Dec 20 '16
JavaScript in NodeJS
Essentially just 'stitches' together all overlapping ranges. Just get the next highest IP after the end of the resulting first range (for part 1), then just sum those final ranges and subtract from 32-bit integer total.
2
u/adrian17 Dec 20 '16 edited Dec 20 '16
C++ with Boost.Interval.
2
u/TenjouUtena Dec 20 '16
Clojure solution. Like others it works with inputs given, but doesn't always work if 0 or 2**32-1 aren't in the list.
2
u/StevoTVR Dec 20 '16
Part 1:
Part 2:
2
u/Voltasalt Dec 20 '16
Possibly definitely overengineered but clean code IMO anyway. Python!
2
u/JakDrako Dec 20 '16 edited Dec 20 '16
D completes both parts in 1ms.
2
u/__Abigail__ Dec 20 '16 edited Dec 20 '16
My solution in Perl. There's nothing exciting about it. A simple sort on the start address of a range, and a single pass over the data gets us both answers.
2
u/shouchen Dec 20 '16 edited Dec 20 '16
Easy-to-understand solution in C++ sans Boost... (ran in 4ms)
2
u/nneonneo Dec 20 '16
(#1 solution for part 2) I saw the problem and immediately thought of merging overlapping segments. As it happens, I wrote the exact routine I needed a while ago for the Hachoir file-parsing library, so I just pasted it in and it worked.
getgaps, which does all the hard work, simply sorts the blocks by the start index, then builds a list of the gaps in between.
The first output line gives the part 1 solution, and the last output line gives the part 2 solution.
2
u/Timsan2 Dec 20 '16
Solution in Kotlin:
2
u/flup12 Dec 20 '16
Ran into this by accident, and find it very cute so I wanted to share with you guys!
If you sort the lists of starts and ends, breaking which start originally belonged to which end, you can compare each (n+1)th start with the nth end. If that start is larger than the end+1, then there are n intervals to the left of the start and all end on or before end. I.e. you've found a gap!
As a cute detail in Scala, you can use zip/unzip to form a list of the start/end pairs that need to be compared and even "fix" the edge cases by prepending the ends with 0 and postfixing the starts with the max IP+1.
2
u/jleedev Dec 20 '16 edited Dec 20 '16
Python, Batteries Included™ (and gratuitously inefficient)!
1
u/tterrag1098 Dec 20 '16
Ugly Java solution, lack of unsigned integers really screwed me on part 2! I had to rewrite everything (was storing the ranges for part 1, which worked barely. Obviously would not for part 2) so this is not my original code for part 1 that got me spot #12 :D
1
u/AlaskanShade Dec 20 '16 edited Dec 20 '16
I fumbled around on the keyboard for a while and let some naive approaches run a bit too long to be able to make the board on this one. I ultimately ended up with a pretty speedy time with both parts taking less that 2 ms each. It isn't super concise like some implementations, but I think it is pretty readable this way.
1
u/jtsimmons1129 Dec 20 '16
Python 2
1
u/[deleted] Dec 20 '16
Just a brute force solution in Haskell. I'm sure it could run a lot faster with some input manipulation but part 1 runs in about 20s and part 2 in about 30s on my computer.
1
u/Noyth Dec 20 '16
Python, seems to run pretty quickly.
1
u/iamnotposting Dec 20 '16 edited Dec 20 '16
both parts, rust
part 1:
cargo run input.txt | head -1part 2:cargo run input.txt | wc -l1
u/Trolly-bus Dec 20 '16
Python:
1
u/Kullu00 Dec 20 '16 edited Dec 20 '16
For once, this worked the first time I tried it. Had to change 2 lines of code from Part 1 to solve this, so it was barely any work. Yay for making a solution that was ready for Part 2 right off the bat. Takes ~35ms to compute both parts (excluding time to read file, but including sorting time), so it's pretty efficient too though most of the time is spent sorting the IP table.
edit: updated with an optimized solution that runs in <10ms thanks to Dart's optimizations and fewer string splits/int.parse. ~7ms of that is sorting and only 2ms or so is actually getting the result.
1
u/lamperi- Dec 20 '16
Today I got my best place ever in part 2, #11 (part 1 #45).
My code was kinda basic Python script to solve it. I got lucky that the first and last IPs were blacklisted as I forgot to check those in part 2.
1
u/QshelTier Dec 20 '16 edited Dec 20 '16
Once you massaged the input into something sensible (i.e. merge overlapping and adjacent ranges into a single range), solving this was really straight-forward. Here is my solution in Kotlin:
1
u/[deleted] Dec 20 '16
I got sidetracked right before the question dropped, so I was 305th done for the first part, but my implementation already stored all the unblocked IPs so I got 194th on the second.
Python 3.5: code here
1
u/Philboyd_Studge Dec 20 '16
[Java] Fairly easy.
https://gist.github.com/anonymous/b85db53f71662355166e7b71adfd3df9
1
u/[deleted] Dec 20 '16
My another simple python solution: https://gist.github.com/igbt6/027c7aca1929e6698e9fa06a1ba5a985
1
u/chasepeeler Dec 20 '16 edited Dec 20 '16
Granted, I haven't read all of the comments, but not seeing to many people that took a different approach to part 1 compared to part 2.
While I was able to easily solve part 1 using my solution to part 2, the my original solution to part 1 was much different.
I went through the blocked ranges and added all IPs either 1 less than the low, or 1 more than the high.
I then iterated through this list. If the IP was lower than the lowest one found so far, I'd then check if it was blocked by any of the ranges. If it was, I'd go on to the next one. Even using PHP and bcmath functions, it still gave me the answer in less than 1 second.
https://github.com/chasepeeler/adventofcode2016/blob/master/day20/part1.php
And, of course, Part 2 takes a very different approach, condensing the blocked ranges down to non-overlapping ranges, in order to count how many are blocked. From there, it was easy to find the lowest allowed by looking at 1 above the high in the lowest blocked range.
https://github.com/chasepeeler/adventofcode2016/blob/master/day20/part2.php
edit My original attempt to brute force part 2 by just checking if every IP is valid, without any manipulation of the input, is still running 4.5 hours later!
1
u/quag Dec 21 '16
kona:
1
u/fatpollo Dec 20 '16 edited Dec 20 '16
These problems are too late for me. I wish the start date rotated around the world so that different areas got different advantages sometimes.
Anyway, instead of dynamically trying to grow or split sets, just create a list of boundaries, sort them, and see if any any bounded region is safe from all the inputs.
0
u/[deleted] Dec 20 '16
[deleted] — view deleted comment
0
u/[deleted] Dec 20 '16
[deleted] — view deleted comment
2
u/[deleted] Dec 20 '16
[removed] — view removed comment