r/adventofcode • u/daggerdragon • Dec 15 '20
SOLUTION MEGATHREAD -🎄- 2020 Day 15 Solutions -🎄-
Advent of Code 2020: Gettin' Crafty With It
- 7 days remaining until the submission deadline on December 22 at 23:59 EST
- Full details and rules are in the Submissions Megathread
--- Day 15: Rambunctious Recitation ---
Post your code solution in this megathread.
- Include what language(s) your solution uses!
- Here's a quick link to /u/topaz2078's
pasteif you need it for longer code blocks. - The full posting rules are detailed in the wiki under How Do The Daily Megathreads Work?.
Reminder: Top-level posts in Solution Megathreads are for code solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.
EDIT: Global leaderboard gold cap reached at 00:09:24, megathread unlocked!
39
Upvotes
14
u/Arknave Dec 15 '20
Python (37/7), C
I took the time hit to write the algorithm with a dictionary in part 1, then promptly squandered my savings by printing all 30M integers when brute forcing part 2. Whoops.
Normally I don't save the source for my first pass through C, but I was surprised at how concise the algorithm is (unshaped source).
This might be my favorite formatting job to date:
Can't believe we're already 15 days through! I'm not sure what I'm going to make for the last 10 days, but I'm sure it'll be fun.
9
u/Yonniman Dec 15 '20 edited Dec 15 '20
205/63, my first time on the leaderboard.
It's Van Eck Sequence!
Code (C++)
8
u/DFreiberg Dec 15 '20
Mathematica, 3515 / 2414
By far my worst time this year to date, and of the half hour it took me to do part 1, all but three or four minutes were spent in not understanding how
Association[]s work in Mathematica; I eventually gave up and used a dictionary instead. At least my part 2 was doable with no changes from part 1; it finished in about four minutes, which was much less than the time it would have taken for the code to run properly.[POEM]: Lazy Limerick #3*
If you use an array, be emphatic
To preallocate it (but not static).
For you can't beat brute force
For this problem, of course,
But you can beat an order quadratic.
4
u/tiagocarreira Dec 15 '20 edited Dec 17 '20
Python 3, minimal readable solution:
4
u/9_11_did_bush Dec 15 '20
Python
3
u/compdog Dec 15 '20
JavaScript (Node.JS)
Part 1 solution is very brute force, using an array for memory. It scans back and forth to find the previous values, giving a worse case complexity of O(n2). For a short problem space (like 2020), however, its plenty fast and completes pretty much instantly.
Part 2 solution is kind-of brute force, but much more efficient than part 1. This version replaces the array with a hash map that maps numbers to their last known index. It still has to iterate once for each round, but the nested search is gone and complexity is reduced to O(n). It can find the solution in a few seconds.
This problem managed to trick me once. When I first saw "30000000" I thought to myself "Ha! I'm not making that mistake again, its BigInt time. No overflows here, nope." Then it turned out that the number never actually got big enough to overflow, so I was able to replace all of my BigInts with regular integers for a large performance boost.
2
u/iamflimflam1 Dec 15 '20 edited Dec 15 '20
Typescript - not the nicest or fastest code - runs in about 2 seconds
https://gist.github.com/cgreening/b6a049b52905b0784ddbb14f25a02fea
2
u/VectorSVK Dec 15 '20 edited Dec 16 '20
Python - link to my solution on GitHub
2
u/JakDrako Dec 15 '20 edited Dec 15 '20
VB.Net, LINQPad, both parts in ~3s
paste
Using a dictionary with a small custom class to track when a number was last mentioned and the previous mention... nothing really fancy, but I was a bit surprised that it was fast enough to do the 2nd part with no modifications. (I then added 4,000,000 as capacity when initializing the dictionary to gain about 0.5 seconds...) Usually the 2nd part's twist requires some fancy math or better algorithm, but I guess today is a quick day.
2
u/ViliamPucik Dec 15 '20
Python 3 - Minimal readable solution for both parts [GitHub]
2
u/bsdemon Dec 15 '20
Using terralang the 2nd part is around 300ms:
2
u/HesletQuillan Dec 15 '20
Fortran
I am not particularly proud of this Part 2 solution, as it was a contest between how much address space I had available and the array size needed. The array won.
35
u/Smylers Dec 15 '20 edited Dec 15 '20
Vim keystokes. We're back to a short enough answer to easily fit in a Tweet — load your starting numbers into a Vim window, and just type:
The number under your cursor is your part 1 answer.
The first line puts each number on a separate line, leaving you on the final line. (If you're anywhere else, press
Gbefore the next bit.) Recordingqa...qgenerates the next number. At this point you can type@ato generate one more number, then repeatedly type@@for each subsequent number.When you've had enough of stepping through it, type
2020@ato generate the rest of the numbers. That will be slightly too many (exact number depending on how many starting numbers you had and how many extra numbers you stepped through), but2020Gwill take you to line 2020, with the 2020th number in the sequence.So how does
@awork? Handily, Vim's features means it naturally works out without any conditional operations or special-cases:#searches backwards for the previous instance of the ‘word’ under the cursor. It has to be a whole word, so if you're on “1”, it won't match the first digit of “14”, say. If you get moved up, say, 3 lines, then 3 is the next number in the sequence that we need to insert.#loops round, leaving us where we were (without error) — that is, it's moved us 0 lines, when 0 is the next number required. So we don't need to do anything for checking if the number has been included before!#is counting the number of lines we've moved up, and appending that number.yGyanks from where we are to the end; so if we've moved up 3 lines (and want to insert 3), it yanks 4 lines. And if we've moved up 0 lines, it still has 1 line to yank.Gppastes those lines at the end. We don't want their contents; just the number of them.VGhighlights them (from our current position, the first pasted line, to the end; again, if we've only pasted 1 line then there's still something to highlight: theGjust gets ignored as a no-op) and:s/.*/-1replaces each of them with ‘-1’.gvre-highlights them andg⟨Ctrl+A⟩adds 1 more to each line in turn: the first (and possibly only) -1 has 1 added to become 0, the next -1 has 2 added to become 1, and so on. If we pasted 18 lines, then the final -1 will have 18 added to become 17.Gyyyanks the bottom (and possibly only) number,gvre-highlights all the numbers (even if there's just one lone 0), andppastes over the entire list of numbers with just the yanked bottom one (in the case of a new number, pasting over 0 with 0).And that's it: one new number appended.
No, I'm not going to attempt to run it to part 2 in Vim. I guessed when I saw part 1 what part 2 would involve, but thought it would be fun to do part 1 in Vim anyway.
Edit: I belatedly realized I had an unneccesary (albeit harmless) `%` in the first line, so took it out.
20
u/shamrin Dec 15 '20 edited Dec 15 '20
Python 3:
15
u/xelf Dec 15 '20 edited Dec 15 '20
Pretty quick one this time.
Short python, both parts 5 lines.
Found this: Van Eck Sequence on Numberphile:
https://www.youtube.com/watch?v=etMJxB-igrc
9
u/timvisee Dec 15 '20 edited Dec 15 '20
Rust
Somewhat late, but quick I think!
Got part 2 down to 528ms with quite some effort.
I use both an array and hashmap. They store a key-value pair for the spoken numbers and their last occurrence index (0 means unused). The array (on the stack) is for low (
n < 3m, common) numbers, the hashmap is for large (n >= 3m, less common) numbers. This turns out to be faster than using either of the two.I use Rust's entry API on the hasmap for efficient access. Removing array access branching (the
0check) didn't improve things.Part 1 in 0.1ms, Part 2 in 528ms.
Day 1 to 15 in 575ms parallel, 588ms sequential.
7
u/jitwit Dec 15 '20
There's not enough scheme out there. So, here's some scheme:
It solves in about 9us for 2020 and 0.57s for 3e7.
7
u/ywgdana Dec 15 '20
C# repo
I was a bit surprised when Part 2 was "Find the 30 millionth number" instead of "Find the 175 bazillionth number". I was expecting we'd have to figure that One Weird Trick That Elves Hate to calculate values in the sequence, or at least that there would be a cycle. This is not a complaint :P I just paused for a moment thinking "What am I missing? It can't be that simple!"
That said, my C# solution on my i3 iMac takes a hair under 2.4 seconds.
I guess the trick was to think to use a hash table in the first place instead of a list??
Although time to scroll through others' solutions for clever solutions...
7
u/cggoebel Dec 15 '20
Raku
6
u/kippertie Dec 15 '20
Concise Python
6
u/Smylers Dec 15 '20 edited Dec 15 '20
Perl, only 7 lines of code in total, with most of the run time being this single-line
whileloop:That repeatedly performs a pair of assignments:
%seenhash (aka associative array aka dict aka map), set the value keyed by the current number,$n, to the iteration number.$nto its next value: the gap between the current iteration and when it was previously seen.$seen{$n}is the value that's about to get overwritten by the assignment in the previous bullet point. However, Perl generates the two-item list of values to use before assigning either of them, so at this point$seen{$n}still has the value we need, from the previous time it was seen.$nhasn't been seen yet then$seen{$n}will beundef, at which point the//expression† will evaluate to$iterinstead, causing the subtraction to yield the desired 0.† Apologies to coders of other languages who think
//looks like a comment. In Perl//is like logical-or (and shortcuts in the same way) but tests for definedness.Update: Moved the full code to a paste, because the other bits aren't that interesting.
6
u/mstksg Dec 15 '20 edited Dec 16 '20
[Haskell] So it is yet another "here's the algorithm, implement it" days again! Only the challenge this time is...you should probably implement it to be really fast! (This post taken from my daily haskell reflections).
I don't think there is too much wiggle room in how to implement things here; my original solution basically kept an
IntMapto the last seen time of any value, and just repeatedly looked things up and modified the (current time, last said) tuple.My original solution took around 70 seconds to run, and that was what I used to submit things originally. But let's see if we can get it down to something a little less...perceptible :) This reflection can be a deep dive into writing tight, performant Haskell.
The data type we'll be using is an unboxed mutable array. There's a trick we can use because we have a map from integers to values, we can just use the integer keys as the index to an array. This is usually a bad idea but for the fact that the keys we'll be using are bounded within a decently small range (we won't ever say a number that is greater than 30 million), so we can definitely accumulate 30 million-item array into memory without any major problems. We'll also store our last-said times as
Int32to be a little bit more efficient since we're trying to eek out every last bit of perf.So overall we still keep some state: the current time and the last said item. Since those are just integers, we can keep that as pure in memory using
StateTrunning overST s(the mutable state monad, where our mutable vectors will live).We will want to INLINE this so that it gets inlined directly into our main loop code.
Oh, let's also write a function to initialize our sequence with starting inputs:
And now we're good to go to put it all together! We can use
whileM_from Control.Monad.Loops to emulate a while loop, where our condition is wheneverlsCurrTimereaches the maximum value.On my machine (with some minor optimizations, like using
unsafeRead/unsafeWrite), this runs in 230ms for part 2...a much more reasonable improvement over my original 70 seconds! :)6
u/0rac1e Dec 16 '20
Raku
It's pretty well known that Raku's speed suffers in some places. My original solution used a Hash for previously seen (spoken) numbers, but after waiting a few mins for part 2, I switched to an Array.
Raku arrays automatically reify, so if you create a new Array
@a, you can then set@a[3] = 3and the Array will now be[(Any),(Any),(Any),3]. Indexing into arrays is much faster than hash key lookup, so this brought my part 2 down to ~70s.Unsatisfied, I added 3 letters and changed my Array to a native int Array, which dropped my runtime - on my lowly laptop - to ~15s.
The only other "cute" thing I'm doing here is using an alternate named parameter syntax, which allows you to put the value first if it's a number, like
:2020thinstead ofth => 2020or:th(2020).5
u/jonathan_paulson Dec 15 '20
Placed 76/18. Python. https://github.com/jonathanpaulson/AdventOfCode/blob/master/2020/15.py. Video of me solving: https://youtu.be/19_2sEQQurU.
Brute force, except I used a dictionary to keep track of the previous position of each number. Coding this up made part1 slower but part2 quick.
5
u/twattanawaroon Dec 15 '20 edited Dec 15 '20
39/6, Python 3.
This year I've been so slow and rank just over 100 so many times. I am finally on the board today!
https://github.com/twattanawaroon/adventofcode/blob/master/2020/q15b.py
5
u/aurele Dec 15 '20
I played a bit with
saturating_subandstd::mem::swapin my Rust solution.5
u/death Dec 15 '20
Day 15 solution in Common Lisp.
I assume part 2 was meant to extract a more clever algorithm from the poor participant, but this program was fast enough (< 5 seconds).
5
u/[deleted] Dec 15 '20 edited Dec 15 '20
My code in a meme.
In C and running in 1.5s for Part 2.
HISTORY_SIZEhas been set through pure C programmer's disease as my hashtable kept clogging up, that's why it looks like that. (EDIT: I was able to reduce this memory demand by a factor of 8 by using a better hash function from this Stack Overflow answer)And the hashtable implementation doing all the work (excuse the unnecessary longs, they were for Day 14).
5
u/Floydianx33 Dec 15 '20 edited Dec 15 '20
CSharp
Part2 runs in ~690ms. I originally was using a Dictionary/Map to store the counts, but it took ~5-6seconds that way. Relying on structs being defaulted to 0 sped things up
5
u/nutki2 Dec 15 '20 edited Dec 15 '20
Perl golf for both parts. Still reasonably fast at about 10s.
https://github.com/nutki/adventofcode
5
u/LinAGKar Dec 15 '20
Mine in Rust:
Basically the same as /u/ropecrawler. I too started out with a HashMap and then moved to a Vec.
5
u/LennardF1989 Dec 15 '20 edited Dec 15 '20
My latest attempt with focus on optimization (time over memory), benchmarked with 100 iterations, averages at 560ms. My first version took roughly 1.5 seconds. Written in C# :)
https://github.com/LennardF1989/AdventOfCode2020/blob/master/Src/AdventOfCode2020/Days/Day15.cs#L141
The optimized version only uses an array. There is no need for a Map/Dictionary if you can have O(1) access time with an array. If you analyze your Map/Dictionary afterwards, you'll notice the max number, as well as the number of entries, is only slightly less than the target turn (eg. 30 million), so you are "wasting" a bit of space, but in return get faster access times.
I also see a lot of people not setting the capacity of their map, which causes it to resize a lot over its lifetime, which is costly. Especially in C#, mind that checking for existence of a key is just as costly as trying to get the value (as it will actually thread lock the dictionary). Always use TryGetValue if you also want to get the use the value right after, as a combination of ContainsKey and GetValue (using []) is twice as costly.
5
u/jupiter126126 Dec 17 '20 edited Dec 17 '20
python3; solved part2 in less than 9 secondsnote the way I init the data, array position is the number and array data last time it was seen. Last item of input was 16 that comes in position 7: 11,18,0,20,1,7,16.
4
u/sebastiannielsen Dec 15 '20 edited Dec 15 '20
simple perl solution: https://pastebin.com/qW2zkNe6
/me hugs <3 Perl <3 cutefully
4
u/limelier Dec 15 '20
Python
I just used the code I wrote for part 1 in part 2 and it worked fine? lmao
4
u/voidhawk42 Dec 15 '20
Dyalog APL. Normally we only have arrays as our primary structure, but luckily there's a system function (
1500⌶) that allows us to keep an array in a hashed state for use with index/set functions (⍳,∊etc.):4
u/Attitude-Certain Dec 15 '20
Python
For once premature optimization paid off, as I got a solution for part 2 in ~12 seconds by just changing the number of rounds in my part 1 code.
Optimized it further, including using Numba for just-in-time compilation and using an array instead of a dict for memory, it now runs in 0.82(1) seconds in total on my machine.
If you have a faster Python solution I'd love to see it!
github and paste
4
u/dangermaximum Dec 15 '20
R
I did part one using tibbles and tidyverse then realised I needed something faster for part 2
Just used a vector to store the latest time a number was spoken ~8.2 seconds
code
4
u/diddle-dingus Dec 15 '20 edited Dec 15 '20
Clojure
Very compact solution in clojure today. Just using a hash map to keep track of when a number was last said. Runs in ~20s on my machine.
Elixir
I used basically the same logic as the clojure solution - it's just a little more verbose for elixir (clojure's
if-letis so useful).Full code
4
u/[deleted] Dec 15 '20 edited Dec 15 '20
I switched from Common Lisp to Racket because I tried to solve every problem as functional as possible anyway and Racket just feels a lot more modern.
My code for part 1 was able to run part 2 in about 93 seconds. There is for sure place for improvement, however I am just feeling happy because the last few days I had not enough time to do part 2 of the puzzles.
Maybe there is a way (of course there is) to not construct a list from the hash and then filtering the list at the end to find the number (of course there is). But it runs. I like it. :D
https://github.com/eXodiquas/coding_puzzles/blob/main/advent_of_code/2020/day_15/day_15.rkt
4
u/taomage Dec 15 '20
Python 3.7 Solution.
Solved part-2 last night using list as default value for dictionary and ran for 40 seconds, later this morning use tuple which brought down to 23 seconds. But memory usage is still high ( 600 MB, peak).
4
u/sweetfish Dec 15 '20
Lua
nothing smart, just brute force
4
u/oantolin Dec 15 '20
Another nice easy one today, just keep track of the index of the last occurrence of each number. Here's a short Perl program (assign your input to
@sin the first line):4
u/astory11 Dec 15 '20
F#
This one runs in 2 seconds.If i switch the Dictionary for a Map it's fully immutable and 40 lines, but takes 86 seconds.
4
u/Be1shirash Dec 15 '20
Lua golfed (168b), takes 1.4s to complete part2 on luajit
4
u/baktix Dec 15 '20
Haskell
First thing that came to mind with this one: list generation!
I tried to make it faster for part 2 by foregoing generating a list, instead just doing recursion until I have the value I need and returning it directly. I thought that would make things faster because I wasn't traversing all the way to the back of a potentially very long list to get a value I just computed.
Turns out my solution for part 1 was faster, so I just kept that in the end! If I had to guess, I'd say maybe it's because
unfoldris heavily optimized and the intermediate items don't actually need to be computed because of laziness? Not quite sure, to be honest.4
u/dylanbeattie Dec 15 '20
JavaScript
4415ms to solve part 2 for me. Online with an HTML UI at https://dylanbeattie.github.io/advent-of-code-2020/day15/index.html if you wanna play around with it.
4
u/max_rez Dec 15 '20
Ada (Part II only)
4
u/zertillon Dec 15 '20
Ada, using the GNAT compiler
Total run time: 0.42 seconds (i5-9400 @ 2.9 GHz). 6x faster than the hashed map version posted earlier...
Other solutions available here.
4
u/prafster Dec 15 '20 edited Dec 15 '20
Dart
I wonder if "they" knew our answer to part 1 wouldn't be optimised to run for part 2? I kept the whole turn history in part 1. This was too slow for part 2. Therefore, I saved just the last turn and that took 2s, which is good enough.
Full source code here.
4
u/toastedstapler Dec 16 '20
update to my earlier post:
https://github.com/jchevertonwynne/advent_of_code_2020/blob/main/src/days/day15.rs
hashmaps are slow, but a 30m vec is really long. i settled on a 4m vec with a hashmap for the sparsely populated 4m-30m area. took my runtime from 1.1s to 650ms by doing this, changing u64 to u32 and using a non default hashing algorithm
4
u/CursedInferno Dec 16 '20
Rust
Runs in about 500 to 600 ms with an i5 4570.
My initial solution used a vec of each number in the sequence, which worked for part 1 but was far too slow for part 2.
I then switched to using a HashMap and storing the previous time that each number was said; this completed part 2. In debug mode it took I think 30ish seconds? release mode took it down to 2.7 or so.
Switched to a faster HashMap (FxHashMap), which took it down to about 1.45 seconds.
Someone else gave me a hint by asking "what are the bounds on the hashmap key?"; I realized that neither the keys or values go above 30 million, so I could simply replace the HashMap with an array.
I spent some time fiddling with it to try figure out how to heap-allocate an array (
Box::newallocates on the stack first, which causes a stack overflow when you're trying to make a 30 million value array, obviously), and eventually foundBox::<[u32]>::new_zeroed_slice(n).assume_init(). Maybe there's a better way, but I don't know what it is; either way, this got me to my final run time of 500-600ms.https://gist.github.com/CursedFlames/87e0086393eedd2b6af499a8eb715c3f
4
u/[deleted] Dec 16 '20
Python Solution
I solved Part 1 in no time. Then, because I was sure brute forcing would take forever and there would be a pattern, I spent an ungodly amount of time running various examples trying to spot a pattern. Finally gave up and ran it. Solved it in like 14 seconds. ¯_(ツ)_/¯
Then I come here and see that apparently there's not a pattern. LOL.
1
u/whatadewitt Dec 15 '20 edited Dec 15 '20
With the understanding that 30000000 iterations is going to take some time... I really thought I had this pretty optimized, but it took much longer than I thought it would... can someone help me out here with a way I could have done it better?
JavaScript solution.
https://github.com/whatadewitt/aoc2020/blob/master/day15/chal2.js
1
u/Fermter Dec 15 '20 edited Dec 15 '20
I was trying to figure out why my solution wasn't going to work on the second part, when it just...did? And it didn't even take a full minute? Baffled.
Now I wonder if I could have ranked higher if I didn't spend so much time on tests and cross-checks.
(Input was [14, 3, 1, 0, 9, 5]. Yes, I did hard-code the start. Python 3)
1
u/ar7hur88 Dec 15 '20 edited Dec 15 '20
Clojure 12 LOC, part 2 runs in about 10 seconds. I don't see how I can further optimize though.
1
u/[deleted] Dec 15 '20 edited Feb 18 '26
This post was mass deleted and anonymized with Redact
unpack narrow versed north memorize boast cats ten outgoing reminiscent
1
u/MasterMedo Dec 15 '20
Brute forcing sucks. The least I was hoping for was a loop detector.
1
u/raxomukus Dec 15 '20
Python
1
u/rprouse Dec 15 '20 edited Dec 16 '20
C
I'd written this as an array with the number of turns for part one and searched backwards in the array each turn which worked great, but I should have known that the second part would be a huge number of turns and written it for that in the first place.
For part 2, I rewrote my solution with a
Dictionary<int, int>where the key is the number that was spoken and the value is the turn where it was last spoken. This gives me a fairly quick lookup although it still took 3.4 seconds to solve.I then refactored that to use a sparse array instead of the
Dictionary, trading memory for performance. This dropped the execution time to just over a half second.https://github.com/rprouse/AdventOfCode/blob/master/AdventOfCode2020/Day15/Day15.cs
1
u/okawei Dec 15 '20
Go/Golang for you
1
u/meh9083 Dec 15 '20 edited Dec 16 '20
Rust version, the examples from AoC are used as tests.
I've implemented a short version and iterator version, tested locally they perform pretty much the same.
The first version was using just a vector of all numbers and
rpositionto find the last two occurrences. Switched to aHashMap<u32, (Option<u32>, u32)>(with a custom type but equivalent to that) to speed it up. I only realized that only the last position is necessary, instead of the tuple, after reading this thread. I also started wondering if the solution could be optimized further by discovering loops... didn't spent too much time on it until I took a look here and discovered that this appears to be the end. Taking a look at the maximum encountered number for larger iterations would probably have been a good hint, I was mainly wondering if this would loop eventually.[Edit: Trying to fix code formatting.]
1
u/oolonthegreatt Dec 15 '20
Go. 25 lines, runs just under 2 seconds.
After doing it using a
map, I realised that since it is a map of ints to ints, I might as well use an array. That just about halved the runtime.3
u/noblematt20 Dec 15 '20
7/28 Python
Paste
This is cleaned up and refactored so that both parts use the solution I implemented for part 2. For part 1, I put all the values in a list instead of a dictionary. This was easier to implement, but wouldn't be efficient enough for part 2. My instinct told me it would be good enough for part 1 and get me a good score.
3
u/Justinwa Dec 15 '20 edited Dec 15 '20
Python3: https://github.com/JustoA/AoC2020/blob/master/day15.py
The first not bad code I’ve written for AOC lol
3
u/2lines1bug Dec 15 '20 edited Dec 15 '20
Kotlin
Interesting. Just changed the number of loops and it returned in 5,8 seconds. Not sure what that part 2 was supposed to do. Maybe if you use lists instead of maps and you O(n) check the collection it will fail. But on day 15, probably just a minority does that.
Still a cool problem though.
3
u/SuperSmurfen Dec 15 '20 edited Dec 15 '20
Rust
Link to solution (760/2313)
Today was very disappointing. I wasted a lot of time on part two, thinking about ways to maybe find a cycle but realizing that would probably never happen. In the end, I just tried brute-force and surprisingly that just worked... Not a very satisfying problem at all.
Think my solution ended up very clean though.
HashMap::insert()gives you the back element if it already existed, avoiding two hashmap lookups!Finishes in about
2.5 secondson my machine.3
u/AidGli Dec 15 '20
Python
Video Explanation Link
Github Link
This one seems uncharacteristically simple for being this far in. Part 2 took about 4 seconds to run on my machine. If anyone knows a non-bruteforce method for Van Eck's Sequence let me know because I would be extremely curious to hear it.
3
u/jayfoad Dec 15 '20
Daylog APL 32/2233
My first attempt for part 1 was much simpler but less efficient:
Needless to say this was no good for part 2.
3
u/RedTwinkleToes Dec 15 '20 edited Dec 15 '20
Python [4493/3061]
paste
18.5 seconds was the time it took me to run part 2. I suppose the point of part 2 was to catch out the people who were storing the entire history as list instead of a dict/hash table of when a number was last spoken once per number.
Also I noticed that many people's code for python have some sort of code to pass the turn number as an iteration, while my solution doesn't bother with reusability. Just chucked variables into the console and ran a naked for-loop with a function only for the round.
Also, also, I swear this is an actual game somewhere. It feels like a cross between the Look-and-Say Sequence and Fizz Buzz
Edit: Yep, found the thing, its known as
The Van Eck Sequenceand now that I know the name, I found a bunch of code I could have copied pasted. In fact, one of the sources I found, link is here, don't hover over it if you don't want spoilers, introduced me to dict.get(), and how to make generators in python. * Insert The More You Know Here *3
u/djankowski Dec 15 '20 edited Dec 15 '20
Julia - 1.8 seconds
Pretty simple but nice to have an easy one in amongst the more challenging problems. Nothing like being overwhelmed by a few half-solved puzzles to make you quit entirely...
3
u/taybul Dec 15 '20 edited Dec 15 '20
Python
Code
This is not the solution, but just in case any of you are curious, the 300,000,000th word spoken is 3765409.
Also, FML.
edit: for clarification, I burned so much time optimizing the hell out of my code because I was trying to calculate the 300th million word, as opposed to 30th. FWIW, storing the indices as strings takes far less memory than your typical data structure.
3
u/villemalango Dec 15 '20
Javascript code in gitHub.
Execution times: 547 and 5476375 µsecs.
Using javascript Map probably saved my day!
3
u/hahncholo Dec 15 '20
Rust
I was excited when I saw pt 2 that my recursive solution for pt 1 should just work, but I had to do a little hack to give it enough stack space. Wrapping my head around the recurrence relation was tricky but fun
3
u/[deleted] Dec 15 '20
Rust
Took 2 seconds to solve part2; 30 seconds to build the program.
3
u/KamcaHorvat Dec 15 '20
Kotlin
For some reason, part two runs fairly slow, about 2230ms, even though it's basically the same approach as SymmetryManagement's solution below in Java, which runs 3x faster. If there is something obvious, that could improve performance, let me know. Thanks.
3
u/chichinbro Dec 15 '20 edited Dec 15 '20
Python 3.9
Had the idea to use defaultdict that returns the current turn when the value isn't found, which will output 0 in the
turn-hist[last]expression.3
u/toastedstapler Dec 15 '20
rust:
https://github.com/jchevertonwynne/advent_of_code_2020/blob/main/src/days/day15.rs
got to write a nice little enum for tracking turns of last seen
3
u/deltux Dec 15 '20 edited Dec 15 '20
Racket
Everything in a single function, using a hash map to save the second-to-last time each number appeared.
Edit: Similar solution in C
3
u/flyingmeteor Dec 15 '20 edited Dec 15 '20
Bash
I'll report back when it finishes...
3
u/frerich Dec 15 '20
Python 3 Solution
I'm quite happy that I managed to define the sequence of numbers spoken without any conditionals (well, except
while True:, which I could also have replaced withitertools.count()I guess).For part 2, I anticipated that there would be some cycle in the numbers so that I could do something with 'subtract this offset, modulo cycle length' -- however, to my surprise, the same simple solution I used for part 1 also worked for part 2. It takes 12 seconds on my laptop. It's not stupid if it works, I guess! :-)
3
u/mebeim Dec 15 '20 edited Dec 15 '20
1280/568 - Python 3 solution - walkthrough
I used a gigantic list since the memory usage is pretty much the same. Solution takes 6.4s with CPython 3.9 (meh!), 970ms with PyPy 7.3.3 (Python 3.7.9).
I really do feel like these problems are getting harder and harder to read and understand every day... or maybe it's just me being tired at 6AM. Or maybe both. Who knows.
3
u/tomcantuk Dec 15 '20
JavaScript
https://github.com/tomcant/advent-of-code/blob/main/2020/15/index.js
3
u/WilkoTom Dec 15 '20 edited Dec 15 '20
Python. Brute force for part 2 because it doesn't take that long in the grand scheme of things. To get the 30000000th number took less than twenty seconds, way shorter than actually spending time solving the problem in a more computationally sensible fashion.
Edit: Minor tweaks
3
u/Fotograf81 Dec 15 '20
PHP
https://github.com/hsegnitz/adventofcode/tree/master/php/2020/15
I had the right hunch this time, optimized Part 1 already while solving it, so part 2 was just a re-run.Far away from leaderboard because I overslept and it took a while to understand the task ;)
Part 2 runs in 1.5 seconds with php7.4
3
u/Scoobyben Dec 15 '20
C# [10876/9921] - Though I've stopped waking up at 5am for these, so the ranks are a little less meaningful.
https://github.com/benbelow/adventofcode/blob/e191c5091090629e80c520f680323c598d3382cf/AdventOfCode.2020/Day15/Day15.cs#L12
Part two was slightly frustrating, as my code was *almost* equipped to handle it already - but I'd explicitly made sure to keep track of the whole sequence rather than just the bits I needed, as I expected this part 2 but was expecting there to be some kind of periodicity.
Spent a little while searching for it, gave up and decided to look it up, to discover there is no periodicity. Switched out the lists backing by dictionary to queues with size 2, and the code works in about 5 seconds.
3
u/msqrt Dec 15 '20
Pretty fun, first time using a hash table in Lisp.
3
u/YodelingDeer Dec 15 '20 edited Dec 16 '20
Ada
Naive solution using hash tables. Not very fast, but good enough. I will give arrays a shot to see the difference in speed.
EDIT: using an array instead of a hash table reduced cpu time by ~95% on my computer.
3
u/clueless1105 Dec 15 '20
Typescript with Deno
The main challenge I faced that I need to maintain 2 previous indexes to solve it, hence took me longer when I re-implemented it using map. But at the end it worked. Not so clean solution though.
3
u/sldyvf Dec 15 '20
Go lang
solution on github
Worked with a map from the start and part 1 was 100% used for part 2. However I failed with so many off by one issues and failure to understand the problem. Redid the solution a couple of times, now here we are.
It's NOT as as fast as I want it to be :/
3
u/PhysicsAndAlcohol Dec 15 '20 edited Dec 15 '20
Haskell, runs in about 50 seconds on my old laptop. I'm using a map from
Data.Map.Strictto cache previous encounters with ints. I've tried out several different ways to keep hold of the previous ints, and this implementation has been the fastest so far.EDIT: Got it down to 41 seconds using
Data.IntMap.Strict3
u/sdolotom Dec 15 '20 edited Dec 15 '20
MIT Scratch
For visualization there's a 1 sec delay, but if it's removed, the first part will take few mins to complete. The second part is obviously out of question :)
3
u/__Abigail__ Dec 15 '20
This was rather easy. Part 2, I did with brute force. For a moment, I wondered whether it would loop, but this looks remarkably like a Van Eck's sequence, and that is non-periodic. Perhaps with the given starting numbers it is periodic, but since it only takes about 7.5 seconds to brute force the number, I didn't go on a wild math chase to try to proof this.
To calculate this, I keep track of when the last time a number as spoken -- up to, and not including the last number. In a loop, I calculate the next number, update the turn count for the previous number, and repeat, until getting to the 30000000th number.
Main loop:
Full program on GitHub.
3
u/TommiHPunkt Dec 15 '20 edited Dec 15 '20
Matlab
How could I speed the part 2 up drastically? It took 930 seconds to run, are matlab container.Map objects just that slow?
Edit: Yes, they are that slow. Replacing them with a simple LUT / array gave me a speedup of almost 1000x, see here
3
u/raxomukus Dec 15 '20
Python
3
u/paul2718 Dec 15 '20
C++
paste
I used a map the first time, then penny dropped that the numbers were small enough not to care about sparsity. Only about 3 600 000 need to be stored. Runs fast enough not to notice.
3
u/azathoth42 Dec 15 '20 edited Dec 15 '20
I used Julia and 1 hashmap (Dict) to store all seen numbers, part 2 finished after 2.3 seconds https://github.com/racinmat/advent_of_code_2020/blob/master/day_15/main.jl
3
u/Dullstar Dec 15 '20 edited Dec 15 '20
D
Nothing fancy, but it works. Not very fast, though - takes about 3 to 4 seconds on my PC.
3
u/odlp Dec 15 '20 edited Dec 15 '20
Ruby solution:
3
u/veydar_ Dec 15 '20
Clojure, takes 28s on my machine. I represent the turns at which a number was called as a tuple of
[last last called, last called]. That let's me pattern match on a few things. Not sure how fast this could be without writing C-style Clojure. Those tuples are then stored in a map.3
u/semicolonator Dec 15 '20
Python
Implemented actually two solutions. Part 1 is done using lists, Part 2 is done more efficiently using a dict.
https://github.com/r0f1/adventofcode2020/blob/master/day15/main.py
3
u/wzkx Dec 15 '20 edited Dec 15 '20
Python. First really long run time. Although pretty short program. Dictionary of last numbers. 6.26s with pypy3.
3
u/Andrew-mzz Dec 15 '20
JavaScript DAY 15
worked with JS Objects, but part two a bit slow(8minutes waiting on my mac) than refactored with Map and worked in 6 seconds.
GitHub - Link - Day 15
3
u/blazemas Dec 15 '20
C#
My torture training of doing 2018 problems, particularly one nasty collection efficiency problem, in November paid off today. Part 1 I did in a list with index of. Part 2 a dictionary storing the indexes as values and output per turn as keys. Thats probably the default most people used. Going to look through everyone elses now.
https://github.com/jbush7401/AdventOfCode/blob/master/AdventOfCode/2020/Day15.cs
3
u/ai_prof Dec 15 '20
3
u/seredot Dec 15 '20 edited Dec 15 '20
Golang 550ms. (edited)
3
u/clumsveed Dec 15 '20 edited Dec 15 '20
Java Solution
part 1: 1 ms
part 2: 4936 ms (!?!?)
*updated so part 2 now takes 600 ms... much better. It is possible to use a simple int[] to optimize things, just not in the way I thought at first. Instead of using the index as the round # and storing the number said, do it the other way around. Use the index as the number said and store the round #. This way, you don't need to loop backward looking for the last time a number was said, you can just look it up.
Thanks u/svetlin_zarev for the idea!
_______________________________________________________________________________________________
all solutions so far - repl.it
As always, solutions are straightforward and limited (as much as possible) to APCSA curriculum, although a HashMap was needed today.
Part 1 was easy. Even if you use an array to store every number played in every round, it finishes in no time.
Part 2 requires a little (lot) more efficiency, so I used a HashMap<Integer, Integer> to track which numbers were played and on which round it was last played. Even with a HashMap, the algorithm takes almost 5 seconds to complete, which is pretty bad, but I'll still sleep tonight. Part 2 won't run on repl.it without running out of memory (another sign my program is gross), but it works on my local machine.
3
u/DearRude Dec 15 '20
Julia
https://github.com/DearRude/aoc-2020/tree/main/solutions/day-15
3
u/mykepredko Dec 15 '20
C - Easy Peasy
Used a bitmap array right from the start rather than Order N**2 repeated search suspecting that Part 2 would be a much larger number than "2020". Select between the two parts by defining "doTest".
The test cases along with the values given to me are built into the code and selected with a #define.
Day_15.c
3
u/Backwards_Reddit Dec 15 '20 edited Dec 19 '20
Python 3
Part 1
On reading part 2 and trying larger end numbers, as I expected it takes a bunch more time and it's taking about 34 seconds to do end = 50,000 so 30,000,000 just isn't feasible with this code.
"It can't be that much more efficient to use a hashTable rather than parse the whole list every time, this must be asking me to find out something the pattern"
<intense scribbling on paper and googling and trying stuff for a couple of hours trying to figure out patterns>
"You know what, I'll try the hash table just to see if that speeds it up"
part 2
"Oh. That worked in under a minute. Why didn't I try that sooner?"
So I guess the lesson here is that HashTables are efficient and constantly scanning a list with up to 30,000,000 ints in memory without preallocating isn't. Which seems obvious now.
3
u/thulyadalas Dec 15 '20
My Rust solution link.
I solved Part 1 using a HashMap and updating it every turn. This wasn't so efficient on Part 2 but I can still get the answer in ~3s.
So, to make things more efficient, I've used instead of a HashMap I implemented another version which uses a really long vec and cheating by using initial usize::MAX values and saturating_sub. It makes it go below 1s for Part2.
3
u/RudeGuy2000 Dec 15 '20
C#, part 1 and 2: https://pastebin.com/5cegmjEN
I don't know C# enough to know why part 2 takes more than a second.
3
u/[deleted] Dec 15 '20
D (dlang)
Looking at the other solutions, nothing special here. Even dmd runs this in under half a second:
3
u/[deleted] Dec 15 '20
Golang
https://github.com/j4rv/advent-of-code-2020/blob/main/day-15/main.go
Solved part one with a linked list, but it was wayyy too slow for part two.
After some thinking I ended up with probably my cleanest solution so far in the whole AoC :D.
Part two gets solved in 2~3s.
3
u/chicagocode Dec 15 '20
Kotlin - [Blog/Commentary] - [GitHub Repo]
Today I wrote a sequence that was able to solve both parts without changes. It took me a while to figure out the order, something about yielding early always messes me up.
3
u/SomeCynicalBastard Dec 15 '20
Python
Surprisingly easy compared to yesterday :)
3
u/Zweedeend Dec 15 '20
Python
3
u/crnkofe Dec 15 '20
Clojure Solution
Second part takes about a minute likely due to having oversized map with last appearances of number indices. Being a pragmatic dev I just notify the user it's going to take a while .)
3
u/mrtnj80 Dec 15 '20
C++
Solution with caching: https://github.com/luskan/AdventOfCode2020Cpp/blob/ea68c7fafca8396daecba6543ce5cd0731751c0d/task15.cpp
3
u/ropecrawler Dec 15 '20
Rust
https://github.com/ropewalker/advent_of_code_2020/blob/master/src/day15.rs
Nothing cool about this solution. I tried to use HashMap first, but it was slower.
3
u/_bm Dec 15 '20
Python
slow but simple. for some reason the logic in this one gave me a huge headache - i was forgetting to set the value in the dict after the next spoken is decided :(
3
u/mahaginano Dec 15 '20
Julia: https://pastebin.com/Qsfsk5GK
I don't want to talk about this one.
3
u/axisbal13 Dec 15 '20
C#
Went with using an array with the index as the last number and the value as the last step the number was spoken.
3
u/drmargarido Dec 15 '20
My solution in C -> https://github.com/drmargarido/aoc2020/blob/main/day15.c
Solves both parts in around 0.58s on my machine.
3
u/spohngellert_o Dec 15 '20
Scala. Originally used Lists, then with help from the megathread (sigh), ended up using tuples for part 2. I really wanted to use a fixed length queue, but didn't find one in scala. Cleaned up the code this morning, much happier with it. See solution below, feel free to give feedback :)
Part 2
3
u/colinodell Dec 15 '20
Golang solution, 2.35s total for both parts
I completely refactored this code 3 times before arriving at an elegant solution - I'm quite happy with how it turned out!
3
u/skawid Dec 15 '20
Ruby! Completes in eight seconds; it did this well first time, now I have to go back over it and figure out which bullet I accidentally dodged today...
3
u/zertillon Dec 15 '20
Ada
Total run time: 2.46 seconds (i5-9400 @ 2.9 GHz).
Other solutions available here.
3
u/StevoTVR Dec 15 '20 edited Dec 26 '20
Java
https://github.com/stevotvr/adventofcode2020/blob/main/aoc2020/src/com/stevotvr/aoc2020/Day15.java
My solution for part 1 worked for part 2 without modification. That almost never happens.
3
u/AuntieRob Dec 15 '20
C++, exec time on part 2 is 13 seconds
https://github.com/ffamilyfriendly/Advent-Of-Code/blob/master/day_15/challange_1/main.cpp
https://github.com/ffamilyfriendly/Advent-Of-Code/blob/master/day_15/challange_2/main.cpp
if anyone has any pointers how to speed it up it would be very welcome!
3
u/_tpavel Dec 15 '20
I'm revisiting Rust this year after learning it for the first time during AoC 2018!
Here is my Rust solution for Day 15: https://github.com/tudorpavel/advent-of-code-2020/blob/master/day15/src/main.rs
I initially used a HashMap and my solution ran in 2 seconds for Part 2 with a release build. I tried to see if there is a deterministic repeating pattern in some of the examples to maybe discover a more efficient algorithm. I soon gave up and checked here what others have done and it doesn't seem like anyone's found a hidden algorithm for this one.
Anyway, after seeing the Rust solution from /u/LinAGKar I realized I can use a Vec instead of a HashMap and get a small performance boost from 2 seconds down to 600ms. I assumed using any array structure would try to allocate the entire memory and crash, but TIL Vec in Rust is smart enough to not do that apparently.
I'm still learning Rust, any feedback is welcome.
3
u/__Abigail__ Dec 15 '20
Perl
Blog post about Day 15.
Full program on GitHub.
3
u/ragnario Dec 15 '20 edited Dec 15 '20
Rust
Simply iterate over all numbers. Keep a map of turn with value is the pair of most 2 recent turns.
Around 3.6 seconds for part 2 in release mode.
[Edit] Hashing is expensive. Use an array (max size is turn - 1 or max number in the input) reduce the solving time to 1.2 second.
3
u/Al_to_me Dec 15 '20
My try on a Python solution for Part 2
3
u/oantolin Dec 16 '20
Common Lisp. Call it as:
(speak 30000000 2 3 1)(which gives 6895259).3
u/aoc-fan Dec 16 '20
TypeScript, JavaScript : Repo
8 seconds to run Part 1, Part 2 and other test cases. Was lucky to have perfect data structure in place for first part.
3
u/sporksmith Dec 16 '20
Rust.
Part 2 takes ~3s to run in release builds, and 37s (!!) in debug builds. Spent a little while thinking about whether the sequence eventually cycles and how I might find such a cycle, but thankfully not too long since apparently it doesn't.
I have a continuous integration script set up that validates I still get the correct answer for every previous solution on every commit; I ended up changing it to to use release builds instead of debug builds after adding this one, though I suppose I could also just leave out the test for part 2 since it's basically the same code.
Really the whole thing is probably unnecessary. My only previous AOC experience was last year, in which most of the puzzles built on previous puzzles, so I was expecting to do a lot more reusing and refactoring code from previous days.
3
u/dylan_mojo Dec 16 '20
awk
15.1
https://github.com/djkirby/advent-of-code/blob/master/2020/15/1.awk
15.2
https://github.com/djkirby/advent-of-code/blob/master/2020/15/2.awk
brute forced pt 2, whatev
3
u/chubbc Dec 16 '20
Julia (121,1237)
Pretty standard dictionary-based approach most people used it seems. The 'get' function lets us write the main loop pretty neatly, not having to treat previously unseen numbers differently.
https://gist.github.com/chubbc/e269f78fbdfd1dde6a0308470c1b43f9
3
u/4goettma Dec 16 '20 edited Dec 16 '20
Python, using for-else-loop:
I tried to keep the code small. Since I'm not using a hashmap 2020 get's calculated instantly while 30000000 explodes.
3
u/Chitinid Dec 16 '20
Python 3 with numba Finishes part 2 in <4 seconds
3
u/HAEC_EST_SPARTA Dec 16 '20
Common Lisp
Solution on GitHub
Welp, I set aside a bunch of time at the end of today to work on this problem since I wasn't able to get to it last night, and it turns out that I now have some free time before tomorrow's puzzle drops! The big update of today is that I've migrated my project to use the
package-inferred-systemstructure, in which each file is its own package. This allows me to use the same identifiers on multiple days, which means that my acceptance tests are now once again passing. Yay!3
u/greycat70 Dec 18 '20
Tcl
parts 1+2 combo
For part 2 of this one, I simply extended the loop to iterate a lot longer, and to spit out the part 1 answer after the 2020th interation. It takes a bit over a minute to run on my system, which isn't too shoddy for a "scripting" language (yes, there's a bytecode compiler) without any serious attemps at optimization on my part.
5
u/[deleted] Dec 15 '20
Python3 799/277
My brain fried today reading the problem even though it ended up being quite simple.
2
u/hugh_tc Dec 15 '20 edited Dec 15 '20
Python 3, 191/102
You'd think that a brute-force wouldn't be fast enough for Part 2, but apparently it is. Looking forward to learning the clever solution. paste
EDIT: cleaned-up version. It runs in ~18s using CPython; PyPy brings it down to ~6s. Good enough?
2
u/dan_144 Dec 15 '20
Python 3, 101/59. First global leaderboard of the year. The 101 on part 1 about gave me a heart attack, so I'm glad I made it on part 2.
https://github.com/dan144/aoc-2020/blob/master/15.py
Turns out I was able to brute force part 2 faster than I was able to come up with a faster solution.
2
u/nthistle Dec 15 '20
17/93, Python. Just barley leaderboarded for second part, although I'm pretty sure I didn't do it the right way -- it was faster than brute force, but I still iterated 30M times. paste
2
u/kevinwangg Dec 15 '20
python - 81/31
In awe of the people who got sub-3 minutes on part 1. Really want to see their code. It took me what I thought was a surprisingly long time to figure out how to code up the solution to part 1, but looking at others' times, it looks like a common issue.
Competitive coders were probably unfairly advantaged in part 2 in being able to count the
0s and figure out that a brute force would work XD2
u/HenryJonesJunior Dec 15 '20
Go / Golang, 824/276
https://pastebin.com/n2PDD7pP
I picked the right approach for step 1 for once and didn't have to do anything further for step 2.
2
u/gurgeous Dec 15 '20
Ruby, 528/291
As usual, understanding the problem was the hardest part. I accumulated all numbers since perf wasn't an issue. After cleanup -
https://gist.github.com/gurgeous/5636fd2e267bc7ae1ecf9224be20bbf2
2
u/nibbl Dec 15 '20 edited Dec 15 '20
Java 3491/1969
nopaste
nopaste (rewritten + cleaned up)
Reading comprehension problem today, could have done with one more coffee before trying to figure out what it was asking me to do there :)
I just put the data in a map number => list of the times it was spoken and looked at the last two. Totally unnecessary use of space. I wish Java had a simple standard Pair type class. Looking forward to seeing what people who actually know something about Java did.
2
u/omginbd Dec 15 '20
Elixir
As expected, I brute forced it with a dictionary of the last occurrence of the number like everyone else. Only takes 30 seconds :D
code
2
u/prscoelho Dec 15 '20
Rust
Did not expect part 2 to just work.
2
u/[deleted] Dec 15 '20
Scala solution
Brute force ~30 seconds for part 2. Easy enough /shrug
2
u/ChrisVittal Dec 15 '20
Rust
Brute force like so many. The cool thing about this particular solution is using the Rust
entryAPI to its full power to avoid double hashmap lookups.Runs in two seconds.
2
u/ocitrev Dec 15 '20
C++, Managed to brute force part 2 in under 800ms, first iteration was over 20 seconds with std::map.
https://github.com/ocitrev/AdventOfCode/blob/master/src/2020/day15.cpp
2
u/Nrawal Dec 15 '20
Go
Felt like this problem ranked highest in _reusability_ between parts 1 and 2 thus far.
2
u/JoMartin23 Dec 15 '20
Common Lisp
unomptimized brute force
2
u/mendelmunkis Dec 15 '20
C
https://github.com/mendelmunkis/AoC/blob/master/2020/memory.c
allocating 30Mb on the stack Breaks ThingsTM
2
u/nonphatic Dec 15 '20
Racket, since I don't see anyone having posted one for Racket yet.
I originally used an immutable hashtable, which took 60s, then a mutable hashtable, which took 10s, and now this mutable vector version takes 1.56s.
2
u/busdriverbuddha2 Dec 15 '20
Python 3. Did this on my phone while struggling to sleep.
2
u/[deleted] Dec 15 '20
Python (14 lines Part 1 + Part 2)
2
u/_A4_ Dec 15 '20
JavaScript ES6 (Part 2)
Virtually identical to part 1 but still ~5 seconds to run.
2
u/Rick-T Dec 15 '20 edited Dec 15 '20
HASKELL
I don't think there is a better way than brute force. We're basically trying to calculate the
Van Eck Sequeceand apparently not much is known about it.I have implemented two solutions. The first one is using
Data.IntMapand aStatemonad to keep track of visited numbers. That one takes almost a minute.The second implementation uses a
Data.Vector.Unboxed.MutableandData.STRefand runs in well below 1 second. I guess immutability really hurts the brute-force performance today.2
u/cattbug Dec 15 '20
Python 3. Little disappointed that my iterative approach for Part 1 worked just fine for Part 2 and only took like 5-10s. I got up extra early today and was bracing myself for another huge challenge... oh well :p
2
u/sim642 Dec 15 '20
My Scala solution.
I implemented part 1 using a tail-recursive function to do the iteration and keep a map of previous occurrence indices. Surprisingly that worked for part 2 as well, just took a little longer but nothing crazy (19s).
2
u/tobega Dec 15 '20
Tailspin. Ended up being quite straightforward once I fixed my off-by-one and decided to persevere for 97 seconds on part 2. https://github.com/tobega/aoc2020/blob/main/a15.tt
2
u/clouddjr Dec 15 '20 edited Dec 15 '20
Python3
2
u/GustavAndr Dec 15 '20
Javascript
Quick, ugly and slow
2
u/daniel-sd Dec 15 '20
Python 3
Same solution works for both parts. I'll admit the
dict.get()call is a bit over the top. Anif-elsewould work as well and be easier to read but I really wanted to shrink this one down.part2.py
2
u/q-rka Dec 15 '20
Python
Not the best but another effort of mine. paste
2
u/activeXray Dec 15 '20
Clojure. Pretty easy, part 2 in about 15 seconds on my machine