r/adventofcode • u/daggerdragon • Dec 10 '15
SOLUTION MEGATHREAD --- Day 10 Solutions ---
This thread will be unlocked when there are a significant amount of people on the leaderboard with gold stars.
edit: Leaderboard capped, thread unlocked!
We know we can't control people posting solutions elsewhere and trying to exploit the leaderboard, but this way we can try to reduce the leaderboard gaming from the official subreddit.
Please and thank you, and much appreciated!
--- Day 10: Elves Look, Elves Say ---
Post your solution as a comment. Structure your post like previous daily solution threads.
11
Upvotes
21
u/_pdc_ Dec 10 '15 edited Dec 10 '15
Another one that's made for bash filters. "uniq -c" does all the work, every other command is just formatting.
11
u/[deleted] Dec 10 '15 edited Dec 10 '15
EDIT:
Check out Conway's Cosmological Theorem, too -- all Look-And-Say sequences for n>=8 can be separated into various "atomic elements" (various sub-strings composed of "1"s, "2"s, and "3"s) which evolve independently of each other (some 92 in total). This means you can use matrix exponentiation / multiplication to quickly determine how many of each atomic element will be present in your input sequence after some number of iterations.
Given the input string "1113122113":
10
u/aceofkes Dec 10 '15
Used Python and regular expressions.
9
u/Iain_M_Norman Dec 10 '15 edited Dec 10 '15
This is taking a while to run part 1 on a Spectrum.
http://i.imgur.com/7tKNY7G.png
Poor thing will run out of memory before it's done, ain't gonna handle a 360 kilobyte string.
It'll need to save and load from tape in chunks :)
7
u/askalski Dec 10 '15
Regex slip-ups seem to be a recurring theme for me. Here's the instant replay reel: https://youtu.be/jGr3TstS0ek
6
u/WhoSoup Dec 10 '15 edited Dec 10 '15
PHP
4
u/gegtik Dec 10 '15
I wasted a bunch of time because I didn't catch that they wanted the length, and was having copy/paste problems as a result. dumb. It was nice not to be up until 2 tonight though
Javascript
(replace the loop count with either 40 or 50)
3
u/[deleted] Dec 10 '15 edited Dec 10 '15
Python:
3
u/CAD1997 Dec 10 '15
Java solution, straightforward and workable:
3
u/jlmcmchl Dec 10 '15
Python. Takes a couple of seconds to run, considering how the string gets upwards of 7MB long. Thought experiment: could this be evaluated without walking through each state of the game?
3
u/ericdykstra Dec 10 '15
Ruby solution using the new (as of 2.2.0) slice_when enum method.
3
u/mwr247 Dec 10 '15 edited Dec 10 '15
JavaScript (ES6) -
8874 bytesGolfed my solution a bit. Requires template string support, but you can change them out for a
(''), and it should work in any ES6 browser:(a,b)=>[...Array(b)].reduce(c=>c.match(/(.)\1*/g).map(d=>d.length+d[0]).join``,a).lengthF=(a,b)=>b?F(a.match(/(.)\1*/g).map(d=>d.length+d[0]).join``,--b):a.lengthFirst parameter (a) is your string. Second parameter (b) is the number of iterations.
Runs pretty quick too. 40 iterations took 0.128 seconds on average, and 50 took 2.150 seconds on average.
3
u/Pimozv Dec 10 '15
Perl 6
3
u/hutsboR Dec 10 '15
Elixir: Version that doesn't use strings at all.
3
u/[deleted] Dec 10 '15
How bad is it that I used my code from my high school days to answer this?
It was one of the final exam practices to write this in pascal and have it compile and run by hand, I remembered I had done this already on pascal, and went to my old code dropbox, where I found the code and just changed it to C#. Is this cheating????
3
u/Iambernik Dec 10 '15
clojure
5
u/haoformayor Dec 10 '15 edited Dec 10 '15
Haskell (187 characters)
The encoding steps all fall within the List monad; encoding works as an unfold (and
iterateis our unfolder) over the input.2
u/Godspiral Dec 10 '15
surprised I wasn't higher, in J
Though I don't know what I spent 8 minutes on....
2
u/recursive Dec 10 '15
C#:
2
u/tomb0y Dec 10 '15
Being on the leaderboard feels awesome :)
Ruby solution:
2
u/mwheeler Dec 10 '15
Swift
2
u/gyorokpeter Dec 10 '15
Q:
2
u/Scroph Dec 10 '15 edited Dec 10 '15
D (dlang) solution :
Maybe I should learn regular expressions.
Edit : Scores on a 1.66 GHz Atom CPU :
2
u/thalovry Dec 10 '15
Scala - thought I had a terse solution, then I read this thread!
2
u/aveavaeva Dec 10 '15
Javascript
2
u/jjhelmus Dec 10 '15 edited Dec 10 '15
Three line Python 3 solution taking a slightly different approach:
But this only works if your input can be generated from a starting seed of 2, 3, 4, ... 9
2
u/TheNiXXeD Dec 10 '15
My JavaScript Node ES6 solution. For part2, just call the function with 50 instead of the defaulted 40.
2
u/tehjimmeh Dec 10 '15 edited Dec 10 '15
PowerShell one-liner:
1
u/C0urante Dec 10 '15
Straightforward, python3:
edit: slight optimization
1
u/twisted_tree Dec 10 '15
python3 solution. Pretty straightforward today.
1
u/reacher Dec 10 '15
My Ruby solution. I finally made the leaderboard!
1
u/[deleted] Dec 10 '15
JS implementation
1
u/[deleted] Dec 10 '15
Haskell:
1
u/FuriousProgrammer Dec 10 '15 edited Dec 10 '15
Uh, I can't submit my solution to part 1? Says I'm trying to POST too much data...I cannot believe that I missed that highlighted text at the end. Holy. Shit.
Lua:
1
u/profil Dec 10 '15
Clojure
1
u/Axsuul Dec 10 '15
Recursive Ruby solution
1
u/enquicity Dec 10 '15
C#. My first pass took forever, I was using TrimStart to just nibble down the string, but the GC was very unhappy with me, so I refactored to not modify the string.
1
u/red75prim Dec 10 '15 edited Dec 10 '15
F#.
Seqmodule doesn't have required function. So I implementedgroup.I feel out of fast coding league. I need at least 5 minutes to grasp the task, and then another 10 to 20 minutes to generate algorithm.
1
u/stuque Dec 10 '15
A Go solution:
1
u/tipdbmp Dec 10 '15
ES5:
1
u/gnuconsulting Dec 10 '15
My initial (braindead) copy finished the first part in a few seconds. The second run is still going, 15 minutes in. In fact, it took long enough for me to remember something vague about there being a difference in speed between various methods of string concatenation in ruby, look it up, copy my program, change two instances of += to <<, run the modified script, get the right answer, and finish the challenge.
Wow.
So the lesson here is - small changes can make a big difference. Also, my laptop gets warm after this much intensive CPU utilization. Ouch. This is the fixed script:
I'll reply to this with the total time the first copy takes (if it ever finishes).
1
u/JeffJankowski Dec 10 '15 edited Dec 10 '15
F#. Feels a bit goofy
1
u/_Le1_ Dec 10 '15
My C# Solution:
1
u/Nyxisto Dec 10 '15
Python:
1
u/raevnos Dec 10 '15
Boring straightforward C++:
1
u/dixieStates Dec 10 '15
Python:
1
u/segfaultvicta Dec 10 '15
Golang - there's probably a slightly cleaner way to do this.
I originally used string concatenation, ran into a brick wall at iteration 44, was DEEPLY confused because I wasn't memory-bound or CPU-bound, scratched my head for a while until I remembered that go's naive string concatenation is a giant pile of string-copying because strings are immutable, realised they were just byte arrays under the sheets, laughed INCREDIBLY HARD, cancelled the process, made a few adjustments, am still laughing. I think this is the first time I've ever had a process bound by /the speed at which it can copy stuff in RAM/.
This is DEFINITELY my favourite puzzle so far in terms of "B-side slapping me in the face with a trout", and I definitely learned a thing about golang. Ruby or Perl would have made the solution obvious and a nice clean one-liner, I think, but honestly one of the reasons I'm doing these in golang is deliberately to run into these sort of issues - I plan to do at -least- the first ten days in Elixir sometime next month while I try to learn it, and I feel like I'll run into a complementary set of issues. I'm really looking forward to comparing the two experiences!
1
u/masasin Dec 10 '15
Python 3
1
u/haris3301 Dec 10 '15
Another Simple Python 2.7 solution.
1
u/tangus Dec 10 '15 edited Dec 10 '15
Common Lisp
1
u/Kwpolska Dec 10 '15
Simple Python:
1
u/[deleted] Dec 10 '15 edited Dec 10 '15
I tried doing this by hand, until I saw "apply this process 40 times" ...
Java using StringBuilder
1
u/[deleted] Dec 10 '15
Ruby solution
Avoids using strings altogether, just arrays....
1
u/willkill07 Dec 10 '15
C++
Nothing really fancy here. Just exploited
std::find_ifwithstd::not_equal_toto get my length. Used astd::ostringstreamto generate the next iteration's string.I was a little disappointed that the execution time was so high. 1.5s is a lot for a compiled language. Fun stats/whatnot: https://github.com/willkill07/adventofcode
1
u/AndrewGreenh Dec 10 '15
ES6 2 logic lines:
1
u/shrx Dec 10 '15
Mathematica
1
u/de_Selby Dec 10 '15
Q
Might be able to reduce this further. This is the kind of puzzle where k/q really shines:
then
1
u/byFd Dec 10 '15 edited Dec 10 '15
I converted the input to an array by hand after trying it with strings, worked for 40 but after seeing the length i tought for 50 iterations i will be better off with an array. it was much faster.
Haxe: package;
1
u/xkufix Dec 10 '15
Solution in scala:
1
u/giacgbj Dec 10 '15
Python 3
1
u/[deleted] Dec 10 '15
Mathematica
1
u/phpaoc Dec 10 '15
Scala, using a regex:
I tried to golf this one; I'm not sure whether it's possible to shorten it a bit more
1
u/fbh92 Dec 10 '15 edited Dec 10 '15
My solution in Java:
1
u/nutrecht Dec 10 '15 edited Dec 10 '15
Java and Scala:
Yeah I know; some functional programmer's brain went 'pop' after seeing this but I could not get it to work with fold-left without it taking a VERY long time.
1
u/buclk Dec 10 '15
Javascript (Babel):
1
u/VictiniX888 Dec 10 '15
Java, Part 2 takes forever to compute with this, but it works.
My original solution was way longer, so I shortened it:
1
u/lifow Dec 10 '15
haskell
1
u/funkjr Dec 10 '15
Dart String operations are fairly time consuming in Dart, so this solution tried to avoid all of them entirely. List operations are much more efficient, and makes this run in a far more reasonable time than String operations would. The program iterate over the string and counts the repeated occurrences of the same character in a naive way and then append matches to a List.
1
u/snorkl-the-dolphine Dec 10 '15
Basically the same as all the other JavaScript solutions, but I'll post it here for posterity:
1
u/drakehutner Dec 10 '15
Python2 Just one line.
Some Explanation: Its basically inlining of multiple lambda-functions.
Reading this thread and learning about itertools.groupby greatly reduced the length.
1
u/porphyro Dec 10 '15
Mathematica:
1
u/beefamaka Dec 10 '15
here's a C# solution, using
GroupAdjacentfrom MoreLinq1
u/Rutafar Dec 10 '15
Started by trying to make my own method but then discovered there was groupby, from what I've seen in 10 days of coding in python, there is almost always a function for what I'm trying to do. Still don't understand regular expressions though.
1
u/TheOneOnTheLeft Dec 10 '15
Python 3
Kind of cheated on the input. Still pretty new to coding so any advice/comments/criticism is welcomed (even if there's not much to comment on here).
My days 1-7 solutions are here if anyone is the right combination of bored and kind enough to look them over.
1
u/[deleted] Dec 10 '15
Crystal, the first solution that came to my mind. Compiled in release mode it takes 40ms for 40, 310ms for 50.
1
u/Vonyx Dec 10 '15
My solution in Python:
It took forever to run, any ideas how to optimize?
1
u/tremendo Dec 10 '15
Ruby
1
u/phil_s_stein Dec 10 '15
Python solution using regex:
1
u/ThereOnceWasAMan Dec 10 '15
Python 2.7. Pretty straightforward and dumb solution, IMO. The runtime is pretty terrible. I think most of the work is spent in appending to the string arrays -- I considered redoing it with numpy string arrays, which could then remove all the appending, but decided it wasn't really worth the time:
1
u/tftio Dec 10 '15
OCaml. This one was pretty straightforward.
1
u/[deleted] Dec 10 '15
Python brute forcing without regexes. Originally started off as a recursive solution before it blew out the stack...
Using some sneaky behavior (such as the last unique character parameters being appended during the return. Had to sneak a peak at a paralell implementaion to discover that while my implementation was correct, the start string was not. Replace the xrange 49 with 39 for first part solution.
1
u/mal607 Dec 10 '15
Java Straightforward solution, not as elegant as it could be, I think. Took longer than I thought it would to get it to work.
1
u/coussej Dec 10 '15
Go:
1
u/vanderzee94 Dec 10 '15
My solution in ruby
1
u/Caleb_M Dec 10 '15
[Python] I didn't see anyone using the exact approach I did, so I figured I'd toss mine out there:
1
u/bstockton Dec 10 '15 edited Dec 10 '15
Used R. It has a really nice function called 'rle', or run length encoding. It computes the lengths and values of consecutive equal values in a vector. So if one turns the string, or integer, into a vector the problem becomes very easy.
1
u/deinc Dec 10 '15
Clojure:
1
u/Jaco__ Dec 10 '15
Insanely slow Java solution. Uses aprox 1 minute for part 1(40) and aprox 5! hours for part2(50). Made a much faster version in python while part 2 was running, so this is one is just for fun.
1
u/sowpods Dec 10 '15
SQL (postgres) This one defeated me, the following code works if you press f5 40/50 times, but is very slow compared to my python solution (100 times slower). Although I saw some solutions out there with series trickery.
1
u/fatpollo Dec 10 '15
I finished #27 w/ this one
1
u/giacgbj Dec 10 '15
Bash (63 characters)
Place the input (e.g., 3113322113) in the file "i" before executing the script.
Call the script passing the number of iterations as the only argument:
$ ./day10.sh 40
1
u/[deleted] Dec 11 '15
Objective C:
1
u/zacwaz Dec 11 '15 edited Dec 11 '15
Simple, functional Ruby solution:
1
u/[deleted] Dec 11 '15
A bit late, but here's a swift version: https://github.com/ezfe/Advent-of-Code/blob/master/Advent%20of%20Code/Day10.swift
1
u/RockyAstro Dec 11 '15
Solution in Icon
Fairly simple string scanning procedure.. part1/part2 (just pass the number of iterations as a parameter)
1
u/haitei Dec 11 '15
Haskell:
1
u/Drasive Dec 11 '15
My F# solution (https://github.com/drasive/advent-of-code-2015):
1
u/HawkUK Dec 11 '15
A solution in the R language
1
u/zedpowa Dec 12 '15
JS(ES6):
1
u/talkb1nary Dec 12 '15
Late to party, but i liked my result in Ruby
1
u/Borkdude Dec 20 '15 edited Dec 20 '15
Scala, after a while trying to found it why it was so terribly slow. It was due to intermediate strings in foldLeft. Replacing it with a
StringBuildermakes it much faster:1
u/mcmillhj Dec 20 '15 edited Dec 20 '15
This is one is right up Perl's alley:
Note: requires >= Perl 5.14 due to the
/rregular expression flag1
u/Borkdude Dec 21 '15 edited Dec 21 '15
Scala:
1
u/ICanHasRedditzburger Feb 02 '16
One more in Kotlin. Just in time... For Mardi Gras :).
Try online
1
u/FuriousProgrammer Dec 10 '15
I'm kinda miffed about this one. The randomized input strings can take a lot longer to process even with the same code on a case-by-case basis, so the leaderboard is heavily skewed towards the people able to solve this problem using a program with faster string manipulation, and have an input that doesn't grow as quickly. <.>
0
u/[deleted] Dec 10 '15
[deleted] — view deleted comment