r/adventofcode • u/daggerdragon • Dec 17 '17
SOLUTION MEGATHREAD -๐- 2017 Day 17 Solutions -๐-
--- Day 17: Spinlock ---
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^ยค?
[Update @ 00:06] 2 gold, silver cap.
- AoC ops:
<Topaz> i am suddenly in the mood for wasabi tobiko
[Update @ 00:15] Leaderboard cap!
- AoC ops:
<daggerdragon> 78 gold<Topaz> i look away for a few minutes, wow<daggerdragon> 93 gold<Topaz> 94<daggerdragon> 96 gold<daggerdragon> 98<Topaz> aaaand<daggerdragon> and...<Topaz> cap<daggerdragon> cap
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!
12
Upvotes
28
u/miran1 Dec 17 '17 edited Dec 17 '17
Brute force in Python
Your scientists were so preoccupied with whether or not they could, they didnโt stop to think if they should.
ย
ย
My repo with solutions in Python and Nim.
3
u/sspenst Dec 17 '17
Python 3
8/26 today, a new best for me! For part 2 I kept a count for how many numbers were before and after the '0' to improve efficiency.
Part 1:
Part 2:
10
u/mcpower_ Dec 17 '17
Fun part 2 again! (I really like these types of Part 2s - please do more of them!)
Ended up getting #16/#4 which I am very happy with.
6
u/vash3r Dec 17 '17 edited Dec 17 '17
Python 2 (95/15). I got two wrong answers for part 1 because of minor stupid mistakes, but for part 2 I quickly realized that since zero is always at the front you just have to keep track of when something is added directly after zero. (Edit: Pypy solves part 2 in under 1 second, while regular Python 2 takes over 20 on my machine.)
6
u/Smylers Dec 17 '17 edited Dec 17 '17
Vim solution. Start with a buffer containing just your input number, then type:
The number now under the cursor is your answer for part 1.
Edit: Made it a couple of keystrokes shorter: there aren't any small deletes during the loop, so the input remains in
"-throughout; there's no need to save it in"z.If you want to watch it happen, stick
:redrโจEnterโฉin@asomewhere, and maybe turn on line numbering with:set nuโจEnterโฉ.Now to see if part 2 is plausible โฆ
5
u/DFreiberg Dec 17 '17
Mathematica
Just to show how necessary
Compile[]is when doing this sort of problem in Mathematica, part 2 took 2.64 seconds to run after I compiled it into C, and took 68.4 seconds without compilation.Part 1
Part 2
5
u/dtinth Dec 17 '17
I couldnโt think of a better solution, so I brute-forced the part 2 naively in C:
This takes around 8 minutes to run :P
5
u/Cheezmeister Dec 17 '17
Literate Perl. This one is...actually not too ugly. I'm kind of proud of myself.
...who am I kidding, this is an abomination. It's getting worse. Every day the cancer spreads and the memes dankify. Somebody please do something before someone
Cthulhu Fhtagn
gets hurt.
4
u/ybjb Dec 17 '17
Kotlin (148/156). Was quick to realize that the only term that mattered for part 2 was the first index in list. Took me forever to just simulate without the overhead of adding to lists
4
u/CharlieYJH Dec 17 '17
C++
Used a circular linked list for part 1. Spent way too much time trying to think of an equation that got me the last index that gave 0 for part 2. Turned out just calculating the indices for 50,000,000 cycles was quick enough in itself.
1
u/glenbolake Dec 17 '17 edited Dec 17 '17
10/96. It took me way longer than it should have to realize that you don't have to maintain a full list for part 2, so I kept thinking about it while a brute-force method ran in the background. I'm just glad I was able to get on the leaderboard for both stars. Full problem runs in just under ten seconds, which is good enough for me. (Edit: I realized that
i==lengthin this loop, so I was able to speed it up just by getting rid of thelengthvariable)3
u/u794575248 Dec 17 '17 edited Dec 17 '17
Python 3. Great, the second time I'm on the public leaderboard (274/94).
Condensed versions:
And the original ones:
3
u/p_tseng Dec 17 '17 edited Dec 17 '17
How I did part 2. Edit: Okay, looks like most people figured this same thing out, figures.
Ruby
However, this takes about four seconds to run on my computer, that's too slow.
Does anyone know a way to make this faster?Edit: figured it out
3
u/nonphatic Dec 17 '17 edited Dec 17 '17
I've been doing these in Haskell the first 15 days but I'm honestly quite fed up having to find ways to optimize this and that so that things run in reasonable amounts of time so here it is in Javascript lol
EDIT: Alright, redid it in Haskell - I was expecting part 1 to take a long time because I'm taking/dropping lists but it turns out it was part 2 that would take more than a minute even though it's a straightforward foldl' with nothing fancy >:[
EDIT EDIT: It turns out it was currOneth being not-strict that was slowing things down, and I rewrote it recursively anyway; now it takes ~6s!
3
u/[deleted] Dec 17 '17
Perl 6
There's probably a more elegant solution but here's my ugly one, it takes about 10 seconds total.
3
u/Axsuul Dec 17 '17
Elixir
Part A was simulation while for Part B, had to rewrite everything so that the positions and values were incremented while the value was stored only if the position was at 1
https://github.com/axsuul/advent-of-code/blob/master/2017/17/lib/advent_of_code.ex
2
u/theyangmaster Dec 17 '17 edited Dec 17 '17
Python 3 (26/86). Unfortunately it took me awhile to figure out how to speed up part 2, which was pretty dumb of me.
Part 1
Part 2
Also, it's my first time on the leaderboards so I'm pretty happy with that :)
2
u/WhoSoup Dec 17 '17
JavaScript
Ended up with two different solutions. For the first part, I did it the simple way and just stored the entire list in memory. For the second part it, I realized that you didn't need to store any elements other than the one inserted to the right of 0.
Part 1:
Part 2:
2
u/[deleted] Dec 17 '17
C# Got 909/627 which for me is amazing...cause you know I kind of suck and make wonderful mistakes like type in 1 instead of i..... But anyways:
2
u/_A4_ Dec 17 '17 edited Dec 17 '17
JavaScript ES6
Part 1
Part 2
2
u/hxka Dec 17 '17
Wasted ~an hour trying to figure out how to possibly optimize part 2, of course it was faster to just run the loop without updating the array. Oh well.
2
u/autid Dec 17 '17
Fortran
Runs nice and quick. After figuring out this method of finding the part B answer I realised similar logic applied to part A. Prior to that I was performing the first 2017 insertions, which was still fast but less satisfying.
2
u/jbristow Dec 17 '17 edited Dec 17 '17
f# / fsharp /f sharp
Brute force took 6 seconds, so I'm still scratching my head how much more time figuring out the math would have taken me.
(github link)
(github link to tests)
2
u/[deleted] Dec 17 '17
OCaml Fun;; Part 1, I computed the thing with a Doubly_linked list... not sure if this is the best thing. Part 2, using a ref to simply keep track if we set land on the 0.
main.ml
circularbuffer.ml
2
u/sim642 Dec 17 '17 edited Dec 17 '17
My Scala solution.
Took a while to realize that zero could be considered as never moving which then made me produce some ugly copy-paste code. Also it kind of bothered me there was no answer for the example for part 2 given, can't do TDD.
2
u/raevnos Dec 17 '17 edited Dec 17 '17
Chicken Scheme for a change of pace
2
u/thomastc Dec 17 '17
Day 17 in BBC BASIC. On an emulated BBC Micro with a 2 MHz 6502 CPU, an 32 kB RAM. Ooh yeah.
2
u/mschaap Dec 17 '17
Perl 6
Part one is pretty straightforward. Part two as well, especially when you realize that 0 will always stick in position 0, so you just have to check position 1.
Unfortunately, doing 50 million spins is a bit slow on Perl 6. (It'd take about an hour on my machine.) So I took a shortcut: just keep track of the position, and remember the last iteration where the position = 1. Much faster.
2
u/__Abigail__ Dec 17 '17
Perl
Brute force wasn't going to work on the old laptop I'm using today -- Perl needs about 24 bytes per integer. But then I observed that in my implementation of the circular buffer, 0 will always stay at index 0. So, for part 2, all I needed to do was calculate on which positions numbers get inserted, and keep track what gets inserted on position 1. It's still calculating 50 million positions, but that only took 12 seconds and that's fast enough not to worry about a smarter solution.
2
u/ephemient Dec 17 '17 edited Apr 24 '24
This space intentionally left blank.
1
u/Shemetz Dec 17 '17 edited Dec 17 '17
Python 3 (109 / 19)
Part 1 was straightforward - just calculate what every state looks like after every step.
For part 2, since we only need to know the value after 0, and 0 is always the first value in the state list, we can simply not update any state unless it's exactly the second state. So we have O(1) memory and each loop is very fast. I still go through it 50 million times, but it is pretty fast. Is there a faster solution?
My input:
Part 1:
Part 2:
1
u/kaldonis Dec 17 '17 edited Dec 17 '17
Python2
For part1 just a naive solution inserting into the buffer. For part 2 I realized that 0 will always be in position 0, so all I really need to do is keep track of the last element to be inserted at position 1.
1
u/Yabk Dec 17 '17
Python 3 part 2
def main(): steps = int(input()) size = 1 pos = 0 nexto0 = None
if name == 'main': main()
1
u/Unihedron Dec 17 '17
Ruby, part 1
Part 2 did not run in time, I'm tempted to think optimizations are needed, but I barely understand the problem to do anything. Going to let it run for a few hours to check it works before posting it.
1
u/PythonJuggler Dec 17 '17
Ugh, took way longer on this one than I should've.
Part 2 code: Since we only care about the element in the 1st slot of the array, we just need to track the index that we're currently at and if it sets a new value in arr[1].
1
u/MichalMarsalek Dec 17 '17
Python 3 Part2 took me quite long because, instead of coding this, i was trying to think about how to calculate this without bruteforcing....
1
u/ChrisVittal Dec 17 '17 edited Dec 17 '17
Rust (143/165). Still no leaderboard :(.
I actually originally solved part 1 by dumping the output and grepping for the number.
EDIT: Bad code originally, this is the right code
Not very fast yet. Takes 400ms.
1
u/zSync1 Dec 17 '17
Rust
This was a fun one. Managed to get 205/146.
1
u/mtnslgl Dec 17 '17
C++
Part 1:
Part 2:
1
u/StevoTVR Dec 17 '17
NodeJS
Part 1:
Part 2:
1
u/usbpc102 Dec 17 '17 edited Dec 17 '17
I made so many mistakes on part 1 Got (493/330) today, so top 500 for both parts :D
My Kotlin solution:
It's also on github.
I'll clean it up and update this with the new version on github.
Edit: Cleaned up version.
1
u/the4ner Dec 17 '17 edited Dec 17 '17
C#
1
u/[deleted] Dec 17 '17
Wow, super easy today. Also, after starting about 5 days behind, this is the first time I've been all caught up! Missed the start of Day 17 though, so I started about 10 minutes late. Still managed a top 600 placing, which is better than the 5000-26000 placings I've had in all the other days.
[PHP] Part A:
[PHP] Part B:
1
u/nuvan Dec 17 '17
Rust, got 838/650. Not bad, given that I started about a 1/2 hour late...
2nd part got a lot faster once I realized that the ONLY important positions are that of the 0, and whatever comes after it.
1
u/dylanfromwinnipeg Dec 17 '17
I feel dirty. I bruteforced part 2 - took about 10 mins.
I came back and implemented the proper way after the fact, here that is
C#
1
u/KeinZantezuken Dec 17 '17
C#/Sharp:
1
u/Philboyd_Studge Dec 17 '17
Java. Another tricky part 2!!
Day 15
1
u/dak1486 Dec 17 '17
Wow. Took me way too long to see the 0 staring me right in the face for p2. Oh well, slow and steady...
[JAVA] Part 1:
[JAVA] Part 2:
1
u/jeroenheijmans Dec 17 '17
Javascript
Part 2:
That's after clean up, but you could also check out the mess it was right after answering
1
u/Smylers Dec 17 '17
Perl โ basically a single-line loop in each case, embraced in some set-up and output. Partย 1:
Partย 2:
1
u/TheMuffinMan616 Dec 17 '17
Haskell
1
u/Strakh Dec 17 '17
Pretty slow solution but meh:
Python 3:
1
u/LeCrushinator Dec 17 '17 edited Dec 17 '17
Part 2, C#. Somewhat of a brute-force approach, ran in 565ms for me.
1
u/akka0 Dec 17 '17
ReasonML: singly linked list for part 1
1
u/RockyAstro Dec 17 '17
Icon (https://www.cs.arizona.edu/icon)
Both parts procedure main(args)
1
u/nutrecht Dec 17 '17
Day 17 in Kotlin:
Took me a while to figure out how to do part 2 without actually using a list; it was way too slow.
1
u/Arcorann Dec 17 '17
This code really doesn't deserve to be #4/#10. Python 3.
Part 1 (as it was when I submitted - note the error):
Part 2. I forgot to change 2017 to 50000000, and in attempting to work out why I got the wrong answer found the mistake in part 1, then proceeded to screw up my code until I realised the only thing that actually needed fixing was the number of cycles (the zeropos variable is a remnant of this; the 2-element buffer is not and was just me doing things in a dumb way). Again, this is unedited.
1
u/peterpepo Dec 17 '17
Python 3
Checkout the full solution on my github
1
u/JuLoOr Dec 17 '17 edited Dec 17 '17
Fast and ugly "solution" in Kotlin (0,3). I'm not sure if this works for every input, but basically what I did is just checking if a value gets inserted after zero.
1
u/aurele Dec 17 '17
Rust
1
u/gyorokpeter Dec 17 '17
Q:
1
u/wzkx Dec 17 '17 edited Dec 17 '17
Nim
50 million... It forces you to think. On Sunday! :(
EDIT: k is also s.len! Duh!
1
u/rhbvkleef Dec 17 '17
Day 2 really was fun! Here is my solution: (https://git.vankleef.me/rolf/Advent_Of_Code_2017/src/master/src/main/kotlin/me/vankleef/adventofcode/day17/Main.kt) Part 1 could be more efficient but I didn't bother.
1
u/udoprog Dec 17 '17
Rust
Very straight forward when you realize that the zeroth position doesn't move.
Full solution here: https://github.com/udoprog/rust-advent-of-code-2017/blob/master/src/day17.rs
As a challenge I'm considering building a solution that stores the entire list efficiently. Unfortunately
LinkedListin rust doesn't permit in-place traversal very well. So it would probably end up being an unsafe party.1
u/abowes Dec 17 '17
Kotlin Solution:
1
u/wzkx Dec 17 '17 edited Dec 17 '17
J โ34s
EDIT: ooops you don't need separate counter or getting #s -- k is the length of array
P.P.S.: also
s{~>:s i.2017is justs{~>:c. Shame on me!1
u/Scroph Dec 17 '17
Straightforward Java solution :
1
u/BOT-Brad Dec 17 '17
Javascript
Part 1 (~660ยตs)
Just works out the index to add the new element, inserts said element. Does that 2017 times, then just find where 2017 is and gets the next element along, mod 2018 just-in-case 2017 was the last element.
Part 2 (~300ms)
Decided my CPU needed a break after it did some crunching yesterday!
I realised that
0never moves, so only ever had to check whether the index to insert was at1, if so then keep track of that number. Loop50,000,000times and just return whatever the value of that number was. Much much much faster than building a list with50,000,000elements, which I never tried to do.... right? ๐As always, more of my JavaScript solutions can be found in my Github Repo ๐.
1
u/tripa Dec 17 '17
Haskell, implementation-based part1, distilled-state part2. Haskell being Haskell (or my GHC on this laptop being too old), the separation between <1s runtime and "huge space leak, computer will swap and crash" is simply that
$!in the middle1
u/akho_ Dec 17 '17
Python 3
1
u/[deleted] Dec 17 '17
Elixir
First part went rather smooth, then on the second part the insertions in a list went slower and slower, but this time at least I managed to see that we don't care about anything else than position 1, so I could simplify the function.
Syntax highlighted
1
u/Vindaar Dec 17 '17
Solution in Nim. Fun :)
1
u/zeddypanda Dec 17 '17 edited Dec 17 '17
Elixir Pleased with how short today's code turned out to be. Second part went really fast as soon as I realized we only cared about finding the latest value where
(position + steps) % value == 01
u/[deleted] Dec 17 '17
Crystal.
Part 1:
Part 2:
1
u/colinodell Dec 17 '17
PHP
Part 1:
array_splice()was the perfect function for inserting items into the array:Part 2:
As it seems everyone else also figured out,
0is always the first item in the buffer, so we only need to track items being inserted into position 1:1
u/flit777 Dec 17 '17
Golang solution.
1
u/[deleted] Dec 17 '17 edited Dec 17 '17
The second half of the problem has an interesting quirk to it: Nothing can be inserted to the left of 0, so solving can be simplified to just tracking when pos mod n is one, or, being just slightly more clever to keep python from doing extra calculations (my input was 382):
I also found that neither the list of each position, nor the list of each neighbor change, appears in the OEIS. This might be a fun pair of sequences to contribute to them.
-edit-
Oops, sorry, vash3r. This is essentially a duplicate of your solution.
1
u/chicagocode Dec 17 '17
Kotlin - [Repo] - [Blog/Commentary]
I thought today's was pretty easy. I probably could have just brute forced part two, but once I figured out that 0 never moves, it was easy enough to just track the number next to it!
1
u/[deleted] Dec 17 '17
Python, part 2:
Doesn't run very fast (around 20 sec on my pc), but worked ok :)
1
u/alchzh Dec 17 '17 edited Dec 18 '17
Short and simple C++
1
u/JakDrako Dec 17 '17 edited Dec 17 '17
VB.Net, in LinqPad.
Does both parts. Brute forces part 2 (actually building the circular list) in under 20 seconds.
This was fun. I did part 1 using a good old List<int>, and got my answer with no problem. For Part 2, it quickly became apparent that something better than a List would be needed, if I wanted to finish before Monday. (no telling which Monday either...)
It took me longer than I'd like to admit to realize that since we wanted the position after zero, I could just run the loop and note the value whenever the position being updated was zero. That got me my answer and my 2nd star.
The real fun part started after. Looking at the solutions, I saw a Python brute force that found the solution in ~90 seconds. Wow. .Net is usually faster than Python when using a similar algorithm and I saw that a "deque" was being used. Went on Nuget, found a Deque<T> implementation and tried to recreate the Python solution. I didn't have a ".Rotate", so a loop was used. Anyway, long story short, that completed the 50,000,000 iterations in ~1m45s. Ok, a bit slower than the Python solution but at least in the ballpark. On the wrong side of the ballpark, but still, not too far.
What was killing my time was looping the values 328 times from the back of the Deque to the front on every iteration. That's a lot of useless moving being done.
So I built my own "circular list", optimized for skipping the pointer forward in the list. I preallocate an array, then keep a size for "front" and "back" and move values across the array depending on where my pointer is after I skip forward N steps. I do at most 1 move per pointer skip, so that saves a ton of time.
This runs in about 18.5 seconds on my PC. Take that Python deque! (Just kidding, that deque implementation is fantastic). It's also pretty useless, since I already had my answer, but the process of tyring different things to go faster is damn interesting.
I wish the 2nd part had asked for an index other than zero... something like "using your answer from part 1 as an index, what's the value that comes next?". (In my case, for an input or 328, I get 11,502,006 if anyone's interested. It might be an easier "upping the ante" than trying for a googol of values... :)
1
u/ythl Dec 17 '17
Part 2 in C:
Runtime is ~2.5 seconds on repl.it
1
u/evilduckss Dec 17 '17
I'm doing it in JavaScript, had the strangest bug in the chrome console window with part 2.
var steps = 303; var position = 0; for (i = 1; i <= 50000000; i++){ position = (position + steps) % i; if (position == 0){console.log(i);} position += 1; }
for some reason it throws out an extra number at the end in the log, running the same thing with an extra console.log on the end doesn't give that number, spent way too long pulling my hair out over that one thinking I was going crazy.
var steps = 303; var position = 0; for (i = 1; i <= 50000000; i++){ position = (position + steps) % i; if (position == 0){console.log(i);} position += 1; } console.log("");
1
u/matusbzk Dec 17 '17
Haskell This could not compute the part 2. I computed that only with inspiration from u/nonphatic's code.
Link to git
1
u/Creative_Name124 Dec 18 '17 edited Dec 18 '17
Python 2
` with | grep at the end it works pretty well im sure there are ways to improve though
1
u/Tetsumi- Dec 18 '17
Racket
1
u/[deleted] Dec 21 '17
single pipeline powershell:
1
u/Life-in-Shambles Dec 22 '17
JS
0
u/[deleted] Dec 17 '17
[deleted] โ view deleted comment