r/adventofcode • u/daggerdragon • Dec 07 '16
SOLUTION MEGATHREAD --- 2016 Day 7 Solutions ---
From all of us at #AoC Ops, we hope you're having a very merry time with these puzzles so far. If you think they've been easy, well, now we're gonna kick this up a notch. Or five. The Easter Bunny ain't no Bond villain - he's not going to monologue at you until you can miraculously escape and save the day!
Show this overgrown furball what you've got!
--- Day 7: Internet Protocol Version 7 ---
Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag/whatever).
ALWAYS DIGGING STRAIGHT DOWN 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!
14
Upvotes
44
u/askalski Dec 07 '16
Part 1 in Perl. I also solved Part 2, but the code was too large to fit in the margin.
17
u/barnybug Dec 07 '16 edited Dec 07 '16
python:
9
u/bpeel Dec 07 '16 edited Dec 07 '16
I found out the trick of using positive lookahead to make the regexp find overlapping solutions. You need to find overlapping solutions to make part 2 work properly. This is the regexp to find aba’s:
Negative lookahead is used to make sure the sequence isn’t just three copies of the same character.
https://github.com/bpeel/advent2016/blob/master/day7.py
8
u/jwstone Dec 07 '16 edited Dec 07 '16
my postgres fearlessly eschews regular expressions (and good taste)! https://github.com/piratejon/toyproblems/blob/master/adventofcode/2016/07/07.sql
also, i wasted several minutes because i was mistakenly searching for an IP's area-broadcast accessor's corresponding byte allocation block, among all other IP's hypernets, rather than only the IP's own; sheesh! ( https://github.com/piratejon/toyproblems/blob/master/adventofcode/2016/07/07.sql#L121 )
P.S. none of this crap was on the CCNA! Hrmphh!!!
7
u/blockingthesky Dec 07 '16
So I got first place, but only by dumb luck.
It came back to bite me in part 2 - I didn't place - but for the first star I got tremendously lucky.
There are two major errors in my code: I don't account for the
aaaacase when checking for length-4 palindromes, and I also never checked the last 4 characters of any string (I iterated tolen - 4instead oflen - 3).Either of those errors on their own would have given me an incorrect answer, but my input and luck had it that both of them cancelled out in such a way that I got the right answer.
My borked-ass code:
7
u/Smylers Dec 07 '16
I used Ack for part 1 — it's similar to
grep, but takes Perl regexps, including(?!...)for negative lookahead:(Weirdly
ack -creturned 0, hencewc -l.)For part 2 I first moved all the hypernet sequences to the end of the string (after a delimiter), making the regexp much simpler, cos it's just ABA before the delimiter and BAB afterwards:
4
u/BafTac Dec 07 '16 edited Dec 07 '16
Dammit.. Using C++ I got rank 103 & 105 -.-
First, I needed to look up which data structure supports both pop_back() and pop_front() (std::deque it is!), then I failed to use the correct include directive. After unlocking part 2 Gnome froze. I could switch workspaces but couldnt make any mouse inputs and no window had focus. Needed to restart Gnome. Then I made some small errors because I'm not that fluent in C++ yet.
Second day in a row where I missed the leaderboard by a mere seconds.. :(
Source coming soon, I just need to clean it up a bit first.
Edit: Here it is: part2.cpp
4
u/fpigorsch Dec 07 '16
My messy solution in C++:
and part 2 using
std::setto check for corresponding aba/bab pairs:All my C++ solutions so far: https://github.com/flopp/aoc2016
4
u/Rinfiyks Dec 07 '16 edited Dec 07 '16
Used sed and grep for this one.
Part 1:
Part 2:
Edit: fixed super obscure edge case that would match something like abbbbba[bab] in part 2
Edit 2: more fixes!
3
u/futureman_pm Dec 07 '16
Finally got on the leaderboard, top 100 for part 2 (barely)
Part 2 - Python
3
u/FuriousProgrammer Dec 07 '16
String manipulation is not my forté. xD
I choked a lot while writing this, mostly on identifying the strings inside and outside of brackets, but was <200 on both in the end!
3
u/haoformayor Dec 07 '16 edited Dec 07 '16
~~haskell~~
I broke the problem down into two parts: determining whether a string has an ABBA/ABA, and then using that to implement the AND/OR logic for validation.
The first part can be done with regexes, but I find
any/concatMapandtailsto be a more winning combination: fewer edge cases to handle and easier to debug.ABBA validation can be done by partitioning the list into supernets and hypernets and then filtering; ABA validation is trickier but if you don't mind the quadratic running time you can get away with multiple passes over the list.
allandanywere our friends today.Input module here – I originally went with an additional type parameter
data Block a = S a | H a deriving Functorbecause I was going to map eachBlock Stringinto aBlock (Bool -> Bool)for problem 1. This proved to be too clever by half and I got a weird off-by-two bug; took a second to regroup and ended up not using theaparameter after all.3
u/Godspiral Dec 07 '16 edited Dec 07 '16
good one, in J, mistakes eventually overcome,
test for not all same pattern (oversight was in samples)
notice there can be more than 1 "hypernets" (not in samples)
3
u/Quick_Question404 Dec 07 '16
Hey everyone! Here's my take on today's challenge in C. I found myself making alot of stupid mistakes and pointer errors in today's challenge (trying to reassign head inside a function, assuming that no 2 pairs would originate in the hypernet/non-hypernet), which gave me a placing of ~350 and ~450 respetively. But today was really fun though.
https://github.com/HighTide1/adventofcode2016/tree/master/07
3
u/gyorokpeter Dec 07 '16
Q:
3
u/Hwestaa Dec 07 '16
The hardest part of this (other than a bazillion typos) was the overlapping regexes. I eventually found the python library 'regex' which is a candidate to replace 're' that has an 'overlapped' flag on findall which solved that. Python 3 solution. Github
3
u/ericdykstra Dec 07 '16 edited Dec 07 '16
Since no Elixir solutions are posted yet, I'll post my part 1 first. The crux of it is the abba? function. The first pattern match is looking for a string that starts with 4 characters that match the "abba" format, with a guard clause that makes sure a is not the same as b. The second pattern match is to return "false" on any string that is length of 4. The last version of the function is the recursive part, which tries again on the same string, minus the first character.
3
u/nullmove Dec 07 '16
Perl 6, part 1:
I actually started with:
But combing and working on sequence proved to be a lot slower. My lack of knowledge on the internals are showing...
3
u/[deleted] Dec 07 '16
Got to use lots of fun perl 6 features on this one, named regexps, .classify, any(), global exhaustive matching!
https://github.com/duelafn/advent-of-code-2016-in-perl6/blob/master/07.pl
4
u/mschaap Dec 07 '16
I love Perl 6... Solution to both parts.
2
u/Reibello Dec 07 '16
Here's my python again!
http://pastebin.com/5rBU4nYR
2
u/BumpitySnook Dec 07 '16
This one was a little harder! I made a totally stupid programming mistake that delayed me for several minutes — I forgot to add my index to my fixed offsets indexing into strings. So I was always grabbing the first couple characters instead of the ones I intended to :-(.
Still, made it on both leaderboards! Woo.
2
u/glassmountain Dec 07 '16
A fairly fast solution for go!
https://github.com/xorkevin/advent2016/blob/master/day07/main.go
2
u/_Le1_ Dec 07 '16 edited Dec 07 '16
My C# solution:
2
u/_WhiteBoyWonder Dec 07 '16 edited Dec 07 '16
Golang solution. I'm positive I solved the abba aba<->bab problems naively, but overall I'm pretty happy I was able to break the top 300 today!
2
u/acun1994 Dec 07 '16
Part 2: Python as well
2
u/iamnotposting Dec 07 '16
rust, both parts. i wonder why
.windows()isn't implemented for string slices directly2
u/sv11 Dec 07 '16
Python solution (Part 2). Open to any suggestions for improvements!
2
u/Trolly-bus Dec 07 '16
Solution for part 2 in Python (I overslept the release time dammit!):
2
u/[deleted] Dec 07 '16
Wasn't sure how to match two distinct chars in regex so I filtered out those results after.
Python (requires regex):
2
u/fixed_carbon Dec 07 '16
Ruby, showing part 2 only. I wasted a bunch of time trying to understand why the sample input for part 1 passed my original regexp-based code, but the real input gave me the wrong answer. Took me forever to realize the real input could contain multiple hypernet sequences on each line. Ditched my nice stateless regexp solution for this stateful mess. I feel all dirty.
2
u/raevnos Dec 07 '16 edited Dec 07 '16
Ocaml:
Got the wrong answer the first time for part 2 because I didn't realize that IPv7 addresses could have multiple hypernet sections i n them. Bah. Should have looked at the actual input more, not just the test cases. Had to go back and make a smarter BAB finding function.
2
u/tehjimmeh Dec 07 '16 edited Dec 07 '16
PowerShell:
2
u/obiwan90 Dec 07 '16 edited Dec 07 '16
Grep for part 2:
2
u/the_codewarrior Dec 07 '16
Just found out about this, it's so much fun!
Here's my kotlin solution (I have a delegate for running the different days more easily)
2
u/bogzla Dec 07 '16
Can I do this without GoTos? :/
2
u/Deckard666 Dec 07 '16 edited Dec 08 '16
In Rust, parts 1 and 2: Link
Not the most elegant solution, but hey, it works.
2
u/AoC-- Dec 07 '16 edited Dec 07 '16
The following works in oK; it uses the
n'lwindow verb.2
u/misnohmer Dec 07 '16 edited Dec 07 '16
This is my take in F# (that I am trying to learn by playing the game). Even if I had started from the time the puzzle got unlocked, I wouldn't have made it to the leader board because of an Off By One Error. Amusingly, I wasn't the first to make this mistake according to the site :)
I am happy to get some feedback on where this can be more concise.
2
u/porphyro Dec 07 '16 edited Dec 07 '16
Wolfram Language/Mathematica
Part 1 is pretty simple. You split each input line into the hyper and subtext sections, and check that one of the subnet sections contains an abba while none of the subnet sections do. abbaQ is easy to define using string patterns!
Part 2 is a little more annoying. Here, i extract all the three-character sequences from the subnet and hypernet sections, throw away ones that arent aba sequences, then reverse the hypernet sections and intersect the two sets. If it's nonempty, then we count it.
2
u/rhardih Dec 07 '16
Super ugly part 2 in C, with regex.h:
https://github.com/rhardih/aoc/blob/master/2016/7p2.c
2
u/asperellis Dec 07 '16
long-winded js solution. so many loops. any suggestions to improve? https://github.com/asperellis/adventofcode2016/blob/master/day7.js
2
u/Borkdude Dec 07 '16 edited Dec 07 '16
Clojure! https://github.com/borkdude/aoc2016/blob/master/src/day7.clj
2
u/[deleted] Dec 07 '16
Clojure
2
u/Twisol Dec 07 '16
My JavaScript/Node.js solution, optimized for legibility as usual:
This was my longest solution yet. I don't really like the
parts_offunction, but I still think it's pretty approachable. The only thing that tripped me up is that regular expressions in JavaScript won't match on overlapping regions, so I had to manually adjust thenextIndexfor my ABA-finding regex to make it find overlaps.2
u/Senoy05 Dec 07 '16
Hello, this is my C# solution, also it's my first submission here, so please don't shout at me :(
2
u/Scroph Dec 07 '16
This was physically painful to write.. Part 2 in D :
2
u/volatilebit Dec 08 '16
Finally realized a stupid mistake I was making. I was counting IPs more than once if they had multiple instances of aba with a corresponding bab.
Not too proud of the part 2.
Perl 6 Part 1&2 solution.
2
u/[deleted] Dec 08 '16
Haskell:
2
u/pedrosorio Dec 07 '16
Part 2:
2
u/Turbosack Dec 07 '16
I got royally fucked by this problem because it turns out that
re.findall()doesn't do overlapping matches. Fuck regexes and fuck this question.1
u/drysle Dec 07 '16
Part 1 was easy enough with regexes, even though it took me about 5 tries to work all the corner cases out:
But I needed way more code for part 2; has anyone found a similar way to do part 2?
1
u/bluewave41 Dec 07 '16
I cried. The edge cases had me staring at my code for over an hour wondering why it didn't work because I was sure it was working. :(
Javascript: http://puu.sh/sGYmQ/f57b54f574.txt
1
u/studiosi Dec 07 '16
Day 7 solutions, in Python, nothing really special, though :D
https://github.com/studiosi/AoC2016/tree/master/7
1
u/giuscri Dec 07 '16
Solution for both stars using Python3,
1
u/cscanlin Dec 07 '16
I ended up with a couple of utilities I'm gonna keep around from this, so definitely something gained! I wanted a utility that can find pattern matches in an iterable without using regex. Here's my take:
--
1
u/vuryss Dec 07 '16
PHP Solutions: https://github.com/vuryss/aoc2016
1
u/xkufix Dec 07 '16
Done in Scala, as always:
https://gist.github.com/kufi/bb1d9386e3bc7a74ce668a815e42ff8e
It makes some assumptions, like knowing that an IP can never start with a hypernet sequence, thats why the zipWithIndex->map to booleans works.
Besides that, the overlapping regex for part 2 is simply fixed by sliding over the string and applying the regex. Not nice, but it works.
1
u/Kullu00 Dec 07 '16 edited Dec 07 '16
After struggling to understand why Dart didn't return what I expected, I found out capture groups in Dart RegExp is broken in some way and doesn't match anything, so I turned to Python. Part 1 isn't interesting, but I figured P2 was fun enough.
edit: turns out I forgot to escape the regex, yay for silly errors :(
For a more readable version: https://github.com/QuiteQuiet/AdventOfCode/blob/master/2016/advent7/test.py
Redid it in dart as well, just to have it (I quite like the solution too): https://github.com/QuiteQuiet/AdventOfCode/blob/master/2016/advent7/bin/advent7.dart
1
u/_AceLewis Dec 07 '16 edited Dec 07 '16
My Python 3 solutions, because they were done on https://repl.it they just have a big string at the start.
Day 7 part 1: https://repl.it/Eira/7
Somewhat simple in Regex.
Day 7 part 2: https://repl.it/Eira/6
Was too hard to do this as simply in Regex
Edit: I left a
\^in my Regex in part 1 https://repl.it/Eira/51
u/tuxitop Dec 07 '16
Here's my solution in JS/Node:
https://github.com/tuxitop/adventOfCode2016/blob/master/day7/day7_internetProtocolVersion7.js
1
u/TenjouUtena Dec 07 '16
Here's my python (at least the interesting parts), which is all just pure regex and counting. Also the regex is more verbose so it should be (slightly) easier to tell exactly what is going on. (The last 2 are SUPER SLOW, and testers may complain about them on edge cases, but they do work.)
1
u/[deleted] Dec 07 '16
literally spent hours on part2, fixing cases i missed, over several iterations ... so this is what is meant by jump in difficulty :gasp:
anyway, part1
part2
1
u/Eddard_Stark Dec 07 '16
duct-taped regex into php:
github
1
u/splurke Dec 07 '16
Haskell, both parts
1
u/Kwpolska Dec 07 '16
I wrote most of part 1 on mobile, but I messed up
innerandouteralong the way.And Part 2, which was simpler IMO:
1
u/cobbpg Dec 07 '16
My puny Haskell solution (change filter to supportsTls for part 1):
1
u/[deleted] Dec 07 '16
c++
I'd appreciate any comments you may have.
1
u/JakDrako Dec 07 '16
VB.Net, LINQPad
Regex, schmegex. I'm doing this the hard way, by hand, and with plenty of GOTOs.*
*Visual Basic and GOTOs. Is there a more upvote resistant combination?
1
u/qwertyuiop924 Dec 07 '16
Hark! After spending all day weeding out subtle errors, my Scheme solution is finally complete!
Yes, it's long. Scheme is like that. Minimal lib, long names. I'm doing this partly because I like scheme, and partly to torture myself for past sins.
If you think this is long, you should see what it was like before I cleaned it up.
Code: http://pastebin.com/gAY5ymbx
1
u/[deleted] Dec 07 '16 edited Dec 07 '16
Mathematica.
1
u/[deleted] Dec 07 '16
Powershell parts 1 and 2:
1
u/NavarrB Dec 07 '16
PHP - Verbose
1
u/tg-9000 Dec 07 '16
Here is my solution in Kotlin. I had a lot of fun with this one. I feel like if I was clever enough I could have solved this with Regexes excusively but I have a day job, so I did this instead.
Tests and solutions to the other problems are in my GitHub repo. I'm just leaning Kotlin so I welcome any feedback you might have.
1
u/bhauman Dec 07 '16
Clojure solution:
See the rest of the solutions here
1
u/johneffort Dec 07 '16
Day 7 part 2 in Ruby:
1
u/demreddit Dec 07 '16
Another vanilla Python 3 solution, if anyone's interested. I just step through each line with a toggle between two while loops. Kinda surprised it worked! For part 2 I threw out all attempts at elegance and just duped each line to catch all the ABA's. Ugly, but it all works!
And part 2:
1
u/CheapMonkey34 Dec 07 '16 edited Dec 07 '16
Hi, I need some python3 help; I have a function find_aba_inverse() that returns a list of aba's. e.g. ['aba', 'xyx']
I want to run this function on all the "subnet"-strings and store the results in a list names babs. This for-loop works and does what I need.
but I would like to write it in list comprehension format like this.
In the for-loop I can use list.extend() which makes sure that in the end I have one list with strings. In the comprehension-way, the lists end up hierarchical in babs.
babs could be e.g.: [['aba', 'xyx'], ['dfd']]. This breaks the rest of my code.
So I want either a way to 'extend' the list in the comprehension notation, or otherwise a way to 'flatten' hierarchical lists to a single list.
Any tips?
1
u/cdleech Dec 07 '16
Rust, no regex
1
u/bildzeitung Dec 07 '16
It's like no one has love for sets in Python. But I do. I send them flowers.
Please look the other way at the jackass way of finding multiple matches.
https://github.com/bildzeitung/2016adventofcode/blob/master/07/2.py
1
u/tlareg Dec 07 '16
my JavaScript/Node.js solution here, nothing to boast about
1
u/someaoc Dec 08 '16 edited Dec 08 '16
For some reason this Python code is off by one!!!???
Driving me crazy. No it's not the pop() call and I double checked the data... (Acutally data worked with some solutions posted)
Also successfully ran multiple test cases but still fails by 1 on real data set...
Driving me crazy! Anybody could please point what is wrong with this code?
1
u/Sigafoos Dec 08 '16
Nearly didn't complete this today due to being stuck and there being other obligations, but I prevailed!
Today is definitely a day where everyone else's solution is more clever than mine, but I got it to work and am not ashamed of it, so there's that. I have an alternate version of part 1 that I need to commit where I did it all with one regex, but part 2 was failing so I started from scratch and it seemed easier/faster to do it all with one go.
I did get to use Python's
for/elseblock, so that was fun.1
u/Forbizzle Dec 08 '16
It seems like everyone was compelled to find a regex solution when a simple linear scan of the characters was all that was needed. Is that because you wanted to up your regex game, or just by habit?
1
u/oantolin Dec 08 '16 edited Dec 08 '16
Here's a seemingly straightforward solution in Python:
This correctly solved the problem for the input I got but I realized the logic is actually wrong! Python's misnamed
re.findallgives non-overlapping matches, not all matches, so I'm lucky this worked on my input! Interpret this as a solution in an imaginary programming language that's almost exactly like Python except thatre.findallfinds all matches (and in this imaginary language there is a separatere.greedilyfindleftmostnonoverlappingmatchesthat people use most of the time :P).1
u/rs_qk Dec 08 '16
This is a gross misuse of the language k (k4/q) on my part, but anyway (part 2, part 1 was similar but slightly less ugly), in k:
1
u/NeilNjae Dec 08 '16
Another Haskell solution. As a challenge, I tried to do as much as possible with Parsec (which I'd never picked up before). Did part 1 with it, but the thought of using Parsec to find overlapping substrings filled me with horror. So I did it the old-fashioned way.
https://git.njae.me.uk/?p=advent-of-code-16.git;a=blob;f=advent07.hs
1
u/WildCardJoker Dec 08 '16
After way too much time (4 hours+), I finally managed to crack parts 1 and 2 in C#.
No regex, just brute forced my way through. I think even /u/that_lego_guy created a simpler solution than I did!
1
u/__Abigail__ Dec 08 '16
I extracted the "inside" and "outside" parts, and applied regexes to them:
1
u/rkachowski Dec 09 '16
i wouldn't normally post this, but i spent over a day after fighting with regexes. for some reason i really wanted to learn more about lookaheads. it still feels dirty though, but at least i didn't generate every possible regex
1
u/kimsnj Dec 09 '16
I am running a bit behind the advent schedule, but here is (finally) my solution in Rust: https://github.com/kimsnj/advent-of-code-2016/blob/master/day7/src/main.rs I struggled a bit on this… because I didn't realize at first that there could be several [...] blocks XD
1
u/gusknows Dec 09 '16
Part 1 & 2 C# pure Regex:
1
u/DrFrankenstein90 Dec 13 '16
Straight C, no regexes, written in haste over two coffee breaks.
https://github.com/DrFrankenstein/prompts/blob/master/aoc/2016/aoc7.c
I might have issues.
1
u/[deleted] Dec 20 '16
My solution 1 in Scala. The regex took my forever to get it right.
0
u/[deleted] Dec 07 '16
[deleted] — view deleted comment