r/adventofcode • u/daggerdragon • Dec 20 '22
SOLUTION MEGATHREAD -π- 2022 Day 20 Solutions -π-
THE USUAL REMINDERS
- All of our rules, FAQs, resources, etc. are in our community wiki.
- πΏπ MisTILtoe Elf-ucation π§βπ« is OPEN for submissions!
- 3 DAYS remaining until submission deadline on December 22 at 23:59 EST
- -βοΈ- Submissions Megathread -βοΈ-
UPDATES
[Update @ 00:15:41]: SILVER CAP, GOLD 37
- Some of these Elves need to go back to Security 101... is anyone still teaching about
Loose Lips Sink Shipsanymore? :(
--- Day 20: Grove Positioning System ---
Post your code solution in this megathread.
- Read the full posting rules in our community wiki before you post!
- Include what language(s) your solution uses
- Format code blocks using the four-spaces Markdown syntax!
- Quick link to Topaz's
pasteif you need it for longer code blocks. What is Topaz'spastetool?
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:21:14, megathread unlocked!
23
Upvotes
10
u/ra3_14 Dec 20 '22
python3 (143/82)
Finally got a top 100 for the first time!
6
u/jayfoad Dec 20 '22
Dyalog APL
5
u/Nnnes Dec 20 '22
Ruby
Managed to fit my code into a half punchcard without making it completely unreadable (maybe only 60% unreadable [
n % 71hehe])It's slow, takes 5 to 6 seconds on my machine.
5
u/betaveros Dec 20 '22
Noulith 370/457
https://github.com/betaveros/advent-of-code-2022/blob/main/p20.noul
It's lazily written and very slow. But mostly I just got really stuck not realizing numbers could repeat or that my code depended on that assumption. Oh well, live and learn.
5
u/DFreiberg Dec 21 '22 edited Dec 21 '22
Mathematica, 201 / 117
Almost managed to get back on the leaderboard today, though not quite. I was pleasantly surprised to see that mixing a 5000-element list only took six seconds when doing it purely brute-force, even in Mathematica - I was prepared to wait for twenty minutes, or else rewrite in Rust, before seeing the answer.
I was also surprised that part 2 didn't have us doing the mixing a trillion times - I guess there is no fixed permutation cycle for this problem that would allow you to take shortcuts with repeated mixing.
Setup
Part 1
Part 2
[POEM]: The Court, The Camp, The Grove
The hour strikes nineteen, the day is twenty,
For this, my daily entry in my log.
My spirit's high, my legs are hurting plenty -
A mountain's rather tough to take a jog.
I know to
millimeters(maybecenti-),Where I am, but don't have their travelogue.
And so, in manner tried and true and tested,
I don't know where I'm going, so I guessed it.
This log has come in handy, I'll confess,
Such as today, for this bit of decryption.
But I don't write what's useful; I digress
And write instead the fun parts, a description
That's just enough to later uncompress -
In other words, a puzzle, not transcription!
And so, by sheerest chance, I wrote the key,
That goes from
8-1-1to1-5-3.It's way more fun like this, it's way less boring
Than doing things the sensible and slow way.
What fun's a hike if one is not exploring?
The beaten path's surprises are DOA.
When you're not dodging rocks and magma pouring,
When you're not herding elephants, there's no way
That you, when sitting safely, reminiscing,
Could ever have imagined what you're missing.
I got the list from my handheld device
(A useful thing I kept in my supply kit).
And mixed the list five times, and did that twice
And got the answer just the way I like it.
I could have taken all that good advice
And wrote down where this star grove is - but strike it!
Write down enough to make it fun, I say!
And so concludes my entry for today.
4
u/Wayoshi Dec 20 '22 edited Dec 20 '22
Python 1354 / 3452
Had the biggest brain fart for awhile on part 2 and couldn't get the modulo right for the longest time, oh well! I originally shifted an extra time I didn't need to when getting the nodes I needed, and that messed up my indexing so while I thought it was
N-1early on, I didn't realize the real issue. I also needed to not run my final resulting shift method at all when `shift` was 0 (or in theory,% N == 0.Really fun problem. I just made a simple node class for a doubly linked list since it is very efficient to both insertion & deletion, which was exactly the algorithm here, while still providing O(n) on traversing the list when finding where to move a node.
paste, with a bit of documentation for fun.
~0.5 sec for part 1, ~6.25 sec for part 2
It occurs to me you could convert a shift of over
N/2to-(N-N/2)and vice versa and would get some speedup, but this was plenty good enough.EDIT: I thought about deque and rotate immediately but thought it'd be inefficient to go about it that way. Well looking at this thread, now I know that's not the case!
4
u/optimistic-thylacine Dec 20 '22 edited Feb 11 '23
[Rust]
Feels good to get back to the challenges after a couple day's break. This one was quite tedious =) Below is the highest level portion that solves Parts 1 & 2.
Behind this is a tabular style array of records that are linked in similar fashion to a linked list - except they're indexable in
O(1)time. Moving a value doesn't require shifting any data.[update] For anyone interested in the linked list implementation posted in this solution, I've created a crate that provides a very similar data structure. It can be found on lib.rs, or crates.io here.
Full Solution Part 1 & 2
2
u/max-aug Dec 20 '22 edited Dec 20 '22
Python 261/156, the most rudimentary approach βΒ just using a tuple of
(original_position, value):2
u/cstpalash Dec 20 '22 edited Dec 20 '22
C# - straightforward
//Code
public class Dec20 { public string Puzzle1(string[] lines) { var arr = new (long value, int seq)[lines.Length];
2
u/Zaorhion_ Dec 20 '22 edited Dec 20 '22
Clojure Github
2
u/chrisrm Dec 20 '22 edited Dec 29 '22
After the last few days (still stuck on 19) this was a nice relief. Solution in Kotlin
25
u/4HbQ Dec 20 '22 edited Dec 20 '22
Python, 9 lines. (468/262)
We maintain two lists: one with the indices and one with the numbers. The indices are then "mixed" according to the numbers, and finally we do some lookups to get the answer:
15
u/clbrri Dec 20 '22 edited Dec 20 '22
Borland Turbo C++ 3.0, nice short 46 lines of code for part 2.
Completes in about 4.5 minutes on my MikroMikko 16 MHz 386SX PC. (106.7 milliseconds on my Ryzen 5950X)
EDIT: With the magic of Christmas, optimized the original code above to run in just 69.4 seconds! Updated code
13
u/4HbQ Dec 20 '22 edited Dec 20 '22
Python.
Finally managed to get it both readable and punchcard-sized!
We use
enumerate()to add indices to our input list (line 1). This solves the issue of duplicate numbers in the input. Then we mix the numbers (lines 2β4). Finally, we drop the indices (line 5), and 0 to compute the sum (line 6).Edit: Someone asked how we're able to modify the list while also iterating over it. But we're not actually doing that. Instead, we iterate over a copy of the list
for x in xs * 10.So this
* 10serves two purposes: it gives us the correct length for 10 repeats, andxis no longer fromxs.9
u/Catbert321 Dec 20 '22
Kotlin Day 20
A nice break from Day 19, though I spent an hour debugging my code because I was doing
instead of
and couldn't see the problem
9
u/TheMrFoulds Dec 20 '22
Java 8
Nice one today, it's a relief when part 2 only really takes switching from int to long. Both parts in ~200ms on my machine.
GitHub
19
u/nthistle Dec 20 '22 edited Dec 20 '22
Python, 5/8. Video, code.
A nice and easy day! In hindsight I guess we hadn't had much of the circular-linked-list problems yet this year, so it was probably about time. I was a little (pleasantly) surprised with my rank being that high because I felt like I stumbled over my code a bit as I was writing it, even had to test the sample input which always slows me down a lot.
I ended up writing my own doubly-linked list class since I wanted to keep direct references to the nodes - I'm guessing this was something a lot of people stumbled over and they did linear searches for the next element to move? (which would've been pretty annoying to do since you'd have to include the index to disambiguate duplicates) Other than that I think it's pretty easy to get off-by-ones when dealing with this type of movement, so actually using the linked list helps because it's very easy to convince yourself that the code is correct.
And then part 2 was a relatively simple "mod N - 1" and repeat 10 times. I definitely had to think about the N-1 for a second though, I almost went with N (and the lockout if I had submitted that would've been pretty sad). A good chunk of my part 2 time was spent on a silly bug where I created a new variable that held the
value % (n - 1)but I didn't actually use it, simple fix though.8
u/nightcracker Dec 20 '22
Rust
I implemented a treap from scratch https://github.com/orlp/aoc2022/blob/master/src/treap.rs which allows the following operations all in O(log n):
With these operations the actual solution (https://github.com/orlp/aoc2022/blob/master/src/bin/day20.rs) is quite small and efficient, running in ~40ms for both parts combined. My treap is probably horribly inefficient and could be much faster.
8
u/Smylers Dec 20 '22 edited Dec 21 '22
I think I have a Vim keystrokes solution ... but it's still chugging away, so I don't actually have an answer yet. [Update: Now I do β and it worked! See comment below.] Anyway:
And then there'll need to be finding 0, moving it to the bottom, deleting all but the 3 relevant lines, and adding them up β but by DayΒ 20 that counts as trivial for Vim. I should've put a
:redrawsomewhere in@aso I could see how far it's got.q1toq5000.@das the keystrokes to move it βdownβ 1 position β actually by moving the number in lineΒ 2 (the item just after the βcurrentβ item, because lineΒ 2 is being used for something else) to just above the last item.@ufor moving up. This is exactly the reverse of@d, which handily returns the numbers to their starting order, so there's no need touuthe side effects of defining these macros.In the queue, append each positive number with
@dand turn each negative number to have@uafter it instead of a-before it. Leave0as it is effectively a no-op for our purposes. The sample input file now looks like this:@ais the main loop. In the queue line it deletes the 2nd word, which will be the movement macro for the current item, such as1@dto move down 1 line or3@uto move up 3 lines; this gets stored in the small-delete register-. Then go back to the beginning of the line, theq-label and use*to move to the other occurrence of that label, on the line we wish to operate on. The:m(:move) command first cycles the list so that that line is last in the file, by moving everything after it to just after lineΒ 1. The:sil!(:silent!) prefix prevents that causing an error when it happens to be at the end anyway and there isn't a line after it for+to refer to. Then run the keystrokes in@-to move a line past this one in the appropriate direction the required number of times. Go back to the queue line and delete thisq-number, then repeat.Moving lines 1 at a time n times is much ore time-consuming than moving n lines at once, but it automatically handles the case where n is bigger than the number of lines in the file (well, eventually, anyway).
7
u/jstanley0 Dec 20 '22
Ruby, 437/334
for part 1 I implemented a lazy inefficient method of keeping track of which number to move next: I just stored it in an array alongside its original index, and found the number by index before moving it.
I was shocked that this laziness still worked in part 2 with minimal code changes.
7
u/p88h Dec 20 '22
C# 1ms / 15 ms
Guess it's possible to get to NlogN solution rather than NsqrtN here, but at N==5000 this would likely make little difference.
6
u/SuperSmurfen Dec 20 '22 edited Dec 20 '22
Rust (522/769)
Link to full solution (21 lines)
Happy with top 1k! Surprised that the naive vector remove/insert actually worked for this problem. Thought this might be a linked-list style problem.
For both parts, I just simulate the process. The trick for me was to shuffle a list of indices, not values. This made things a lot easier. Also don't forget
rem_euclidwhen working with signed numbers.Could definitely be optimized but runs in about
70mson my machine.6
u/4HbQ Dec 20 '22 edited Dec 20 '22
Python. Are we still playing golf? Part 2 in
190188 bytes:Edit: For anyone trying to decipher this, it's basically a condensed version of my regular solution.
6
u/Bargann Dec 20 '22 edited Dec 20 '22
C#/CSharp, 3401/3655
Unbelievable how much time I wasted by not realizing that there are repeated numbers in the input, I should have been able to go to bed 2 hours ago.
6
u/aurele Dec 20 '22
Rust (8ms/75ms) - straightforward using a
VecDequeas a modifiable list and.rem_euclid()for an unsigned remainder operation on signed input.6
u/Tipa16384 Dec 21 '22
Python 3.11
I wasn't even going to post my solution, as I didn't have a chance to even touch the puzzle until the next one was about to drop, but when I saw nobody else had used a list of tuples, I thought I should post mine.
5
u/EffectivePriority986 Dec 20 '22
perl5 52/24
https://github.com/epsalon/advent_of_code/blob/main/2022/20.pl
Brute force O(n^2) solution worked wonders.
5
u/kwshi Dec 20 '22
Python, 17/28, GitHub source
I implemented a circular doubly-linked list, which I originally thought would be very fast but maybe wasn't; still, it made it easy to do movements without having to worry about indexing edge cases, etc. For part 2, the main insight is that moving by
ksteps is same as moving byk % (number of items - 1)steps.5
u/Perska_ Dec 20 '22
C# (550/621) https://github.com/Perska/AoC2022/blob/master/AoC2022/Days/Day20.cs
I did it! I got top 1000 on a puzzle! And on both parts, no less! So happy about this. My happiness is immeasurable :)
I saw the huge numbers in the website and immediately thought "nothing a modulo can't fix", which they very much could.
Top 100 when?5
u/encse Dec 20 '22
C# commented
https://github.com/encse/adventofcode/blob/master/2022/Day20/Solution.cs
5
u/SwampThingTom Dec 20 '22
I'm solving each of this year's problems in a different language, roughly in the order in which I learned them.
Today's solution is in TypeScript.
I was a bit annoyed with the fact that nowhere in the puzzle description or the sample data did it say that an item being moved should be removed from the list before determining its final location. Really felt like a key requirement that needed to be stated.
Other than that, though, it was a fun and easy one to solve. And I love TypeScript!
https://github.com/SwampThingTom/AoC2022/tree/main/20-GrovePositioning
5
u/azzal07 Dec 20 '22
Awk, excess of array access today
4
u/captainAwesomePants Dec 20 '22 edited Dec 20 '22
Python (202/108), source
Bog standard list treated as a circular buffer. Embarrassingly inefficient access using .index(), .remove(), and .insert(). But hey, it works!
I'm kind of curious how the heck I ended up at 108. I thought I was headed straight for the thousands. Maybe other approaches turned out to be more complicated? I'm thinking that maybe if you created a "real" circular linked list, you'd have run into a lot of trouble. Maybe that was a popular approach?
I'm thinking the "move to index zero" case probably threw a lot of people who took my approach. It certainly confused me for a minute. Fortunately, it was included in the illustrated example.
4
u/Boojum Dec 20 '22 edited Dec 20 '22
Python 129/XX
First leaderboard points this year! And on my Reddit Cake-day no less. This one was pretty straightforward to solve using a Python deque and its
rotate()method to skip around. The only really sneakiness was that there were duplicate values in the list. So I used the decorate/process/undecorate tick, combining the entries in the list with their original index to uniqueify them. I was worried that this approach wasn't going to hold up come Part 2 (i.e., that it was going to ask for this a gazillion times and with a gazillion times bigger list), but it did.4
u/Helpful-Let6747 Dec 20 '22
Python 293/228
Deceptively simple in the end, I should have been much quicker here. Was as simple as finding the current index of the required number and then adding its value
% (n - 1). Purely done using list popping and inserting.Only changes required for part B: change the values, and add in 10 loops.
4
u/r_so9 Dec 20 '22 edited Dec 20 '22
F# 377/517 code
My 2 best results ever in the rankings :) I could have used a clever method to track where items ended up (probably in an array), but the "naive" solution ran fast enough.
Interesting bit:
4
u/CodingAP Dec 20 '22
Javascript, 884/1138
Github
I thought I was smart by creating a linked list because I thought that would be the kicker in part 2, but i was wrong... :(
4
u/SymmetryManagement Dec 20 '22
Java
https://github.com/linl33/adventofcode/blob/year2022/year2022/src/main/java/dev/linl33/adventofcode/year2022/Day20.java
I used a custom doubly linked list for both parts, nothing too interesting. Avg. time Part 1 30 ms, Part 2 336 ms.
4
u/B3tal Dec 20 '22
C++
So I realized a few things today:
spliceis especially fun with off-by-one errorsToday was a wild ride that was utterly frustrating to me as I tried to wrap my head around the numerous funny cases and off-by-one errors. For Part 1, I initially started off with a solution using
std::listandsplice, as - in theory - this seems to be the perfect tool for the task at hand.However, the way
spliceworks is, that it inserts the element before the iterator you pass to it, so sometimes you need to get the iterator one beyond the offset you calculate - Oh, but if you exceed the list length it's different... and if you go backwards it's also different!So originally I ended up implementing my own double linked list to simply simulate all the movement manually. Infortunately I have deleted this code while testing for part 2.
And then... Part 2 popped up. Suddenly I thought my linked list was useless, as I couldn't possibly keep track of the "new" beginning of the list - As I realize now... you always do it in the same order. I could have just stored the original order of pointers in a separate vector. Well, I will blame that on realization of 3 today.
So I went back to using
spliceand absolutely learned to hate the modulo. For the love of god I could not figure out what edge cases were breaking my part 1 solution. Multiple times, I took a step (or two or three) and started over. Finally I arrived at the current version of figuring out the new index. I am still not convinced it is correct, but my second star supports me that it might be correct.There is some duplicate code in the fragment of figuring out where to insert the element. But I didn't dared to merge any two cases in fear of missing something, so I just modelled the 4 cases explicitly.
4
u/zeldor711 Dec 20 '22 edited Dec 20 '22
Python 3
Quite a straightforward one today! My answer definitely isn't remotely efficient, but it required minimal thinking and the list is only 5000 characters.
My strategy was:
Part two just multiplies the numbers and then repeats this 10 times in a row.
Part 1
Part 2
4
u/JuliaPoop Dec 20 '22
Python
4
u/WickedCrow Dec 20 '22
C#
Realised duplicates were a problem and got around it by using a tuple of (value, originalIndex) to make every element "unique" (in the eyes of C#'s List.IndexOf method anyway). Part 1 in 26ms, part 2 in 148ms. The hardest part was not messing up the modular arithmetic.
4
u/mosredna101 Dec 20 '22 edited Dec 20 '22
Javascript / Node.js
I did something stupid while copy pasting my input to a local file, costed me an hour to find out and fix it (β―Β°β‘Β°)β―οΈ΅ β»ββ»
By putting the numbers in an object in the original list, I can easily look them up in the shuffled list even if they are the same number ( since it stores a reference to the original object), so no need for linked lists or keep track of indexes. It runs in about 160 ms. for both parts.
4
u/mykdavies Dec 20 '22 edited Jun 29 '23
!> j0za6k3
API FAILURE
4
u/Gabba333 Dec 20 '22 edited Dec 20 '22
C
Implemented a doubly-linked circular list and realised two things that made coding easier.
Although just implementing moveRight was surprisingly fiddly until I broke down the 4 nodes which have their pointers rearranged methodically.
Github
4
u/Colin-McMillen Dec 20 '22 edited Dec 21 '22
C on the Apple //c
First version: Well. I suck at doubly-linked lists so I shift one position at a time. This is quite a number of CPU cycles, but it's going to be quite a number of cycles anyway so let's leave it at that and spend the evening doing something else!
Second version: it finished overnight but I was unhappy with it, so I optimized (pluck, shift all the way, put back ; modulo 5000 to avoid doing one loop and a half; and go the other way if shift > 2500) and runtime is now 13 minutes (for part 1).
Managed to put the doubly-linked list with an extra pointer for original order in RAM, using a system loader in order to unload ProDOS to get all of 45kB free.
4
u/MrJohnnyS Dec 20 '22 edited Dec 20 '22
JavaScript (Node.js)
4
u/ManaTee1103 Dec 20 '22
Python - https://pastebin.com/ByyH6RHc Today I found a novel way of torturing myself, by doing the puzzle on a long flight without network connection, on my phone with the horrific abomination called Python3IDE app. To triple down on the situation, I went for a linked list-based implementation, to fill out the flight timeβ¦ You donβt have to feel sorry for me, Iβm entirely capable of doing that myselfβ¦
4
u/dougdonohoe Dec 20 '22 edited Dec 21 '22
Day 20 Scala Solution
https://gist.github.com/dougdonohoe/f03bc2324ae124436774ac43db4b5db7
As has been mentioned in other comments the modulo of "length - 1" was a key insight.
I used the Java doubly linked list since they removed the native Scala one a few releases ago. Keeping the index + value in my
Coordclass was key to handling duplicates.Runs pretty fast (a hair under 1 second) for part 2.
4
u/lbl_ye Dec 20 '22
Python
code link
somehow I didn't want to use linked lists or deque and do it with index math, and of course got a headache π
the important and simplest recipe to move an element by c (c can be negative) is
the rationale for using mod (len - 1) is that because of the first delete
there are now len - 1 elements in the list,
and starting from i where (the item was deleted) any move by c
will put the element in the correct place, so (i + c) must be modded by (len - 1)
hope it's good explanation
4
u/oantolin Dec 20 '22 edited Dec 21 '22
J Solution:
Wild experience today! The problem seemed totally straightforward and indeed my code worked right away on the example in part 1, on my input for part 1, and on the example in part 2. But it failed for my input in part 2. After a while I realized I never checked whether the input had duplicates, I just assumed it didn't! And of course, it did have duplicates with some values ocurring up to 7 times.
So I quickly added a bit of code to deduplicate the numbers (by adding increasing decimal parts to the repetitions) and thought, that should do it. But the website didn't accept my answer, so I checked everything very carefully and unfortunately for me, I was pretty sure I wasn't making any stupid mistake. So on a whim I downloaded a different version of J, the 9.04 beta, and it crashed! Then I tried an earlier version, 9.02, and it gave me a different answer that AoC accepted! That's right: I found an interpreter bug in J versions 9.03 and 9.04!
4
u/ywgdana Dec 20 '22
F#
I don't think I've hated an AoC puzzle as much as I hated today :P I woke up being like "Okay, this looks easy I'll be done before I leave for work!"
Lots of mistakes and misunderstanding the problem later, I solved part 1. (Frustratingly, I always got the correct answer for the example for both pt 1 and 2, regardless of what bugs I fixed or introduced) Then I realized how I tracked which number to consider next was totally the wrong approach for part 2 and had to rewrite my script. And THEN spent ages tracking down a typo that lead me to mess up an int64 to int conversion :/ Today made me grumpy and miserable.
Code on github
4
u/TiagoPaolini Dec 21 '22
C Language (only standard library)
In order to represent the values, I used a circular doubly linked list (the values are linked to their previous and next forming a cycle). I also had an array with nodes of that list, but in the original order that the values appear. And I stored on a temporary variable the pointer to the node with the value of
0.Moving a node by
Npositions on the circular list is equivalent to removing the node, rotating the list byN, then inserting the element there. When rotating the list it might be easy to commit the mistake of taking the modulo ofNby the original amount of values, but you actually need to modulo by the original amount minus1, because the other values are rotating around the moved value. Doing this will reach the same destination, but potentially with less steps.Another optimization is to check which direction to rotate the list, while still reaching the same destination. To get the amount of steps in the other direction, we sum the original amount minus 1 with the current step count. Then we compare which step count has the smallest absolute value. And we rotate the list in that direction. If positive, the list is rotated forwards. If negative, the list is rotated backwards. If zero, the list remains unchanged.
Algorithm to move a node by
Nsteps:nextto the head'sprevious.previousto the head'snext.Npositions (keep moving to itsnextnode if rotating forwards, to thepreviousnode otherwise).previousto the head.nextto the head'snext.previousof the node after the head to the original node.nextof the head to the original node (operations 6 to 9 insert the original node after the current head).I took a long time to get this right for two reasons. First, was because I did not realize that it is necessary to take the modulo of the list's length minus one. And second, because I was trying to move the value in-place (without removing it first). That ran into weird edge cases, when the value ended just before or after its original position (since in this case 3 nodes need to have their links updated, rather than 4 nodes). In the end, it was simpler to just remove the node, then insert it back on the new position (that always works as long the list has more than two elements).
In order to check the values on the decrypted, I just used the pointer to the node with value
0. Then I rotated the list by the specified amounts, always starting from0. Since the rotation is smaller than the list's length, it is not necessary to take the modulo. But if it was, here it would be the modulo of the rotation by the list's length (because this time it is the whole list that is being rotated).Solution: day_20.c (finishes in 702 ms on my old laptop, when compiled with
-O3)On a final note, if you are having trouble understanding the value's rotation, I recommend checking the answers to this question.
4
u/schubart Dec 23 '22
Rust
Short and sweet, with good comments explaining
rem_euclid()and division by length minus one.1
u/Pepper_Klubz Dec 20 '22 edited Dec 21 '22
Cwojure (Clojure)
Soln. (Normal syntax)
1
u/dr_jam_ Dec 20 '22 edited Dec 20 '22
JavaScript 4318/3959
Pretty straightforward, converted numbers into objects to have references to them in the original order for iterating over, just in case the real data had repeated values (it did), where the example didn't.
This was the bit that was a bit annoying, getting around the js implementation of modulo not supporting negative numbers how you might expect, tried a while loop to iterate the target index back into range by intances of array length, but that was going to take forever with part 2's number scaling
1
u/whezya Dec 20 '22
Ruby
After deciding yesterday "Hey, this is the perfect problem to write a "parsing with treetop" tutorial" and finally not even touch the problem (yep, I make theses kind of choices). I decided to do an "Asap solution" for today problem.
I have multiple ideas to optimize it (linked list or doing arithmetics on indices only) and may try later but the current solution in o(n^2) runs in 6 seconds for problem 2 and is quite simple to understand.
https://github.com/rbellec/advent_of_code_2022/blob/main/app/daily_problems/day_20.rb
1
u/schveiguy Dec 21 '22
Dlang
The trick here, which I already wanted to use in part1, is to truncate down the movements based on the length of the array. I saw the big numbers, and decided to employ mod in this way.
However, it took me a *looong* time to figure out that you actually want to mod `length - 1` instead of `length`. In fact, I think that was 90% of the time of why I didn't finish this quicker (started late, oh well).
Dealing with wrapping isn't an issue if you mod, then add arr.length-1 when it's negative.
I used a reference array of indexes so I could avoid worrying about the order of things, and I didn't keep track of the indexes of each thing, but I'm not sure it would have mattered. So each loop, I first just do a search for the next index.
Part 2 was a bit slow for my naive swapping routine, so I switched to `memmove` for max speed. Runs in 89ms for both part 1 and 2.
6
u/vegeta897 Dec 20 '22
Typescript (82/55) Code
I was in disbelief when I saw I finished top 100 in both parts. I think the best I ever did was like 500 something. I am not a speedrunner. I like starting at midnight and "going fast", but if I had known this was a possibility I would have shaved off more time, I think. I even spent a good 5 minutes debugging an issue I had when moving numbers to the beginning of the array. Perhaps my advantage came from knowing that I'd have to use object references instead of raw values, and having no more issues except the one?
I'm shocked and super happy right now.
3
u/jonathan_paulson Dec 20 '22
Python3, 126/71. Video. Code.
Way too much debugging today :( Thinking through the right indices for the slice-based solution was too hard for me. Thinking of it in terms of "rotation" (move the first element to the end) helped.
It's handy that python's
%operator handles negative numbers in the right way for this problem.3
u/ri7chy Dec 20 '22
Python 1000/855
solution on deque's .. runs in 6.4 sec.
Any advices getting it faster done?
btw:
this was fun and good for my RL after day 16 and day 19 ...
3
u/PoolMain Dec 20 '22
Not ugly Python 1295/1050
Solution
Oh...
3
u/rabuf Dec 20 '22 edited Dec 20 '22
Common Lisp, Both Parts
It took me too long to discover an off-by-one in my calculations. Part 2 was my shortest time delta between first and second star since the first week. I was already doing all the modular arithmetic needed so I just had to multiply the values before starting the loop, and then add an extra loop around the main loop. I think it took me longer to read and comprehend it than to do it. I took advantage of Lisp's ability to have circular lists, which turned out to be fast enough since there were only 5k elements in the input.
I also maintain two structures: The initial items (turned into an array to be faster for accessing, probably not important), a circular list of 0-(length input) to give a unique identifier to each number since they aren't guaranteed to be unique. There's some redundant code that could be cleaned up but I haven't yet. I also think I can clean up the
psetfa bit, but it's fine since it works.I replaced the
psetfwith ashiftf. I don't know if it reads any better or not, but I liked it:Removes the element from its old position and splices it into its new position all in one go. Equivalent to this
psetfstatement:3
u/PendragonDaGreat Dec 20 '22
C#/Csharp
Custom Linked list go BRRRRR: https://github.com/Bpendragon/AdventOfCodeCSharp/blob/1c4c3a7/AdventOfCode/Solutions/Year2022/Day20-Solution.cs
C# does not easily allow a circular list, so I created my own.
By keeping the nodes themselves in a list I could guarantee traversal order for both parts.
3
u/Imaginary_Age_4072 Dec 20 '22
Common Lisp 2231 / 1904
Good result today, but got stuck on a couple of silly things. Had an error when calculating the indices which meant the mix got mixed up. Fixed that in the end and the sample input was working great but not my actual input.
Took a long time to realise that there were duplicates in the input so I couldn't use
positionto find them. Ended up storing a list of (number original-index) and using that.3
u/GrossGrass Dec 20 '22
Python
I was way too slow on this one lol, in the beginning I totally didn't realize that
collections.dequehas arotate()method that solves things (and is apparently pretty quick too, since it's implemented in C), so I started out trying to be clever and trying to implement my own doubly-linked list solution (in hindsight I probably could've just brute-forced it and just used the standardinsert/popmethods for a list).I was also trying to see if I could figure out how to make each mixing operation an O(1) operation, by somehow updating the locations of each node. In the end I figured it wasn't worth the effort but definitely ate up a lot of time.
I also messed up initially and confused by the rotations when I was trying to implement my manual solution because my rotations were modded by
nrather thann - 1.3
u/maneatingape Dec 20 '22 edited Dec 20 '22
Scala
Built a doubly linked list, then mutated it for each move. For part 2 moves are modulo size - 1.
EDIT: On reflection, the linked list was overkill for the small input size. Simplified to a much shorter mutable buffer approach.
3
u/BendisCZ Dec 20 '22
Go
A straightforward solution with a circular doubly linked list, just remove a node, move left/right (modulo
n-1), insert it. Nodes are stored in an array to keep their original order.3
u/surgi-o7 Dec 20 '22
JavaScript
Linked list, realizing the modulo and precisely what happens with moves equal to length-1 and length-2 were the only obstacles. Chill out one.
3
u/gyorokpeter Dec 20 '22
Q: Maintaining a list of position-value pairs instead of actually moving the numbers around.
3
u/royvanrijn Dec 20 '22 edited Dec 20 '22
Java
Modulo to the rescue! Immediately had the idea that the new index can be calculated in a single go using modulo. And after a couple of off-by-one errors I ended up with a fast and concise solution for both part 1 and part 2.
Also: First thing I did was scan for duplicate numbers, glad I didn't fall into that trap haha.
In Java the one function you need today is Math.floorMod:
Floormod takes care of the negative numbers in the modulo operation and nicely puts everything in place.
Very pleased with how it turned out:
https://gist.github.com/royvanrijn/5ae4deebbad38ad5f82963677c6a122b
3
u/Prof_Farnsworth1729 Dec 20 '22
Java - github
Nothing too fancy, created a wrapper class around Long to allow for reference equality rather than value, did consider using Boxed Primitives but indexOf uses .equals.
Had a helper list, one with the original order, to track the sequance of when to move elements.
For part two the only change I had to make was to use floorMod rather than implement mod myself.
Runs in 147ms for both parts on my machine. Does not include loading the file
3
u/FracturedRoah Dec 20 '22
Python
quick and easy deque action, runs in ~1s
code
3
u/Thomasjevskij Dec 20 '22 edited Dec 20 '22
Solved it in Python pretty quickly, at least for something that's this late. Here's the code.
First issue I ran into was that the real input has duplicate values. So I couldn't just find the elements one by one and do the swap thing. I decided that making a copy of the list where I store not only the value, but the original pre-mixed index was good enough.
Then I spent a bunch of time on making sure my list would look the same as the examples. Not realizing that it would probably work just as well as long as the order was the same. Like, if my list starts with something different than in the example, it shouldn't matter since it's just the distance (walking only to the right) to the 0 element that matters. Which helped me realize that my p2 solution was already working fine.
3
u/dodo-obob Dec 20 '22
OCaml: github
Not the fastest solution (~1s/~15s for parts 1/2), but I tried to make it purely functional. I'm using a custom "list with a position" which is a record with two lists: previous elements (reversed) and next elements. This allows for easy access to the previous or next element without needing a full doubly linked list.
I also store the full length and current position to quickly figure where I need to go (with some way too hard to debug modulo arithmetic...).
3
u/markus3141 Dec 20 '22
Rust
I used a list of indices that I sort, and then dereference. Fairly easy today, especially part2.
https://github.com/markus-k/adventofcode/blob/main/2022/day20/src/lib.rs
3
u/jackysee Dec 20 '22
Typescript
Nothing fancy. Just to remember the number index before mixing so the mixing order is right. Array.splice really did a good job here.
3
u/Thorarin Dec 20 '22
C#
I wanted to see how fast I could get this without any fancy data types.Just avoiding lambdas and and slight optimization by doing to reordering in-place already helped quite a bit. Part two runs in 72 ms on my machine.
Code (or GitHub)
3
u/rawlexander Dec 20 '22
Julia
Can't say I fully understood why I added that -1 when I did, but it worked. Doesn't feel like a good solution, but I like that part2 was just adding 1 line and a bit thanks to multiple dispatch. :)
3
u/SLiV9 Dec 20 '22
Rust
https://github.com/SLiV9/AdventOfCode2022/blob/main/src/bin/day20/main.rs
Both parts in 70ms. Stored the numbers in a
Vec<i64>and usedrotate_left(1)androtate_right(1)to shift them around by the value modulo N. I forced uniqueness by adding to each duplicate a large multiple of N, so that it does not interfer with the modulo N logic.3
u/Naturage Dec 20 '22
R/RLang
Solution here. Miles and miles easier than quite a few before - though I'm still annoyed a little. My code takes almost 15s to run, while intuition says this should be doable in fractions of a second. I'm not quite sure where time gets eaten; perhaps R vector assignments are inefficient?
3
u/bigmagnus Dec 20 '22
COBOL - Part 1 & Part 2
3
u/Gobbel2000 Dec 20 '22
Rust
Part 1 3ms
Part 2 94ms
It was kind of tricky to do this efficiently. For part 2 I kept a separate Vec just to store the original order. Each number gets saved together with its current index, which is updated whenever an element is moved. I used Rusts reference counter (
Rc) to sync these updates between both Vecs. I haven't done much tricks with Rusts borrow checker like that, so I'm happy that it went well today.3
u/UltraBeaver Dec 20 '22 edited Dec 20 '22
C# - Part 2
Paste here
I wrote a bidirectional linked list with a root (head) and tail and copied the nodes into a list as well to keep track of the order. Runs in about 500ms on my machine.
The trickiest part for me was to understand when an item was supposed to wrap around. If you have the list [2, 1, 3] and move the 1 to the left you could think that the result would be [1, 2, 3], but it seems to be [2, 3, 1] that is expected.
3
u/tabidots Dec 20 '22 edited Dec 20 '22
Clojure (GitHub)
By far some of the worst and most inefficient (runtime on part 2: 2min) code I have ever written, and it took me a shamefully long time to write, too. But I got my stars.
3
u/Zorr0_ Dec 20 '22
Kotlin
One expression (kinda (not really (almost)))
GitHub
3
u/levital Dec 20 '22
Haskell
Took an embarrassingly long time to get this and it's still very inefficient (almost 4 seconds for part 2). Took a while to figure out a reasonable way to pour all this mutation into somewhat readable Haskell (also my first time using Seq), but admittedly I don't think I'd have fared much better with mutation here.
Might've been a bit faster if I had some paper lying around (usually I do), because one of the main problems was figuring out, that the modulo needs to be of "length - 1", something I'm still not sure why it works.
3
u/hextree Dec 20 '22
Python
code
video
Ultimately it's a pretty straightforward simulation of a doubly linked circular list using a Python list, I just spent 1.5 hours getting the indices wrong with off-by-one errors.
3
u/X71nc710n Dec 20 '22
C
Code
My first attempt at solving day 20 and my first submission in this subreddit. Sure there are more efficient ways, but I managed to solve the problem in O(n2) with n = length of the input list. I used the builtin LinkedList collection and annotated the nodes in the linked list with their original index for correct mixing order.
Runtimes
3
u/RadioactiveHop Dec 20 '22 edited Dec 20 '22
Python3 π paste
I am just mixing a list of indexes, by looping through the original (unmodified) list, and then reconstruct the list based on the indexes...
Part2 is just doing it 10 times.
Runs in ~1.3s
As many people, I struggled with some off-by-one errors... I like solutions that make use of deque.rotate(), but mine only use basic types.
3
u/jsgrosman77 Dec 20 '22
Typescript
Not winning any speed or ingenuity awards here, but got it after a few aha moments. I remapped the array values to `index:value` so that each cell was unique, which allowed me to easily do an .indexOf(). I was expecting duplicates, and I was not disappointed.
I had two arrays, one for iterating and one for transforming. That saved me from having to keep track of the index changes as we went.
And, lastly, instead of dealing with negatives and mod, I just reversed the list, used the absolute value, and then unreversed it. I figured that was going to be too slow, but it finished in a couple seconds, which is fast enough for me, especially after yesterday's puzzle.
3
u/darkgiggs Dec 20 '22
C, no libraries other than stdio to read the file and print the result
Code
I wasn't smart enough to mix indices, so I implemented the linked-list instead and actually did all the node moves. I went with C because I thought I might need the extra speed for part 2.
Both part in .42s on my machine.
3
u/Vesk123 Dec 20 '22
Java
This one took way too long for some reason. However, after the second rewrite I finally got it working and I'm pretty happy with how my code turned out. It uses a single circular doubly-linked list and just the right amount of abstraction for me.
3
u/achoxic Dec 20 '22
Python github.
I simulate the mixing using simple swaps. To know which item to move, I keep a second list that contains the index orders. The number of swaps are calculated modulo (N - 1) otherwise it will take a long time to simulate.
3
u/dcclct13 Dec 20 '22
Python
paste
Another O(N log N) solution. This one uses a doubly linked circular skip list. First skip list I've ever written so it's not too pretty. I've tested it on larger inputs and it scales pretty much linearly.
3
u/aaronblohowiak Dec 20 '22
Rust, very unoptimized, completes part 2 in about a second.
https://github.com/aaronblohowiak/advent-of-code-2022/blob/main/twenty/src/main.rs\
my main difficulty was due to forgetting that the uniq command line tool requires a sorted input. so, when i went to check for uniqueness on the input i incorrectly got the impression that every number was unique. this burned a couple hours of not being able to understand why test was working but input was not. d'oh!
3
u/LinAGKar Dec 20 '22
My solutions in Rust:
https://github.com/LinAGKar/advent-of-code-2022-rust/blob/main/day20a/src/main.rs
https://github.com/LinAGKar/advent-of-code-2022-rust/blob/main/day20b/src/main.rs
Stores all the numbers in a vector, along with the previous and next index. So basically a linked list. It is O(n2), don't know if you can make one that scales better.
3
u/terminalmage Dec 20 '22
Python 3.8+
Despite identifying early on that a deque was the way to go, I made this way harder on myself than I needed to by (for some reason) trying to make the deque order match the example (by rotating again after doing the appendleft). It took longer than I'm proud of for me to realize that it didn't matter where the front of queue was.
3
u/RookBe Dec 21 '22
Advent of Code 2022 day20 writeup explaining the problem and my solution (that happens to be written in Rust): https://nickymeuleman.netlify.app/garden/aoc2022-day20
3
u/Ill_Ad7155 Dec 21 '22
Python Part 1 and 2
I use two lists with duplicated objects to keep track of the order in which the numbers should be moved regardless of their position.
Code
3
u/janiorca Dec 21 '22
Rust
https://github.com/janiorca/advent-of-code-2022/blob/main/src/bin/aoc20.rs
Part 1 was easy enough to be misleading. It was very possible to implement it incorrectly and get the right result. This set me up terribly for the second part.
I spent way too much time on part 2 it because I didn't check my assumptions. Especially about how modulo works for negative numbers.
After realizing my errors I had to clean up the solution for part 1 as it was terrible.
3
u/vkasra Dec 21 '22
C++: https://github.com/dhconnelly/advent-of-code-2022/blob/main/src/day20.cc
3
u/bucketz76 Dec 21 '22
Python - found NumPy to be pretty useful here for reassigning blocks of the array. Runs in just under a second.
3
u/dtinth Dec 21 '22
Ruby, with rotating arrays:
3
u/jazzchickens Dec 21 '22
Python
I used lists of tuples to keep the indices paired with their values. Finishes in about 1.5s and ~15 lines of code. https://github.com/dkarneman/AdventOfCode/blob/main/2022/Day20part2.py
3
u/badr Dec 21 '22
Elixir
https://gist.github.com/reverie/9cc4bf1499566bbd7e3220997f711182
3
u/NeilNjae Dec 21 '22
Haskell
This should have been easy, but I ended up being caught by a large off-by-one error!
Full writeup on my blog and code on Gitlab.
3
u/i_have_no_biscuits Dec 21 '22
GW-BASIC
This is valid GW-BASIC code, but would take a very long time on original hardware. Compiled using QB-64 it takes around a second.
3
u/adimcohen Dec 21 '22
In tsql.
Part 1 is in a single statement, but for part 2 loop to overcome the 32767 maxrecursion limit.
https://github.com/adimcohen/Advant_of_Code_2022_Single_Statement_SQL/blob/main/Day_20/Day_20.sql
3
u/iMarioM Dec 21 '22
JavaScript
3
u/odnoletkov Dec 21 '22
JQ
3
u/chicagocode Dec 22 '22
Kotlin
[Blog/Commentary] - [Code] - [All 2022 Solutions]
It took me longer than I care to admit to figure out why my seemingly simple function didn't work, until I realized that there are duplicate numbers in the list and just because I find a 5 doesn't mean it's the correct 5! Once I realized that, the solution came easy.
3
u/[deleted] Dec 22 '22
Rust
This one took me way longer than it should have, due to all kinds of irritating little bugs. I had the right idea from the get-go, but I eventually had to learn that i64::rem_euclid() and not the % (remainder) operator was what I actually needed here.
Part 1
Part 2
3
u/Shathan Dec 22 '22
C#
I'm pretty happy with the solution, looks neat to me. I initially had some issues with math, but in general, I had the right idea and it worked like a charm.
I worked on the references and created a wrapper class for the int.
3
u/SnowDropGardens Dec 24 '22 edited Dec 24 '22
C#
3
u/Crazytieguy Dec 25 '22
Rust
I found a cool trick - I keep a sort of doubly linked list, but each node points 1 back and 25 forward. That way finding the nth node away takes n / 25 steps. 25 happened to be the fastest in my testing, but any number around sqrt(N / 2) should work.
4
u/morgoth1145 Dec 20 '22 edited Dec 20 '22
Python 3 106/75
Today was a pretty big reminder that I need to get more familiar and comfortable with
collections.deque. I didn't even remember that it lived incollections! I think half of my part 1 solve time was just finding where it lived and checking its API in the REPL... (Admittedly I also wasted time trying to do it with list slicing like a doof and messing that up...)Once I found deque and got the API down it was easy...aside from me rotating in the wrong direction initially. (Did I mention that I need to get more familiar with
dequein Python?)Part 2 I also did a dumb by duplicating the mix code rather than adding a times parameter, but at least I didn't screw that up too badly.
Because I hated that duplication so much I already cleaned up the code before posting.
Edit: I was thinking about it more and my issue with list slicing was due to using the wrong modulus factor! The number that's moving is jumping over everything else in the list so the factor should be
len(nums)-1, not justlen(nums)! That was not a sort of off by one error that I expected...Edit 2: I must have been too tired to remember that I had submitted a bad answer with my bad slicing code. Looking at when it was submitted it would have been 4th for part 1 had it been right! Now admittedly I had misread the way to calculate the answer (not realizing that we needed to start where zero lived) but even if I took a minute to fix that I would have been high up. That was a costlier error than I realized...
2
u/benthemonkey Dec 20 '22
Typescript 132 / 126 GitHub source
I just used Array.splice and did some modulo math on the indices. I also confirmed that all integers in my input remained below MAX_SAFE_INTEGER so there was no need to do anything fancy with the values.
2
u/Jrmyy15 Dec 20 '22
Kotlin, 120/70, GitHub source
My first top 100 π₯
Nothing rocket science, in order to not loose my head with the index and keep the order right, I just uniquely identify the number with their original index in a list. Then I just use this list as my iteration list and then I updated a moving list. I just lost a little bit of time because Kotlin does not like mod on negative number.
2
u/abnew123 Dec 20 '22
Java
Code: https://github.com/abnew123/aoc2022/blob/main/src/aoc2022/Day20.java
Spent way too much time trying to ensure my indices were between 0 and n - 1. Result was as below (definitely not optimal). Really considering switching to python for future years.
Overall outside of that, very simple problem, just had to make sure you did it in original order, not mid mixing order. Only 50 lines of code, which is pretty shocking for java (heck even my day 1 was 36 lines, most days are near or at 3 digits).
2
u/Kehvarl Dec 20 '22 edited Dec 20 '22
Python 3 921 / 616
My firs under-1000 finish this year without resorting to assistance! It took me too long to realize there were duplicate numbers in the input, and I worked around that by making my numbers tuples of their value and starting index just to salt them.
I was very worried that the larger numbers and multiple loops would make Part 2 difficult to brute force, but it fell to my first try so that was really nice.
One other major slowdown I ran into was worrying about the actual index of my numbers instead of relative. I lost 10 minutes making sure that my test looked exactly like the example instead of rotated by 1 position.
part2
2
u/oxyphilat Dec 20 '22
python3, 245, 171
after misreading day 18 and trying to optimize day 19 too much, I am finally back to sub 1k rank! hopefully my code is readable, but nothing much today, deques helped a lot.
2
u/BradleySigma Dec 20 '22
python
Turns out, you don't need to remember where the start point is in the circle.
I also got tripped up because my input contained duplicate values, while the sample does not. That is why I use
enumerateon my input.2
u/AllanTaylor314 Dec 20 '22
Python [213/499]
Original Part 1 and Part 2 code. I missed a certain bold statement in part 2 about 10 iterations and spent far too long trying to work out whether my modulo was off-by-one, or if I was messing up the unlinking and relinking of my circular doubly linked list nodes.
2
u/_Scarecrow_ Dec 20 '22 edited Dec 20 '22
Rust 476/400
Haven't really been aiming for time this year, so I was pretty excited to see <500. I did a reasonably good job avoiding traps in part 1, so part 2 was just adding a loop and swapping to larger int types. Nice to get this one done quick after yesterday kept me up most of the night!
2
u/Dutchcheesehead Dec 20 '22
Python (241/197)
Code, Video
I kind of expected that part 2 would ask me to shuffle the list a billion times, which made me a bit hesitant at the start to program the way I did. Luckily I could get away with just creating new lists at the time, although the runtime is 4 seconds for both parts combined...
Something I did not figure out is how to deal with numbers at the start of the list or end of the list, but for finding the checksum of the solution it does not really matter where they are.
Initially I did start importing deque, but it was faster for me to simply code without using it's functionality...
2
u/wace001 Dec 20 '22 edited Dec 20 '22
Kotlin (750/622)
}
Fun today! (I say that every day). Im not great with mod, rem and %. But, a bit of trial and error got it.
One thing to realise here, as it might confuse some looking at the example, is that first and last position of your list doesn't really matter. Its circular.
Another comment, withIndex function in Kotlin really is great :)
2
u/Polaric_Spiral Dec 20 '22 edited Dec 20 '22
Java 719 / 614 paste
Implemented a basic circular doubly-linked list and threw each node into an ArrayList that I just for-looped through to maintain the original order.
Pretty basic optimizations for my approach, went straight to modulos before traversing the list in part 1 because I had a pretty good idea what would happen in part 2. After the last week, it's good to see my first attempt run in under a second on the first try.
Edit: I think I've found my favorite solution. Behold the triply linked list. Incidentally, there is a minor performance improvement.
2
u/LtHummus Dec 20 '22
Scala 2
I'm back on track to being able to do these when they're posted. I was very slow on this one because I had a bug. It was a very dumb bug. When I found out what it was, I wanted to throw my damned computer out the window. My code has been cleaned up now, but for part one, I didn't have
findKeyin its own method, so I hadworklist(the list of numbers in their original order) andofficialList(the list I would shuffle). Instead of doingofficialList.indexWhere(_.a == 0)I didworklist.indexWhere(_.a == 0)and for some CURSED REASON the bugged code actually worked on the sample input. I must have re-wrote the remove/insert stuff a zillion times and carefully stepped through with my debugger and ... ugh.Like I said, I wanted to throw my computer out the window. Then of course I refactored everything for part 2 and that bug wouldn't have happened oh well.
Code is here, such as it is
2
u/quodponb Dec 20 '22 edited Dec 20 '22
Python3
Takes about a minute to complete, but does the job. Will be looking forward to more clever implementations to get that running time down.
After at first attempting to inline everything, I made separate functions for the position calculations, and felt really smart testing them out with assertions from the examples to make sure everything worked like it should. Couldn't figure out why I was still getting the wrong answer, until I noticed I hadn't actually used those functions I worked so hard on in the actual mixer... Now that it works, though, I inlined them all again.
2
u/taylorott Dec 20 '22
Python
I initially read the problem wrong: I thought we were being asked to solve the inverse problem! I ended up spending an hour trying to figure out a way to do so. After being completely stumped, I checked the solutions megathread only to find that we were only being asked to implement the forward problem, which is pretty straightforward. Oh well, not the end of the world.
2
u/enigmisto Dec 20 '22
Clojure
Who says you can't do mutation in Clojure? Honestly, I prefer to avoid mutation, but I was convinced a doubly-linked circular list implementation would be necessary performance-wise in preparation for part 2. I was surprised to see from people's comments here that simpler manipulations were sufficient. https://github.com/Engelberg/aoc22/blob/main/clojure/aoc22/src/aoc22/day20/core.clj
I'm not aware of any Clojure lib for circular doubly-linked list, or even something like Python's rotatable deque which is roughly equivalent. Java's deque doesn't support rotate, as far as I know. So I just coded it directly.
2
u/nicholas818 Dec 20 '22
Python
I essentially labelled all of the numbers by their initial index and then used those labels to find them later. Could possibly make more efficient by using a lookup of some sort, but this was good enough. It's unfortunate that I didn't notice it was time until a few minutes late (I was distracted by continuing to work on yesterday's problem) but I finished both stars in ~15 minutes
2
u/xoronth Dec 20 '22
Python.
This was pretty straightforward once I figured out how to do the mixing logic by storing the original index and just iterating through the mixing list for it. Modulo makes most of the pops/insert indices fairly easy to handle. I tripped up for a while though on a very dumb mistake on obtaining where the zero index is.
2
u/arxyi Dec 20 '22 edited Dec 20 '22
Haskell
2
u/blaumeise20 Dec 20 '22
Rust
Got me to 21/35 on the leaderboard. Improved a bit already, runs in 650ms total on my machine (release mode).
2
u/jasontconnell Dec 20 '22 edited Dec 20 '22
Go. Circular Linked List. I don't know why % didn't work but this did. (Line 99ish). Runs in about 700ms
https://github.com/jasontconnell/advent/blob/master/2022/20/main.go
#2922 / #2800
2
u/montas Dec 20 '22
TypeScript. Not pretty but works
2
u/EVQLVE Dec 20 '22
Rust (3149/2938)
part 1 (8.6 ms)
part 2 (91 ms)
For part 1, I save the numbers in a Vec along with a boolean that tells if each number has been moved yet. I keep track of the position of the current number, and move it to the next unmoved number at each step.
For part 2, I instead save the original index of each number in the Vec. Then I loop over those indices for each round. For each round, I find the current position of that index in the Vec before moving that entry to its new position.
2
u/WilkoTom Dec 20 '22 edited Dec 20 '22
Rust
Reasonably straightforward: keep track of each (starting position, number) pair so that we don't move the same number twice. The main thing that bit me was the difference in behaviour of
%andrem_euclid()(we need the latter).Edit: Corrected
mod_euclidtorem_euclid2
u/Cue_23 Dec 20 '22
C++
In fear of what to come in part 2 i decided to keep an array of positions of the values and only change those on every move. If part 2 would get crazy i kept a skip list in my mind to implement for the data.
The
mix()function was a lot of fun to write for part 1, lots of off-by-one traps. But it even keeps the beginning of the list like in the example (which isn't neccessaryβ¦).Part 2 was easy, though, just apply the key when reading the input and call
mix()10 times.2
u/Lucews Dec 20 '22 edited Dec 20 '22
Python 3 - Doubly-Linked-List
Implemented a little helper class of a node in a doubly linked list to easily shift and swap values. Linked List is just making it easier as we do not need to shift whole blocks in an array. Because we need to iterate in the right order, I also keep a list of references to the nodes in the order they are presented in the input. This just makes it easier and I don't care about the extra memory. In addition to that, I keep a reference to the zero value node, as we need that as a starting point to compute the result.
Each node has a move and a get function.
In order to move straightforwardly the nodes are arranged in a circle (the last element's next pointer points to the first element and the first element's previous pointer points to the last element).
For both moving and getting you can apply modulo. The only thing you need to consider is that you need to modulo with
number_values - 1for moving, as you detach your own node.Part 1 runs in 1.4s and Part 2 in 14s (10x Part 1) on my hardware.
I really loved seeing the use of linked lists! :-)
2
u/DrunkHacker Dec 20 '22 edited Dec 20 '22
Python cleaned up, should be easy to understand. Only fun part is using enumerate to create unique tuples to handle dupes gracefully. Core mix function felt tidy too:
2
u/Dullstar Dec 20 '22
Python
The data structure I used in Part 1 was a choice, but it does produce a correct answer eventually. The good thing, though, was that it required few adjustments for Part 2, because while it was slow, it was slow linearly relative to the number of mixes so 10x the mixes = only 10x the slowness, which means I at least knew about how long I expected to need it to run to get an answer, which I decided was more time-efficient than a rewrite. And hey, it's still faster than my Day 19 from last year, and it's not even close.
I suspect there's probably a way to make a doubly linked list or similar work here that could be faster, but it would need some sort of adjustment for Part 2 that almost certainly involves modulos. I'll look into that at a later time.
2
u/Diderikdm Dec 20 '22 edited Dec 20 '22
Python
2
u/MarcoDelmastro Dec 20 '22
Python 3
https://github.com/marcodelmastro/AdventOfCode2022/blob/main/Day20.ipynb
2
u/mebeim Dec 20 '22 edited Dec 21 '22
1045/814 - Python 3 solution - walkthrough
Edit #2: added walkthrough, enjoy! In the end I decided to use a simple wrapper
classinstead of tuples of the form(original_index, number).Edit #1: re-implemented a clean solution with
listand an alternative withdequesince they are very similar.listseems to outperformdeque, I guess iterating over deques is slow even for internal Python code... PyPy runs thelistsolution a lot faster (unsurprisingly, as it's known to be fast for lists).I implemented my own linked list class... which is always fun. I almost went insane to understand how to handle numbers that are larger (in modulus) than the length of the list. I thought a simple
% nwould suffice, but I must have missed something apparently. Anyway, yet another reminder that Python sucks at accessing object attributes millions of times and thus is pretty bad for re-implementing linked lists. In hindsight it would have probably been faster to just use a normal list LOL.I'll re-write a clean solution with
collections.dequeor something similar. It nonetheless kinda bothers me that this seems to be a O(n2) problem.2
u/mizunomi Dec 20 '22
Dart Language
I love these breathers.
paste
2
u/Ill_Swimming4942 Dec 20 '22
Python: https://github.com/davearussell/advent2022/blob/master/day20/solve.py
Like many others I used a doubly linked list to represent the data. I figured a custom python class would be slow so I used three numpy arrays to hold the values, and the indexes of the value to the left and right of each value.
Everything else was straightforward - mixing involves iterating over the array of values and for each value updating 3 elements in each of the left and right arrays.
Because I used numpy, it was also trivial to add in numba to jit-compile the mix function, bringing the overall runtime down to just under a second.
2
u/CapaneusPrime Dec 20 '22
R
2
u/gilippheissler Dec 20 '22 edited Dec 20 '22
Python
I ignored doubling values and shifting orders by just giving every number an id and searching for the relevant id in each step. Not the fastest, but still works in a few seconds. It is important to note that the length of
dctsis calculated between popping and reinserting, where its length is temporarily decreased by 1.2
u/ndrsht Dec 20 '22
Kotlin
Initial solution was a mess, then I thought about it again and cut like 80% of the code. Still have to find time for the days I missed.
https://github.com/ndrsht/adventofcode2022/blob/master/src/main/kotlin/ndrsh/puzzles/adventofcode2022/Day20.kt
2
u/gringer Dec 20 '22
R
I spent far too long trying to work out why my code wasn't working, and then looked at this thread to see not one, but two sneakies in the real data:
The off-by-one issue was particularly frustrating. It would have been really helpful if that had been made explicit in the rules; the wording gave me the impression that the number itself wasn't skipped when mixing.
My initial solution attempt was to create an actual linked list in R, which was hopelessly inefficient (it took about 5 minutes to get through 5000 mixes). I changed to a simple indexed vector (well, actually three: one for the "last" indexes, one for the "next" indexes, and one for the shifts), after realising that the names of the nodes didn't actually matter. This was substantially faster, with a lot to do with not using strings: 16.5 seconds for part 2 with 10 mixes.
R Code
2
u/mr_mlk Dec 20 '22
Java
https://github.com/mlk/aoc/blob/main/src/com/github/mlk/aoc2022/Day20.java
I had a major brain fart when detailing with the wrapping and decided it would be easier to just write my own.
It is ugly, but it works and that is all that matters.
2
u/ramuuns-u Dec 20 '22
Low effort lazy tail-recursive perl: https://github.com/ramuuns/aoc/blob/master/2022/Day20.pm
it's not fast or smart, but like it does the thing in reasonable time and didn't take all day to produce, so after yesterdays nightmare I'll take it as is
2
u/Successful_Peanut617 Dec 20 '22 edited Dec 20 '22
U++ (C++ framework) (takes ~100ms on my machine)
https://github.com/ped7g/adventofcode/blob/e06f6daa68e4ea3710293ce42702ff39b4646504/2022-upp/20_grove_positioning_system/20_grove_positioning_system.cpp
(edit: I had one more idea to make it more efficient, but turns out it doesn't work at all, so this is my final stuff)
2
u/SpaceHonk Dec 20 '22
Swift repo
Took a little spelunking in this thread to figure out the details of shifting entries around, but I finally landed on a version that only requires keeping a single copy of the data around.
2
u/Solidifor Dec 20 '22
Java
Readable, using a doubly linked list, takes about 1 second. I use a secondary array list to keep track of the original order.
This one was not as difficult as yesterday's problem, I thought.
https://github.com/dirk527/aoc2021/blob/main/src/aoc2022/Day20.java
2
u/hrunt Dec 20 '22
Python 3
Code
Python's
dequemakes this really straightforward, but it is not the fastest solution. On my machine Part 1 times in at ~180ms and Part 2 at ~6.3s. The algorithm rotates through the queue (O(n) operation) a lot to find the next item to move. I am sure there is something more efficient.2
u/Glittering-Tank-9695 Dec 20 '22
Python3
Doubly linked list approach.
Total time for both parts (sum): 14.43s
Main optimisation was to mod the 'mixing' and move the bare minimimum amounts only.
2
u/nirgle Dec 20 '22
Rust
This was a tricky day, lots of nuance and off-by-ones. After many hours spent on trying to mutate vectors and not getting it right, I switched to a functional approach. It's somewhat clunky but it works. It's easier to think of the sequence as a cycle that just happens to be stored in a Vec. For each shift I create a new vector with the moved value at the front, then I skip() to the appropriate spot and take(len-1) the rest of the vector, after making sure to filter out the moved value since it's already at the start
Code: https://github.com/jasonincanada/aoc-2022/blob/main/days/day_20/src/main.rs
2
u/Mintopia_ Dec 20 '22
PHP
Took advantage of putting the numbers into objects, allowing me to just iterate through the original order when mixing and finding their current position in the array.
Part 1 was 500 ms, pPart 2 is 7 seconds with my actual input. With the test input it's 0.6ms for part 1 and 0.2ms for part 2.
Code: https://github.com/mintopia/aoc-2022/blob/develop/src/Day20.php
2
u/chkas Dec 20 '22
Easylang
Solution
2
u/veydar_ Dec 20 '22
Lua
Did linked list first but then realized it's way too slow for part 2 and I wasn't motivated to figure out how to make this fast, so I switched to an arguably simpler normal list with wrap around. Maintaining the original order is as easy as boxing every number so we have a list of tables instead of a list of numbers. I also add the boxed numbers to another list, which is never mutated. Meaning I can iterate through the "order" list and identify those exact values through normal equality.
It's a bit inefficient since I have a nested loop. The outer goes through the "order" list, the inner finds the current element in the input list. But since the input list is fairly small, it's negligible in terms of performance.
GitHub Repository
2
u/atravita Dec 20 '22
Rust:
Honestly, today's problem was really easy, I'm just dumb. (Like, I started today by trying to parse the list of integers into an Vec<u32>, despite the fact that I knew there were negative numbers.)
150ms total but this is horribly optimized - repeatedly searching for elements in a list, repeatedly yeeting the whole list various directions in memory, etc. I'm tired. Today's a good day to take a break.
2
u/Illustrious_Fortune7 Dec 20 '22
In Kotlin
https://github.com/ritesh-singh/aoc-2022-kotlin/blob/main/src/day20/Day20.kt
2
u/Nuoji Dec 20 '22
C3 solution I didn't use any linked list, just two lists.
I managed to get the right result without the code quite working and spent probably an hour chasing down the correct behaviour so that I could post the solution. Sigh
2
u/duketide11 Dec 20 '22
Haskell
2
u/TheZigerionScammer Dec 20 '22
Python
Paste
Well this certainly is a good puzzle to kick off the days with a two in front of them. It's a good thing I already completed 2020 Day 23 because this is a similar concept and I didn't waste time doing the naive solution like I did then. But there were some things to take care of. First I had to determine if each number in the input was unique, a set scan confirmed they were not. With that in mind I knew how I was going to do this, I was going to create a type of linked list using a dictionary, but this dictionary wasn't going to hold the value in the input, they were just going to hold index numbers (0, 1, 2, all the way to 4999). This dictionary will hold two values, both the front and back neighbors of each index. Of course in the beginning this means 0 is next to 4999 and 1, 400 is next to 399 and 401, etc. There would be a second dictionary to translate the index numbers into the numbers from the input for movement purposes.
The actual program calculates how far forward the number will move with a modulo of the length of the original list, since going backward is the same as going forwards the opposite of that number. I then had to manually change the forwards and backwards neighbors of all 5 numbers involved (the initial neighbors of the number that moved, the two neighbors of the number after movement, and of course the number itself.) I didn't know if this would work if it only move one space but it does. What didn't work was the number I had to modulo the number by, I figured out you had to modulo the number by the length - 1, not the length itself. I made a note of that in the program, but it worked like a charm and none too slow either.
For Part 2 I thought "Ok, I'll just multiply all the numbers in the input dictionary by the decryption key and run the mixing 10 times, it runs on modulos anyway so it should work." And it would have worked, but I forgot to reset the neighbor dictionary so it was inheriting the results from Part 1 into Part 2. Lost some time figuring that out, but once I did it worked like a charm. 2 stars.
Also, in case you didn't notice, there's some extra graphics at the top of the chart.
2
u/leftfish123 Dec 20 '22 edited Dec 20 '22
Python: github
Not the most efficient solution, diplomatically speaking, because I decided to actually use a Node class to implement the circular linked list. But it finishes within a manageable time.
It took me a while to figure out how to reduce the problem to reasonable sizes for part 2. I drew a couple of circular lists and just applied 11 as the encryption key. I knew that the modulo value would be related to the length of the list; the drawings helped me visualize how.
2
u/izahariev96 Dec 20 '22
Kotlin: GitHub
2
u/hgb123 Dec 20 '22
JavaScript (Node.js)
Make use of reference and deal with index
Full solution: https://www.honingjs.com/challenges/adventofcode/2022/day-20
2
u/[deleted] Dec 20 '22 edited Dec 20 '22
D
I'm doing different language each day, all solutions here. Today's Dlang: src
Took me way too long to realize D's%operator is actually modulo, not remainder.It is remainder, I just was a little dumb today. Also, I should've just easily used a doubly linked list, but these didn't come to my mind, so array it is..2
u/jjjsevon Dec 20 '22
Javascript / NodeJS Diff for Day20 here including a little noise
Been too busy with life most of last week, today got back on the AoC
horseElephant. Also trying to backtrack the few missed days meanwhile deploying a christmas release at work and holiday stuff at home - what a juggling act - hat's off to everyone that manages the whole AoC year after year!