Our great sponsors
-
InfluxDB
Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.
-
AdventOfCode
My Advent of Code solutions. I also upload videos of my solves: https://www.youtube.com/channel/UCuWLIm0l4sDpEe28t41WITA
-
WorkOS
The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.
-
advent-of-code-2020
Solutions for the 2020 Advent of Code (https://adventofcode.com/2020) (by rujames)
-
advent-of-code-2020
Source code for my solution to 2020's Advent of Code. This year, I'm learning Kotlin! (by richzli)
-
advent-of-code-go
All 8 years of adventofcode.com solutions in Go/Golang; 2015 2016 2017 2018 2019 2020 2021 2022
-
advent-of-code-2020
My solutions for Advent of Code for 2020, done in Python 3. https://adventofcode.com/2020 (by BradonZhang)
-
adventofcode
🎄 My Advent of Code solutions. Often done with unfamiliar languages so don't expect idiomatic code. (by dmshvetsov)
-
advent-of-code-2020
ASCII art of digits that also happen to solve Advent of Code challenges (by arknave)
-
-
SaaSHub
SaaSHub - Software Alternatives and Reviews. SaaSHub helps you find the best software and product alternatives
TypeScript
Haskell
Pascal - runs part 2 in 0.248 seconds on my laptop.
They're not; line 20 is computing a mapping from cup to next cup, and they're using that to look the destination up on line 30. So this is already using direct lookups on a hashmap.
Updated my code to use an array of "next" pointers (as some other folks here suggest) and it's like half as long.New code: https://github.com/jonathanpaulson/AdventOfCode/blob/master/2020/23.py
Current code, comfortably within the 250 ms limit. Data structure is just a permutation (which is much the same thing as a circular singly-linked list but there's no need for any per-node data). I did peek, though.
Took a while to come up with a data structure that would make the moves efficiently. After a bit of thought today I realized I could use a (single) linked list with a dictionary from cup label to list node. Code: github (v1) runs in < 15 seconds on my machine.
Lua 44/49
Racket, part 2
Golang 925 / 299
part 1 part 2
This one was interesting! Part 1 wasn't too hard aside from me mucking about with a data structure I created pretty poorly. Then when part 2 unlocked I found out that the part 1 solution would take about 60 hours to find a solution :D So back to the drawing board. I had to implement a data structure (referenced in the code) from scratch :D
Java ~2s to run.
Python 3
Python3 - solution using a circular linked list + hash map.
Python 3.8.
For part two, I first tried rewriting my code with a circular list structure I wrote for Advent of Code 2018 day 9 (Marble Mania). I figured the mutable circular list implementation would be more performant. It was, but nowhere near enough.
Haskell, takes about a minute to run on my old laptop, presumably due to the high memory usage.
My Python and Rust solutions run in 10s and 250ms respectively. Do you guys know how to improve the performance for the Python version?
Python Solution parts 1 and 2
C++ Part1 and Part2
Link to CircleLinkedSet on Github
For me, switching from shuffling vectors / lists to updating an array took it from never going to finish to about 10 minutes, which is dishearteningly still 150x slower than yours. 😩
Here's my somewhat slow solution in Python3
My Python solution is under 2 seconds on pypy3 (macbook air). It's still about ~10 seconds on CPython though. https://github.com/wimglenn/advent-of-code-wim/blob/master/aoc_wim/aoc2020/q23.py
Singly Linked List and Dictionary Lookup Solution here
Code Repository: https://github.com/haskelling/aoc2020
Solution: part 1, part 2.
Part 1 / Part 2
Code here
Rust 489/629 This was fun. Since linked lists in Rust is a meme, I wound up using an array of next/prev pairs, which worked fine. Unfortunately I burned some time trying to get it to work with std::collections::LinkedList, which wasn't great because I wound up having to scan through the list too many times.
Go 1250/199
Python, 116 / 13, code
github
C++ 557/553
Nice you and I did about the same thing! if you're curious, a ring.Ring with Value as an int does not make it any faster. Im sitting at about 3.5s: https://github.com/A-UNDERSCORE-D/aoc2020/blob/main/2020/23/solution.go
Part 1 Part 2
Python 3 (permalink)
Python (1026/63)
part 1 https://github.com/dmshvetsov/adventofcode/blob/master/2020/23/1.rb (rank 3504)
C# https://github.com/Bpendragon/AdventOfCodeCSharp/blob/master/AdventOfCode/Solutions/Year2020/Day23-Solution.cs
python - circular linked list/dict
Python 3 2576/1581 (yes, I know, nothing to brag about)
Python (19/133), C
Go's deficiencies actually pointed me to a faster solution here. From the readme of kentik/patricia (an optimized radix tree for storing IP addresses), emphasis mine:
Python, (optimized) runs in .2 seconds on pypy
JavaScript 3234/2003
python
My thoughts exactly. But after the initial dread, I just used a vector and used indexes into that as pointers. Think this is sort of a general rust pattern (https://github.com/Japanuspus/adventofcode/blob/master/2020/day23/src/main.rs).
F#
Thanks. "Dyalog APL" in each post links to my repo.
Two solutions to part 2 in Scala, using a hash map and a vector respectively to implement a linked list / permutation.
C# LinkedSolution
After spending way too much time trying to implement a circular linked list in Rust (and figuring out why that is a bad idea), I realised we only need to store the next value for every cup. After that part 2 was quite straightforward. (part 1)
Javascript solution
Python3 solutions on GitHub.
Code available here.
Linked lists! Still took me a bit to implement though. I'll try to clean this up a bit
If you really want speed, you'll need to drop to Java arrays. Overall, your approach is based on a map from cup value (a long) to next cup value (a long). Clojure maps are great for many things, but if you need a fast representation of a mapping from integer to integer, the best option is a Java array. For me, switching from a map-based implementation to an array-based one reduced the time it take for part 2 from ~48s to ~4s.
golang
C++
https://github.com/diccy/AdventOfCode2020/blob/master/d23.py Same in Python... but runs in 12 seconds :'D
Python - I'm so glad I finally got this! There were some very helpful comments about today's Part 2 on this sub that helped me get on the right track. You can sorta see my process with list slicing at first which worked fine for Part 1, and then moving on to a linked list for Part 2. Takes a little under 35s to execute, which is abysmal, but I showed the crab who's boss and don't really feel the need to mess with it any more lol.
I don't think it's in the array access but in the moving stuff around. I used a vector where a[[i]] contains the label of the label of the cup next to the cup with label i. Twenty seconds
Nice! I struggled with the performance of my Swift solution. I thought the problem was that my huge nextCup array was getting copied every time I updated it due to Swift's copy-on-write. I worked around it by making it an array of integer references which can mutate without triggering the array's copy-on-write process. This helped a lot, but it still takes >30s to complete. 😬
Code (Python) I brute forced part 1, used a linked list stored in an array.
Javascript Day 23 part 1 and 2
For those interested: Numba guide; my code (updated).
Yes, definitely don't create a list for every pick up. No need to insert and delete if you use an array as a linked list. My code: https://github.com/ednl/aoc2020/blob/main/day23.py
both
Python (23 sloc. CAUTION: walrus operators!)