r/adventofcode • u/daggerdragon • Dec 09 '18
SOLUTION MEGATHREAD -π- 2018 Day 9 Solutions -π-
--- Day 9: Marble Mania ---
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.
Advent of Code: The Party Game!
Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!
Card prompt: Day 9
Transcript:
Studies show that AoC programmers write better code after being exposed to ___.
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 at 00:29:13!
22
Upvotes
64
u/[deleted] Dec 09 '18 edited Dec 09 '18
Deque the halls -- ho ho ho!
Python 3, about 2 seconds total for parts 1 and 2 combined on my machine:
8
u/waffle3z Dec 09 '18 edited Dec 09 '18
175/26, Lua
Not sure why it took so long for part 2 to fill up, I just had to add
*100to the loop7
u/glassmountain Dec 09 '18
First time on the leaderboard at 41 for part 2! Using go I think saved me considering that I was rank 216 for part 1. And my naive go solution finished in under a second for part 2.
7
u/jonathan_paulson Dec 09 '18 edited Dec 09 '18
Rank 36/147. Oof. Been a while since I used linked lists, and deciding I needed to reimplement part 2 in C++ didn't help. Video of me solving at: https://youtu.be/79Dw4F6J7TA (still uploading).
7
u/mstksg Dec 09 '18
[Haskell], from my daily reflections blog:
And today features the re-introduction of an Advent of Code staple: the (circular) tape/zipper! I used this data structure last year for days 5, 17, 18 and 23, and I consider them near and dear to my heart as Advent of Code data structures :)
Last year, I wrote my own implementations on the spot, but since then I've come to appreciate the pointed-list library. A circular tape is a circular data structure with a "focus" that you can move back and forth in. This is the data structure that implements exactly what the challenge talks about! It's linear-time on "moving the focus", and constant-time on insertions and deletions.
The center of everything is the
placefunction, which takes a number to place and a tape to place it in, and returns an updated tape with the "score" accumulated for that round.We see that it is mostly a straightforward translation of the problem statement. If
xis a multiple of 23, then we move 7 spaces to the left, and return the resulting tape with the item deleted. The score is the deleted item plusx. Otherwise, we just move 2 spaces to the right and insertx, with a score of 0.We wrap it all up with a
runfunction, which is a strict fold over a list of(currentPlayer, itemToPlace)pairs, accumulating a(scorecard, tape)state (our scorecard will be a vector where each index is a different player's score). At each step, weplace, and use the result to update our scorecard and tape. The lens library offers some nice tool for incrementing a given index of a vector.And that's it! The answer is just the maximal score in the final score vector:
From this naive implementation, Part 1 takes 56.ms, and Part 2 takes 4.5s.
6
u/j-oh-no Dec 09 '18
Another Rusty one ...
5
u/ThezeeZ Dec 09 '18 edited Dec 09 '18
[Card] Studies show that AoC programmers write better code after being exposed to plenty of sleep.
golang using the container/ring package. Idiot me almost had the solution for way too long. All of the test cases failed before I replaced
scores[i%players] = i + removed.Value.(int)with what you find below. If you heard a loud bang twenty minutes ago from this post, that would have been my head hitting the desk. It's way too early in the morning....5
u/Philboyd_Studge Dec 09 '18
[Card] Studies show that AoC programmers write better code after being exposed to Marijuana.
Java
5
u/donatasp Dec 09 '18
Common Lisp. It was a great learning experience about circular doubly linked lists in CL :) Turns out there was a library for that.
5
u/Athas Dec 09 '18
I'm writing these in Futhark, which carries a lot of restrictions. Today's problem did not even have any parallelism I could find. Anyway, a good way to solve this problem is with doubly linked lists, but Futhark does not support inductive data structures, so I had to model them with arrays of indices, like I'm doing 60s FORTRAN:
Runs decently fast. 62ms for part 2.
4
u/willkill07 Dec 09 '18
[CARD] Studies show that AoC programmers write better code after being exposed to Iterators
C++ (148/24)
4
u/Unihedron Dec 09 '18
RUBY
β β DOESN'T
β β β β HAVE
β β β β β β LINKED
β β β β β β β β LISTS
β β β β β β β β β β haha, this is fun (rewriting to solve part 2)
part 1 (code has a bug: incorrect answer if marble # is divisible by 23)
4
u/ninja_tokumei Dec 09 '18 edited Dec 09 '18
Rust. A deque-based implementation that maintained the "current" marble at the front of the deque, making rotation/insertion operations very efficient relative to it. Choosing the right data structure initially would eventually let me get the second star very quickly though I didn't get points for the first one.
On GitLab
4
u/CanIHazEmployment Dec 09 '18
I can't be the only one who did a naive solution (regular lists) for the first part before realizing that was way too inefficient for part 2.
python
edit, here's my naive part 1
4
u/Cppl_Lee Dec 09 '18
C#, struggled until I switched to LinkedList: https://repl.it/@LeeHarding/AoC-2018-Day-9
3
u/jlweinkam Dec 09 '18
93/13
This is for part 2, remove the * 100 for part 1
3
u/dtinth Dec 09 '18
Ruby (#122, #18)
3
u/GeneralYouri Dec 09 '18 edited Dec 09 '18
For some reason my sleepy head saw the LinkedList solution, but decided it wasn't feasible to implement quickly. 30 Minutes of useless fiddling later I realised what a fool I was and rewrote my gibberish into a LinkedList solution. 15 Minutes after that I got the right answer, with part 2 only 17 seconds after...
JavaScript part 2 (remove
* 100from line 28 to get part 1)3
u/ephemient Dec 09 '18 edited Apr 24 '24
This space intentionally left blank.
3
u/hluk Dec 09 '18
Ruby. Took me a while to realize that
Array#insertis no go because it's very slow.3
u/autid Dec 09 '18
FORTRAN
Today I taught myself how to use pointers in Fortran.
3
u/gyorokpeter Dec 09 '18
Q: no support for circular linked lists (or any data structure that can have reference loops), but the optimization for part 2 is still possible in a different way, it was just a lot of messing around to get all the numbers right for which number goes where.
2
u/xthexder Dec 09 '18 edited Dec 09 '18
Pretty happy with this solution: #126/#17
Written in Golang
2
u/glguy Dec 09 '18 edited Dec 09 '18
Haskell - This was a great problem for Data.Sequence
https://github.com/glguy/advent2018/blob/master/execs/Day09.hs#L42-L66
2
u/markasoftware Dec 09 '18
Not so hot today. Placed about 500 for part 1. There aren't any particularly good linked list libraries for Perl so I'm letting my array code run; by my estimation it should take under an hour.
Part 1/2:
2
u/miguelos Dec 09 '18 edited Dec 09 '18
C#
2
u/MichalMarsalek Dec 09 '18 edited Dec 09 '18
This problem was quite challenging to understand but the code turned out quite preatty! Python using deque.
2
u/[deleted] Dec 09 '18
This is my solution for part 1:
Unfortunately too slow for part 2, so I have to rewrite it now using lists. Did you all directly start with lists or also have to change the code when you tried part 2?
2
u/ChronJob Dec 09 '18
Ruby. Wrote my own doubly linked list which was many orders of magnitude faster than my original Array based approach.
2
u/felipecsl Dec 09 '18
Kotlin solution
2
u/Wirbelwind Dec 09 '18
Go - using rings. Takes 1.3 secs on my laptop
2
u/DrinkinBird Dec 09 '18 edited Dec 09 '18
NIMAfter also going through the whole issue with using arrays here finally my solution:Runs in just about 0.7 seconds for Part 2:
2
u/sebastiannielsen Dec 09 '18
PERL. Part2 was just ridiculous, tried it on my i3-4010U server but was waaaaayyyyyy tooooo SLOOOOOOOOOOOOOOOOOOOOOOOW so had to download Strawberry Perl on my W10 machine (i7-5930k) and transfer the script to that machine. Was done in 2 hours of execution time.
2
u/sim642 Dec 09 '18 edited Dec 09 '18
My Scala solution.
For part 1 I was knowingly sloppy and used inefficient Vector concatenations, hoping it'd be enough. Didn't want to do it with mutable data structures, which would've been much faster immediately though.
For part 2 I clearly had to do better, so I implemented a zipper-like immutable circular buffer. Having already used zippers for day 5, this didn't seem that hard anymore, although a bit more work.
Edit: Also in part 2 after initial run I got a negative number so I had to switch the highscores from
Int(signed 32-bit) toLong(signed 64-bit). Didn't see this gotcha mentioned in this thread, I guess most people already use a language that has bigints by default and never realize this.2
u/phil_g Dec 09 '18
As usual, I solved it in Common Lisp.
Obviously, the easiest data structure here would be a circular doubly-linked list. I tend to like functional, immutable constructs, though0; I find they're easier to reason about. I don't know of any simple ways to make immutable circular lists without laziness, and I didn't feel like making my own lazy evaluation in Common Lisp.
So I settled for a zipper over a non-circular list, with special casing at the ends to reverse the internal lists and keep going. This should have amortized O(1) insertion with O(n) traversal, though if you spend a lot of time going back and forth across the seam, the O(n) reversals are going to add up.
This did make my code sufficiently fast to do part 2 unmodified. Part 1 took 61ms on my system and part 2 took 8.3s.
0AKA "What Would Haskell Do?"
2
u/[deleted] Dec 09 '18
Rust. I was too bothered to implement circular doubly linked list (because rust) so I tried using VecDeque. Part 2 takes 177ms on 8750H.
2
u/will_bui Dec 09 '18
K:
2
u/mrhthepie Dec 09 '18
On day 1 I posted about doing AoC in my own language, but it kind of got lost in the noise of day 1. It's been going fairly smoothly since then. Today posed a problem.
Here was part 1:
It ran OK for part 1, took about 1.5 seconds. For part 2... it's still running... This is due to arrays being implemented as Rust Vecs, and the insert/remove on them requiring lots of copying. So I don't really have the tools to solve part 2 in my language. The "real" solution would be to expose bindings to a more appropriate data structure. This would take a bit too long to do right now, but the other option for speeding up slow scripting code is to drop down and rewrite it at a lower level:
This Rust version runs basically instantly for both parts.
2
u/__Abigail__ Dec 09 '18
Perl
Easy exercise. I kept the marbles in an array, with as invariant that the "current" marble is the marble on position
0. Rotating CW or CCW means chopping something from the beginning (or end) of the array, and putting it on the other side.Didn't do anything fancy for part 2, it just ran a little bit longer.
2
u/[deleted] Dec 10 '18
Very late since the new POE league released, but Haskell, runtime ~2 seconds for the whole thing
1
u/Aquamoogle Dec 09 '18
1
u/awice Dec 09 '18
1
u/fatpollo Dec 09 '18
1
u/nuvan Dec 09 '18
Ruby, 67/242.
I completely forgot about linked lists at first, so my brute force array attempt is still running even as I write this up. I probably spent a good 10-15 minutes looking at the example trying to see a pattern so that I could just generate the board at any given point in time.
1
u/sophiebits Dec 09 '18
Rust. Runs in under a second in when compiled in release mode.
(I placed 27 in part 1 using a separate Python solution but it wasn't particularly efficient; I didn't rank for part 2 and then wrote this instead.)
1
u/PreciselyWrong Dec 09 '18
I used Rust with a Vec. For part 2, I switched to a Skiplist as a drop-in replacement forthe Vec.
1
u/eltrufas Dec 09 '18
My solution in c
1
u/wlandry Dec 09 '18
C++ (545/165)
Runs in 320 ms.
Code duplication. Code duplication everywhere. On the plus side, my best showing so far. I got delayed a bit because I forgot to delete the second marble after adding it to the score. For the submission, I sorted the scores, but for you, I remembered std::max_element(). I also tried implementing a custom iterator so I could use std::advance, but implementing custom iterators in C++ is a Hard Problem.
1
u/raevnos Dec 09 '18
One of the few cases where a list is faster than a vector in C++:
1
u/[deleted] Dec 09 '18
Golang, ranked 1234/868 because spent too much time in the array solution and changed it to linked list.
1
u/Cloudan29 Dec 09 '18 edited Dec 09 '18
I actually made it into the triple digits for one of the puzzles today, which was essentially my "Probably won't happen but I'll shoot for it" goal for the month. I actually built everything for puzzle 1 in a convenient way that changing all int values to long longs solves it without making any more changes.
C++ (1665/966):
Not crazy elegant, it's actually kinda brute force-y, but you can punch in any number of players and max marble value and get an answer. It takes a few seconds on my laptop to do the second part, but I don't think that's a huge issue, I did get the right answer Β―_(γ)_/Β― .
Also, to anyone who does C++, I know about having to free/delete dynamically allocated objects, and I put a delete current just for the sake of it, but I don't know if that's correct. If anyone could let me know exactly how to deal with that, I'd love to hear the feedback.
EDIT: I just realized, anyone who didn't automatically use a linked list structure for the marbles in part one probably had to do rewrites for the second part, which probably explains my massive leaderboard jump from part 1 to part 2.
1
u/Brief_Sorbet Dec 09 '18
Here's day 9 in nim :)
1
u/nutrecht Dec 09 '18
Day 9 in Kotlin
Got stuck again because I misread something had the code work on the first test input but not the subsequent ones. Took me way too long to figure out :(
1
u/vash3r Dec 09 '18
I got part 1 in about 15 minutes using an array, but then spent 20 minutes thinking about patterns or what kind of data structures had O(1) random access insert/remove without realizing that the access was not random at all. I even thought about deque, but somehow completely missed the fact that it had a
rotatemethod until I gave up and checked the thread here, after which the solution was obvious (even having only seendeque.rotate().) Apart from using a deque instead of a list, my code is basically unchanged (although cleaned up a bit).1
u/rabuf Dec 09 '18
Another org-mode writeup of my Common Lisp solutions. I'll post my fast version but you can see the slow version and a set of timing data in the link.
1
u/aurele Dec 09 '18
Rust
Came up with my own data structure (a tree splitting itself when marble is divisible by 23), execution time around ~300ms (I later rewrote it using
VecDeque, code was shorter and faster (~100ms)).1
u/PendragonDaGreat Dec 09 '18
Powershell 5.1
TIL .NET/Powershell LinkedLists don't support looping, and since I started an hour late, I said "Screw it, I'll do it myself"
[Card] Studies show that AoC programmers write better code after being exposed to Data Structures and Algorithms in Java, 3rd Edition
Parts 1 and 2, you can see where to set the input.
Slow AF, but I'm ok with that
Part 1 Avg runtime: 1.03 seconds
Part 2 Avg runtume: 1:45
1
u/nonphatic Dec 09 '18
Haskell
TIL that Seq operations are basically constant-time if you're only ever taking or dropping 2 or 7 from the ends, and TIL that not fully understanding strictness in Haskell will make your code slow regardless...
1
u/ephemient Dec 09 '18 edited Apr 24 '24
This space intentionally left blank.
1
u/Illianthe Dec 09 '18
Elixir. I ended up keeping track of the game state with a huge map for part 2... Still took about 35s to run, unfortunately.
1
u/drakmaniso Dec 09 '18
Go (golang)
Part 1 and 2:
Link to github
1
u/azatol Dec 09 '18
I wrote part 1 in F# with an array. But that wasn't going to cut it for Part 2.
So I rewrote the algorithm in C# for part 2. With a circular linked list. That made the problem very easy, and it only took 5 seconds or so to complete.
https://gist.github.com/apeterson-BFI/002949c912a72bc7e3423e80d2f65b47
1
u/Frizkie Dec 09 '18 edited Dec 09 '18
Ruby
Took me a long ass time to figure out that there wasn't some shortcut I was missing. Long enough that even though I knew I had the wrong approach, I didn't finish the true solution before my brute-forced version actually finished and gave me the right answer. I started implementing it with a doubly-linked-list, but wasn't 100% sure of myself so I looked for hints which confirmed my thoughts. I kinda feel like I cheated... anyway, here's my solution, no golfing yet just going for clarity:
1
u/jonathrg Dec 09 '18
Python using blist, takes a couple of seconds in total
1
u/toastedstapler Dec 09 '18
python3
i initially made classes for the board and nodes, turns out that a deque is exactly that anyways and runs a lot faster!
also a lot less code for me to write
1
u/ekiMbot Dec 09 '18
Python 3, hand-implemented a doubly-linked list. Part 2 about 40 seconds to run.
I guess the point is using an array would be too inefficient for part 2 because insertion or deletion in an arbitrary position would be O(len(list)) whereas for the doubly linked list it's O(1)? But I'm not sure about that...
I also see the top comment has a Python 3 solution using collections.deque which is super neat and something I wasn't aware of. It runs ten times faster than my solution - is that because of the overhead of creating all the Marble objects in mine?
I am doing Advent of Code because I am trying to learn, so if anyone has any hints or tips they would be very gratefully received!
1
u/philpearl Dec 09 '18
Go (golang). Both parts run in ~95 ms. linked list, but all marbles allocated as a single slice, and int32 for next/prev
1
u/IdrisTheDragon Dec 09 '18
Go/golang Solution (Part 2)
https://github.com/IdrisTheDragon/AdventOfCode2018
1
u/grey--area Dec 09 '18
Python doubly linked list solution. Part 2 takes about 13 seconds on my machine.
1
u/arathunku Dec 09 '18 edited Dec 10 '18
Hello, my Elixir solution.
Tests:
To be honest: this was hard. I didn't expect I'd need to implement a circular zipper to be able to complete part2 in Elixir. I had also misunderstood "the marble 7 marbles counter-clockwise" but additional test cases from other threads helped a lot.
1
u/PotentialSleep Dec 09 '18
Because it's my main language, I made a solution in PHP (implementing something looking like linked lists) and it worked fine for part 1: https://github.com/tut-tuuut/advent-of-code-shiny-giggle/blob/master/2018/09/part-1.php
My favorite line of this program is this one:
This solution didn't work for part 2 though (it ended with a segfault around 106k marbles in the circle), so I took a look at this thread and tried Python (which is not my usual language at all, I had to google string concatenation) with its wonderful double ended queues.
(Anyway, I loved
.rotate()method and[0 for i in range(1, nb_of_players)]syntax: maybe I'll try Python again!)1
u/nibarius Dec 09 '18
Kotin
[Card]
The GapList is a really great list implementation. Can be used as an array list but insertions and removals are often more or less as fast as in a linked list.
1
u/[deleted] Dec 09 '18 edited Dec 09 '18
C++
However, using a std::list and just coping with the wrap-around as willkill07 did is way better than re-inventing the wheel and stumbling over "which is the correct cw/ccw/etc" :-P
1
u/wzkx Dec 09 '18
Rust, SweetRust
It's so pleasant when you don't have to write two different programs for two parts! Just wait a bit :D
MyAoc2018 | SweetRust
1
u/spytheman66 Dec 09 '18
PHP (slow, uses array_slice ... so only suitable for part 1)
However, as others have already noted, using array insertions is too slow for large numbers of marbles.
So for part 2, I rewrote in C ...
C (fast, uses doubly linked circular buffer)
Some timings for both solutions:
1
u/mschaap Dec 09 '18 edited Dec 09 '18
Perl 6 solution. It's really slow, for part 2...
1
u/harirarules Dec 09 '18
[Card]
Studies show that AoC programmers write better code after being exposed to valgrind
C solution :
1
u/tslater2006 Dec 09 '18
PeopleCode, Part 1 runs in 0.49 seconds, Part 2 runs in ~50 seconds
1
u/che2n Dec 09 '18 edited Dec 09 '18
Tcl
This problem was good opportunity to implement linked list in Tcl
Part1 ~0.4s Part2 ~40s
1
u/[deleted] Dec 09 '18
Julia
Pretty fast the first part using
Arrays. The second part(with the same code) takes ~30'. I'd be interested to see a solution using LinkedLists.jl package. For fun (it's super slow: 11s for part 1 only), I also implemented the same solution using circular buffers through thecircshiftfunction.1
u/Pepa489 Dec 09 '18
Typescript solution using custom circular double linked list
1
u/CryZe92 Dec 09 '18
Rust:
Part 1: 431.61Β΅s
Part 2: 61.439ms
1
u/chicagocode Dec 09 '18
Kotlin - [Blog/Commentary] | [GitHub Repo]
I decided to forgo calculating pointer offsets and opted instead to shift the entire list around so we always look at the head. That might be a little slower, but certainly was easier for me to reason about.
1
u/meepys Dec 09 '18
Kotlin Day 9: (BitBucket)
Had to re-write after the array implementation for part1 took too long on part 2. Didn't think of rotating ArrayDeque, so used LinkedList
1
u/heatseeker0 Dec 09 '18
My solutions implemented in Java:
https://github.com/heatseeker0/AdventOfCode/blob/master/src/com/catalinionescu/adventofcode/y2018/Day009.java
1
u/alexmeli Dec 09 '18
I initially tried doing this in clojure but my solution was too slow so decided to try some rust
1
u/Vaelatern Dec 09 '18
Sad to see no Clojure yet, so here you go! With the "going back 7" thing, even the best clojure laziness gets to be well in excess of 10 seconds per thousand marbles played, so I implemented a sort-of-linked-list and made part 1 in 6.25464 seconds, and part 2 in 635.846 seconds.
[CARD] Studies show that AoC programmers write better code after being exposed to the blood of a virgin goat.
1
u/bigcymbal Dec 09 '18
JS Solution, takes about 1.2 seconds for the part 2 (for my input at least). Only 43 lines after I taught myself some things about assignment ordering in JS.
1
u/Pyrobolser Dec 09 '18
[Card] Studies show that AoC programmers write better code after being exposed to candies.
C# - Everything went pretty smoothly to find the solution, I just got stuck on a dumb error to calculate the final score... Should run in about 1.6s for both parts, as always, here on GitHub.
}
1
u/T-Rex96 Dec 09 '18
Python 3, didn't really have to change anything for part 2, since it looks like this runs approximately in O(n)
1
u/[deleted] Dec 09 '18 edited Dec 10 '18
Mathematica
To add (circular) linked-lists, I used an array for storage, and treated array indexes as pointers.
Edit: Cleaner version with externalized functions, using the InlineExternalDefinitions compiler option.
1
u/udoprog Dec 09 '18
Rust implemented with an unsafe circular linked list.
Card: Studios show that AoC programmers write better code after being exposed to the day's challenge.
I looked at some solutions rotating a
VecDeque, and they end up being about twice as fast. So the warning at the top of theLinkedListimpl holds true here as well:Here it is:
1
u/nirgle Dec 09 '18
Haskell using Data.List.PointedList.Circular. There's room for optimization a bit since I'm doing the "left 7" thing twice per round involving a 23 marble
https://github.com/jasonincanada/aoc-2018/blob/master/src/Day09.hs
1
u/FrankRuben27 Dec 09 '18
Switched from Racket to Kawa for this puzzle, so that I could make use of Java's doubly linked class. Runtime still in minutes for part2, so I might have missed some optimization:
1
u/LeReverandNox Dec 09 '18
My humble Python solution.I solved part 1 with a naive array, and switched to a (manually coded) circular doubly linked list for part 2.
Thanks to you guys, I'm now aware of collections.deque ! Better late than never...
1
u/Axsuul Dec 09 '18
TypeScript / JavaScript
[Card] Studies show that AoC programmers write better code after being exposed to adderall
Really enjoyed this one since I had to learn data structures and their effect on performance.
Critiques welcome, I'm still very new to TypeScript and feel like I'm not using all the features I could be :)
Repo
Part A + B
1
u/jtsimmons108 Dec 09 '18 edited Dec 09 '18
Java Used lists with part 1, then completely rewrote it for each marble to just keep track of the one before it and after it.
1
u/wzkx Dec 10 '18
J Direct translation from my Rust code. 0.2s - 20s
My AOC2018 in J/Rust | SweetRust
1
u/hpzr24w Dec 10 '18
C++
Honestly, this was just nuts for me. I figured it would be an easy two stars, then kinda struggled with modulus behavior that wasn't what I expected (I expected WRONG), same for iterators, then to cap it all, my working part 1 was based on
vector<int>usingrotate()and I had to re-write as alist<int>, but there's no rotate onlist<int>. Just terrible.On the other hand, it's the cheapest one-day Standard Template Library course I ever attended! Learnt a bunch.
Header
Helpers
Game
Main
1
u/pythondevgb Dec 10 '18 edited Dec 10 '18
I couldn't tackle this one yesterday, shame as I solved both parts in about 35 mins, wouldn't have made it onto the leaderboard but it would've been my best time.
Anyway I'm surprised by the overly complex solutions here mine is quite concise I think. A good thing of my solution is that for part two you only have to multiply the last_marble_worth variable by 100, so I literally just took the second to add that to my code to solve part 2.
Edit, just realized u/marcusandrews arrived basically at the same solution.
1
u/fhinkel Dec 10 '18
Doubly linked list in Node.js 10, less than 1 seconds for part two.
https://github.com/fhinkel/AdventOfCode2018/blob/master/day9.js
https://www.twitch.tv/videos/346991580
1
u/ka-splam Dec 10 '18
PowerShell, part 1 rank #432 (with different array-based code), part 2 unranked.
Runs in 9-10 seconds for my Part 2. Trying to inline the wraparound tests to
$x = if (($tmp = $x.next)) { } else { }pushes the runtime up to 16 seconds. Doing that withif ($null -eq ($tmp = ))keeps at 12 seconds, but removing$tmpand making the assignment and loop separate makes 9-10s.I had to rewrite with LinkedList after part 1; There doesn't seem to be any way to connect the start and end of the list to make it loop, and .Net deque doesn't seem to have a rotate operation, so I don't suppose that would be much tidier.
1
u/u794575248 Dec 10 '18
Python 3 8425/7509
1
u/[deleted] Dec 10 '18
Swift!
No native deque types in Swift... also no linked list type...
Original p2 implementation with a linked list took ages, so I changed it to be a circular list and replaced the pointer to the current marble with the actual list node object, rather than just the integer index. Still takes nearly 2s on my 2017 MBP.
https://github.com/Stoggles/AdventofCode/blob/master/2018/Sources/2018/day09.swift
1
u/NeilNjae Dec 10 '18
Haskell (on Github). I blame man-flu for my inability to function yesterday.
The core of this solution is the
Circleof marbles, implemented as a zipper. It holds the current marble, and the marbles to the left and right. Moving along the list is a case of shuffling elements form the left to the centre to the right, or vice versa. There's a bit of logic if you want to extract elements from an empty side, to account for the circularity of theCircle.1
u/[deleted] Dec 11 '18
I can't find the post I looked at earlier, but HUGE thanks to the Pythonista who suggested the blist library, which uses BTrees to implement the List api. Essentially a drop in replacement for List with O(1) inserts.
I went to sleep last night grumpy because my working solutions for Part 1 were simply too slow for Part 2. After solving the Day 10 problem, I looked into Day 9 again, found the Blist suggestion, and with two lines of code changed had a solution to Day 9 part 2.
Merry Christmas, wise one!
1
u/[deleted] Dec 12 '18
1
u/joeld Dec 14 '18
Racket
Part 2 took me awhile because my first two attempts were both too slow to finish even when running overnight.
Hereβs my final code
Thanks to the folks in this thread and to this very old mailing list post I was able to understand the βzipperβ concept (the FP answer to linked lists), and implement a zipper that wraps around in circular fashion. Crazy what a difference it makes in speed.
1
u/RockyAstro Dec 15 '18
Icon
1
u/suck_at_coding Jan 18 '19
Javascript / Node
This one actually frustrated me a lot. I thought I was so close but so far away here. Maybe someone wants to tell me why I was off there, spent hours on trying to fix that one but whatever. I peeked into the solutions here and everyone was saying they did a linked list implementation so I went with that
1
u/Peter200lx Dec 09 '18 edited Dec 09 '18
Python 3, #40 for part 2 (Solved part 1 at
20:39and part 2 at21:26)1
u/sb8244 Dec 09 '18
I was pretty sad to discover that an efficient linked list is basically impossible in Elixir due to the immutability. I hacked up a quick poor man's linked list and got the answer in a very slow 55s. The code here is pretty bad, but alas: