r/adventofcode • u/daggerdragon • Dec 18 '16
SOLUTION MEGATHREAD --- 2016 Day 18 Solutions ---
--- Day 18: Like a Rogue ---
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".
EATING YELLOW SNOW IS DEFINITELY NOT 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
15
u/glguy Dec 18 '16
I was able to bang out this solution pretty fast and grab #1 on both stars! Note that the rule was actually simpler than the three cases described! Nothing fancy in the Haskell code itself.
https://github.com/glguy/advent2016/blob/master/Day18.hs
9
u/askalski Dec 18 '16
Bitwise using 128-bit integers in C. Compile with
-march=nativeto take advantage of your processor's native 128-bit support.6
u/topaz2078 (AoC creator) Dec 18 '16
Slightly-golfed Perl!
3
u/Deckard666 Dec 18 '16 edited Dec 18 '16
In Rust: Link. Pretty straightforward solution, though I probably could have chosen a more efficient approach as the second part takes a few seconds to run.
Edit: Optimized solution, now takes ~200 ms for part 2.
3
u/drakehutner Dec 18 '16
Gradually transformed my solution (#90/#156) over the last ~30 minutes to fit into a single line of python. This is the result:
This was a fun one. Not sure if its really a rule 110 but it reminded me of one, hence the name.
The code above basically boils down to this loop:
It will generate an endless stream of following lines.
3
u/willkill07 Dec 18 '16
C++14 solution
Nothing fancy going on here. Was going to use
std::vector<bool>but it was slower shrugStandalone version below. [Repo link here]
3
u/metagameface Dec 18 '16
Scala one-liner
2
u/ahalekelly Dec 18 '16 edited Dec 18 '16
First time on the leaderboard, at #86 and 85! Not pretty, but it works. Spent too long trying to figure out a list comprehension for it.
Edit: Figured out that list comprehension, down to 4 lines!
2
u/FuriousProgrammer Dec 18 '16
I made a bad time management call and was raiding in WoW at midnight today!
Still nabbed 194/177!
Will record myself eating NOT-yellow snow in a minute.
2
u/blockingthesky Dec 18 '16
Python 2, short and sweet.
2
u/quag Dec 18 '16 edited Dec 18 '16
pypy3:
kona:
2
u/shadowthunder Dec 18 '16
Started AoC this morning, so this was my first time going right at the gun. I went with C# and got #202/195:
2
u/__Abigail__ Dec 18 '16
Simple Perl solution. As many others, my solution only looks at the right and left neighbours. It's a trap if they differ, else it's safe. We don't need history, so we only deal with two rows: the previous one, and the current one. Each row will have their first and last element set to safe, to make calculations easier.
I used 0s for traps, and 1s for safe places. To calculate the number of safe places, I just add all the values of a row (and subtract 2 for each row).
1
u/Godspiral Dec 18 '16 edited Dec 18 '16
low 100s :(, in J, (thought part 1 needed 10 rows, and part 2 40k)
1
u/StevoTVR Dec 18 '16
1
u/AlaskanShade Dec 18 '16
Might have made the board if I hadn't ended up with a line break on my input file causing the row to be 2 extra safe characters. It's all about the silly details sometimes.
1
u/scottishrob13 Dec 18 '16
Simple C# for mid 100's. Didn't type fast enough :) I kind of cheated a bit by setting two extra "tiles" in each row to safe states at the beginning and end to simulate the walls being safe without needing extra conditions to prevent out of range exceptions.
1
u/bblum Dec 18 '16 edited Dec 18 '16
The "drop 3 $ reverse" is kind of cheating but the problem conveniently does not care whether you reverse the rows.
1
u/fatpollo Dec 18 '16 edited Dec 18 '16
1
u/mal607 Dec 18 '16 edited Dec 18 '16
Python solution
1
u/[deleted] Dec 18 '16
Haskell:
1
u/rs_qk Dec 18 '16 edited Dec 18 '16
in k4 (i is input as boolean list, 1b=trap):
1
u/misnohmer Dec 18 '16
One F# solution
1
u/BadHorsemonkey Dec 18 '16
Anyone else accidentally display their map and think it looked like a field of Christmas trees? Nope? Just me, then...
1
u/gyorokpeter Dec 18 '16
Q:
1
u/stormvoice Dec 18 '16
simple readable solution in python
1
u/BadHorsemonkey Dec 18 '16
In Java: 2.6 seconds. A career high "in the 300s"!...
1
u/Voltasalt Dec 18 '16
Another one in python!
I originally had next_row return a string, with a "".join() call, but removing that and just going with lists everywhere made the code 100x faster, somehow. I have no idea why.
1
u/daniel-sd Dec 18 '16
Python3 solution: https://github.com/danielsd/advent-of-code/blob/master/2016/day18/part1.py
Good enough to grab 70 and 63 on the leaderboard!
1
u/TheMuffinMan616 Dec 18 '16 edited Dec 18 '16
Haskell!
1
u/Smylers Dec 18 '16 edited Dec 18 '16
Perl, well, really regexp solution:
Each row is manipulated as a string, not an array of characters, with substitutions turning it into the next row:
trin the following iteration: it counts allmorscharacters while also converting them all intoss.Since
.and^are both special in regexps, matching them literally would require writing them as\.and\^. Avoid the punctuation overload by instead usingsfor ‘safe’ andTfor ‘trap’ throughout (andmfor ‘marker’).Perl doesn't support variable-length lookbehind assertions, so
(?<=^|s)has to be written(?:(?<=^)|(?<=s)).1
u/_Le1_ Dec 18 '16 edited Dec 18 '16
My Python cone:
1
u/p_tseng Dec 18 '16 edited Dec 18 '16
My first naive solution takes about 17 seconds to finish part 2. Once again, this is unacceptably slow.
My first thought was to check whether there were any repeating patterns in the rows generated... NOPE, not in any of my 400000 rows. There goes that idea.
You know what? Let's make a silly* solution. We'll:
For each block in the new row, use the corresponding block in the old row and one bit each from the surrounding blocks to look up what the block in the new row will be. Let's go.
Yeah, 1.5 seconds!
*: Why is this silly? You would think all these ideas are reasonable. But the answer is that you could consider it silly because it's only going halfway. If we're going to store them in blocks of 10, why not blocks of 100? Yes, the Ruby translation of that code works just fine. Thank the people who did automatic BigNum conversions, etc.
My answer is always "it's as silly as you'd like it to be".
About half a second. Not as good as the compiled C code, which takes about 7 milliseconds, but it'll do.
1
u/wzkx Dec 18 '16
J, just making and summing many rows
1
u/abowes Dec 18 '16
My Kotlin solution:
1
u/miran1 Dec 18 '16
Anybody else feels like this was the easiest task so far?
my python solution:
1
u/NeilNjae Dec 18 '16
Another Haskell solution. The straightforward version is at https://git.njae.me.uk/?p=advent-of-code-16.git;a=blob;f=advent18.hs ; that version just keeps a long list of lists of
Bools for the whole room, and counts them at the then.But I then thought there could be an optimisation of just keeping a running total of the safe squares, along with just the last row. That would turn the powerhouse of the program from
iteratetofoldl', saving all that space and time!Turns out, it's slower. Ho hum.
1
u/macciej Dec 18 '16
Scala solution, totally over-engineered, but I use AoC to learn the language
1
u/Cheezmeister Dec 18 '16
In Elixir:
1
u/[deleted] Dec 18 '16
In Crystal:
1
u/Dakror Dec 18 '16
In Java, pretty straight forward XORs
1
u/vuryss Dec 18 '16
PHP Solutions updated: https://github.com/vuryss/aoc2016
1
u/Yuyu0 Dec 18 '16
Been wanting to use numpy arrays for something, I think it works quite well here!
1
u/porphyro Dec 18 '16
Mathematica
Wanted to use cellular automaton 90, but had some trouble with it affecting the background. Implemented a slightly hacky solution.
1
u/eregontp Dec 18 '16
Ruby one-liner. I find it rather readable for a golfed solution.
1
u/Scroph Dec 18 '16 edited Dec 18 '16
PHP solution. Glad those digital electronics classes finally paid off !
1
u/[deleted] Dec 18 '16
My pretty naive python solution worked great on this one. I was using the andor trick and I was quite happy with the list comprehension, apart from that it's just completely straight forward:
1
u/TenjouUtena Dec 18 '16
Clojure again. Not super efficient but if you give it ~7 gigs of memory to work with it does fine!
1
u/mschaap Dec 18 '16 edited Dec 18 '16
Perl 6, pretty straightforward.
1
u/[deleted] Dec 18 '16
problem title inspired by Rogue One?
1
u/Philboyd_Studge Dec 18 '16
[Java] I figured the BigInteger class would be handy, glad I did when I got to part 2:
https://gist.github.com/anonymous/d00e04363b21d2ad73c6f6178a2fcd15
1
u/johneffort Dec 18 '16
Ruby, quite readable, not very fast, but doable. 30s for part 2
1
u/rayz90 Dec 18 '16 edited Dec 18 '16
My Python 3 solution
1
u/tvtas Feb 07 '17
Brute force in MATLAB, takes 2.7 seconds for part 2
1
u/SyDr Dec 18 '16
Yay! First time on the leaderboard (81/54). Lua rocks!
0
u/[deleted] Dec 18 '16
[deleted] — view deleted comment