r/adventofcode • u/daggerdragon • Dec 05 '17
SOLUTION MEGATHREAD -๐- 2017 Day 5 Solutions -๐-
--- Day 5: A Maze of Twisty Trampolines, All Alike ---
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!
22
Upvotes
16
u/willkill07 Dec 05 '17 edited Dec 05 '17
(Modern) C++ Repo
Part 1 runs in about 1ms and Part 2 runs in 75ms on my laptop.
12
u/zSync1 Dec 05 '17
Here's a rather straightforward Rust solution.
12
u/askalski Dec 05 '17
Part 2 using self-modifying x86-64 opcodes. That was how we were supposed to do this, right?
9
u/drysle Dec 05 '17
#3/#5, my best time so far this year:
though it always feels a little weird bragging about python solutions that are probably almost identical to the even faster people...
8
u/[deleted] Dec 05 '17 edited Dec 05 '17
First Haskell solution was pretty slow, got it down to ~4s using Data.Sequence, but then just decided to switch to mutable vectors and both parts run instantly now.
8
u/volatilebit Dec 05 '17
Perl 6
No fancy Perl 6 tricks, just some old fashioned procedural code. That made me sad. Exposed how slow Perl 6 can be as well.
8
u/Young_Man_Jenkins Dec 05 '17
My friend and I ran code that was essentially the same. He used Rust, I used VBA in Excel. His code took 121ms to run, mine took 15 minutes. I'm starting to think one is a bit more efficient than the other.
7
u/iBeliever Dec 05 '17
First time competing (it starts at 11 PM local time, so normally I do them the next morning), and I got on the leaderboard as 86 for part 2!
Here's my solution in Python:
(I have some util functions for reading the input as well as writing tests).
7
u/ephemient Dec 05 '17 edited Apr 24 '24
This space intentionally left blank.
6
u/misnohmer Dec 05 '17 edited Dec 07 '17
Easier to use imperative code on this one. C# version making use of local function syntax.
6
u/[deleted] Dec 05 '17 edited Dec 05 '17
Language is 32 bit MIPS assembly:
Source including formatted data section
5
u/StevoTVR Dec 05 '17
NodeJS
Part 1:
Part 2:
5
u/Portal2Reference Dec 05 '17
My solution for part 2 was taking forever, couldn't figure out what was wrong with my code.
Turns out that I forgot that leaving in the print statements dramatically slowed it down. Finished in <1 seconds after removing them.
5
u/flaming_bird Dec 05 '17
OOB reads in Lisp are an error, and errors can be caught and ignored, so I can then print out the number of steps that I took.
4
u/fatpollo Dec 05 '17 edited Dec 05 '17
4
u/DeveloperIan Dec 05 '17 edited Dec 05 '17
Part Two. Python:
4
u/vectorprocessing Dec 05 '17
In k3:
4
u/vash3r Dec 05 '17 edited Dec 05 '17
I feel really good that I managed to make the leaderboard for part 1 (29th), but I think it was ultimately my machine that made me lose out for part 2 (running part 2 took over 40 seconds on my 3-year-old laptop, giving me 113th).
Edit: thank /u/fatpollo, looks like my machine isn't the problem, it's just that
Cpythonis much slower thanpypy.My solution was in Python2 and pretty much identical to other people's solutions:
4
u/Godspiral Dec 05 '17
in J, interupted part 2 a few times thinking it was stuck :(
4
u/[deleted] Dec 05 '17 edited Dec 05 '17
My rust solution was pretty boring and imperative so here's my clojure instead.
Edit: Part 1 runs in ~147ms, Part 2 in ~5 seconds. Really good for a dynamic language that is creating and throwing away an immutable number vector every iteration.
Edit 2: Switching to mutable vectors gives Part 1 in ~93ms, Part 2 in ~1.1 seconds.
4
u/Axsuul Dec 05 '17
Elixir
Finally getting the hang of pattern matching but still need to get used to a functional programming mindset. Appreciate any feedback :)
https://github.com/axsuul/advent-of-code/blob/master/2017/05/lib/advent_of_code.ex
4
u/chunes Dec 05 '17
Factor part 2. (Part 1 is the same sans the
alter-offsetword.)4
u/APLtooter Dec 05 '17
APL [GNU]
6
u/mmaruseacph2 Dec 05 '17
Haskell. Runs slow (~1min for part 2) and that cost me the leaderboard. Most likely there are a lot of optimization venues (to work on as an upping-the-ante extra).
3
u/ka-splam Dec 05 '17 edited Dec 05 '17
PowerShell solution. Reasonably pleased, in that my code worked first time for part 1 and with a single typo costing 11 seconds for part 2.
Puzzled and mildly annoyed that part 1 took me over 4 minutes to read the challenge and write the code (comments added after for this post), and part 2 took nearly 4 minutes just to run - some people had both their answers in less time than just the runtime of my part 2. What languages are they using that are so fast to write and also so fast to run??
3
u/AndrewGreenh Dec 05 '17 edited Dec 05 '17
I started implementing my TypeScript solutions a bit more "pythonic", because debugging is way easier in imperative loops over iterables. Was 50 seconds too slow for leaderboard :( [267/164]
3
u/giftpflanze Dec 05 '17
Tcl:
3
u/nospamas Dec 05 '17
F# Solution using recursion and mutable array
Left the printing function (massive slowdown) and my infinite loop protection check in but commented out :).
3
u/Philboyd_Studge Dec 05 '17
Java.
3
u/Cheezmeister Dec 05 '17
Literate Perl. Viewer discretion is advised.
3
u/rkachowski Dec 05 '17
in ruby, this felt simultaneously wayy too easy and waayy too dirty of a solution. i feel like i'm missing some really elegant iteration trick, but everyone in this thread seems to have the same approach
3
u/uno_in_particolare Dec 05 '17
I'm using Java since I want to exercise a bit (it's the language we use in our introductiory course in university)
I see no one else used exceptions... is it a bad idea to use them in this case? I know it's a bit like "cheating", but it works like a charm :D
3
u/wzkx Dec 05 '17
Nim Easier and easier
3
u/f0086 Dec 05 '17
Emacs Lisp
2
u/ghlmtz Dec 05 '17
Pretty simple in Python.
2
u/TominatorBE Dec 05 '17
PHP
Part 1:
Part 2:
2
u/tvtas Dec 05 '17
Day 5 in MATLAB:
2
u/gbear605 Dec 05 '17
Rust
Not super idiomatic (the mutable variables are screaming at me), but I'm not sure how else to do something like this.
2
u/autid Dec 05 '17
Fortran
2
u/monikernemo Dec 05 '17 edited Dec 05 '17
ANSI C
Didn't want to mess with the positioning so used different indices for current position and array index PART 1
PART 2 Basically the same thing with different conditionals within while loop;
2
u/[deleted] Dec 05 '17
Here's my simple tail-recursive solution in Scala:
2
u/sakisan_be Dec 05 '17
elm
2
u/Dooflegna Dec 05 '17
2
u/sciyoshi Dec 05 '17 edited Dec 05 '17
Rust - using closures!
GitHub
2
u/WhatAHaskell Dec 05 '17
Haskell
2
u/hxka Dec 05 '17 edited Dec 06 '17
Bash, anyone? It's too goddamn slow :(
2
u/madacoo Dec 05 '17
optimised Python3 part 2
Since I couldn't start when the problem was released, I tried to get my Python code as fast as possible. Managed to half it down to ~ 8 seconds. Most interesting thing is that checking for an IndexError is about a second faster than checking i < length of instructions. It would be cool if you could turn off negative indexes in Python but I don't think that's the case.
Interested to hear if anyone has further optimisations. Although I'm not sure why I'm even bothering to optimise in Python. Should probably just write it in C at this point.
2
u/mtnslgl Dec 05 '17 edited Dec 05 '17
My C++ solution:
2
u/nutrecht Dec 05 '17
My Kotlin solution for Day 5:
2
u/[deleted] Dec 05 '17
Javascript - one liners
1.
2.
2
u/mschaap Dec 05 '17
Perl 6. Solution for part one:
For part two, the change is simple, just change
method jumpto:I was just about to get worried when this finally finished in about 7ยฝ minutes. (Don't run it with
-von the actual input! Works fine on the sample input though.)2
u/u794575248 Dec 05 '17 edited Dec 05 '17
Python.
2
u/[deleted] Dec 05 '17
Java 8 single implementation of part 1 & 2
2
u/binajohny Dec 05 '17
My Kotlin solution:
2
u/Reibello Dec 05 '17
Here's my Day 5 in Lua - https://github.com/Reibello/AoC-2017-Lua Pretty sure I left part B commented out for testing something. As always, critique is welcome (learning is hard). Not looking forward to going back to day 3 (day 4 should be okay I think) and figuring out how to go from Python to Lua.
2
u/ZeroSkub Dec 05 '17
C++
PART 1:
PART 2:
2
u/sguberman Dec 05 '17
Python: GitHub
Saved you a click:
2
u/53bvo Dec 05 '17 edited Dec 05 '17
I've never used python before this advent, and actually never coded anything besides some matlab calculations. So far the challenges were doable, with the usual googling forever how to do a simple task. Today went quite good except that it takes 19 seconds to do the 2nd calculation. Anyone got any suggestions on how to improve performance?
Edit: I reduced the code to:
But now it takes 10s longer to run
2
u/Nhowka Dec 05 '17
F#
2
u/Genie-Us Dec 05 '17 edited Dec 05 '17
Day 5 Code - Javascript - Both stars! Hurray!
She's not pretty, but she's mine!
2
u/exploding_cat_wizard Dec 05 '17 edited Dec 05 '17
Edit: Perl5
For part 1 I chose a recursive function, since that just fit the problem so well. It worked, and ran in 0.26s and used 191000 kbytes (almost 200MB!) of memory. No idea what's going on there, perhaps Perl isn't meant for recursion (there's a warning, after all).
Part 2 bombed my 8GB memory as recursive script, so I switched to a loop, which finished in 4.88s using a whopping 4888kbyte of memory, according to
time -v ./aoc5.pl:I also, for the heck of it, wrote a version where $now is not needed, thinking this would save memory, but increase run time. Instead, the if (and else) statements now get the line finding the next $next:
and
respectively. This did the exact opposite of what I thought: time was slightly shorter (4.4s) and max mem usage slightly higher (4984kbytes)
2
u/akho_ Dec 05 '17 edited Dec 05 '17
Python3:
2
u/Jaco__ Dec 05 '17
Quite happy with my Haskell solution today. Takes ~5 sec for part 2 without any optimizations.
2
u/MetaSaval Dec 05 '17
Swift once again. Pretty easy puzzle, probably the easiest one so far. And I was able to reuse code from Day 2 again, so that's neat. Could probably be made to be more efficient, though.
2
u/BOT-Brad Dec 05 '17 edited Dec 05 '17
JavaScript
Part 1 (~2ms)
Part 2 (~140ms)
2
u/Smylers Dec 05 '17 edited Dec 06 '17
Buggy Perl, which happened to come up with the right answer. Part 1 was fine:
Then for part 2 I just added a line, subtracting 2 for values that were supposed to go down by 1 (to take into account that all values were being unconditionally increased by 1), making the loop be:
Except, clearly that subtraction is happening on the wrong jump! By the time the subtraction executes,
$pchas already been updated, so it's the new value that's being changed. Yet it still worked!A jump over 3 will be left too-big by 2. However, the next time the program lands there (if ever), it will then be reduced by 2 (instead of the instruction just jumped from), just before it is used in the following iteration. So all instructions that are actually used will end up being modified correctly. Phew.
The bug is that any initial value over 3 will also be increased by 2 the first time it is encountered. Obviously those values aren't in need of such increasing, so will end up jumping to the wrong place. Ooops. How come my program worked then? It seems /u/topaz2078 didn't include any jumps bigger than 3 in my input; the largest was 2. So I got away with it.
Obviously I fixed it anyway. It's what others such as /u/ephemient came up with in the first place: a
?:condition picking between postfix--or++, ensuring the jump value doesn't change until after$pchas been updated:2
u/RockyAstro Dec 06 '17
Icon (https://www.cs.arizona.edu/icon)
Part 1:
Part 2:
1
u/miran1 Dec 05 '17
Python 3, 14th silver, 36th gold
This is just the quick modification for the second part. Delete unneeded if-else for the first part.
1
u/dylanfromwinnipeg Dec 05 '17
C#
1
u/Shemetz Dec 05 '17
PYTHON Was very straightforward! Part 2 took a while (15 secs?) to compute, however.
PART 1
PART 2 lines = [line.strip() for line in open('input.txt', 'r').readlines()]
1
u/Keep_Phishing Dec 05 '17
Just about managed to make the leaderboard today.
My solution in Python3:
1
u/NewHorizons0 Dec 05 '17
Rust. #264 :(
1
u/the4ner Dec 05 '17 edited Dec 05 '17
C#, hooray, made the leaderboard for the first time this year with part 2. would have made part 1 and placed better in 2, but I executed it the first time with > 0 instead of >= 0 in my while loop :facepalm:
1
u/braksor Dec 05 '17
Was extremely lazy.
1
u/RevoRevo Dec 05 '17
Python 3 Undoubtedly not the cleanest, but I had fun!
1
u/nstyler7 Dec 05 '17
part 1 & 2 in python 3
1
u/[deleted] Dec 05 '17
OCaml is the life for me.
1
u/Overseer12 Dec 05 '17 edited Dec 05 '17
C#, Github
Part 1: (24135 ticks, 7 ms.)
Part 2: (1441114 ticks, 447 ms.)
1
u/JeffJankowski Dec 05 '17
Forgot to clone my input array, d'oh Typescript
1
u/LeCrushinator Dec 05 '17
C# solutions:
1
u/[deleted] Dec 05 '17
a kotlin solution
1
u/vesche Dec 05 '17
Python solution
C solution
1
u/SlightlyHomoiconic Dec 05 '17
Here's my clojure part 2 solution. The only difference between this and part 1 is replace the second
ifwith justinc1
u/OneEyedGammer Dec 05 '17
My god, I spent almost 10 minutes trying to figure out why my code wasn't working on part 2. Turns out it doesn't want an absolute value.
Here is my garbage code in ruby:
1
u/Inqud Dec 05 '17
C#
1
u/[deleted] Dec 05 '17
C++
1
u/superlameandawzm Dec 05 '17
Simple javascript solution
1
u/_Le1_ Dec 05 '17
1
u/aurele Dec 05 '17
Rust
1
u/Warbringer007 Dec 05 '17 edited Dec 05 '17
Erlang, both parts ( only main function ):
Second part for Erlang is just too slow, didn't want to wait for it to finish so I solved it in C++ also ( my first C++ code :D ):
1
u/xkufix Dec 05 '17
In Scala, the solutions can be easily made generic to provide a frame for both parts:
1
u/EquationTAKEN Dec 05 '17
Can anyone take a look at my Python solution for part 2 and see why it takes so long to run?
It prints the right solution, but spends about 10-15 seconds on it.
I made another solution in JS which ran in just a few millis, so I know this can be faster, I just don't know which steps are draining time.
1
u/bolshedvorsky Dec 05 '17
Python 2.7
1
u/NeilNjae Dec 05 '17
Haskell. Using an
IntMapto store the state of the maze, a record to store the whole state, and a monad to thread the changing state through the computation.There was a possible ambiguity in the Part 2 question, though: should we be checking the absolute value of the step or not? I took the simpler route at first, and that was the correct guess.
1
u/Vindaar Dec 05 '17
Solution in Nim. Compared the approach using while with a recursive one. Not sure if I could improve the recursive version to make it faster. Currently the first approach takes ~100ms and the recursive about 180ms.
1
u/Hikaru755 Dec 05 '17
Tailrecursive solution in Kotlin. Took me way too long to figure out why part II gave the wrong answer, until I noticed that I ran both functions after another on the same mutable list. That should teach me to be more careful with mutable state next time...
1
u/[deleted] Dec 05 '17 edited Dec 05 '17
Golang
My first year of advent of code and first time using go.
Feedback is much appreciated.
Part 1
Part 2
All my go solutions here
1
u/Borkdude Dec 05 '17
Clojure: https://github.com/borkdude/aoc2017/blob/master/src/day5.clj
1
u/JakDrako Dec 05 '17
C#, both parts.
1
u/wzkx Dec 05 '17 edited Dec 05 '17
J sorry no tacits, no u^:p^:_
0.43s & 30.2s (29.2s if move #y out of loop)
1
u/thehaas Dec 05 '17
I think I have a similar solution to a lot of other people (esp Python).
1
u/[deleted] Dec 05 '17
Go Part 1:
Go Part 2:
1
u/raevnos Dec 05 '17 edited Dec 05 '17
Kawa Scheme:
Part 2 isn't particularly fast, which is annoying. Kawa runs on the JVM and I figured that it would have done a better job at optimizing and JITing the code. Edit: Made a few changes (vector to s32vector, type annotations, rely on an out of bounds vector ref to throw an exception instead of explicitly checking the current index) and went from around 43 seconds total run time to 9. Much better. (Also slightly faster than when compiled to a native binary with chicken scheme).
1
u/CatpainCalamari Dec 05 '17
My solution in scala, inspired by /u/mlruth usage of
Vector.lift, which allows for some nice pattern matching.1
u/Morphix0 Dec 05 '17 edited Dec 05 '17
F#
1
u/Pheasn Dec 05 '17 edited Dec 05 '17
Kotlin using tail recursion (because Java can't)
1
u/[deleted] Dec 05 '17
Clojure
1
u/[deleted] Dec 05 '17
Elixir Part 2 is waaay too slow, but apart from that it seems to work pretty nice :)
1
u/KeinZantezuken Dec 05 '17
C#/Sharp:
.
1
u/rimbuod Dec 05 '17 edited Dec 05 '17
Haskell! I love it!
but it's slow as fuck!
probably because I'm clueless!
1
u/adventOfCoder Dec 05 '17
Java
Part 1:
Part 2:
1
u/Krakhan Dec 05 '17 edited Dec 05 '17
C# solution. Pretty straight forward:
1
u/varunu28 Dec 05 '17
Day 5 in Java
1
u/Life-in-Shambles Dec 05 '17
(JAVASCRIPT) IT'S UGLY AND SLOW BUT IT WORKS
1
u/asperellis Dec 05 '17
my day 5 solutions in js. any suggestions for improvement welcomed. https://github.com/asperellis/adventofcode2017/blob/master/day5.js
1
u/4rgento Dec 05 '17 edited Dec 05 '17
Straight forward strict haskell solution:
1
u/[deleted] Dec 05 '17
Haskell
takeStepis part 1;takeStep'is part 2Took quite a few minutes, even with
-O2optimization.1
u/cptwunderlich Dec 05 '17 edited Dec 05 '17
My attempt at (modern) C++. I'm trying to write all my solutions in a more "functional style". This isn't really that functional, but I guess some more code reuse than before. I did write it with plain old loops before and it was significantly faster. Unfortunately, I overwrote that solution.
I saw u/willkill07 's solution, where he filled the array without a loop. That's really neat, I was looking for something like that, but I didn't figure it out.
Edit: it takes ~2.36s for the whole thing. Really not so great. Edit2: Oh no! Nevermind! I forgot to pass "-O3", so now it runs in 0.2 Seconds...
1
u/JPry0 Dec 05 '17
A PHP solution: https://github.com/JPry/advent-of-code/tree/master/src/y2017/day05
1
u/chicagocode Dec 05 '17
Kotlin: Repo, Blog/Commentary
I did this as a tail recursive function to handle both parts that I'm pretty happy with. It's very quick too.
This year I'm challenging myself to publish my code to Github and to blog about each solution.
1
u/virtron Dec 05 '17
Go
Nothing fancy:
1
u/[deleted] Dec 05 '17 edited Dec 05 '17
Kind of late because I forgot to post my code after I finished, but here's a pretty fast C solution (compiled with -O3, runs in about .07 s)
1
u/[deleted] Dec 05 '17
PowerShell:
1
u/ramrunner0xff Dec 05 '17
scheme (chicken) repo
1
u/[deleted] Dec 05 '17 edited Dec 05 '17
single pipeline powershell
1
u/[deleted] Dec 05 '17
Took me a long while, still can't figure out how to get the second star properly. Gotta read up on haskell data. I ended up just using python to figure it out in the repl, but here's my slow, not working haskell:
1
u/peterpepo Dec 05 '17
Python3
Full solution on github.
1
u/[deleted] Dec 05 '17 edited Dec 05 '17
Solution for one in Go.
inputis the input string of numbers. Completes in around a 1ms.Solution for two in Go.
inputis the input string of numbers. Completes in about 98ms.Almost the same code.
Edit: Added timings.
1
u/Unequaled Dec 05 '17
Python3:
I am learning Python for fun as a university student. Please, be gentle
1
u/omegaxLoL Dec 05 '17
My solution in Golang. Constructive criticism always welcome of course!
1
u/8483 Dec 05 '17
Node/Javascript
1
u/fost97 Dec 05 '17
Postgresql (not very space efficient at all...):
https://github.com/seltiko/sql_advent_2017/blob/master/Day%205.sql
1
u/andreesgor Dec 05 '17
Ruby:
1
u/SurplusSix Dec 05 '17
Learning Racket, this is probably terrible code :)
1
u/[deleted] Dec 05 '17
Java
https://github.com/imoutopantsu/adventofcode-2017/tree/master/day%205
Excel
I gave up after seeing how many interactions I would had to do manualy to solve the problem :( I will try my best to do it later though.
1
u/mastercake10 Dec 06 '17
Just switched from Py to Rust in order to archive better time results. Python tooks about 8 seconds to solve, my Rust code only 90 ms. This was my first time using Rust, actually I'm quite surprised by its performance.
https://github.com/mastercake10/AdventOfCode2017/blob/master/rust_solutions/src/day5.rs
1
u/RockyAstro Dec 06 '17
Snobol using the spitbol implementation (https://github.com/spitbol/spitbol)
Part 1:
Part 2:
1
u/Sparrow_1029 Dec 06 '17
Python 3! Pretty slow-running solution for part two...
https://pastebin.com/FXvXJ8kN
1
u/thomastc Dec 06 '17
ALGOL 68
1
u/gurkab Dec 07 '17
PYTHON
1
u/engageant Dec 07 '17 edited Dec 07 '17
posh:
Part 1 (~2.6s)
Part 2 (~180s)
1
u/[deleted] Dec 08 '17
Simple JS
1
u/matusbzk Dec 09 '17 edited Dec 16 '17
Haskell
Actually, this one is really inefficient. Calculates the first part in like 6 seconds, but the second part takes more then 10 minutes (then I closed it). I calculated the actual solution in C#. But I found some Haskell solution here.
Link to git
1
u/[deleted] Dec 10 '17
Crystal.
Part 1:
Part 2:
1
u/micirsk Dec 11 '17 edited Dec 11 '17
Python - part1
1
u/miran1 Dec 11 '17
Nim
Repo with all solutions
1
u/mathleet Dec 15 '17
Here's what I've got for a Python 3 solution:
1
u/n3nn3nn Dec 19 '17
My C solution:
1
u/[deleted] Dec 21 '17 edited Dec 21 '17
1
u/greycat70 Dec 28 '17
Tcl (any 8.x version)
My choice here was whether to use an array, or a list. Decided to try a list and
lreplacefor today. Performance was rather slow on part 2 (28 million steps -- did not anticipate anything near that large) but I never got around to trying with an array to see if that was any better.Part 1:
Part 2:
1
u/znrgtrl Dec 05 '17
The tasks are too easy it's just a typing challenge basically. Should be more difficult to make the competition actually interesting.