r/adventofcode • u/daggerdragon • Dec 25 '17
SOLUTION MEGATHREAD ~โ๐โ~ 2017 Day 25 Solutions ~โ๐โ~
--- Day 25: The Halting Problem ---
Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or 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.
Need a hint from the Hugely* Handyโ Haversackโก of Helpfulยง Hints^ยค?
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!
Thank you for participating!
Well, that's it for Advent of Code 2017. From /u/topaz2078 and the rest of us at #AoCOps, we hope you had fun and, more importantly, learned a thing or two (or all the things!). Good job, everyone!
Topaz made a post of his own here.
If you're interested in a visualization of the leaderboard, /u/FogleMonster made a very good chart here.
And now:
Merry Christmas to all, and to all a good night!
4
u/Axsuul Dec 25 '17
Elixir
Parsed the entire input while the turing machine was built using an Elixir stream. Was delighted to see that the last star was by far the easiest challenge of the series :)
A big THANK YOU to /u/topaz2078 and team for another great year of AoC. The puzzles are always so interesting and I really appreciate all the hard work put into them. Had a blast and in the end walked away with learning Elixir and a better grasp of recursive functions.
Happy holidays everyone and see you next year!
GitHub
4
u/twiho Dec 25 '17
There's no way I'm not ending up in programmer's hell.
40
u/jlweinkam Dec 25 '17
I really enjoyed this years puzzles. Thank you and Merry Christmas.
19
u/varunagrawal Dec 25 '17 edited Dec 25 '17
First time participating in Advent of Code and managed to get on the rankings on the final day (Rank 100)! This was immensely fun and the private leaderboard made it a great activity to do with friends. Thank you so much and a very Merry Christmas.
P.S. Also provided some support to AoC from whatever meager grad student stipend I make. :)
6
u/DFreiberg Dec 25 '17 edited Dec 25 '17
I'm really glad I decided to fix my Day 22 bug and solve that problem less than a minute before midnight, even though I had no idea that I'd need to do part 2. /u/topaz2078, thank you for making so many good puzzles. /u/daggerdragon, thank you for getting me to resurrect my TI-89. /u/hackerknownas9gag, thank you for showing me even loftier functional-programming heights to aspire to climb in Mathematica.
Merry Christmas!
109/97
Mathematica
6
u/_Voile Dec 25 '17
5/5, JS. I exploited the fact that input is highly structured and hardcoded many things.
(Also I know the code is golfy; you can't be fast without being golfy, every byte is a frame save ;-)!)
5
u/onesk_ Dec 25 '17
Python 2, 53/100
Seems like today's solutions will be extremely similar to each other ;)
5
u/iamnotposting Dec 25 '17
Rust, 246. This was the first year i completed all the puzzles the day they came out, and i had a really fun time doing so. I'm glad this exists. I even can see myself getting better by looking at my global score. In 2015 i got 4 points, 2016 12, and this year i got 68 points. I'm really happy with myself and with this whole thing and i hope this continues for many years to come. thanks for everything!!
I probably slowed myself down with this last one by reversing the zero / one checking vs the input format. the perils of copy/paste.
5
u/Philboyd_Studge Dec 25 '17
Java. Love this kind of one. Giant THANK YOU to /u/topaz and the ops team on here for another really, really fun 25 days!!!!
4
u/streetster_ Dec 25 '17
q/kdb+
Nothing special here, just a bruteforce. Merry Christmas everyone!
3
u/vash3r Dec 25 '17
Python 2, #62/#62.
3
u/jonathan_paulson Dec 25 '17 edited Dec 25 '17
Seems like my decision to sort-of write a parser (this assumes the states are in order from A to whatever, the tape symbols are exactly [0,1] and they are given in that order) was a mistake.
3
u/ChrisVittal Dec 25 '17
Rust: Manually coded the machine, very verbosely.
Thank you all, this has been a real pleasure, I've learned a lot. Merry Christmas.
3
u/ephemient Dec 25 '17 edited Apr 24 '24
This space intentionally left blank.
3
u/mstksg Dec 25 '17
What a fun 25 days! Thanks /u/topaz2078 and the admin/mod team.
My Haskell solution today is a bit succinct, thanks to:
Array Boolis just aSet Int, where whether or not an index is True/False is whether or not it's in theSetcontains, which allows you to treat aSet Intas if it were a anArray BoolSemigrouptypeclass, which lets you "update" states using only<>by leveraging tuples and newtype wrappersThe actual logic of today is basically a one-liner:
And finally you can wrap it all up together using
iterateand!!:Full code online at github!
3
u/bitti1975 Dec 25 '17
Clojure. No need to write a parser. A few substitutions are enough to generate a valid Clojure form out of the instructions:
5
u/fatpollo Dec 25 '17
I felt like this year was a bit worse than the last two.
a lot of the problems felt like "heh guys remember our compsci curriculum?" inside-jokes, rather than weird esoteric stuff like the pseudo-RPG fights from Y1 or the bunnycoin mining from Y2.
still, incredible effort and value from /u/topaz2078. thank you for hosting this once again! looking forward to next year.
2
u/obijywk Dec 25 '17
Python 2. 28/25 (as I had everything else solved!). Decided to parse the input file by hand this time :-)
2
u/Unihedron Dec 25 '17
Ruby; 35/33; tfw it was easy but I'm slow
โจ๐ฃ Merry christmas! ๐
2
u/glenbolake Dec 25 '17
Python 3. I manually wrote a long if block at first:
Then once I had my final score, I wrote a regex parser (because Python doesn't have a sscanf built-in). I like this solution much better:
/u/topaz2078, never stop doing what you and your crew do. AoC is my favorite thing about the Christmas season! Merry Christmas!
2
u/StevoTVR Dec 25 '17
NodeJS
2
u/KeinZantezuken Dec 25 '17
C#/Sharp part1:
Cant do part2 apparently at all now
2
u/TheNiXXeD Dec 25 '17
NodeJS / JavaScript
I decided to actually parse the input, because regex is fun. Plus I think it made the solution a lot prettier.
2
u/TominatorBE Dec 25 '17
PHP
Thanks for the puzzles, have a Merry and a Happy!!
2
u/vescoc Dec 25 '17
Merry Christmas!
Thank to all AoC team, great work!
Scala (with input parsing)
2
u/aurele Dec 25 '17
Rust
Thanks again /u/topaz2078!
2
u/nutrecht Dec 25 '17
Day 25 in Kotlin
I'm happy and a bit sad too. It was a fun last challenge, quite simple too (literally a turing machine). And when I submitted the first part it was suddenly all over. What the heck am I going to do now with my life? ;)
Merry X-mas everyone!
2
u/wzkx Dec 25 '17 edited Dec 25 '17
Nim
It turned out, not easy to use enums and ranges without explicit conversions, so I had to stick with ints.
All "programs" are here: AoC 2017 Nim & J
Merry Christmas to everybody!!! ๐ ๐ ๐
2
u/death Dec 25 '17 edited Dec 25 '17
Woke up and wrote this (Common Lisp)
Note that the abstractions are obviously imbalanced, but it was this halfway, nondesigned version that satisfied the solution. Getting it right may be an exercise to the reader.
2
u/hermanbergwerf Dec 25 '17
I really enjoyed all the puzzles! Thanks Eric! All my solutions in Dart: https://github.com/bergwerf/aoc2017
2
u/thomastc Dec 25 '17
Day 25 in Kotlin. Finally allowed myself to use my favourite language!
A retrospective of my polyglot challenge is in the making. Watch this sub!
2
u/udoprog Dec 25 '17
Rust
Translate the input by hand, execute (with
--releaseto speed it up) and wait :).Enjoy all my solutions here: https://github.com/udoprog/rust-advent-of-code-2017
Thanks a bunch to /u/topaz2078, /u/daggerdragon, and everyone else involved in making this happen. It's been a blast! Happy holidays!
2
u/V13Axel Dec 25 '17
FIrst time doing Advent of Code, and I had a whole lot of fun doing it. Thanks a ton for putting it together!
My input-parsing solution in Python 3:
turingmachine.py:day25.py:2
u/RockyAstro Dec 25 '17
Icon (https://www.cs.arizona.edu/icon)
Merry Christmas/Happy Holidays...
Thank you Eric Wastl (/u/topaz2078) and his helpers for creating a fun and entertaining puzzle.
I still have some work to do -- I need to finish working on the Snobol solutions.
For jollies, I parsed the input to build the turing machine's state table.
Day 25:
2
u/matusbzk Dec 25 '17
Haskell My solution was too ineffective, then I found out about existence of IntSet here in comments (thanks, u/mstksg). After little changes in my code, now it runs in reasonable time. I did not feel like writing a parser, so parsing is just in the code.
Link to git. I really enjoyed solving AoC this year, for the first time I had enough time to actually do it all. And doing it all in Haskell was quite a challenge too.
2
u/greycat70 Dec 26 '17
Tcl (nothing fancy, but I do use lassign which requires >= 8.5)
1
u/QwirkyQwilfish Dec 25 '17
Python 3. vals = {}
Still have to finish off a few other problems to deposit 50 stars though.
1
u/wlandry Dec 25 '17
C++ 14
201/181. For once, I did not use the test vector. I parsed the input file by hand and wrote out the state transitions. It worked the first time?!?!? It runs in about 30 ms.
1
u/doctorbaggy Dec 25 '17 edited Dec 25 '17
perl
Nice state space model - we start by defining a map of state/value changes {remap states to 0..5} - and loop through the prerequisite number of times - and dump the result { include a die if we haven't made our "infinite tape" big enough!}
1
u/Aehmlo Dec 25 '17 edited Dec 25 '17
Rust, 375/???. Decided that for the last day I'd actually try the puzzle right when it unlocked, but I spent a little too much time making it human-readable. :)
Edit: I made it a lot less stringly-typed.
1
u/[deleted] Dec 25 '17
Haskell:
Just hardcoded the rules for a quick solution, will go back and add parsing for the input when I have time.
Merry Christmas everyone!
1
u/stkent Dec 25 '17
Throwing my thanks-hat in the ring for another fun year! I was much more effective this year, mostly thanks to the lessons learned last year :)
1
u/The0x539 Dec 25 '17
Lua (421)
This was a nice way to end things. Punctuation was annoying, though.
1
u/hpzr24w Dec 25 '17
C++
Basic stuff. Set up for fast copy/paste. Had a bug in state E. Gah!
1
u/[deleted] Dec 25 '17
Great work, AoC team! Was really fun and look forward to 2018! (And finishing up 2015 and 2016! OCaml Fun;; train is just getting started.)
Anyways, here's your tape machine:
main.ml
machine.ml
1
u/m1el Dec 25 '17
Rust, 538. manually coded state machine. Nicely visible state machine.
Run time: 50ms.
1
u/[deleted] Dec 25 '17 edited Dec 25 '17
C# Brute force is the (only) way (I know) to go 737/737
1
u/LeCrushinator Dec 25 '17 edited Dec 25 '17
C#, ugly but it worked first try (well second try, I got a stack overflow on the first try). I just allocated a huge list because the state machine input I was given looked like it wouldn't wander too far even with 12 million iterations. On my first try I was just calling states directly from other states, and after running it I immediately got a stack overflow and knew that was a bad idea:
1
u/sclark39 Dec 25 '17
Javascript / Node.js
I think like many others, I decided writing an actual parser would take longer than just parsing the input myself. Simple switch-based state machine. To simplify actually calculating the checksum, I just keep a running checksum and update it with each write.
1
u/Lokathor Dec 25 '17
Big manual switch statement :P
1
u/u794575248 Dec 25 '17 edited Dec 25 '17
Python (80/77). To submit my answers I parsed input manually as almost everybody else, and here's my regex based alternative:
s: current stateS: list of parsed state transitionsN: number of stepsV: list of parsed value transitionsM: list of parsed movementsD: map states to a tuple of(value if 0, value if 1, move if 0, move if 1, state if 0, state if 1)c: cursor positionT: tape1
u/Borkdude Dec 25 '17 edited Dec 25 '17
Clojure
1
u/maxxori Dec 25 '17
Nothing special but here is my solution in C#:
You'll need to add a reference to System.Drawing in order to get access to the "Point" object.
Some of the functions are over-engineered because I had used them for some other solutions.
1
u/sim642 Dec 25 '17
My Scala solution.
Took my time to actually parse the input too, crudely with regexes.
1
u/xkufix Dec 25 '17
Nothing too fancy for the last day. Just a "normal" implementation of a turing machine. The main part is basically just parsing the input into the state transitition, the actual calculation is quite short.
Code in Scala:
1
u/dario_p1 Dec 25 '17 edited Dec 25 '17
Did the last day in x64 assembly for a change. No parsing tho, it's already long as it is.
https://github.com/dp1/AoC17/blob/master/day25.0.asm
1
u/Floydianx33 Dec 25 '17
C#
Not the greatest -- but it works. I did it out manually (no code) so now I plan to add the parsing code in.
1
u/McBooley Dec 25 '17
If you could rate the starting, middle and ending difficulty of these challenges, what would it be?
For example how much should a beginner, mid-range be able to do and where/if you would rate it senior difficulty?
Sorry for the weirdly asked questions but I'm just curious.
1
u/adrian17 Dec 25 '17
Rust. Would appreciate some feedback.
(Also, confusingly, without --release it's 3x slower than my Python code)
1
u/BOT-Brad Dec 25 '17
A great set of puzzles this year, yet again. Thanks to all involved and Merry Christmas!
For anyone interested, all my JavaScript solutions are available (for all 49 puzzle stars) on my GitHub repo
JS
I parsed the input myself because it seemed faster than writing the code to do so.
1
u/chicagocode Dec 25 '17
Kotlin - [Repo] - [Blog/Commentary]
After hard coding the inputs I decided parsing wouldn't be all that hard. Thanks to everybody who gave me feedback, I feel like I learned a lot of Kotlin this year. Thanks to Eric Wastl for creating such a fun set of puzzles! Only 340 days until Advent of Code 2018! :)
1
u/NeilNjae Dec 25 '17
Haskell. Nothing fancy, but I thought I'd use it as a testbed for trying out
Megaparsecon something slightly less trivial than the AoC inputs so far. I think the parser turned out quite well, giving something much more readable than a hodgepodge of regexes.It's on Github as well
1
u/willkill07 Dec 26 '17
Modern C++
Parse ALL THE THINGS
https://github.com/willkill07/AdventOfCode2017/blob/master/src/Day25.cpp
1
u/Tetsumi- Dec 26 '17
Racket with input parsing
1
u/miran1 Dec 27 '17
Nim
ย
Repo with solutions (both Nim and Python)
0
u/[deleted] Dec 25 '17
[deleted] โ view deleted comment
1
u/[deleted] Dec 25 '17
[removed] โ view removed comment