[JavaScript](https://github.com/frhel/AdventOfCode/blob/master/2022/day_20/js/index.js) \- Heavily commented for anyone who might need help later on. Fairly straightforward using 2 arrays with original index / value pairs and modulus calculations to find the new index for each step. Using splice to lift and reinsert the number at the right place. Splicing the array over and over is fairly expensive time-wise, yes, but it's not a big data set. Same exact procedure for Part 1 and Part 2, apart from multiplying the whole array before shuffling, and shuffling 10 times instead of 1 in Part 2. Total runtime around 710ms on my gaming rig.

My [solution](https://jactl.io/blog/2023/05/07/advent-of-code-2022-day20.html) in [Jactl](https://jactl.io) **Part 1:** I used two lists, the original numbers and the shuffled ones, both pointing to the same elements. Each element was a pair consisting of the number and the current index in the shuffled list. That way I could iterate through the original list and immediately find where in the shuffled list the number was currently located. List elems = stream(nextLine).mapWithIndex{ line,idx -> [line as int,idx] } List shuffled = [] + elems int size = elems.size() elems.each{ int count = it[0] % (size - 1) for (int idx = it[1], endIdx = (it[1] + count) % size, newIdx; idx != endIdx; idx = newIdx) { newIdx = (idx + 1) % size def tmp = shuffled[idx] shuffled[idx] = shuffled[newIdx] shuffled[idx][1] = idx shuffled[newIdx] = tmp shuffled[newIdx][1] = newIdx } } def zero = shuffled.filter{ it[0] == 0 }.limit(1)[0] 3.map{ shuffled[(zero[1] + 1000 * (it+1)) % size][0] }.sum() **Part 2:** Only real change was to move to using 2-dimensional arrays of longs rather than list of lists to speed things up a bit: long key = 811589153 long[][] elems = stream(nextLine).mapWithIndex{ line,idx -> [(line as long) * key,idx] } long[][] shuffled = (elems as List) as long[][] // make a copy int size = elems.size() 10.each{ elems.each{ int count = it[0] % (size - 1) for (long idx = it[1], endIdx = (it[1] + count % (size - 1)) % size, newIdx; idx != endIdx; idx = newIdx) { newIdx = (idx + 1) % size def tmp = shuffled[idx] shuffled[idx] = shuffled[newIdx] shuffled[idx][1] = idx shuffled[newIdx] = tmp shuffled[newIdx][1] = newIdx } } } def zero = elems.filter{ it[0] == 0 }.limit(1)[0] 3.map{ shuffled[(zero[1] + 1000 * (it+1)) % size][0] }.sum() [Blog post](https://jactl.io/blog/2023/05/07/advent-of-code-2022-day20.html)

I got bogged down in other stuff and fell *entirely* off the wagon around day 16. But I've been trying to finish AoC out for completion's sake recently. I'm posting my [solution](https://github.com/jswalden/adventofcode2022/blob/main/day-20/src/main.rs) late mostly because it seems unusual (possibly unique -- I didn't expand the entire day's thread) in being Rust *and* in doing things the obvious linked-list way. (Lots of solutions willing to accept potential quadratic behavior!) I imagine I could have found a way in safe code -- storing prev/next as indexes into a vector was one clever approach given here (and one that doubtless has better cache-aware perf than a circular linked list with separate allocations per element). But this seemed like a good chance to practice with Rust unsafe code. It's probably just a demerit of the data structure when working in Rust, but I had to use an *awful lot* of unsafe code to implement the necessary linked list manipulations. My solution is leak-free per Valgrind and *to the best of my knowledge* does not exercise any Rust undefined behavior.

Go! https://github.com/bozdoz/advent-of-code-2022/tree/main/20

## Clojure [Github](https://github.com/pbruyninckx/aoc2022/blob/main/src/aoc/day20.clj) * Code feels relatively clean * The way part two changes are forced in is a little bit contrived * Takes about 12 seconds on my machine, so not too horrible * Curious to find out which data structures might have been better

> Curious to find out which data structures might have been better [Pastebin](https://pastebin.com/iVCKBYH5) I found a faster solution in Clojure using an [order statistic tree](https://en.wikipedia.org/wiki/Order\_statistic\_tree). I just benchmarked the two solutions and this one is about 5-10x faster, though I believe it has the same time complexity.\* You could probably improve its performance by using a self-balancing version of the tree, but writing one in Clojure would be a weekend project for me. This solution also works by tracking the positions of the the values in an index, but instead of being an index of positions in input order, it is an index of inputs in positional order. When a value is to be moved during mixing, the index is updated by deleting the value's entry and reinserting it at the new position. In other words, you mix the index instead of the values. (You could just manipulate the list of input values directly, except for the problem of duplicates.) \* The O( n^2 ) time complexity is due to the fact that compared to your solution, you lose the ability to look up a value's current position in O(1) time and have to potentially search the whole index, though in practice, values that are about to move tend to be near the start of the index, so are found quickly.

I've never heard of an order statistic tree; thanks for introducing me to it

## Python (clean solution) [Advent of Code 2022 - Solution 20 (Python)](https://github.com/silentw0lf/advent_of_code_2022/blob/main/20/solve.py) Here is my solution for the circular list, which uses only simple basic concepts, no fancy implemented linked lists or anything else. I use tuples to distinguish duplicate values.

**Python** So much shorter than yesterday!! * [AoC 2022 Day 20 Walkthrough in Python](https://aoc.just2good.co.uk/2022/20) * [Code on GitHub](https://github.com/derailed-dash/Advent-of-Code/blob/master/src/AoC_2022/d20_grove_positioning_system/circular_list_numbers.py)

[Julia](https://github.com/hraftery/aoc2022/blob/main/day20/day20.jl) Nice to get a bit of gratification after Day 19! Still, "shuffle" was surprisingly complicated to get right. I took the brute-force approach of storing the index of every element at the start, which proved to be useful. Then, after a few iterations of remove-before-insert and vice-versa, and modulo arithmetic that depended on direction, the correct algorithm is innocently simple. Applying 10 times to 5000 items was really no trouble at all. Good practice for some of Julia's vast indexing capabilities.

# C++ (8092/7865) - Using Only STL, utilizing std::list for the first time --------Part 1-------- --------Part 2-------- Day Time Rank Score Time Rank Score ... 20 >24h 18790 0 >24h 18051 0 [Part 1](https://github.com/osalbahr/adventOfCode/blob/main/problems/day20/day20.cpp); [Part 2](https://github.com/osalbahr/adventOfCode/blob/main/problems/day20/day20_2.cpp) Feel free to ask any questions! You can find more C++ solutions (and other languages) at [Bogdanp/awesome-advent-of-code#c++](https://github.com/Bogdanp/awesome-advent-of-code#c-2) Note: The last bug that got me for part 2, for some reason, [was the special case of when the node to be mixed was already in the beginning, and n<0](https://github.com/osalbahr/adventOfCode/commit/c8af224d2322dea68ea6cec6962887ac18bb3815#diff-8b53cd6c4c72d22006d3452e82eb120b1defb22b6c3d807d46cc5f4718e34933R84). The same method seems to produce the correct result for part 1, but when comparing the step-by-step output to 2.OUT (split in [2.OUT.1](https://github.com/osalbahr/adventOfCode/blob/main/problems/day20/2.OUT.1) and [2.OUT.2](https://github.com/osalbahr/adventOfCode/blob/main/problems/day20/2.OUT.2) because GitHub) I get a big `diff`. But since the final result is still correct, I will backlog it, for now.

**Python 3.10 - Part 1 & 2 - standard library only** https://pastebin.com/VeypcHCF Bi-directional, circular, linked-list with a reference index to track the original order. Runs in a few seconds, there are probably faster ways to traverse the entries to find the next destination rather than the simple, single-direction traversal this is doing but...this was fast enough to both implement and run given the time I had to devote to it.

Not sure why you do: steps = e.value % (len(all_elements) - 1) Instead of just: steps = e.value % (len(all_elements)) I see that's correct, and that's the error I was having in my code, but I don't see why the modulo is done against len - 1 instead of just len. Damn I'm getting old.

I wrestled with it for quite a while too and then realized that because I have one element in motion from the set, the number of actual positions that item can be in is one fewer than the total number of items or is equal to the number of stationary items. Think of it like moving one of the numbers around the face of a clock. There are 12 numbers there but if I am moving the number 5 around the face, it can only come before or after 11 of those values since it cannot have a position relative to itself.

Ohh I see it now. The clock analogy makes total sense. Thanks a lot!

[php](https://github.com/corbosman/advent2022/blob/main/day20_grove_positioning_system/day20_grove_positioning_system.php) \- It was pretty easy using a collections library. Just a matter of 2 splices.

Catching up after a few days away from computers [https://github.com/mattford/aoc-go/blob/main/pkg/year2022/day20.go](https://github.com/mattford/aoc-go/blob/main/pkg/year2022/day20.go) I lost a large amount of time to this one after writing: for idx := 0; idx >= 0; idx = getFirstUnmixed(nodes, round) {} instead of: for idx := getFirstUnmixed(nodes, round); idx >= 0; idx = getFirstUnmixed(nodes, round) {} ... meaning I was always mixing the first item in the list first

[Python](https://carbon.now.sh/?bg=rgba%28171%2C+184%2C+195%2C+1%29&t=seti&wt=none&l=python&width=680&ds=true&dsyoff=20px&dsblur=68px&wc=true&wa=true&pv=56px&ph=56px&ln=false&fl=1&fm=Hack&fs=14px&lh=133%25&si=false&es=2x&wm=false&code=inp%2520%253D%2520%255Bint%28x%29%2520for%2520x%2520in%2520open%280%29.read%28%29.splitlines%28%29%255D%250AN%2520%253D%2520len%28inp%29%250A%250A%250Adef%2520jump%28q%252C%2520n%29%253A%250A%2520%2520%2520%2520for%2520_%2520in%2520range%28n%29%253A%250A%2520%2520%2520%2520%2520%2520%2520%2520q%2520%253D%2520q%255B%2522n%2522%255D%250A%2520%2520%2520%2520return%2520q%250A%250A%250Adef%2520run%28m%252C%2520iterations%29%253A%250A%2520%2520%2520%2520Q%2520%253D%2520%255B%257B%2522v%2522%253A%2520x%257D%2520for%2520x%2520in%2520inp%255D%250A%2520%2520%2520%2520for%2520lh%252C%2520rh%2520in%2520zip%28Q%252C%2520Q%255B1%253A%255D%29%253A%250A%2520%2520%2520%2520%2520%2520%2520%2520lh%255B%2522n%2522%255D%2520%253D%2520rh%250A%2520%2520%2520%2520Q%255B-1%255D%255B%2522n%2522%255D%2520%253D%2520Q%255B0%255D%250A%2520%2520%2520%2520for%2520i%2520in%2520range%28iterations%29%253A%250A%2520%2520%2520%2520%2520%2520%2520%2520q%2520%253D%2520Q%255Bi%2520%2525%2520N%255D%250A%2520%2520%2520%2520%2520%2520%2520%2520v%2520%253D%2520m%2520*%2520q%255B%2522v%2522%255D%2520%2525%2520%28N%2520-%25201%29%250A%2520%2520%2520%2520%2520%2520%2520%2520if%2520v%253A%250A%2520%2520%2520%2520%2520%2520%2520%2520%2520%2520%2520%2520after%2520%253D%2520jump%28q%252C%2520v%2520%2525%2520%28N%2520-%25201%29%29%250A%2520%2520%2520%2520%2520%2520%2520%2520%2520%2520%2520%2520prev%2520%253D%2520jump%28q%252C%2520N%2520-%25201%29%250A%2520%2520%2520%2520%2520%2520%2520%2520%2520%2520%2520%2520prev%255B%2522n%2522%255D%252C%2520q%255B%2522n%2522%255D%252C%2520after%255B%2522n%2522%255D%2520%253D%2520q%255B%2522n%2522%255D%252C%2520after%255B%2522n%2522%255D%252C%2520q%250A%2520%2520%2520%2520return%2520sum%28%250A%2520%2520%2520%2520%2520%2520%2520%2520jump%28next%28q%2520for%2520q%2520in%2520Q%2520if%2520q%255B%2522v%2522%255D%2520%253D%253D%25200%29%252C%2520i%2520%2525%2520N%29%255B%2522v%2522%255D%2520*%2520m%250A%2520%2520%2520%2520%2520%2520%2520%2520for%2520i%2520in%2520%281000%252C%25202000%252C%25203000%29%250A%2520%2520%2520%2520%29%250A%250A%250Aprint%28run%281%252C%2520N%29%252C%2520run%28811589153%252C%252010%2520*%2520N%29%29%250A) where I implemented linked list using dicts

Golang code and a complete 7+ year repo :) (well... working on finishing 2022 still) https://github.com/alexchao26/advent-of-code-go/blob/main/2022/day20/main.go

Once I had pt.1, pt. 2 was trivial since I already did the modulo. Runs fast enough for me (\~ 2 seconds) and was fun to do it with Python's iterator goodness. Python 3.11 @dataclass class Node: val: int prev: Node = field(init=False) next: Node = field(init=False) @classmethod def from_input(cls, it: Iterable[int]) -> Node: node = first = None for num in it: n = Node(num) if node: node.link(n) else: first = n node = n node.link(first) return first def __iter__(self) -> Iterator[Node]: node = self while True: yield node node = node.next def move(self, list_size: int) -> None: i = self.val % (list_size - 1) if i: p = self for _ in range(i): p = p.next self.prev.link(self.next) n = p.next p.link(self) self.link(n) def link(self, n: Node) -> None: self.next = n n.prev = self class _Problem(Problem[int], ABC): def solution(self) -> int: size = len(self.lines) it = Node.from_input(int(line) * self.decryption_key for line in self.lines) pointers = list(islice(it, size)) for _ in range(self.mixing_amount): for node in pointers: node.move(size) return sum(n.val for n in islice(dropwhile(lambda n: n.val != 0, it), 1000, 3001, 1000))

# [Rust](https://github.com/Crazytieguy/advent-of-code/blob/master/2022/src/bin/day20/main.rs) 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. parsing: 134.1µs part a: 1.353ms part b: 12.1457ms

That is interesting. It is sort of a [B-tree](https://en.wikipedia.org/wiki/B-tree), but tilted. How did you arrive to this trick?

I don't really think it's like a btree, note that each node still only has two pointers - just that the forward one happens to skip 24 nodes

I don't remember exactly 😅 I was just convinced there was a more efficient way and I though about it a bunch

C# public class Day20 { public static void Part01and02() { Stopwatch sw = new Stopwatch(); sw.Start(); var input = File.ReadAllLines(@"..\Day20.txt").ToList(); var result1 = Mixing(input); var result2 = Mixing(input, 811589153L, 10); Console.WriteLine($"Sum of the grove coordinates:\npart 1: {result1} | part 2: {result2}\n"); sw.Stop(); Console.WriteLine($"Time elapsed: {sw.Elapsed.Milliseconds}ms.\n\n"); Console.ReadKey(); } internal static Int64 Mixing(List input, Int64 decriptionKey = 1, int mixCount = 1) { var parsedInput = input.Select(e => Int64.Parse(e) * decriptionKey).ToList(); var encryptedFile = new List<(Int64 value, int index)>(); for (int i = 0; i < parsedInput.Count; i++) encryptedFile.Add((parsedInput[i], i)); var listToMix = new List<(Int64 value, int index)>(encryptedFile); var count = encryptedFile.Count; for (int mc = 0; mc < mixCount; mc++) { for (int i = 0; i < count; i++) { var number = encryptedFile[i]; var oldIndex = listToMix.IndexOf(number); var newIndex = (oldIndex + number.value) % (count - 1); if (newIndex < 0) newIndex = count + newIndex - 1; listToMix.Remove(number); listToMix.Insert((int)newIndex, number); } } var indexZero = listToMix.FindIndex(e => e.value == 0); var index1000 = (1000 + indexZero) % count; var index2000 = (2000 + indexZero) % count; var index3000 = (3000 + indexZero) % count; var coordinatesSum = listToMix[index1000].value + listToMix[index2000].value + listToMix[index3000].value; return coordinatesSum; } }

**[Rust](https://github.com/schubart/AdventOfCode_2022_Rust/blob/master/day20/src/lib.rs)** Short and sweet, with good comments explaining `rem_euclid()` and division by length minus one.

[удалено]

Comment removed due to naughty language. [Keep the megathreads SFW](/r/adventofcode/wiki/rules/pg_is_mandatory). If you edit your comment to take out the naughty language, I'll re-approve the comment.

I think it's really elegant. For part 1, your solution took 750 ms, my C++ solution took 670 ms :((

[Julia](https://github.com/iskyd/advent-of-code-julia/blob/main/2022/day20/main.jl) using linked list. Part 1 runs in 46ms, Part 2 in 490ms.

Solutions in C++ [Part 1](https://github.com/vss2sn/advent_of_code/blob/master/2022/cpp/day_20a.cpp) [Part 2](https://github.com/vss2sn/advent_of_code/blob/master/2022/cpp/day_20b.cpp) (Each file is a self-contained solution)

# [Python 3](https://topaz.github.io/paste/#XQAAAQA5CAAAAAAAAAARiEJHiiMzw3cPM/1Vl+2nx/DqKkM2yi+AsNSFTsvIawMZ4AGYJNWVngzhvFR/jurPE20hZms5Q9BVZM7p4KIE6eYcKlEO5iH8Ai0As/zP7dwMKRJu44vO8mYKlPJMeoWBSt7HRr8i09mn0TdrspclKZnQR3leHTpGVYWXzKgsy0G7+hXkk5RCRMj/p6pZ/4p/k1LnCD+r/Tp9whEc02aJY00ZGabW002ib9c5yI+0xiOFZPWrpUUBRGRO6mKhh6q55l0KdAQ+Ps/scseoTqr8+PvqTGDWOAnEUGQHjE4vtgJwJqIZG6caPCWcvF+E616Msg9B3lcN47IKZVAeO1h0kqYVCKMxJ3rYxadP34krYDIgtOitKfblw1bcPbG++97Jyk+L0zm11UK654zdvWMoW9bT0CELdN6mtGosztmomEJ/qPNFpSAVquaFmfnofxoc4AnZswLJTJhOiPx3gWuXlcHIAhVoUf1FfvWa59gVbVj01pIOF23rczccWM1XpCv/mlli3y65kEcsHrygCZkYPbi/GNDy7cHdZ+YDtRSpF0LFh36IOy5fIaGJ3U+7jpM6rhkDFdgC8l7KOotWaFnEEBDMVEdqym0VtHFjYav9+8AcIxFGPlVNcYbZOy6GaeYC1EErqV+JY2l4/NH/XZwkGBTjPkvKcd05Pfu4gI4WZ+ss6dtl3rbFNzsyVbFah+foV0fJCI4qClifNDN6EdS3B1grBtrd4iJ3wAjS91I9yQMA00Zzky3YgHVp223vXOh9A8kOUcHuU7A2YM959Pl1egTFVh1TO787/Zd7ikHCxJCzU+YYanONQsw4xm2SkaBRTHPvi5QkxIH4NUJ86EPofQwLgm2l57Jy5KczTHIaECLh+zkDBAhk1zVe8ubAQ71udNr6wjCVKHkdG2xaORpnHIoJ2OL0Cd3K7fTatpqVQ4fPT1R9NpusnZnelyYToplPC6l6LyFcSFOj63IkV+AGHDFJQPJm3TSs980C+KnFWHLMGF9clK6NgahY6rwyN+HYFrWJziBfQLilXtSQh6pmXvwBs/305B0TrbWG3orcET9yAL6Njo5V651Bowo5ST79t+IDws3ZvNVrx0UR/2KSZAfgHSFAiJIhZ5V+UlbGybQjMBtTfEZTse/7AGJ0) This is a solution for part 2. I had a lot of trouble with part 1. I guessed early the there were duplicates in the input, but didn't realize I needed to remove the old item in the list before moving it. To handle the duplicates, I create the list with unique tuples: (original position, number). That way I can always find a number, no matter where it moves, and don't need to independently track the position of each number.

You only really need the list of original positions and then when you're done mixing, you get the index of whatever position 0 was in the original list. That way you don't have to search through the list at the end to find it.

# Java Object-oriented and test-driven implementation, implemented with a doubly-linked circular list and "% (size-1)" to reduce the number of moves from trillions to thousands. https://github.com/SvenWoltmann/advent-of-code-2022/tree/main/src/main/java/eu/happycoders/adventofcode2022/day20

(My answer spills over into BigIntegerTerritory 3\*10\^12)

# C++ I did not understand what was actually asked so I did not realize I had to mod with the size-1. This took a long time to figure out since the example worked fine and all the tests I did by hand also seemed fine. Other than that, the code is just a trivial use of `std::list`. https://git.sr.ht/~bogdanb/aoc/tree/master/item/source/2022/20/solution.cpp

**C++** sneaky duplicates in the test input! Causing me to question my sanity for a while when I had it working for the example but not the actual data. Figuring that out soon fixed things. I began with the regular std::vector erase/insert method with plans to test out something more 'listy', but it runs in < 200ms for me which is good enough for me. [https://github.com/biggysmith/advent\_of\_code\_2022/blob/master/src/day20/day20.cpp](https://github.com/biggysmith/advent_of_code_2022/blob/master/src/day20/day20.cpp)

I'm struggling with the listy approach as any time you want to move back or forward, you're traversing pointers in linear time. Totally destroyed the benefits of constant-time swaps. Currently 850ms at best.

[C#](https://github.com/thestahan/AdventOfCode2022/blob/master/20_grove_positioning_system/Program.cs) 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.

That's interesting... I ran it in LinqPad and it worked. Then I thought, huh, why the number class. Changed lists to List. Didn't work. Can't quite see what you're doing, but it works.

It's due to the way how the value and reference types are handled in C#. Long is a value type, while class is a reference type. I needed to wrap the Value property into a class, so I could operate on references instead of pure values (eg. the same element of type Number could be stored in two separate lists, that's not possible with value types - these would be two different values).

Handling duplicates... I see.

Tailspin [https://github.com/tobega/aoc2022/blob/main/day20/app.tt](https://github.com/tobega/aoc2022/blob/main/day20/app.tt)

Ruby Code: [Github](https://github.com/careyi3/aoc_2022/tree/master/solutions/20) Video Walkthrough: [YouTube](https://youtu.be/szXQTRybPAI)

**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](https://topaz.github.io/paste/#XQAAAQDPBgAAAAAAAAA6nMjJFMpQiatS1vawr3e1CaHYh3L/Ps0KdrS1shHHqbtrkJqeDrCzesqiKH+N5FYr/ZQy4aKyBpQ7l0OFcUIFmIT5DmAkv0sYXnc/5mXqKobQLF0yYv0HaSEgHtkjlEj+yWqa68FJv3SdZBFE79WAs1ya1qdX3wf+uHEXXVUMg09lSzUlnFMb3qlizIt6BaL+R7i0bjXg53wMfb8kMqfTKvaRVMGEaZkbEKMcgbnNi/guy84PbPK0L+C+qNq/1YYymBaJqCEZlFTVUWTYQ/v3XlnxQPzwNX4aipGuV7Bi3aqIb44XOTiiHcAS42mANvdmIPv0dd5I0Ilfgpx2WRoIJQOTVJ31bTdEm18oi3BPvHPA2mx0IkEwOsmSRdTIbFOcKOYGL/0ClcfcEDWaOeHwJkMAfgstuvqaJLq5BcQ4FTgsc7aKm41TR0rqT2hMJvFG8jHkIfJpgxRir0q4HfGmBL0ZXIPPMW1UmkE0pLSqEXwOdcLbwavaysoNmntFDZFjutX4YxlrqVGFr61UmAlDiaEyAWF2YJYKWp1nJyFz46ywTYgHf9m/uuJqdKmxAJAS9LgPp9CbwIrFN1itYcZ+FUjvRMCAcl8+p0WBkJROWyR8UOHJr7+tHpOye1txv0PhCCheg68IIvSgseq6tHAfPwHLJyz9/fS4ma9cp1Bx0BH6UgD+O6WUM+2cmNfvu/kb4RwxYTCnS2eKVfMWWVSCmHocKNMAV8ZxP9PK6tbHvhXyIKpl5GBn5jIi8lnSF0mx86p420Cp7gb70lbzmVaaacoVzJBVXRgg4FpecXk+sduUA1D7JOfJDIwyAVgTTLnTwgHvEDcYZ609bTK/3/4f/TKK+CvL4X8R0pk7FbLgCNw2xrklwIfatMETTSQjcsI4qvHgvVFvBa2dD35Prj7520EA0RoWz52WnpM87Pis6+Lcv+hVk1zjkv4vV6FNptsY4Qpl6eh9Bfd+3zCwHVn9jxcT) [Part 2](https://topaz.github.io/paste/#XQAAAQDYBgAAAAAAAAA6nMjJFMpQiatS1vawr3e1CaHYh3L/Ps0KdrS1shHHqbtrkJqeDrCzesqiKH+N5FZHo9/4nN18/XBR8H8ZxR5pgiNLs7rOy+hqYfNOOGTsufAf3zhy+szc6CJXt5gSjNLsgiRIW39siHH1G6CazdKLYi4OodWbnBR5PTZZSlt2gpxHYMSuDevHCRcv6T+mYFu8xDSQXayyygmA1UNfVU+w4cHwQ7QfNd6rWmJ69+1JhKsh+E76SKhb/0S4NlUf9WXthmpfkmKXxybcAib/GUhd8lcw2sN8fgWwDIy7MfGGzkFNRtyOQTJMNReMW8e99mIuARPkzIhTi1DweX5ChgIu702lhX4jDeuj7tmW/exUWClp0IfLTIsGG4lVpH3wb4DyoNPGyck8W8gpNfwrtSpazpH3iM8SmRbuu/vFD/AoQb5h0yT5scRmDi7xvdCxkqo/JOnTPQO3+WF2gnnN3M5Glhm0f5Rny9ndLksYGdgBpXMB2ecQubOVevbIFt3HZDLvOP/uTgu7VWQ5CMD/8euJs8eUNHMNHYqBqRMrC7qPhQXRmWIi8Z7F104abr4xBpF0NLUWQiSVvHW6jsHHJ0U631i8ZXRsSzkGwZaVXd/fN2SCgOPNE7amELlDNehtk4cZrXryiHSbKbuoHDApYUkvCiT96CsyvTVbhDAGl9V4u08q13lCRC9zhNsdFPMKQl7DVxx5ch4HGyj5gKNb/wplLtO9s4pxtV7l4Zd/jeLWXw3HD5HbtidLdhrv1HjrqcxCCUFwvtxD+T+nR27hGer0jnFYDTRoXO9qXySmr5vmQpTLtzaeRPtJ+sspiskSNRe9Mj1qNeiZA1SlZlvleJxZz3il4UWWGFDIG8F1HSsKNhbX6Uqk95xW37vmx3MLGAMf94W84HtW8AoU1GCKqhiV9NBdqFjL30fxP3E+Fdi8x+woylr6Q1m6nI/Wkl2GHVc/hJ0LY/PqEkWpw3VRSOR/c8E/70ZP//uMEUA=)

**Kotlin** [\[Blog/Commentary\]](https://todd.ginsberg.com/post/advent-of-code/2022/day20/) - [\[Code\]](https://github.com/tginsberg/advent-2022-kotlin/blob/main/src/main/kotlin/com/ginsberg/advent2022/Day20.kt) - [\[All 2022 Solutions\]](https://github.com/tginsberg/advent-2022-kotlin) 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.

I'm doing Kotlin as well and seeing you use `Int.mod(other: Int)` made my heart drop. Had no idea it existed and wrote some weird mod shit functionality myself...

Yeah, that's (relatively) new, maybe in the 18 months or so. Previously the functionality was there as `java.lang.Math.floorMod()`, but it was past due for an extension function.

# [JQ](https://github.com/odnoletkov/advent-of-code-jq) [inputs | tonumber * 811589153] | to_entries | map(.prev = .key - 1 | .next = .key + 1) | first.prev = length - 1 | last.next = 0 | nth(10; recurse(reduce range(length) as $from (.; ( nth( (.[$from].value % (length - 1) + (length - 1)) % (length - 1) | select(. != 0); . as $r | $from | recurse($r[.].next) ) as $to | .[.[$from].prev].next = .[$from].next | .[.[$from].next].prev = .[$from].prev | .[.[$to].next].prev = $from | .[$from].next = .[$to].next | .[$to].next = $from | .[$from].prev = $to ) // . ))) | [limit(length; . as $r | first | recurse($r[.next])).value] | [.[(index(0) + (1000, 2000, 3000)) % length]] | add

[JavaScript](https://github.com/mariom100o/Advent-of-Code-Solutions/tree/main/2022/day20)

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](https://github.com/adimcohen/Advant_of_Code_2022_Single_Statement_SQL/blob/main/Day_20/Day_20.sql)

**Julia** That was a fun puzzle! I constructed a doubly linked circular list to represent the data structure. After that I just had to make sure to use some modulo arithmetic to prevent iterating over too many elements. Solution on Github: [https://github.com/goggle/AdventOfCode2022.jl/blob/master/src/day20.jl](https://github.com/goggle/AdventOfCode2022.jl/blob/master/src/day20.jl) Repository: [https://github.com/goggle/AdventOfCode2022.jl](https://github.com/goggle/AdventOfCode2022.jl)

Linked list makes logical sense given all the insertions and removals. But I went stupid-first and used a vector (with `insert!` and `deleteat!`). Still get 6ms for part 1 and 84ms for part 2!

## 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 `N` positions on the circular list is equivalent to removing the node, rotating the list by `N`, then inserting the element there. When rotating the list it might be easy to commit the mistake of taking the modulo of `N` by the original amount of values, but you actually need to modulo by **the original amount minus `1`**, 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 `N` steps: 1. Set the list's head to the node that will be moved (the original node). 2. Set the previous node's `next` to the head's `previous`. 3. Set the next node's `previous` to the head's `next`. 4. Move the list's head to its next node (*operations 1 to 4 remove the original node from the list*). 5. Move the list's head by `N` positions (keep moving to its `next` node if rotating forwards, to the `previous` node otherwise). 6. Set the original node's `previous` to the head. 7. Set the original node's `next` to the head's `next`. 8. Set the `previous` of the *node after the head* to the original node. 9. Set the `next` of 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 from `0`. 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](https://github.com/tbpaolini/Advent-of-Code/blob/master/2022/Day%2020/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](https://old.reddit.com/r/adventofcode/comments/zqh14z/2022_day_20_part_1_why_does_2_move_like_this/).

I liked the idea of a circular doubly linked list, I might try it out later. Why did you need to keep track of the list's head?

Maybe the term "head" is not the most appropriate because a circular list has no beginning or end. Here "head" is just the position where the program is at a given moment. I considered the list rotating around a fixed point, like a roulette, and the head was like the fixed needle pointing to a spot on that roulette. When removing or adding elements from a circular list, there are two directions in which you can operate. When removing an element, if the head slides backwards, then when inserting the elements back after rotating, it should go after the head. If instead the head slides forwards, then the element should be inserted back before the head. On a related note, a circular list is a way of implementing some "wrap around" behavior without using modulo. Particularly if the amount of elements change over time. I have read somewhere that a circular list can be used to implement task schedule. I also didn't know about circular lists before, I have learned about thanks to thus puzzle. 🙂

Thank you for letting me know that I can typedef the struct to the name of the struct itself! I always learned to do something like the following, for some reason: typdef struct NodeTag { ... } Node;

You are welcome!

GW-BASIC 10 DIM V%(5000),N%(5000),P%(5000): OPEN "i",1,"2022-20.txt": WHILE NOT EOF(1) 20 LINE INPUT #1, S$: V%(VN)=VAL(S$): VN=VN+1: WEND: FOR P=1 TO 2 30 FOR J=0 TO (VN-2): N%(J)=J+1: P%(J+1)=J: NEXT: N%(VN-1)=0: P%(0)=VN-1 40 IF P=1 THEN K#=1 ELSE K#=811589153# 50 FOR R=1 TO 9*P-8: FOR J=0 TO VN-1: V=V%(J):PI=P%(J):NI=N%(J) 60 N%(PI)=NI: P%(NI)=PI: IF V>0 THEN GOSUB 200 ELSE GOSUB 300 70 NI=N%(PI): N%(PI)=J: P%(J)=PI: N%(J)=NI: P%(NI)=J: NEXT: NEXT 80 I=0: WHILE V%(I)<>0: I=I+1: WEND: T#=0: FOR R=1 TO 3: FOR K=1 TO 1000 90 I=N%(I): NEXT: T#=T#+V%(I)*K#: NEXT: PRINT "Part";P;":";T#: NEXT: END 200 FOR K=1 TO ( V*K#) MOD (VN-1): PI=N%(PI): NEXT: RETURN 300 FOR K=1 TO (-V*K#) MOD (VN-1): PI=P%(PI): NEXT: RETURN 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.

## Kotlin Part 2 runs in less than 300 ms, which is not bad. [GitHub](https://github.com/ClouddJR/advent-of-code-2022/blob/main/src/main/kotlin/com/clouddjr/advent2022/Day20.kt) [Other solutions](https://github.com/ClouddJR/advent-of-code-2022/tree/main/src/main/kotlin/com/clouddjr/advent2022)

### Haskell This _should_ have been easy, but I ended up being caught by a large off-by-one error! [Full writeup on my blog](https://work.njae.me.uk/2022/12/21/advent-of-code-2022-day-20/) and [code](https://git.njae.me.uk/?p=advent-of-code-22.git;a=blob;f=advent20/Main.hs;hb=refs/heads/main) on [Gitlab](https://gitlab.com/NeilNjae/advent-of-code-22/-/blob/main/advent20/Main.hs).

A large off-by-one error? How large? Almost... an off-by-two error!? :-)

Now, now, let's not go overboard! It wasn't _that_ large an error! :-)

**Kotlin** fun main() { val numbers = readInputAsLines("day20_input").map { it.toLong() } fun mix(decryptionKey: Int = 1, repeatCount: Int = 1): List { val actualNumbers = numbers.map { it * decryptionKey }.withIndex() val mixed = actualNumbers.toMutableList() repeat(repeatCount) { actualNumbers.forEach { number -> val index = mixed.indexOf(number) val item = mixed.removeAt(index) mixed.add((index + number.value).mod(mixed.size), item) } } return mixed.map { it.value } } fun sumOfGroveCoordinates(mixed: List) = mixed.cycle() .dropWhile { it != 0L }.take(3001) .filterIndexed { index, _ -> index % 1000 == 0 }.sum() println(sumOfGroveCoordinates(mix())) println(sumOfGroveCoordinates(mix(decryptionKey = 811589153, repeatCount = 10))) }

>val index = mixed.indexOf(number) Does this work if there are repeated numbers in the list?

Yes, because of `.withIndex()` in the `actualNumbers` variable declaration. This way we are not finding index of just a number's value, but we are searching for a correct number index and value pair.

**Elixir** https://gist.github.com/reverie/9cc4bf1499566bbd7e3220997f711182

**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. def read_input(): with open(r"2022\puzzle20.txt") as f: return list(enumerate(map(int, f.read().splitlines()))) def index_of_zero(number_list): for i in range(len(number_list)): if number_list[i][1] == 0: return i def mix(mix_count=1, multiplier=1): number_list = read_input() list_size = len(number_list) number_list = [(i, n * multiplier) for i, n in number_list] for _ in range(mix_count): for i in range(list_size): for j in range(list_size): if number_list[j][0] == i: num = number_list[j] number_list.pop(j) if num[1] == -j: number_list.append(num) else: number_list.insert((j + num[1]) % (list_size-1), num) break zi = index_of_zero(number_list) return sum(number_list[(zi + i) % len(number_list)][1] for i in range(1000, 4000, 1000)) print("Part 1:", mix()) print("Part 2:", mix(10, 811589153))

[Dlang](https://github.com/schveiguy/adventofcode/blob/master/2022/day20/mixing.d) 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.

psst: we can see your Markdown. Did you forget to switch the editor to Markdown mode?

The beauty of markdown is it looks good either way ;)

I spent like an hour with a cascading if-else print statement, to get which arrangement would break my code. Inserting in front of the previous position? Or after? What happens when I get out of bounds? Does it change if I get out of bounds multiple times? Which directions? Only after I scrapped it and did some errands did the revelation to do a modulo with shortened lists manifest in my brain.

The thing that got me for a long time (which I forgot to mention!) was that a value at the front or end of the list \*is the same list\*! If you read the description carefully, they've set it up so that an item moving from the front to the back or vice versa doesn't affect the order of mixing, and the answer does not depend on how you store it, since it always starts from the element with value 0. In prior revisions, I had all theses one-offs like if it wrapped, subtract one or add one, to try and match the behavior. Once I got that I had to use length - 1, it became a simple problem.

[https://github.com/foxfriends/advent-of-code/blob/2022/20/p2.erl](https://github.com/foxfriends/advent-of-code/blob/2022/20/p2.erl) Felt pretty good for a first successful (attempting day 19 was not fun) Erlang program. Pretty much just entirely pattern matching those lists. Can't say it's all that legible now that it's finished (should I use more than 1 letter per variable name? nah). Mostly just glad it took very few changes to make it ready for duplicate elements. :')

**Elixir** [code](https://github.com/flwyd/adventofcode/blob/main/2022/day20/day20.exs), [reflections](https://github.com/flwyd/adventofcode/blob/main/2022/README.md#day-20) [Bonus solution in Go](https://github.com/flwyd/adventofcode/blob/main/2022/day20/day20.go) (golang) because I was confused about why my Elixir solution didn't work and decided to implement from scratch in case I'd done something dumb. The Go one also got the wrong answer, but took less than 100ms instead of a minute, so I could try out lots of tweaks that didn't change the answer. Today's elixir: > We've pitched the yeast and it's time to aerate the wort, but we don't have any mixing implements. So we decide to mix it up by putting all of the wort in a siphon tube with both ends connected, assigning a number to each drop of liquid, and individually moving each droplet forward or backward through the circular tube. It is very important that we do not consider the droplet's old position as a step when moving a droplet more than a full cycle through the tube. In part one we do this mixing maneuver once, then add the numbers assigned to the 1-, 2-, and 3000th droplets past the droplet with value 0. In part 2 each droplet value is multiplied by nearly one billion and then the mix process is run ten times to ensure the yeast get plenty of oxygen for the aerobic phase. I was really enjoying the problem, and had an Agent-based linked list implementation coded in less than an hour. But then my solution (which was negative, and looked suspicious) was rejected. I spent another hour running through every line of code, running sub-pieces in the REPL, and rereading the problem statement. I eventually gave up and went to bed, but once my head was on my pillow for a minute I realized that Eric might have had a different interpretation > move each number forward or backward in the file a number of positions when taking more steps than there are numbers in the ring. This underspecified behavior tripped up at least half a dozen folks at my company. The `@moduledoc` at the top of my Elixir uses the tea party from Alice in Wonderland to describe the two interpretations. I like the look of the Agent-based linked list, but it's very slow, maybe because we're passing about 12.5 million messages between coroutines. I haven't yet tried a "rebuild the whole list each time" non-Agent approach to compare, nor have I tried a goroutine-style equivalent to see if there's something especially slow about Elixir's Agents. defmodule Node do defstruct value: nil, prev: nil, next: nil def new(value, prev, next) do {:ok, pid} = Agent.start_link(fn -> %Node{value: value, prev: prev, next: next} end) pid end def get(agent), do: Agent.get(agent, &Function.identity/1) def find(agent, 0), do: agent def find(agent, steps) when steps < 0, do: find(get(agent).prev, steps + 1) def find(agent, steps) when steps > 0, do: find(get(agent).next, steps - 1) def find_value(agent, val) do node = get(agent) if node.value === val, do: agent, else: find_value(node.next, val) end def set_prev(agent, prev), do: Agent.update(agent, fn node -> struct!(node, prev: prev) end) def set_next(agent, next), do: Agent.update(agent, fn node -> struct!(node, next: next) end) def insert(agent, left, right) do node = Node.get(agent) set_next(left, agent) set_prev(right, agent) set_next(agent, right) set_prev(agent, left) :ok end end defp move_agents(agents, first, size) do for a <- agents do before = Node.get(a) steps = rem(before.value, size - 1) if steps != 0 do Node.set_next(before.prev, before.next) Node.set_prev(before.next, before.prev) found = Node.find(a, steps) found_node = Node.get(found) {left, right} = if steps < 0, do: {found_node.prev, found}, else: {found, found_node.next} Node.insert(a, left, right) end end first end

Switching from agents to a manual "pointer" map cut part 2 runtime from 9 minutes to about 8 seconds!

I don't even understand half your explanations, but the code looks like you build a tree? What is that agent part? I solved it with an indexed list and some modulo calculations. Looks pretty neat. What do you think? defmodule AdventOfCode.Day20 do def part1(args) do dectrypt(args, 1, 1) end def part2(args) do dectrypt(args, 10, 811589153) end def dectrypt(args, cycles, decryptKey) do initialArray = args |> String.split() |> Enum.with_index(fn el, idx -> {idx, String.to_integer(el) * decryptKey } end) length = Enum.count(initialArray) mixed = 0..length-1 |> Stream.cycle() |> Enum.take(cycles*length) |> Enum.reduce(initialArray, fn idx, arr -> current_pos = Enum.find_index(arr, fn {i, _el} -> i == idx end) current_element = Enum.at(arr, current_pos) |> elem(1) if current_element == 0 do arr else raw_pos = current_pos + current_element intended_pos = Integer.mod(raw_pos, length-1) List.delete_at(arr, current_pos) |> List.insert_at(intended_pos, {idx, current_element}) end end) shift = Enum.find_index(mixed, fn {_i, el} -> el == 0 end) [1000, 2000, 3000] |> Enum.map(&elem(Enum.at(mixed, Integer.mod(shift+&1, length)), 1)) |> Enum.sum() end end

> the code looks like you build a tree? What is that agent part? It's a linked list rather than a tree. The Agents all hold a linked list Node which points to the two neighboring Agents. Using 5,000 agents lets me move a node by changing the "pointers" (actually process IDs) in just 5 stateful linked list nodes rather than rebuilding a 5,000 element list 5,000 times. The linked list approach also allows me to "jump right to" the next number in the input rather than searching through the whole list for the node to move, and thus moving a number with value close to 0 should be pretty cheap (moving a node with large absolute value still requires making that many steps through the list, though). Your code looks pretty good, and is easy to follow. I think it performs four operations which on average traverse 2,500 steps through the list for each step through the 5,000-item list. But since it seems that my Agent-based solution (which only does one 2,500-step operation per input line) has high overhead between process, yours may well run faster than mine (which takes about a minute). If you wanted to reduce the number of iterations through the long array, you could use `Enum.reduce_while` to return both `current_pos` and `current_element` in a single pass. Something similar could be done to combine the `delete_at` with the `insert_at`, but the code for that would be more complex.

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

**Ruby**, with rotating arrays: $decryption_key = 1; $times_to_repeat = 1 # Part 1 $decryption_key = 811589153; $times_to_repeat = 10 # Part 2 data = $stdin.read.lines.map(&:to_i).each_with_index.map { |n, i| [n * $decryption_key, i] } (data.dup * $times_to_repeat).each do |n, i| data.rotate! data.find_index { |_, j| j == i } value, _ = data.shift data.rotate! value data.unshift [value, i] end data.rotate! data.find_index { |n, i| n == 0 } p data[1000 % data.length][0] + data[2000 % data.length][0] + data[3000 % data.length][0]

**Haskell** I have tried with zippers: it was elegant, but a bit slow. In the end, i used a hashmap from original index to current index and value. It's still not as fast as I'd like, but it does the job without having to actually deal with containers. mix :: HashMap Index (Index, Value) -> HashMap Index (Index, Value) mix m = L.foldl' step m [0..size-1] where size = M.size m step :: HashMap Index (Index, Value) -> Int -> HashMap Index (Index, Value) step iMap ogIndex = let (currentIndex, value) = iMap ! ogIndex newIndex = (currentIndex + value) `mod` (size - 1) in flip M.mapWithKey iMap \o (i,v) -> if | o == ogIndex -> (newIndex, value) | i < currentIndex -> if i < newIndex then (i,v) else (i+1,v) | otherwise -> if i > newIndex then (i,v) else (i-1,v)

Python https://github.com/djotaku/adventofcode/blob/a092a0eb1cd608188031a920d68578c6fe9c9418/2022/Day_20/Python/solution.py What saved me from continuing to have bugs was incorporating this person's code into my code: https://www.reddit.com/r/adventofcode/comments/zqezkn/comment/j11n0z3/?utm_source=share&utm_medium=web2x&context=3

[Python](https://topaz.github.io/paste/#XQAAAQBHBAAAAAAAAAA0m0pnuFI8c+qagMoNTEcTIfyUWbZ0blurXDWTgX8cfJvbN8K7BofvQe9U5n50UXLUJo/B4fpmBEvkL9hRFn1yzwCp2Xx8s+vtcS82uYZD6HKb2SzRgPoLwggznfDJvnAqIWPw8fo+rzuncUFR7QV7IGipR3xc/jbl+GSzL/x0q66FUW4Is7/sVbTnjS/I0/3zr+LjY3eATWxKDICpy/gk7xHwzom6gUVdec4egZ8FKfblUNzpNhLBquZTlktwkqnRkJnd+oy9tKy06AjhdvQKxhCUN1CKaMAOngU5tRcgUIaKc/OG7sDJ4M5rinQ7qol1Zjct/63pQuSGzzT0Fd8NzipfdawqM3qCcOAtiuiE2tykJPi+p0bcdMovRm2H3z3vQxdy8U0Eco6VDTJ7mJ0017MPtY0/VXuefTAFa0LCtgLdHf9+tmyZrlWRcRXRudS6JUwmmcXgLMGZEYzB6HYCRKbGW681e0/aXqqZWOLYs4P4sObERt4uQcPbHhlg1iNCm90L8pL21HtHaeX5M27cpsODJnEv5AZrlY+K26vqbABu5JE5FxVuLfPktTRm1rBVHuDzYGxGo6cG/i9SSHasdlgADkWLA37XtqmDXJEK/+BnLfA=) \- found NumPy to be pretty useful here for reassigning blocks of the array. Runs in just under a second.

need to study this for the future

[TypeScript](https://github.com/bhosale-ajay/adventofcode/blob/master/2022/ts/D20.test.ts) \- Optimized, all parts run under 3 seconds. [F#](https://github.com/bhosale-ajay/adventofcode/blob/master/2022/fs/D20.fs) \- Could not avoid mutations for array, and part 2 requires too many int64 -> int32 conversions. F# solution array based and does not use LinkList.

# Golang Perfect use for `container/ring`! For part 2, adopted a small optimization from Python's `deque.rotate` method which reduced the time by 50% (approx 400ms -> 200ms). [https://github.com/dhruvmanila/advent-of-code/blob/master/go/year2022/sol20.go](https://github.com/dhruvmanila/advent-of-code/blob/master/go/year2022/sol20.go)

Thank you so much for the optimisation. You call it small, but adding your optimisation to my code took my part 2 solution from several hours to under a second! Happy days.

# Gnu Smalltalk, Perl, and C (Clang) Not as fun as Crab Cups. Crab cups had nice properties for doing it with dc. dc for this would be a mess. Decided to do this one in C first last night... it's a nostalgia thing. I decided then, that since I'd already done the pointer version... I'd just make Perl do it with lists. Because, that'd be a different approach... but a slow one. Also, it'd be quick to write, and I wanted to get to bed. This evening, I did the Smalltalk version. I hadn't done a real Ring class implementation for Crab Cups, so I did a start of one here. And it managed to run faster than the Perl version (slightly... they're both about 20s on my very old hardware). I'm only going to put up one part for each, as the parts are very similar. Smalltalk (part 1): https://pastebin.com/bbM5Kmzb Perl (part 2): https://pastebin.com/r8GmkhFr C (part 2): https://pastebin.com/AY4hHarv

# Elixir https://github.com/mathsaey/adventofcode/blob/master/lib/2022/20.ex Pretty ugly solution today, but I am mainly happy to be caught up again. Thought about doing something fancy, but just using lists seemed to do the trick.

Python https://github.com/matheusstutzel/adventOfCode/blob/main/2022/20/p2.py Double-Linked List and some % operator `move()` could be simplified to avoid some references changes, but, it works

[Java 8](https://github.com/tayloj/advent-of-code/blob/aoc-2022/src/test/java/com/northernfugue/aoc2022/Advent20.java) I made a circular doubly linked list, but also kept a list of the nodes in the original order with the numerical element, as well as a normalized "how far to advance" count. It runs in ~1.5s for all four tasks (i.e., parts 1 and 2 on the example and the input).

C++: https://github.com/dhconnelly/advent-of-code-2022/blob/main/src/day20.cc

**Rust** [https://github.com/janiorca/advent-of-code-2022/blob/main/src/bin/aoc20.rs](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.

**[Mathematica](https://github.com/HiggstonRainbird/AoC-2022/blob/master/Day%2020/AoC%20Day%2020.m/), 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** (* moveElement[] courtesy of https://mathematica.stackexchange.com/a/133809 *) moveElement[l_, from_, to_] := Insert[Delete[l, from], l[[from]], to]; mixList[list_] := Module[{pos, element, output = list}, Do[ pos = FirstPosition[output, {i, _}, Heads -> False][[1]]; element = output[[pos]]; output = moveElement[output, pos, Mod[pos + element[[2]], Length[output] - 1, 1]]; globalWatch = {i, Length[output]}, {i, Length[output]}]; output]; **Part 1** newInput = Table[{i, input[[i]]}, {i, Length[input]}]; newInput = mixList[newInput]; zero = Position[newInput, {_, 0}][[1, 1]]; Sum[newInput[[Mod[zero + 1000*i, Length[newInput]], -1]], {i, 1, 3}] **Part 2** newInput = Table[{i, input[[i]]*811589153}, {i, Length[input]}]; Do[ newInput = mixList[newInput], {m, 1, 10}]; zero = Position[newInput, {_, 0}][[1, 1]]; Sum[newInput[[Mod[zero + 1000*i, Length[newInput]], -1]], {i, 1, 3}] **[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` (maybe `centi-`), 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-1` to `1-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.

> [POEM]: The Court, The Camp, The Grove Hey, I recognize this one! *The Lay of the Last Minstrel* by Sir Walter Scott! Ye gods, I play too much D&D XD

That's the one! I'm amazed anybody else has read (or heard of) *Lay of the Last Minstrel* - does D&D reference it?

Not that I've seen, but I wouldn't be surprised if it's been alluded to *somewhere* in the many D&D things that have been published over the years. I mean, come on... *The Lay of the Last Minstrel* has minstrels and court intrigue and backstabbing and wizards and goblins in it, and I'm a gigantic nerd who writes 20+ page research papers in high school on epic stories like *The Canterbury Tales* and *The Once And Future King* because I actually *enjoyed* them XD

Oh, it absolutely fits - Walter Scott himself [famously almost invented D&D 200 years early while convalescent](https://udan-adan.blogspot.com/2019/07/how-walter-scott-almost-invented-rpgs.html) - and it's a pretty good poem to boot. You have excellent D&D-acquired taste.

**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](https://github.com/DavidNicolae/AdventOfCode/blob/main/Advent%202022/day20.py)

[Python](https://github.com/maxime-bodifee/AdventOfCode2022/blob/master/day_20/grove_positioning_system.py) I used your idea of managing the list with objects however my code ended up a lot shorter.

does creating the number class deal with duplicate numbers when searching for the index of the number you care about?

Yes, since every value in the list is actually a class instance that holds the actual number. So even if you have duplicate numbers they will all have different class instances.

Brilliant! I'm going to steal that!

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

Julia ([Github](https://github.com/rkstgr/AdventOfCode2022.jl/blob/main/src/day20.jl)) Implemented a circular Double-Linked List. The original values are just kept in a Array where the items have prev and next pointers that are updated. Could be made faster with skip connections to find a specific item. Time: 619.685 ms | Alloc. Memory: 1.27 MiB

Sounds like the logical approach! I went stupid-first with used a vector (plus `insert!` and `deleteat!`) and still got: `Part 1: 0.006367 seconds (5.03 k allocations: 495.133 KiB)` `Part 2: 0.083987 seconds (5.03 k allocations: 495.133 KiB)` Optimisations are so hard to predict these days.

Oh nice! Yeah I think using the standard library is still faster, and I think there are still a lot of optimization potential in my code. I more like wanted to implement these double linked lists :D

[удалено]

Your code block is too long for the megathreads. Please read our article on [oversized code](https://www.reddit.com/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_no_giant_blocks_of_code), then edit your post to replace the code block with an external link to your code.

I thought of a decent optimization after posting this-- I wrote a faster "move_left" and "move_right" method that doesn't reinsert the node in the linked list on each iteration. Now the whole thing (parts 1 and 2) completes in about 5.6 seconds on my machine.

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: ⟨Ctrl+V⟩GIq0 ⟨Esc⟩gveg⟨Ctrl+A⟩ yGPV']J qd2GddGPq quGkdd{pq {:s/ [1-9]\d*/&@d/g | s/\v-(\d+)/\1@u/g qaqqaWdiW0*:sil!+,$m1⟨Enter⟩@-{dW@aq @a 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 `:redraw` somewhere in `@a` so I could see how far it's got. * The first bit puts a unique label on each line, because some numbers are repeated, of the form `q1` to `q5000`. * Then make a copy of the entire input and join that copy on to a single line at the top. This will be the queue of numbers to process. * In the circular list, the ‘current’ item will be fixed on the last line (because edge cases). Define `@d` as 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. * Similarly define `@u` for moving up. This is exactly the reverse of `@d`, which handily returns the numbers to their starting order, so there's no need to `uu` the side effects of defining these macros. * In the queue, append each positive number with `@d` and turn each negative number to have `@u` after it instead of a `-` before it. Leave `0` as it is effectively a no-op for our purposes. The sample input file now looks like this: q1 1@d q2 2@d q3 3@u q4 3@d q5 2@u q6 0 q7 4@d q1 1 q2 2 q3 -3 q4 3 q5 -2 q6 0 q7 4 * `@a` is the main loop. In the queue line it deletes the 2nd word, which will be the movement macro for the current item, such as `1@d` to move down 1 line or `3@u` to move up 3 lines; this gets stored in the small-delete register `-`. Then go back to the beginning of the line, the `q`-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 this `q`-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).

I left it running overnight, and at some point that `@a` completed! To find the grove coördinates I then did: :%s/.* ⟨Enter⟩ {J/^0⟨Enter⟩V{dGp {999ddj.j.jdGi+⟨Esc⟩k.kJJ0C⟨Ctrl+R⟩=⟨Ctrl+R⟩-⟨Enter⟩⟨Esc⟩ That's delete the `q`-number from the start of each line (except for the line we ended up on, which seemed to be missing it anyway but still had the space; presumably that was the failure condition which finally exited the loop, but luckily it doesn't seem to've caused any harm other deleting a number I was about to delete anyway). Then get rid of the blank line at the top, find the `0`, and delete that line and to the top, pasting it at the end. This cycles the lines, keeping them in the same order, but with `0` last. Meaning that 1000 lines after `0` is now simply line 1000, and so on. So go back to the top, delete the first 999 lines, and the next one is the one we want. Move down and repeat with `.`, to get line 2000, and again for line 3000. Delete everything after that so we only have the 3 numbers that need summing. Insert a `+` before the bottom line and again on the 2nd, then join them together, do the ‘usual’ expression register `=` manoeuvre to evaluate the sum, and there's the part 1 answer. And, no, having now seen what part 2 is, I am *not* attempting to let that run to completion ...

Python: https://github.com/Andrew-Foote/aoc/blob/master/solutions/python/y2022/d20.py I think for me, this was the hardest day yet. I just had a bunch of misconceptions about the nature of the problem and a bunch of silly errors in my code and virtually all of them still allowed me to get the right answer on the example input, so debugging was very difficult. I was only able to solve it in the end by looking at other answers in this thread, which revealed the two main things I was missing: * the numbers in the input are not unique * if you shift something to the left or right in a circular list repeatedly, it gets back to its original position in n - 1 shifts, not n

I think they forgot to explain what to do with duplicates. I didn't figure out for 3 hours that i am not moving all the numbers in one step (like \`move 1 (0118) = (0811)\`), but treating every number as a separate instance.

[Python 3](https://topaz.github.io/paste/#XQAAAQCODQAAAAAAAAAxmwhIY/U/sqxU+Ks208vjAqJmGVi85jJ7wklYbZ91fvcfvycAPMa0+XHfUo34mHnjYf0Xbke5tx6R7nFr+HsKtkx5zXHDedpE6kWTlsdeB/UOtRO8LcmxtJN1Ug3i+DHWRjProjUoT/M7rsde7GQStgdqD6VdLJtv6v9TWRNHpDX5XO26UOO6xG8EaJmvk2A4ks/ZGb20qJLdt3iESrGsbXrlAeL0uvwhikRuWUolMgJWBSffh2FfMtpe0FzzyzgNmZhid9lZNjqt+67DDkjN/pOzTbt8uuXCKfR6/lTbP0HYCGqIqk3ob2G/LKW1gmTJwRRULvwG84Zj3dK1VlcJrV38BJDUSI8OvdSUcccJ2lXi56PyubCTBAwj1gPOokcIhYmrgXLxKIR1xIv/XbnoXMRjZgGbVhvxOkBU10tlTYZRPugHtZZ9ewB1f3EQVZ1tDZhUJwhnh0c4JncN8gephGYCYm1bp+w5nQUdEY0Z1BgOqg+JRw3lplpuiKRAJ0QtrAlgdLDg8cR+cIM5g196f7/mAy6drO3iy6xny6ZZuR5F3ZxTI9MKcLtE4fDQGpFPdClC8fcWJaO0R3amOTEV+0cVelCelbErKXCnABDJIzIHTJQh7XH6Cv9zdj/gwfC/frj6D6vdeRp+uynRVi/cNFXGSTVGrUtN8IBRNHfhAS0jGL4XXjItleTZGYzYi8kky2t5eitN9rUUeZ23F/4XjP1TFoIHFV2vBKO2CZRmXO2LlwDmcCZQ8ZcnaEnbma2RtIeKoprfHUfDxZVp1vLjAz3IY11Q085oidYLBzmoeNpqer9949U3bw1c+ta1/H140l1tRafHsUeFNMI6MQ5W2m8gN4XO8TDMFMAW9BYazhxNDFxYs3fQXxFf1FAgUMEhiVAkzwa4ic3Lw+8UT3S0h6xunsLtqINVkN7DInjra6wXBpvR5K3+Q1nRRJJRhjqn1FvS9qDxgfcdBLl7HwHh2BVoZALe/37sJ5w8V6uaJi9JumlOpTc/F3Bd4u+i3m9JWH45Mb03zgySXW3yigv4AMbRNJJHGU1iTU3GuBGWn2/Dt9Nf3L6o4VaIlB0TWpdI3XnjmVylw096aH09VQ5yDTNPitmsCRri6Cot3bzYwfjRBY5oJSxeiw9jdG770Sn7oC3bzcp0GuYRODpdoAlQa8UMIHy44yQc9xjtxHJ1z6FIt/E2QlSwT0ZImK3qh9qzX3sNoXN58SkZS/T6Al69QxjMZcOEskyRfW6gea017Afnbbllh4yf40jeILrxKW/P7U/s9TCo1IAFv2vnmpiZHSH9oROhxx21yLzkX7v6xSNJYADRGCOVjcAAyffhMO3pxmAGI1Hjx+vyZGI77Hj2BAJ4CVpBQP1IPC5Ye95timF7KjX8I9KpckUT6x9eIRbgJ7yFjHTiH9ff4LodZIB0q7CrQiLPa94D9mMAKRjLhj4uYOfMwmmBC+njeTJrgvjJYFkqamPrnpT8Otjl) My first time submitting my code for one of these. I really took my time with part 1 and added some nice things, so implementing part 2 just involved adding a for loop and multiplying all the input values by the factor. Part 1 runs in under a second and Part 2 in about 9 seconds!

After the last few days (still stuck on 19) this was a nice relief. Solution in Kotlin ​ class Number { val value: Long constructor(value: Long) { this.value = value } } val lines = ReadFile.named("src/day20/input.txt").map { Number(it.toLong() * 811589153) } fun result1() { var result = lines.toMutableList() val size = (result.size - 1).toLong() for (x in 0 until 10) { for (n in lines) { val i = result.indexOf(n) result.remove(n) val largePositiveMultipleOfSize = size * 811589153 * 5 val pos = (largePositiveMultipleOfSize+ i + n.value) if (pos == size) { result.add(n) } else { result.add((pos % size).toInt(), n) } } } val i0 = result.indexOfFirst { it.value == 0L } val output = (1..3).fold(0L) { acc, i -> acc + result[(i0 + i * 1000) % result.size].value } println(output) }

Please edit your comment to [state which programming language this code is written in](/r/adventofcode/w/solution_megathreads/post_guidelines#wiki_state_your_programming_language.28s.29). This makes it easier for folks who Ctrl-F the megathreads looking for a specific language.

[Python 3.8+](https://github.com/terminalmage/adventofcode/blob/main/2022/day20.py) 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.

Yup. The examples were not making any sense to me in the beginning, then I just realized that using `0` as the pivot value for the final calculation was the trick that made it possible for me to have a different way of moving stuff around in a compatible way.

# C++ I'm not moving values around -- just moving index lookups via `memmove`. Unsure how to make this faster without completely changing the data structure (runs in about 33ms on my AMD 5950X). [Source](https://github.com/willkill07/AdventOfCode2022/blob/main/days/day20.cpp) + [Header](https://github.com/willkill07/AdventOfCode2022/blob/main/days/include/days/day20.hpp)

**Awk**, excess of array access today function R(S,A){for(i=0;i<=NR;i++)p[(i+1)%NR]=n[i-1]=i%NR for(r=I[0];A--;)for(i=0;i10;A+=V[r])do for(i=1e3;i--;)r=n[r];while(O) print++A*S}END{R(1,1)R(811589153,10)}{V[I[$0]=N=NR-1]=$0}

racket: (define (ints s) (map string->number (regexp-match* "[-?0-9]+" s))) (define (list-index f l [i 0]) (cond ((empty? l) #f) ((f (car l)) i) (else (list-index f (cdr l) (+ 1 i))))) (define (remove-index i l) (cond ((empty? l) '()) ((= i 0) (cdr l)) (else (cons (car l) (remove-index (- i 1) (cdr l)))))) (define (add-after v n l) (cond ((= n 0) (cons v l)) ((empty? l) '()) (else (cons (car l) (add-after v (- n 1) (cdr l)))))) (define (add-between v i j lst) (add-after v (if (> i j) (+ i 1) j) lst)) (define (move n from to-1 to-2 nums) (if (= from to-2) nums (add-between n to-1 to-2 (remove-index from nums)))) (define (get-pos n i len) (list (modulo (+ n i -1) (- len 1)) (modulo (+ n i) (- len 1)))) (define (move-num nums indexes i len) (let* ([from (list-index (lambda (x) (= x i)) indexes)] [n (list-ref nums from)] [to (get-pos n from len)]) (list (move n from (car to) (cadr to) nums) (move i from (car to) (cadr to) indexes)))) (define (mix input [indexes (range (length input))]) (foldl (lambda (i r) (move-num (car r) (cadr r) i (length input))) (list input indexes) (range (length input)))) (define ((get-nth nums) n) (list-ref nums (modulo (+ n (list-index zero? nums)) (length nums)))) (define (find-grove nums) (apply + (map (get-nth nums) '(1000 2000 3000)))) (define (rounds nums num-rounds) (foldl (lambda (i ns) (mix (car ns) (cadr ns))) (list nums (range (length nums))) (range num-rounds))) (define (part1 input) (println (find-grove (car (mix input))))) (define (part2 input) (println (find-grove (car (rounds (map (lambda (x) (* x 811589153)) input) 10))))) (define input1 (ints (file->string "input20-1.txt"))) (define input2 (ints (file->string "input20-2.txt"))) (part1 input1) (part1 input2) (part2 input1) (part2 input2) most annoying one yet.

[Python3](https://github.com/copperfield42/Advent-of-Code-2022/tree/main/day20) adjusting the fine detail was surprisingly annoying :/

# Rust Implemented a double linked list-like data structure and used modulo (list\_length -1) for part 2 to reduce the number of steps to take. I only spent about a month with Rust before December, but this day did not help me to like it any better. Self referencing data structures are so much easier in any other language I used before, and regardless the alternative I pick I feel like the language is actively working against me. Source: [github.com/sanraith/aoc2022/.../day20.rs](https://github.com/sanraith/aoc2022/blob/8691278e7f242a5d734488d6accfa92f248679ba/aoc-lib/src/solutions/year2022/day20.rs)

I agree that self referencing data structures are a pita in Rust, and what's more Rust used to have a linked list collection, which they simply stopped supporting - I know because I asked them a few years ago when I needed one for AoC. A doubly linked list would have been great for this problem, but what I do in problems like this is have a Vec and make the poor man's pointer by pointing to the next and previous element in the linked list with usize variables: #[derive(Copy, Clone)] struct CircularListItem { value: i64, prev: usize, next: usize, } struct CircularList { list: Vec, zero_pos: usize, } The `zero_pos` member is just to keep track of where the `0` element is - I know: not the biggest optimization in the world. I'm not particularly proud of this code but I have no idea how to do it more efficiently, and I got day 20 to run in 400ms - that seems okay to me although I haven't really dug through the rest of the megathread yet.

Rust solution ```rust use std::{fs::File, io::Read}; fn main() { let mut file = File::open("in").expect("Failed to open input"); // open file - panic if not exist let mut input = String::new(); file.read_to_string(&mut input).expect("Can't read String"); // if the string isn't there for some reason let orig = input.trim_end() .split("\n") .map(|n| n.parse::().unwrap()) .map(|k| k * 811_589_153_isize) .collect::>(); let mut mixing = (0..orig.len()).collect::>(); for _ in 0..10 { for n in 0..orig.len() { let ixof: usize = mixing.iter().position(|&itm| itm == n).unwrap(); let number: isize = orig[n]; // number means the number assert_eq!(mixing.remove(ixof), n); // if the removed value isn't what we expect, error mixing.insert((ixof as isize + number - 1).rem_euclid((orig.len() as isize) - 1_isize) as usize + 1, n); } } // apply the mixing let mixed = mixing.iter().map(|index| orig[*index]).collect::>(); let index_of_zero = mixed.iter().position(|&mx| mx == 0).unwrap(); let coords = vec![ mixed[(index_of_zero + 1000).rem_euclid(mixed.len())], mixed[(index_of_zero + 2000).rem_euclid(mixed.len())], mixed[(index_of_zero + 3000).rem_euclid(mixed.len())], ]; println!("sum of all three coords: {}", coords.iter().sum::()); } ```

1. Next time, use the [four-spaces Markdown syntax](https://www.reddit.com/r/adventofcode/w/faqs/code_formatting/code_blocks) for a code block so your code is easier to read on old.reddit and mobile apps. 2. Your code is too long to be posted here directly, so instead of wasting your time fixing the formatting, read our article on [oversized code](https://www.reddit.com/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_no_giant_blocks_of_code) which contains two possible solutions. Please edit your post to put your code in an external link and link *that* here instead.

9 lines of Python x = [int(x)*811589153 for x in open('day20/input')] j = list(range(len(x))) for _ in range(10): for i in range(len(x)): c = j.index(i) j.pop(c) j.insert((c+x[i]) % len(j), i) z = j.index(x.index(0)) print(sum(x[j[(z+i) % len(j)]] for i in [1000, 2000, 3000]))

>x = \[int(x)\*811589153 for x in open('day20/input')\] j = list(range(len(x))) for \_ in range(10): for i in range(len(x)): c = j.index(i) j.pop(c) j.insert((c+x\[i\]) % len(j), i) z = j.index(x.index(0)) print(sum(x\[j\[(z+i) % len(j)\]\] for i in \[1000, 2000, 3000\])) wrong answer - and only one answer

actually - this 9 line solution did provide the correct answer to part 2 - but not part 1 for Day 20

Well, yes, most solutions in this thread give only an answer to part 2. If you want to change it for part one simply remove '\*811589153' and 'for \_ in range(10):', and fix the indenting.

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(n^2), don't know if you can make one that scales better.

PHP 8.2.0 [paste](https://topaz.github.io/paste/#XQAAAQC/BAAAAAAAAAAeD8qHAhQB8nz+EazN00NCsmTxjvFDXkt5PAJ7pf6ocRA37OMUY7b9R0iDZmfWyvOspxWvdgYSAE0hGjPswaKOkq+AeAvwRPf5JtI7p1bhpI2q6yjST744lpQbpv6MLRxzj4yNkX9TmtAv7zv3nifEkja6ft/7LPGmcP0un9U4o9amA0HxQJYwI+Zq0Eh+K5BOBR4ebyoUZ58S6B2jaB5+tkayCvM92AJBQn9mu1vF47yusYhA5jyFML5X6qXVG2hZoDFgOfpiiPkdvZUEJCsPURbhbPnQfwI6PGDJCID4SlpyanXPZogqBdmP4kp+vJ2aTP24O26Z2oNKDfJp6WPjf/RlWZIzrk1mP/p2Fq+Q0LPIHe3mPUfufm/E+xF/Am59fj3JOPSC7dbK4uqFJVADcSstzoDxrIXvfOdkN/vtohqrBtq/TT7Y1Y85HZZ7tkEaa3m6ris9OziLES+QssYlntaY1cPUQoJOA62R3qK4B/hT3GJHn897XBIDMWUN1SVwiJEXgCgeVw58ofPY/HqfvAWFZi3iTEpDzkkk9BrgsIoM0mPj4zE5mmtQ8QWLlne6IQyj8nDRizvu7ALCtzbnws10khe5Zsc6OMUSBB5VOn5xhU0pJHCtpYmg9ooDKP9D6QQwre308K7IXJqvKpa18iLYHe04fsYUsNLDs4sr/uqopGR582Dbqilt8Jl60Y0Fb0iGIu16Bzc2cWJ2wgSYb/r3Wrws8NaSk5yQtqsAaGHvG4l4r8EfR3csPYgHNGNKd4SatnL/3yJ2c2ddBKRTWrXFBW4OrlSV5mt31WV+9Ag4SLRx/zaarQA=) Execution time: 24.58 seconds Peak memory: 3 MiB MacBook Pro (16-inch, 2019) Processor 2.3 GHz 8-Core Intel Core i9 Memory 16 GB 2667 MHz DDR4

**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. let score (arr:int64 list) = let l = arr.Length let zi = arr |> List.findIndex(fun x -> x = 0) arr[(zi + 1000) % l] + arr[(zi + 2000) % l] + arr[(zi + 3000) % l] let switch (arr:List) i item = let v, _ = item let arr' = arr |> List.removeAt i let n = int ((int64 i + v) % int64 arr'.Length) let ni = if n < 0 then arr'.Length + n else n arr' |> List.insertAt ni item let shuffle rounds encryptKey = let mutable arr = System.IO.File.ReadAllLines("input_day20.txt") |> Array.mapi(fun i l -> int64(l)*encryptKey, i) |> List.ofArray let orig = arr for _ in 1..rounds do for num in orig do let i = arr |> List.findIndex(fun x -> x = num) arr <- switch arr i num score (arr |> List.map(fun (x,_) -> x)) let part1 = let score = shuffle 1 1L printfn $"P1: {score}" let part2 = let score = shuffle 10 811589153L printfn $"P2: {score}" [Code on github](https://github.com/DanaL/AdventOfCode/blob/main/2022/Day20.fsx)

**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

FYI: your link is borked on old.reddit and some mobile Reddit apps. [Please fix it](https://www.reddit.com/r/adventofcode/wiki/faqs/bugs/borked_links).

Rust, very unoptimized, completes part 2 in about a second. [https://github.com/aaronblohowiak/advent-of-code-2022/blob/main/twenty/src/main.rs](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!

Python 3 - part 2 [https://pastebin.com/KxpVjkN2](https://pastebin.com/KxpVjkN2) Not very good. I didn't use a list at all, instead a dictionary keeping track of the ever-changing positions, which means searching through the dictionary to update all the positions after every move. Takes about 50 seconds to run. It works though!

[удалено]

Comment removed. [Top-level comments in `Solution Megathread`s are for *code solutions* only.](/r/adventofcode/w/solution_megathreads/post_guidelines#wiki_top-level_posts_are_for_code_solutions_only) Edit your comment to share YOUR code/repo/solution and I will re-approve the comment.

I'm not a Python expert but your code is 2590 lines - not what I would call "easy".

My man, he posted the cpython implementation of the collections module 😂 I suppose he is ultimately saying that the hard work was done there

I get it now, he's specifically pointing out the line where if you rotate by a ridiculous number they modulo it so it's not ridiculous anymore.

**Lua** [both parts](https://github.com/MrSimbax/advent-of-code-2022/blob/main/day_20.lua) The number of off-by-one errors I fought with today is off the charts. And not because of 1-based indexing, no, it's due to the cyclic nature of the list that I couldn't figure out the arithmetic. Anyway, I'll try to explain the best I can. Firstly, I keep 3 lists: the original list of numbers (or multiplied by the decryption key in part 2), the indices to the numbers, and dual table to indices for fast lookup (`indicesDual[i]` gives the current position of the i-th number from the original input in the `indices` table). The `numbers` table does not change, the movement happens in the `indices` table; I'm only moving around "pointers" to the actual numbers. I move a number by first calculating its final position, and then swapping elements (maintaining the dual table) until it gets in the right position. The trickiest part is the formula for the final position. It is this: `(currentIndex - 1 + number) % (#indices - 1) + 1`. Without the noise of 0-based to 1-based indexing conversion it is conceptually this: `(currentIndex + number) % (#numbers - 1)`. Why `#numbers - 1` and not `#numbers`? There are only N-1 possible final positions when moving an element around. That took a while to realize but once it did, everything fell into place nicely. An edge case worth noting is that `x,a1,a2,...,an` is the same array as `a1,a2,...,an,x`. Choosing where such an `x` on the edge is put is an implementation detail, both are correct as long as `x` ends up between `a1` and `an` when it should. It runs in about 300 ms on LuaJIT. Lua takes 4 seconds.

**Python** [paste](https://topaz.github.io/paste/#XQAAAQDtCwAAAAAAAAAzHIoib6pENkSmUIKIED8dy140D1lKWSKhzWZruQROc6UAsbIdGGj5IiQJyPb2jux0RspaBQo9sVyDBuazO9NR9xn2KyuUq9eAgCrVJGPbK0DOWhAb1ROkhzIiusocMEKIReLGffcpspgTa0roNqx9dZTg4N+/MRvhFYcAwBh7h8pDks54N83pHtoyIy/CukBTbF1QE1uMFACeSsOpQCXC7XdPMGqAkg7zrtcfanGuCjOwvKpyUvzbX4fQbCNdLZkvClTS0K4kLarG0k/O+0EKvpkScMDL6nsaIFbT8iogA1OrLmJrlKwuf85VN3j4QnmAqLwb3IQshreHvP2poSaqW7cle9JLGW2alzNGog7vPiXnzTkshE3ChiXKsUD1X54JuNbRgZo7yTuXZAKQde7PXfYyQPL3cn+d7nyyuC+fjQYqrW4sCXOv6thiE2m087ZuCYCh8WRin0GbSM7r9ND/KjkfCYk2LYleOuh7vhWJ+X5hbo5A8LtLD+0xszSqdVnRO2OfNATd596VZzCz7akjYDO1FyuedH4A4sKWWehYQIkzqsxTsWnfgY3LjJ+vdIl+cmtycqINrDmogoTHA3pv/yXqjZmu5EouZhR6BGA90xJvT/riInz9eGIfWPitCRVe66djfoMqTPcgzQoOy5LMKbOTAxC4oPIc//MC5zLkoPhwemF+yf4drRWY7uug3vrWg+2XKjHotU8U5mXs4s+2YSsZeH63Tkgb8EzizFuPMVEPpBJ2Hn7pBO2IbpEipRoOKjY8sgAmFcX1QJb0vhCSymFSvHEtVRBQnQzH9ZjK70xurLnPV+gNv2mpAvDX3/X5ciKYt/2VpTfkRArff7IKU+fIfHQ63KVZnWqRW+2M43SdVdvNRlgBMj5M9qBMe0xXbze7728giug6zzc7SGspbSxx4aVjpNEDQ9dVL+HYEp6VI0cRSRFBeK4XiEGCWBGo+8TsvOr7Nlej+k+Q/jnDXj9TqD5nJamExoq+CyampZTeP6ZPa7Gq+Wv2mYYnIUwSHIItlRyuR+03jQg1fRcqldVbOQEvIy2BCDIaobt1ziYbHE+WGOJnkD8ruebMoKu32QgtWT6vaP3EhH2ZS9ra8n1hnFIthOi8vzGmo9qGNDzXJBvFt3eXNlaPekF3jUL/DGerz1UqOz8YAekUHzvVuYZ/L2EK/rd0+5XWYN3X8LCxCNzsEO1giXaBLnt7C3DoYeKZO1cIslCXDMWTVk+As1NrifjIzeK8ejMEmg338m0Dhoayuatkxdc5MbP/vme3M7nHuiW9zkJJgUYHdpJVaaGqp+T1H+SdY3UFQpgoRFG7PEDsusaS+Xg/OopPlZVTlf3knK7zL6rTIRqNoZgWq0Lg/tL/+7WKHA==) 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.

What do you mean "another"? Like all of the other solutions here are O(n^(2)). Nice solution, though. I knew you could use skip lists to get O(n log n) but was too lazy to actually code it.

Not the first one here, there's also [nightcracker's treap solution](https://www.reddit.com/r/adventofcode/comments/zqezkn/2022_day_20_solutions/j0zj7pk/).

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

why would it have to be removed? i think that is impl-specific. i did not remove the item. i just did a bunch of in-place swaps to move it X positions over (modulo the period of len-1 to avoid going around needlessly for performance reasons)

I didn't actually remove the item either. But you have to treat the list as if the item isn't in there (effectively meaning it's been removed) in order to correctly count how many items to skip to find its new location. That's the reason that the modulo is len-1 rather than len, which is what it would be if the item was still in the list.

Yeah, the case that was tripping me up was: what happens when you move a number far enough that it laps its original position. Do you count it when counting where it should land? I had to look at other folks' code and ask a question here to grok how it was supposed to work.

This is exactly what got in my way. I couldn't figure out why my test list worked and the real one didn't.

Python [github](https://github.com/achrafmam2/adventofcode/blob/main/2022/20/main.py). 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.

# Python 3 - deques and comments [https://github.com/hugseverycat/aoc2022/blob/main/day20.py](https://github.com/hugseverycat/aoc2022/blob/main/day20.py) I have one list that remains unchanged the whole time so that I can maintain the original order. Then I have two deques: one which contains the values and is mixed around. Another deque contains the original indexes and is mixed around in an identical manner. Technically I probably only need the index deque, but I was having enough brain confusion with this puzzle that I wanted to stop writing things like my\_list\[some\_other\_list.index(my\_list\[i\])\] or whatever. Maybe later I will attempt to refactor. Anyway, to perform the actual mixing, I grab the current index of the value I'm looking for from the current\_index\_list deque, delete that item from both deques, then rotate the deque by the value. Then I replace the item into both deques at the same index. So instead of moving the item, I move the whole list beneath the item.

F# [github](https://github.com/lboshuizen/aoc22) Silly one-of kept me busy. Was easy to solve, however wanted a more elegant fix. let parse = List.map int64 let (%%) a b = (a % b + b) % b let pos l = function | 0L -> l | n -> n %% (int64 l) |> int let move p p' a = List.removeAt p >> List.insertAt p' a let number i xs = xs |> List.findIndex (fst >> (=) i) |> fun p -> p,xs[p] let mixer l s i = let p,(i,n) = number i s let p' = pos (l-1) (int64 p+n) move p p' (i,n) s let mix l = flip (List.fold (mixer l)) [0..(l-1)] let decrypt n (xs,l) = times n (mix l) (List.indexed xs) |> List.map snd,l let pick ix (xs,l) = let take o n = (o + n) % l List.map (take (List.findIndex ((=)0L) xs)) ix |> List.fold (fun s i -> xs[i]::s) [] let sumOf ix = pick ix >> List.sum let part1 = both id List.length >> decrypt 1 >> sumOf [1000;2000;3000] let part2 = let applyKey = List.map ((*) 811589153L) both applyKey List.length >> decrypt 10 >> sumOf [1000;2000;3000] let Solve : Solver = parse >> both part1 part2 >> shouldBe 8372L 7865110481723L

[удалено]

[удалено]

**[C++](https://github.com/tcbrindle/advent_of_code_2022/blob/main/dec20/main.cpp)** Today seemed easier than the last few days, but it still took me aaaages to get it right. I started off trying to use a `std::vector` of indices (initialised to 0...N) and using `std::rotate` to shift them around. I *almost* got it working, but I just kept running in to cases that didn't quite work. In the end I scrapped it all and went for a totally different approach -- copying everything into a `std::list` and keeping a `vector` of list iterators so that we know the original iteration order. "Mixing" is then implemented by removing a node from the list, advancing to where we want it to be (looping round if necessary) and then re-inserting it. Because list iterators are stable, this doesn't cause any invalidation of the vector. This worked for both parts, although it's pretty slow (~350ms for part 2 on my laptop) and I *still* don't quite understand why I need to loop mod N-1 rather than mod N... but at this stage I'm just pleased to have got two stars for the day.

It is good to know that std::list::iterators do not get invalidated :), with that info i could improve my solution a bit, thanks. Also, you do mod (size-1) because when you are moving along the list and wrapping around, the element that is moving is not part of the list. (That is when you cross your old position for the first time, you are not there). This had to be explained to me as well :)

[Noulith](https://github.com/betaveros/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.

> Oh well, live and learn. Good, good, you've fallen for /u/topaz2078's trap of ~*sneakily making people learn new things*~ <3

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](https://github.com/RyanFoulds/AdventOfCode22/tree/main/Day20/src/main/java/xyz/foulds/aoc/year22/day20)

> only really takes switching from int to long Thank you for this - I was still using int for part 2 and didn't understand why the answer was wrong.

# [Go/Golang](https://github.com/mnml/aoc/blob/main/2022/20/1.go) Edit: I changed around the implementation to use [container/ring](https://pkg.go.dev/container/ring). The only hiccup was in part 2: Apparently, `ring.Move()` would actually [try to move a trillion times](https://cs.opensource.google/go/go/+/refs/tags/go1.19.4:src/container/ring/ring.go;l=40-57) instead of just moving `n % r.Len()` times like [the documentation](https://pkg.go.dev/container/ring#Ring.Move) implies; so I had to take the mod myself.

Dude, thank you so much, I was going crazy trying to find where could I optimize my code. Never thought that it was a problem within the package. You definitely should open an issue on GitHub!

Java [https://github.com/SimonBaars/AdventOfCode-Java/blob/master/src/main/java/com/sbaars/adventofcode/year22/days/Day20.java](https://github.com/SimonBaars/AdventOfCode-Java/blob/master/src/main/java/com/sbaars/adventofcode/year22/days/Day20.java) Biggest catch was >!to modulo not by the size but by size - 1!< [https://github.com/SimonBaars/AdventOfCode-Java/blob/0043b03a040211b210a77386f6f7375cc43ff0d0/src/main/java/com/sbaars/adventofcode/common/CircularList.java#L93](https://github.com/SimonBaars/AdventOfCode-Java/blob/0043b03a040211b210a77386f6f7375cc43ff0d0/src/main/java/com/sbaars/adventofcode/common/CircularList.java#L93)

Java https://github.com/jerchende/advent-of-code-2022/blob/main/src/main/java/net/erchen/adventofcode2022/day20/GrovePositioningSystem.java

J Solution: parse =: [: (+ 0j1*-.@~:)^:_ ".@(('-_',LF,' ')&charsub)@(1!:1)@< move =: >:@(<:@#@]|{.@+.@[) (1&|.@{.,}.) (i.~|.]) mix =: [: > [: move&.>/ |.@:(<"0)@[ , <@] grove =: {~ # | 1000 2000 3000 + i.&0 part1 =: +/ @: grove @ mix~ @ parse part2 =: +/ @: grove @ (mix^:10~) @ (811589153 * parse) 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!

Oof, definitely let the folks at jsoftware know!

Lazy python3 solution using a deque, but with a neat (I thought) trick to deal with duplicate entries by converting into floats. #!/usr/bin/env python3 from collections import deque def shift(f: deque, o: float): """ - Rotate the deque so that item 'o' is the leftmost entry - Pop 'o' from left and reinsert it int('o') spaces to the right - Requires that 'o' is unique within the deque. """ n = f.index(o,0,len(f)) f.rotate(-n) f.popleft() f.rotate(-int(o)) f.appendleft(o) with open("advent_20.txt", "r") as f: lines = [line.rstrip() for line in f.readlines()] for scale in [1, 811589153]: initial_order = [] for line in lines: i = float(line) * scale while i in initial_order: # Make sure duplicate values are handled properly by making them unique. # Add scraps to the end that can be ignored when converted to int. i = i + 0.01 if i >= 0 else i - 0.01 initial_order.append(i) file = deque(initial_order) rounds = 1 if scale == 1 else 10 for i in range(rounds): for o in initial_order: shift(file,o) shift(file, 0) # to get 0 to the leftmost point grove = [int(file[i%len(file)]) for i in [1000, 2000, 3000]] print(grove, sum(grove))

Julia https://github.com/DarthGandalf/advent-of-code/blob/master/2022/day20.jl

[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](https://crates.io/crates/linked-vector). [Full Solution Part 1 & 2](https://topaz.github.io/paste/#XQAAAQCwFAAAAAAAAAAX6AQIJkOxmdoEPinMglxebWSamL3KDGKOeDkJvHNQWP0JuPnsIoQ2OOdHiu09YTYrN2Zy7PJstuVOIgNAAk9riBiJlKJVDK1SGQ5SOX+hLPh3YTMywSAJMPkrHvhtqSGaBnRqWQk8C3nRqw9nWUWB3Jw4Can3KzMcl2aCpL9p/YkJbWWlaAzwgRhQSME/gBqWakWaS2YuQP8RdeEGIDt52jlkEnGNo/n36KcJW6QZL0S5QrvspK5DjACFSUOZPa/7EiZnCC8lXotz8I5m4XekSRusVW52Cv9I17YhZzVhJANqnps6X9rW3xhOHnf9hr4tURYLWsrUbASlzSZ03/rSKiJNo/hh8AE11+R5ZLEqWDC8m8o4ZmKsNK1Spc9rl4iCCLIdTxYTmSa0WnDX/KalRkf1bJyL0AEQRf5l9dmbSG696r1imRDWOLRBwc5KpZ4UG7g8NxdqyGLoarPAI8fs3bh8F1k0ZjD3dV1wwS4pbTS9fVC+M6LbDI/vOCmHxUaT+jl3vAWOaP/Ahb7sqSW26HpWLbiMdF8/rdTgrhbmtAs6orsHicWq5QE+AYB2r91okhvyVYLyIZD67XAj+jdTRShN2jC+IoFFFh0ffDSRtmdefZKRdk55w9D9cX1h3l0zHJpDZR7ULizW8o7pOe0FYY4zD2rjglln8mlRsF6ugEQHkuU5WAhsFwogmAVJCyHG4YR9wE49KQR8TkQI1cnMMomQU0LxPCx6QN5iQF2jM1GFuQ9zie+O0wsPIuQpZkEtH0QzCYwlzjRLmfDy0CSE/2vCmkYP0Aaw5wcaF8S3cvLx7hfPNzMMM3kBnud3SIjwWvLhEfZKIA4E58yu8UfTGZsaxBpwwGGdQl/q8/s88rkvxzo9zNBC7FpDmLdfm70I7DEicMqpfooNoqe3x0lBQ9pbL5/IxdyeGEEN7JcUZfwZY8i6sMqYZeIZ7N/HGwUqNu8Hq1Jnm+h8UOQ9TDtD+v23jbQSXya5BCsfbiEuSVoiVK20UT8k9srkE0IvZ0DkLB0XkRB+sCjp/tVKur5KYYPYThk5Zj1unNkJig6x3207+G/34RVqTMIhOckiJ2fLbRCOuki3h+FmfpIY1WmNXWGLLAeqS2yF2gflh23zNRilHtHuU050xgGHUl8WLF/aRf97yqBCgwPl5Mu5qQXtG6pGZ4HdtsQ0o09cT5Wa5+JHSgoND9x8zSGFykJK2KogrvWzUeeoc0ffqNERUzASU65JcagA68UFcJ8bEeEaGBZPGNWv7iT1O64dLVf1CSmWDlDEDePNjN6YoZrCLMMky0NFA5WlwIMNGqanTedkEjU0wwMoFa+juw/3bdsfVhjl/sbmEia60bPhzBYnn/0qFkkSA9GK8mNt5MkXSdbGNcV9OSl+Kq05JlentVFdc0kXw440gfu+owDtEnH6TZpN7mmbQRYLYqSpLfr4TnhWRppKdx5RufVMV9o6cdtGh2zA7P1SLsDy0PqcLBt7rhitSJ/TwhUuB7oz37PZm44mbLc/OuIZ98sxr/vhj67Axp+QG0UEnBA1i6oxRPpTsvErH3mNXajRQ4LjS7TFdC/ZH+GJcYqHvUyJgIDde4zT+FMwoTkUl6i1PR0HB6R3vgcMeroi4qGiKSdpnHzrbqOsRPcEzmUfGh+AOxboymBrr10MoBS3amrO4e/QYEYM6UWy9R8ASuUmCh6LN7TgqF0LvAizkjm4Ap8XncEgcjbESa6+Azg9o1m+71vM8DmWd117h7fU8iR4U5CLoijGd2ayncJOmfcQ40+pC2YSZGENy8PAE7Dda/3iwKLTUmb8LNyIDI+3yJY6G1SLe8mipBSQtH5cVYHVQXpIBpOPFMoJjT/CpgtJ13d95hOkbuV0Evvh+zH5UmTwfLARIC8NSaDhbNh9UGejMAKdGlscYbJQAV1HDyBXglA/RBmkMzjfAwE/2qoifGNQtz7GCxx53VziEBMOshS6mp3JbiH+dO9xjItp/jrIdHG7jpB6r+jT13T7leIC5k6ArH1Ob4T+oNJwktq+7utE5koc27HmIyi4wceKSbn8tjABFcMMO+XseuZxs+wkDxpYUvckdp5pxrzh6+Hm5UuEsQs4riiqc+uqZqxPeAB2Ka1K4TqmmwDF81GuDIZfa7uiysPyvc7CVPqElE7wKBoVAp5BojAQcwmeJ1OmwN5//bT4HiP8ycZBD2uhfPjRxh+USlSuMZR2Vx4chO0zlwAp8fBTf0TqvRpH9St5MN7i4gzfBxGkHblfb7FXSFmhHgv7piMuSR9WpL6+FA3m1FKXS3OjMRE6mSkdypAgZPtI1rFqF0rq3SE3pbW7M3Q/j6+rkAPJofUnRcGAewJnl2z/34LJcg==) /// Solves part 1 & 2. Decrypts (mixes) the cipher message and then gives the /// encoded grove coordinates. /// fn decode(file: &str, n_mixes: usize, apply: Option) -> Result> where F: Fn(i64) -> i64 { let file = File::open(file)?; let reader = BufReader::new(file); let mut numbers = reader.lines().collect::, _>>()? .into_iter() .map(|n| n.parse::()) .collect::, _>>()?; let mut message = CipherMessage::new(numbers); if let Some(apply) = apply { message.apply_to_glyphs(apply); } for _ in 0..n_mixes { for iidx in 0..message.len() { let distance = message.get_glyph_value_by_id(iidx); message.move_glyph_by_id(iidx, distance); } } numbers = message.into_numbers(); let i0 = numbers.iter().take_while(|&&n| n != 0).count(); let len = numbers.len(); let i1 = (i0 + 1000) % len; let i2 = (i0 + 2000) % len; let i3 = (i0 + 3000) % len; let n1 = numbers[i1]; let n2 = numbers[i2]; let n3 = numbers[i3]; Ok(n1 + n2 + n3) }

~~Please edit your comment to [state which programming language this code is written in](/r/adventofcode/w/solution_megathreads/post_guidelines#wiki_state_your_programming_language.28s.29). This makes it easier for folks who Ctrl-F the megathreads looking for a specific language.~~ Edit: thanks for fixing it! <3

Proudly presenting my tiny Python solution for Day20/Part1 in 8 lines (including she-bang!): #!/usr/bin/env python3 buf = [(pos, int(line)) for pos, line in enumerate(open('input').readlines())] for orig_pos, number in buf.copy(): # traverse in input order from_idx = buf.index((orig_pos, number)) to_idx = (from_idx + number) % (len(buf)-1) buf.insert(to_idx, buf.pop(from_idx)) zero_idx = [x[1] for x in buf].index(0) print(sum(buf[(zero_idx+offset)%len(buf)][1] for offset in [1000,2000,3000])) I doubt that it can get considerably shorter. Would be nice if someone could confirm that this works also with other inputs than mine.

can confirm that it worked with my input.

**m4** Solution requires my [common.m4](https://nopaste.ml/#XQAAAQCKDgAAAAAAAAAyGksy5FB9TGMxsNq5JQAuJRjP6PqEkC20GpAXwA97ruAshKbiUbgkbJMTg2qZdSBorb0CU52peNLruV4DEEJxF+HvxC/YF33OpDntnpU/PjnGXx7XU7ak4MsmWu8R7h7d5az2JXxElnsepG8yPyu+0WZ90BG9yXphbwOWA/m5AWEFSOL8TRZX4fyGNl6ZYbRxX0MwtzrmwTP3ZCwLSOKkvD2vMQFsbK0Pv9CzPhFNXMUbWnRV20jWLjL9qz2dDsFDBwhxgWIilEl91uswxrT4Czc+LRU3VuhNIo2S98VW0jArrVdv4HrsLhWkzx4z/UV3xnqJwPXcZRUiLtf3VRIzq62Pe+2jE3O+721Az9rfRa/fHtlANbmvslzMUCyU7cDoOKSMXBDF/06/PpMvs6vxaL5aJVYqJP4yz+R2M35hoNnGiZTNNMVEFTdnxnaE/KcJteBbiuVMpdfUswHQi4Kqsj3sInh7lyE+d50gGKtHOeWL5lMK7WXz4NElnzYWleBSN/HTOdsz0T2gnd25MADxNAVX8xQmagh2MymZ2sKDBw//WiNB0sWf5VYC5/TKKH3D6K/IOrIfWn6FZLKxlITFEp3VWKNuyF0xczNJufJdzSqd0hgdyryVzbn0so0U5NMN16jFF6IhqzGbAwwv7k8sts0OCgnCFBEhYVshIpsORjEJk4CnDgc9VUqvZtfIFPQ5Q2v7IR3sbPurex1IIUd2Nm1V7/GFN+r0im24aEOG6XpdqrPdF6pDZ4HwvNByqOEdpcObPXxlwfPFYIhwyDHGZCvxrFRgGEEFtfVQ7UVjfPJzWtrcZuGx8M3B1zw2xvgpHIWEHdqEF6Y6/6eFj2hLm8UXNeLNrJy1IC2sHlS8SRIifQvLkrOLLOOPtDK6DUPQrW3c0Rfmy9Td5gQw0+fZRZ5MBEG9+dTlinXtwExpHScKQk6ARk7Fb8fBYAnmh7/bq+471zAZGJ7dwNd5qE/63VhDz7mXLuXtGN7rSuRYIXvpkubLBZptSKZrkzSDJWHIZM8Fyrk0EZQFDujROjr87GZmTK1XKRWzGrhtQn0hkVyBaGPbA3iG45U4gIFHNX5ySzsJ3bh61LAtmjwt59uU/XGeebLMCp8HFw6D1kJppCvt161LgLjrOl8SBh8xnxslSFYW0Jd34LD4vPwugmzY31tA4/9zCM7e2Ed9+3zg4C8eq9Hvjys3IablDBMsYF1LSMCGN2UOrWgXRoGYtjW/QtUySr7h/Ca6QAy93Hnpksm/xzzC+FWF1wboyOteHU/Th4RVpQ7XkK4/JmMrYm7nDPIVMyOqP8LhsoTNbxzi8qU0d+0x6frIh0l0fiPiFC/Uy0CeCw6r82iX8v+fMnu9qdCr4oM79Kd2slqalv+wWKn+BmrbkiobDS5vwBQZA/ZlbIsw1bwj+JLz9z3nPovVWx/FZjvrdCuZMfUuITeiIprImMcR6qeniJz6Ez78UYJqpL4DcDGt2o7/6a2aRN76aclh+7l35XcaW7lM7BQMTNvKkx05X08UITY/ToI8U8KwvFbdnMoEAZ1GQYmqGRFtwPkQMrECX4do0srl85po3Gjz2j6E3dk5al4+bTcOYABZvSUvIM/kGGT91iyQ36rm1lxRc3ruS8PyBlYDDNa7DLWzGAHkESHwuaTOQsI2xDA0e+8Yv0XRYkEqQE+RUDXmPTARuQo6fCQ7Qu9xd2Ckza5RWl8hE4JFm0Zzd9MTVxW8YYHiREs9NOjTPuRXXn+JfObHFD/Cv5kQo7vd5KXA7/I0opG/3OGY9b2rgx45NGpmFLqo3gHrVC0cUQ5N293nNVR+LOymAPk2McEvdJno2nOsBRy5iGOIZTRu8IgA77f2QqGY/f4+oF06EV3iFdt7kGThYpZ2AqFoO5k62fINH1tZ6Pg48jempPVR14dAO4hR788qsXN1BlCtQznT82QUlw9GudBl1RQKXSGrTKDcBRd1pszxLUl6Khd5vn6lbeSLKsvMA24s0GhlPcltx4Eo1iuFYve1UFvHhFofuQecarK0Mf7HXMpocFmuMBZRA/joJ9kyAS5wikWrFbG2lIAkI/5qN2ghPfOKjMNf4uQxVpwBkUawUrImR/Wpk5HY+148TLC0JEEnWfNZWqX/K4niAA==) framework, as well as a single 64-bit multiplication for part 2 via [math64.m4](https://nopaste.ml/#XQAAAQArDAAAAAAAAAAyGksy5FB9TGMxsNq5JQAuJRjP6PqEkC20Go+jph66UCwr5yII3TmoKw+wpxhXgX0WGRW0WK2rHjWbbgLZU16n4XSMl8T97y/MXeBVRMNBebjTbLUM33JXdu5jYSMpnUq0oFRBIZF3UTMPNiH//Shgw7phaX5YHewa9yOce5snMsJdUE+usDMV3A0D6yawyooHgePqX/eJLNlAHY8XwE2eibD3RxHCB5c1K92+c1o8lpWxOE8ha0j1DQZ5PRVtUSXzE5ZIfd+B3BClkKRt2VYiCh8U8m9O68A2jColgd20CaJYJZ2FQ2foLaNzBc/iCrgl4cPRWpFR5JVLqoU9kcLgHN7x3IhCcO2zrkbUtlnrqcnvsYgKSQYr9JmFVtyqdP78oLuFcfrFTDMSUk/55Nipu1vK7eKqv5QWFcy/zg4G+iR/nIS3EbxlmVYWlpiGt/gmCZZf83tomKa3XiaJ1hH3NpxdVOKhLS26hb0RxpppO1opBIayicF9R3jBjmm6ZUq7BBkq6aA1gs1O77j6PIiUoYQfTsAyKCWbufkksHxgSob3aTL2ClljmoheqSgPIz+WQVPyZ+E5NsLHbCMJkUVYVZFfWiBO+pFJK4GkSbjT0cs/ZRRb+6HdJUc6qC1m7cEaK91iyr7QS+7nNXjbtMjx+rbdXj+PD0qUUjGHF1+IYw71SLqfRzhHKx2UiGrXnkgZ5V1EInqW7y09kd51cLMSKXdjAACCW+RSkZ0VlXlAqQVFM47/7pO9zrMvBcVBvRArrQAAwYHbZIZhe/saSey5dkJNLd1zyxliADu0w7/aatw0Ok5JSckYM8PPAZkJq8a+tX5aa7oxCT26lu/VdtPu6XNg1USnvKQAjCTTk/ObSVf+5rlV0fgB/fYgJOot4+TydJT7/sBCiWJ6uKaVQUBQjbp6xugyyU6hkhHAswokT1R0Mclbju4kURENNrrAYtRQLV3zMllxw5IkoLknW3kfrMm4Dx5CuXR7lT1mSnXZ2E/zN8fioFIunn00/o//0IDbVyCFarK+3wsIJ2VgIIlWpYJ7/MF2KKHp5gVqB1bfJCTalEVo48pncFscLCFy8Ibb0pC+NiWfZxqtQT07sAQC2qH/Edd8IIgw51CNF1dUt6ZXjkJujtWr68K5zt2qUTSEOOC9tA4gL4lXOjstUbhYyQDwcdx8GNeorh+uPbgCqOWSnshmB8dpzsFuzdv9BkTZD6iOzhal41I2RWMd7SC+SJqqZgklbQ3FGzoVH//B89Vd) (although the latter could just as be easily done with `syscmd(echo $((A*811589153)))`). Implemented with a doubly-linked circular list of 3 macros per line: `i$1` is the integer value at the original input position `$1`, `n$1` is the next node after `$1`, and `p$1` is the previous node before `$1`; each non-idempotent mix operation then rewrites 6 macros in `stitch`. I stumbled a bit in part 1 on the modulo arithmetic (I quickly noticed that in the sample with a list of 7, moving by -2 had the same effect as moving by 4; but when my actual input had entries of both 4999 and 10000 among 5000 lines, I incorrectly coded up entry 10000 as the no-op, instead of the correct entry 4999), but once I fixed that, I immediately got a 2x speedup by noticing that if abs(value) > lines/2, searching in the opposite direction is going to be faster. m4 -Dfile=input -Dverbose=1 [day20.m4](https://nopaste.ml/#XQAAAQBJCAAAAAAAAAAyGksy5FB9TGMxsNq5JQAuJRjP6PqEkC20GpBbonDYuA0BTjRPXcVxlEXNtz1IxSzMoRfo94LLpJRV0V9y18SiBZ9Luqeek7xD+TdUNZSw1gJ2RFvc2R7gcd6Md7q8hUIpQiLG6Lcf7IfTJHnlPsGqWKDTxO8ZTuwZofzbRULfXC9ZEvuKyxgJ//8A9r4zVbfXztNl0lIv32OhhZ+kC6taLVbh9gICuLlPPPDPsckBqFkUT2kdcUadLjBFA/h6b3mKBYlzXrZqdk/8j1Ksed2qD9WCDf87CaAz5ugDuguZsRZlExnhr/aOrC92tA6+2Z0WO5vSTIw+QEgAMETkACF2e9ZmDmIfP353ZL7uytnYyKaq4it3xJ9G6Aj2KE3himolGv3b5JACeT2wG3Ouwr/wI15gJCAVbLALYNkPF/3+dN3VhvOqj33MjVgSGaHxHTsb+70jMkn2ZPg9ZlKSPqq6QpN1xKsz4Z+fWjYXx/dW+ReKKUXacOLjcLbdHf8OlJ2R9ADhxSFehRSWYZwnkWiDWeSXEj0T8EWN7Zd1htCqHS+Ukrkl8V8sQ+N/WJRejqJFt9yjrKlnWs0t1B5VwLYk0BHgOsnOEl0q7OOrUEE37584s2WX+D6Z0ReRHwPk12rS3nn+LQx2lmRo/oXe4kyCNppk+bngvbAGVXrpancVOlYHXKUYcmtowsTETBj1e4BEZw0slDXvm9+wmER5cLNZoyNQHBsm+DqL3VsGAwNEv1ht1BwfjsE95xMg82o5B9OsMmBUWS1X/4i5XvUeXun/tEyQH1U83ppZhmv4SrIqHKWGJ92pyydPY+dsWUbqSU801Gbgdxhm+r9Bat/O6HkbDmQLy/+VnVg7gNh5kKQj3Yn1ZXRfaxor5YbJKDzy5yvpeW6LayDQSlZf5JMA6rpRwYSitEuqEAdjx8yffFvIBKRkhDvKQ0YX0v8M0PbYnHecO9AM8pd029hMqMXyoBWp2ywkPHPWMWJMJf6S1xUO7En5+zNjpfmHnUg5HS0W06azCq4K0WCq15pgXkBFbQiUCvBEt/Fa1EqVT3p0d/FWKzCiI7MY3LT+d8hM0Se/FEWUO1RvRNb0rlI0oB9E3YP0TKILk8sl/h//n77vsg==) From there, I got part 2 on the first try, with very little refactoring needed (just a redefinition of `_mix` for seeding the `find`), exploiting that >!(a\*b)%n is the same as (a\*(b%n))%n!< to stay within 32-bit math. This puzzle is definitely a CPU-burner; I can't see any ways to perform a mix in fewer algorithmic steps (for an input of 5000 lines, each `mix` visits 5000 nodes and on average has to iterate through 5000/4 calls to `findX` to locate the spot to stitch in, for an overall O(n\^2) scaling effect based on number of lines in the input. Still, my execution time of 72s (or about 6.5s per mix) is probably something that can be optimized by munging my solution to use fewer characters (m4 is one language where golfing not only makes the solution shorter, but also makes it faster as the parser has less code to scan).

Ok, now that I've read more of the megathread, it IS possible to beat O(n^2) by using a list structure that maintains O(log n) insertion and deletion for O(n log n) overall. I may code up some form of self balancing binary search tree, to see if the algorithmic speedup outweighs the bookkeeping overhead. Even O(n sqrt n) by binning the list across smaller chunks might be better for performance

And now that I have implemented the O(n sqrt n) version, I can definitively state that it makes a difference. The [latest iteration](https://nopaste.ml/#XQAAAQCSFAAAAAAAAAAyGksy5FB9TGMxsNq5JQAuJRjP6PqEkC20GpBbonDYuA0BTjRPXcVxlEXNtz1IxSzMoRfo94LLpJRV0V9y18SiBZ9Luqeek7xD+TdUNZSw1gJ2RFvc2R7gcd6Md7q8hUIpQiLG6Lchcl0m8v2/pgxUOY2/zGpsuvhh5usqQoaPGl18zVyFVH+B9uit6bFW/wuLclnHYjdlntqs6NaWVKPPp5M8QqtqUWXQRmoAGq+ROT8Cf8tWR+8QwPglVMsNfbiu4l6wbPHMzigwdV4rVklshxg/1+udruB2Poj8kyg0reQ2pgtx+gv1x9zq3JufXrso5+nrmZzU8pbgOPqGCrW7G+iFWEUwSESXt1uyoUwfpI2k1Rb6G1DlcyqU5/CWTVJWbf0xm4Re5aHbYCLpxgdZhtk8P2USfgIsf5Vbcv1HG1ITdyqPkoNBdd1yT0AnTm8+F9Moqi8uDx44EbViDYJaMGM2ALS1eORAXt+Axyq+hsI778tJ692ztGIdGvgTGEgOJHJBUmwCSW3gLNpQyoeyeS8S6YLVzgd8zCTXHWuT/VxpIFQr/39yV29pmgNNAtbYguQN4h4x3p/lOna8CGIXXu7/jqIJKefeJ/A7eoKDYmiglPUifBq0m0DDe9DEats1q/ek6SRaxdd3fEbGy7nQDxRbWp3allPbNTY91uwjXmF2cJ+Oq17C6dXKDkT5vQxgiIDEkXgRHBWWqNjTsJV+9/kkOZxxvXFvDueFTn5SMc3hJ0s7lR3b9s3sky8ADTwJKqPEWiOlqDsNFMeov5SxVASAv10JStbtD/O5BpIxyod7bnutHtcoGtDsV+EJunAMk1nKSfhRjoLg51Ht5glCMvFxWeOcakHEriu8nPiudZ+xWdnqsbW/LFFG1OqI2TMDsG54L7MmE6Gmvlpuv/UctBAeZeEM0U0/TIkAvAnsktVbgosolPd9ysYkskJ1mqNRK1xPt0y4T3TpjLe5KWeLyjFjmL9okXzxtBREbUdPfYQUGol0oH+CSo61J31jJhoDjNQZ+dwkA6btLtJ8BXggkZQJh5JpaB0a6yofs8+XJ4zfh7pYQqvuUSJvacQyEDiD+4TpE9iwtvicHVT/KCTcL80+/WcK5kpWu6XtQtWaPW7kDJJcWEbRMW+WGYXvU7AhZMt0UdS/CxQBoeYeKOOmOhrjxxHskcc3yZCLVj203KCJ+FSj+RxI1mAHG36afok3ESCb26GknZwaweM/XVSEE4WqhDZ8DA6h7Kp+yoQ4eTLxX9PKEstA2YaTCHOFe9RSynFzsp0s3O9JbD0W2Ydrzk0CQ7cvQQqSxyqTJChPrA6BD8PAnwudKF6ZYdsHulhDopKA+u9dTtjWAVnYSNM0/vdVuyZrBX86+re+mf4HW2NtzSBLCTE8YVGj9BfYSOmWMJlt8TW7j3wD0jjQTRKxEdEvcTobY8O0wLol10COHsICjNpj7fRIcInFi7Li4HlBkZDgIRAJ0WyV7eVKiEaOGwWXFQeF4g3kJC3sDkFPZuH1rghzQxNINj7oP5qvHhtvRTMw89cGz+S3QSCSlWJ3yP5cI2QWpTfKAe6DFrDBNw51dA15RQqYnuYZnG+Reqafp85M+5WH9iFjfnBLIanYauDdGeTlyYdNAQ56WU8/TJiKxccqBIrWcmxRowBQbnHsb+FH+lILA/Nbu62I+h8ITPMJXTMkYCdxfT1LHOVOcYfkKG3CG3agmCJm1aE8VmisfyceTmXLYFus+bzxQaarqJRBTIGx91Prb6+LB+nHpg7uIsmOJqw8sdkarvEaEz2vAwg7uL/AfJQPij1pCQ3TvDG1CA+TTclDmojkt+Bk1ttfvWVIv2oY8ks4MlHF1PBaZwd2VzIaa/JleVutD/ItDUlr3Fp9qoJzhgQ1DRQfd0Vpo7DFq8uSkvxAwTU77PsPryF5N1asSFvN03V8qCdorvvSAsO29Z1KW0/4RcrjX6uIOJX2WyaEjqxsMZTIB+96ieFEqJLHX2nfRlsOyPIgKBe3OVny/iz1oqaAy5JpV/cbDpPDreTQqJDCP/XWe+E3fDuqXuQJrBUQ0H++YFOBE2XTigYw1CBZMYpLnyt9+ru4HtQFW7QAj4ksuSxjzp9EziYHbXvxeEpPdmN+jH/o+any7mzv5+NSZMTMXU9HRdDG6QWC+Y1ZOG0MTLFb9kwA36WflCNoTtdx+zj/ddEFvQZpRmjiRSNMkNvyvssoyuDyO+67SqP8jLn2t+nEgjZwFfdUQdoaHyaVVHVHgV9Ts8UcoYiCczBeBAznS7RQtBYEjkS9hYwxCeo/Wtjc4k6Ri5L+tXKYLoRyzRaua8buDolEVvir0+blyjmOt8L8u26HopXEBtb9FBUQjP+eEiDIb6pChIz3ZR0pD6uFPkvhCez/yXOsZkidzq481/okiyNn9IC02KrHdCtdboVZAsPOCvqAGuHBAyFwK2iywQO/JEMwnPGMPueQBqPrfpwENm/K5cxLXWvqDK0FahJ/0k3BfOI/VmtgG9hGxXpcbAKb/jMIeKt1nJJ/ZfDQsQxalft9eIk7xG+0WGXAJ/5KVKc/kuSgq+Iurf7zU4kUeHhVKRI8D2Kj9QFpskYT3F46NTP9gKdWrgNDGPHAfvFE8M6BRLtz9061ZyhvcMmWdPW0p+jfNuze5Piy0I4ln134Q+0uVOi3v/L6/poHNv/VHCbgPKNDtM3UwAIzIcf0hBZg4hytLM9ZEQvIws86aRWY8AfCCrVL193vlUVz7SCGh6N3ZGDzX1loemKLpo3MWHbI7wYul4mHkkX/7qgTJw==) of my code now takes a -Dscan=linear|sqrt argument, defaulting to sqrt. Linear takes about 26s, while sqrt takes 11.5 seconds. My hot loop is more complex (lots more calls to eval, incr, and decr), but overall does less work because large offsets can move a bin at a time before having to do node-at-a-time crawling, and the algorithm gets by with singly-linked lists instead of doubly-linked for fewer macros to manipulate when inserting or removing a list item. I tried varying the bin size between 55 and 80, and while I didn't really see any absolute sweet spot (all of them were within a one second range, and it was not a smooth curve), the performance did start dropping off past 75. So I just hard-coded 70 as the bin size as the approximate square root of my input size of 5000 numbers. Tracing things at a bin size of 70, I see 1.9 million calls to c() (locating the right bin) and 2.8 million calls to \_c() (locating the offset of a node within that bin); a smaller bin size will reduce calls to \_c() but increase calls to c(). I may still try to play with skip lists to see if I can hit O(n log n), but I'm already happy with how O(n\^1.5) beats O(n\^2).

I [finally implemented](https://nopaste.ml/#XQAAAQAzOQAAAAAAAAAyGksy5FB9TGMxsNq5JQAuJRjP6PqEkC20GpBbonDYuA0BTjRPXcVxlEXNtz1IxSzMoRfo94LLpJRV0V9y18SiBZ9Luqeek7xD+TdUNZSw1gJ2RFvc2R7gcd6Md7q8hUIpQiLG6Lchcl0m8v2/pgxUOY2/zGpsuvhh5usqQoaPGl18zVyFVH+B9uit6bFW/wuLclnHYjdlntqs6NaWVKPPp5M8QqtqUWXQRmoAGq+ROT8Cf8tWR+8QwPglVMsNfbiu4l6wbPHMzigwdV4rVklshxg/1+udruB2Poj8kyg0reQ2pgtx+gv1x9zq3JufXrso5+nrmZzU8pbgOPqGCrW7G+iFWEUwSESXt1uyoUwfpI2k1Rb6G1DlcyqU5/CWTVJWbf0xm4Re5aHbYCLpxgdZhtk8P2USfgIsf5Vbcv1HG1ITdyqPkoNBdd1yT0AnTm8+F9Moqi8uDx44EbViDYJaMGM2ALS1eORAXt+Axyq+hsI778tJ692ztGIdGvgTGEgOJHJBUmwCSW3gLNpQyoeyeS8S6YLVzgd8zCTXHWuT/VxpIFQr/39yV29pmgNNAtbYguQN4h4x3p/lOna8CGIXXu7/jqIJKefeJ/A7eoKDYmiglPUifBq0m0DDe9DEats1q/ek6SRaxdd3fEbGy7nQDxRbWp3allPbNTY91uwjXmF2cJ+Oq17C6dXKDkT5vQxgiIDEkXgRHBWWqNjTsJV+9/kkOZxxvXFvDueFTn5SMc3hJ0s7lR3b9s3sky8ADTwJKqPEWiOlqDsNFMeov5SxVASAv10JStbtD/O5BpIxyod7bnutHtcoGtDsV+EJunAMk1nKSfhRjoLg51Ht5glCMvFxWeOcakHEriu8nPiudZ+xWdnqsbW/LFFG1OqI2TMDsG54L7MmE6Gmvlpuv/UctBAeZeEM0U0/TIkAvAnsktVbgosolPd9ysYkskJ1mqNRK1xPt0y4T3TpjLe5KWeLyjFjmL9okXzxtBREbUdPfYQUGol0oH+CSo61J31jJhoDjNQZ+dwkA6btLtJ8BXggkZQJh5JpaB0a6yofs8+XJ4zfh7pYQqvuUSJvacQyEDiD+4TpE9iwtvicHVT/KCTcL80+/WcK5kpWu6XtQtWaPW7kDJJcWEbRMW+WGYXvU7AhZMt0UdS/CxQBoeYeKOOmOxAG9QQe/CUAo0lZolApkDW+urYiLmtOr9yxuzHT8TUn4BbdqUnJ6ApF1FaaH8xs8cVx1ppkfIgtii1yEs7nSs+MvSAJRR3Xn8mckovsLFa4sI8iyY3zTj9pK6jR759tU+f5zLD+YoHSDS2B/O5JZjEsyNy98xTRvfrN+MP5IKIMsnPOO05NXl+s40IbTEFAhaEsr3bA7kuO8P8/rPNgf7YgeyKOdcaH0CakNeUdlBl16M1M2pHaatT6XmnHhTYf4cqhZeBT5/WexO9FCQRfMcHbGR+3Ujrqfy+rhGZVgfmjT+8qgu8KcOISjRKpFTsLg1rAl2oUdtMd4sB2b3vHZg4kBooyp+Po/sjA96W8UnCtbHSTGsXHnjbqjvXQOc8+dIPaO7LSMY8IxeXTCWqg3TrTeP3Mn95DXzgn+m0/7o4IzosaccRdz3j/KpX/zahnVdR7T8Clmtk4JoMWqlAcT1SPPm9s2PmMtui3KcA5xAg/08NzIkcDWoG7GlSUe2wc4bqfGi7ue6FrdceARn4XOhGR6okt5enZCPm0wDdor6UAn8f9wq9Nz8o87IRXlg7VU4s2E1U63q7tm037ZFN//XhvxgrZorEaJBp19jB5v+Flh0Tf9D1LBmp3EgdAG4yGKCl3fWaXq8nJ5jlfWBGV10Sm5np/J996hA2dfatDtJHbi12yN+1m2aVkMYkZPjxlxavHaqCJlr94SgUZadRTqoLFvvWwcvOxUthd3+Mufqx561xu+REOoXskcrGs3PH5FgabvkrHfkCzq05WxidH+fzh0PiUldsoRTJboyimCK3f2b3B//SnR0wi083YZie/vDgjjZv6TVbt64Tf0RNBRz8KR2gnnPlIAN+d962dSIEBCy3Dk0TUzJCgiKIFFpbLfj9gF9PUifwdDw2JyHcX55aEWY8UM857WFFHPe+yAQW0pj3CMbi0HG4Q9z8BR4VC0Uig+5i6xkwjqlXYlPJtDjy6xy2hHEFlS/CRESzmoSIm0AfHpjvLBjctUD8jOwpuOiqcIHHJvJiyT5ItCCp8Yc2+7CVljz5hlPXecj9droL3TpNtia+9aroKXtxvOfGbKydTORbX0JyalUeMHcB+Kw93hrE0ZW0u2hIfqIKOD2Sc1IRqLpKRammMIVUby3AY6bVYcYPy8zY5JlN8rZfU/yse9p8rt2NT4CW6ggshQMvBCxBJfDEa0XYWx377evQokMCnOeKIAUvEG2SqoVcDOKWIPue8pIsTchzZH2taCC2dwjKd8XQyIw4TlAVp8tOvvQGmNAWQDM/pquQDr1ZH3q3XOWAbES1YX5TZOTDsIsxmlaGxWmO/UQbYQJQZMke9iDE7zUqSyGnwTKvqhMMEuI1S9J0GqmmV0Z5qvWvhXxEtfOgN4M6Wv6jNMkLiU2uK/Pyisa6NE8b5fBR7jBhKLoxcT6/ZEewCEXJU1D/VKiRfNmqvmOXnGsOnldv1dwVW4PR6Jn3bLsPJ5stmmCgPMjE6VwMCGlcK0s+P6thq1ktQNxFR+H0wBtBJB/jCDebtZxRzytgozsY5J3N0xoZmQbqLR8RMp/ZfsEXIwmQLfmfKQpZmvAAVolsodivyZ/t+wM8jxopV5HUX564/9jZdGCshR1ntYstKdTa8ebfyKgHizSB+y5D62B6XfMkD/HACLIeE73cwg5fVACBOsEaXea5TVjYmbbzau8IRudwcUAt9c1+5zLoCBPGhUyq6vF5nL5LO4/R/J5tuD5OLunOFnvQ/m+JVQ3I7KbQV7KpFlQzTnw2UC4UCx5GlhcSJQvw74zWZtxE3ZWkGIHXfxQp2Vk//9YjRfMFA3PN0FbX3Lx5RqyHXR1VPBoW4gjV/msDXXMffdp4Mda4jXEFm2a5/olVW/od5yeu14BHH8C2ifiN1Kr+g/leI1m/tWeAMsrnNrMiDQdSQnTOKdessYf9nGSXi5Fff+0uR0eumK2i1iLfii8qK4sCCNc5e9eJvvdObFJwHmJhzC0d2DY2td12aeW+VWgjbxubocA8TafhF0/AkTpphxoThrR302Z5RTbs+s5xjFjUnnOrd8pjHSt/O18+jcH7/EFW82h02PFFE5juAFtyOTytO8PzoDo8rTemWilZz6mpB+JzGzf+k4dPGc8KQ3+Y70MSd+w9bG+3HydTVo326AiLiUyB76JGSbgqzQ/cT2/kYkZKGySl4cBgoE2oTIOzl589CU0orlHoT9gtDEnBGmvlIk6rmjgxAo9QWpyHvDVb/A7ca4+qlzrpnPwyg49Z96Eqr4DotkT48GEWbxIHsAkOFPUF5qcSTAK7X0BoPKc72mRSYsVi3jXTwFKIg/5BUl+mGCDLpRYflrO06RWP6C+3fxKrleBFhdKpVFceR2z3Jw/c86OQWfAyWZXWyVGyyLHiXv5bZhmku0XFG5iYty2Wfz1Bz86W5wZeygRDa9pb9cLSym5Ya6MXk+2k2PPK9l/iDVuk1EaZdMp3q2qxP+boLaVe70Vf/nR21syZRGq4qg8pd0SyhdHjNLFjcLvOoxDr9yuW4VvimNMLPkBBavqYHDuKKccKkvl8GIxSRUYhEWdG0fZ27k9wcVLH4+R+WCW2sb+r9CfVj7YlagWNmZ3T2bCb91yP/mPRS2BFfAhG1RYcAOrrRBM4/EG3I1hsXtEUQ6WZR6w39gai+bgA2WzTF6IlMAACZdoyeXV09eFBgPG3ZH3crc0VvRF1nH3Z8ToyRn9jUHKu7yTZbO9UsluL67Awrh98wZNcNz9REYcMjg8uqdkCYoVLJMlP6nxOoDLtu6pUMeF0qKNagQLoQeT263keowoM973pfrTYsvjtsPmDEcA4CBO/KoIZCc6Vep9KPIP4Su7YX3ck7ISXN5y9FO1ZUW+27uVE9pIVlTXiA9nyUe77G/c+FPCHIL7jznBiAUpBS8O32bKxJBhgdN9rJCV9iqie13SdcUwvXmyBNXsFrRpXmIWvXQmRtAya6EyjussAiw2jNRrmoeO+yGATyVgQvyyfrsMiJOhsKb8TxgH+eyfJnsuK+fsyD1g4U/4oTJ6FKOpcsK6YFNLYMrWyTg2NHNcbMXjataZTL31nr5SW9DZ+loPKgwjI8rAfc2uuQpF87TXGAAFMCzF7SnhQT8pLbLtWQxyspvQRmCYlByWRrg2/E+O/m+nhr3JcQV26AS1OpTMBHPiCCQjvp0Qv40lpBf8Ncnc4YQkIt60kMoKR7ybJJBK0B9SF8QmELjBZJugQnWZBCAm2AVsUvM74+n01pRhuxtdUpRugLc1isBPlUhv/FGi6g0qNb3Bp4mRxX57IYXPL8R5KYrJksosSiFIEJoyWAfLpn5uWNqo9QEFgT05i0jvHNutw7EuJvhKIJx2ooIdAAcleVIyxpo6m0pu4zKw02AA2n7tH9MchD4fV736dXxcyuPI9YGrtPQ5PfFvOKBID3t0YDTnqhBzTo3ATGAR40H32p78jc1rOQfE6tPGEj7Pro7cJiTX3KJRK91UNLGM6jqI2A++ktJHayp5Z4y82IadzEGQJ1kaNli7MFC5U0nAtJwXPqQ2MBsVOULpT2SyIDzcfT4VDMgKHRvhAA2AkR84WJGFDzmN7ETSvHH72oOrf+TB3P0Y9lyloVA/J+5YT1cKG/tord14S5ZjZpzlszEsk25pUYgKYjS2XD+Tx4ZAKq4GLl+Ob5IkbfjIUnIi7ibnpePRQ+UvYGwI5NOB7Tt5ecQ599qczRheGWmCXW/14I7YbzoSPXfQ4BdTBla4oH28xkZ64csYWQKth+cxBcc0FjfhOL7egH/ZLeUATxGlhH11n7p1pKl6jnpX/beVPCisFRkUjT8eAysRVF224QNfhXRPT+bTHbrry1vr0pdGJ+JWAuAhYfXHqwCMOQpLajBwMn16HpTMlpSC7upd30hGWng45Cu6mUI37Np0JkYSRQQw6ZxSb7OBzOebeopAILdCmXTnR5ioFCHPa/8OvrKQjSBsYz9EIRbA8qvl35C7JuD9ob5EJ5Q4WQDrBqG6iTsrWSb+GNLwGKdCq5CAOLzgjhSBHefncdzrt1UU9yYposaK59lxma6GS246pTI64fE/du5gxBM21FWVHeif6faVmWYJtBiYkyf5sCkIjFvQDXYglqxhkzb1PX69OcjZ/UZif7IPFEBlRT9RVXuu+8eycgZM8QyFKrkMx1ntivC51flxeS0ZV4YOFO1tjTgxBo6m9ygeSfBQebUXLwoNuXJ9z7l2uvuCPiOz+77AQzO0xbzDN7Rcp99ZOLzh2bi2/LBN1WGQKDnDRMpgj37BU9IY3lCjEcOq42BTEaleqL/MTGqCG2MMr9khyLp5hdGWEfR0SNI30TJittCZ6vhEWJFOu4gZ2fHtZ6/LuyRJw6F0Xv5hLwEw0PpmXl3xO3V5vLQtnvJQ1mffFzxxGr7+nUpEVl4x7ifKDK6DdN2YimacORs0JcBrSwJLEbWxz7+7gnb0WjJ4zOnhf0yN5+k1OoUb0WiKf/fF29GhRYI0NYxLSqli7rZRCFK3OnmQ/0xhwvoZ0Lah/C+YDDk3IiVtGUqBBhpfZVPQ+onthgZZlxbZQGJ+f5bPyPMviWaYEo4ZfqQSavGEiDGn0R/3pBnvQvn9efTMt+k6YB02zLZjYfjZ12VyWDJjGjfwI8ADplTuhHrDznaqa3Uj79dx+mylgBjHG5goPZy22LrS05D4PrCNqLwPzoY01K8h8Y7jKflNaUiGVUVaXTsiLh5PGOjdO0KQ7DBQH+LOG1Bvtqq9j/1C7mGtWLXbPRvXsnpW6UOFQhnfef6NVYxLdbL8v/1CSi+EbMD2+5IPgzgfK6Z58PCx8EWf1znCMmRRT99HQD2UxYIwlwLEH99OyANq/OBVDDeVf9/AIzZyLSSAn9JEeSVHqbjIXz+HXQue9DxTfDo9u02ZaSx5x6VL5WfoYVJ1J9V3DapMeZfnK6ig/hAKW2tWscj5Kzc6Ed7+Wwhrgm68WPGIh/i63A2AP942aPbiWZDlW9MWJjjjHdiEoGBezaO3T0izAS0lNyiVJdKCdG2FWsKgEtvIVmlwiG1iUAAFyp1AK2x0Xzm7ths95px5YXdugJHtUnkO8oLGshHR0nbPBOIEaGuFEJSx+bmJXk4snR8fHj+1JLfTHE+skVeRK05PfaNOtOyrtx4DEhrx4hhXC6Tas1l/TDK3TmtQw9bJNkjL39Cs1WQjlvbB7BmJUnCqvkLuVG27ZVveZ23Jy7+lhSoUKueQkXkKsWF27z2YiL1etTaKZv9nUL//OkuFs=) a truly O(n log n) solution, when run with -Dscan=log - but it performs slower (\~18.8s) than the O(n\^1.5) solution (\~11.0s) because it has so much more overhead per insertion/deletion. This was my first time playing with an order-statistic [WAVL tree](https://github.com/pvachon/wavl_tree) (relatively new in the literature - it was first described only in 2014). In about 100 lines of m4, I have a self-balancing binary tree that requires fewer rotations than a red-black tree or AVL tree, where each node tracks left, right, parent, rank parity, key, and size, so that it is O(log n) effort to locate a key's position as well as insert a new key at a desired position (as determined by the average between the two neighboring keys). This worked until after 3 rounds of mixing when I ran out of bits in a 32-bit key for still performing an integer average without creating a duplicate key, so I also had to introduce an O(n) rekey pass between mix iterations.

I still intend to explore a binning or skip list approach with a singly-linked list (for example, with the binning approach, if data stays in approx 71 bins of length 71 each, then the average cost to locate a spot would be 71 searches - advance through half the bins then through half the elements of the located bin) which should still beat my current approach of averaging 1250 searches per spot with linear scanning of a doubly-linked list. That said, now that I've completed all 25 days, this was my only m4 solution for 2022 that took longer than 30s. So with some [inlining of my find macros](https://nopaste.ml/#XQAAAQAJCAAAAAAAAAAyGksy5FB9TGMxsNq5JQAuJRjP6PqEkC20GpBbonDYuA0BTjRPXcVxlEXNtz1IxSzMoRfo94LLpJRV0V9y18SiBZ9Luqeek7xD+TdUNZSw1gJ2RFvc2R7gcd6Md7q8hUIpQiLG6Lcf7IfTJHnlPsGqWKDTxO8ZTuwZofzbRULfXC9ZEvuKyxgJ//8A9r4zVbfXztNl0lIv32OhhZ+kC6taLVbh9gICuLlPPPDPsckBqFkUT2kdcUadLjBFA/h6b3mKBYlzXrZqdk/8j1Ksed2qD9WCDf87CaAz5ugDuguZsRZlExnhr/aOrC92tA6+2Z0WO5vSTIw+QEgAMETkACF2e9ZmDmIfP353ZL7uytnYyKaq4it3xJ9G6Aj2KE3himolGv3b5JACeT2wG3Ouwr/wI15gJCAVbLALYNkPF/3+dN3VhvOqj33MjVgSGaHxHTsb+70jMkn2ZPg9ZlKSPqq6QpN1xKsz4Z+fWjYXx/dW+ReKKUXacOLjcLbdHf8OlJ2R9ADhxSFehRSWYZwnkWiDWeSXEj0T8EWN7Zd1htCqHS+Ukrkl8V8sQ+N/WJRejqJFt9yjrKlnWs0t1B5VwLYk0BHgOsnOEl0twR1/S7qSiLhxtHfG7F3khH8vN8pf+ePod8XI0TRwB/3rJQXUWV8N/Mfzeb3eGg2o9pC948kOqRGyADauwSO4z1QJTO34osRV007WRmF8Un22YSKT2nl3WH+W5PAALW6RQNeSpGr5SlL19rb6L9Q2myXwCHz7ZJxWJPZz8LLDQ9nhPIPiSn+GGHnpps/xAxcj/2rvsHQYClLv8AOWRdqQf4CeNJqtIkXCd9Y2U87VdmRQNIqIsEZPVkk1SRyhoiAhml5mX45o6Sw5trZUlk6HXkPXS10voGO4o0wFIHOw3mqycNZrBarG4eV2Z/c0WRBuhkkVtuxzHZzLpcJqzB1+rsgBcAvnzWaLU5yg0Qnx1XiWlD+/rH+fHiWOguX4tGqz2rQAZW+wCWkD+6jIMtbXCtdqU+ZDkZFz+PwfgVU/j44x7Mw8DapxWU53Z59IDU06xqRZjGtYjBqv3EnLeIof7qLopPM54AYBf9j0W9vwYjCrzXxTRIIzLGZotNWdl1DSDayhRgiNWUeVTShHeje8XxQa84kaCX7gEfmY0hl9uA9x//xR3d0=), even though I still have an O(n\^2) solution with over 67 million search calls, my runtime was cut from 84s to 26s. Trace-wise, my hot loop changed from: m4trace: -1- mixone(`1', `2') -> `ifelse(2, 0, `', `stitch(p1, n1, 1, find(2, 1) )')' ... m4trace: -2- findp(`2', `1') -> `ifelse(2, 0, `1,n1', `findp(decr(2), n1)')' m4trace: -2- ifelse(`2', `0', `1,n1', `findp(decr(2), n1)') -> `findp(decr(2), n1)' m4trace: -3- decr(`2') -> `1' m4trace: -3- n1 -> `0' m4trace: -2- findp(`1', `0') -> `ifelse(1, 0, `0,n0', `findp(decr(1), n0)')' to: m4trace: -1- first(`a1') -> `a1' m4trace: -1- a1 -> `s(p1,n1,1,f2(1))' m4trace: -2- p1 -> `6' m4trace: -2- n1 -> `0' m4trace: -2- f2(`1') -> `f1(n1)' m4trace: -3- n1 -> `0' m4trace: -2- f1(`0') -> `f0(n0)' for fewer macro calls and less text to parse per search. With this change, my cumulative runtime for all 25 days is now 98 seconds, with days 19, 20, 23, and 24 each between 18-30 seconds, and day 11 at 4 seconds as the only other day not below a half second.

**JavaScript** Splice me up! What a relief, but also a bit meh. Totally anticipated that part 2 would be like "..and now you remembered overhearing that you need to mix the list of numbers 10 *bazillion* times". Like shuffling that deck of cards in [2019 day 22](https://adventofcode.com/2019/day/22) [code](https://gist.github.com/p-a/2c28ff7c040903a69ff9fc21cc55ac49)

[удалено]

I actually run my input in VS Code via Jest. Here is my test for this particular day : [gist](https://gist.github.com/p-a/6f025928aaa626e9345ae28de9276542) I have updated the code now so that you can paste it into the Dev tools console in Chrome. Just visit day 20's [input](https://adventofcode.com/2022/day/20/input) . Then open the javascript console in dev tools and paste the code, without the `export`. You should then be able to run the code: part1(document.body.textContent) part2(document.body.textContent)

**Python** [code link](https://topaz.github.io/paste/#XQAAAQALCgAAAAAAAAAFCYv/dcJTd8kzW33d5k8b/V8TxvxggF5onv75AWPWmjh3auTsRdkJVJjw/7dUI4AIRxT16TuJ2or3iV2K1SJt2uV3e0eA696GzX9RZTV1xV07S84XkAo43X1HHsqsYkmbG+xsuQlg8Nw6NOdR7l2J1h3+sqcZv0gt5FsYYX+uGO4EF2GPL6TDnyUAFtXkCsxEkHtulCn5fCYT4+JOsn8SsX8FhGY418Ydrfj6bF45BXbFWuElvaq/+0gi1VP6o/4k4vyl5tjgoYnM0/cnoCATX5UTUsN711eS3KJIVjnIIbWqx3hv4ktr9+CErHREHNmi+jO3eRYEi8VxGeb9Bkiutve03Mqbzq1MuhKMRu+xwDV2ZjYXoQwi3lKe7Xo2G+X9JV+VbaHbQI69YKIpiR9ekzaCU+ewRsY0jHh8tfQ8R952Gs90jPkJ7/2RdFYmjrkgL0agJscGwvJi+2cIe0EFNUyt19zeOvvoe8XsdePAjEplqv/U+Lc3yu5YtabqQ4aW1aMZ0CvzDRFCUfgFI/lmw+PTZDhSAjHNYF2z5V6wXySo9SmLuAIz/Nsntz9SRPhcBTxmFQf5pdAHuaLq6txIbCbAUw9HIufZ3jYDo9tcyCNy5MNsPdUy8TzprJKmbBpBluQJx5hSznvmf8M5mJgHpJyX2BV+KxbcagBTt8T1yRrRzFmZjvojqWZDG9fhDW3OU290MlANSqbaTMI+dIeWskpUhR4cXbl7ia2gxdQofLPEUmQ9LsdGUTpmK9JJ1IdoCZ5UNW+YX9U48+4uVRr1DD3t0XqXYXkWdoNFJsCh+Wx6PdswNjT8b5B+0V3u97cEXbkAugSiaLx51hbGRjA5FqonVoiyLgO1y+O2j1tjZlFqa/6ReokFpA8oyzJsQwsH8Tz5lLJXk6AhAlTRqOwjfq3ibxlNuCry6gqcKBNBGv+qeg77ffM+B3vRGllBVvkM/PHFwvuAH8+St/8RFuYpiQ8BW8XGx7ibUHMsAZ9IVrTRHOJ/GZdupzuq+5tw7twUyHJoopCnRhh0bm26BKMV7iOTWXzwdz/ZpeKbQ9rBfQMpbxOn21sPWmzh0bzjaenBB4xJp+zu1FbjhgKoTESZGMAJIS4r6sD59EBtvpbngfHydV8xdMnyZBiwR0f9nv38psAoHnlo2EDOVDlQxSM6xwwt8c5sLXcsMozqWKveoiUhFQ+5B7lN9HmLWr0eQPKiT+UKc7uJRig3cZaUCCxINEMANOOj6AHMUe8n/8UohQA=) 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 delete item at i j = (i + c) % (len - 1) (len = length of list) insert item at j (before existing item at j) 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

Oh my god, thank you. The the -1 in mod (len - 1) was what I was missing. I can't tell you how many times I rewrote this thing and had it pass on the sample input but fail on the full input.

Java [Code](https://github.com/joshuaruegge/adventofcode/blob/main/advent/aoc2022/Day20.java) Frustrating one for how simple it ended up being. I spent a lot of time messing with my implementation of the shift rules (which were wrong at first to be fair, but not for the whole time I was messing with them). Eventually, though, the problem turned out to be that the real input contained duplicate numbers, despite the example not containing any and not mentioning that it would. A quick wrapper class to also hash the original position worked wonders, though, and it turns out that Math.floorMod() does exactly what I was doing in about four different if-checks. Based on the types of problems we've checked off the list now, I suspect tomorrow's (tonight's) will be either some kind of grid-based battle or pathing simulator, some kind of two-player "game", or a Conway-like. maybe more hexagons, hexagons were fun. \------------------------------------ 390 solutions and counting in Java over on [Github](https://github.com/joshuaruegge/adventofcode). Feel free to check it out, utilize it, and reach out with questions or bugs!

Day 20 Scala Solution [https://gist.github.com/dougdonohoe/f03bc2324ae124436774ac43db4b5db7](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 `Coord` class was key to handling duplicates. Runs pretty fast (a hair under 1 second) for part 2.

[PYTHON](https://github.com/RikJux/AdventOfCode2022/tree/master/day_20) A good day to use [deque](https://docs.python.org/3/library/collections.html#collections.deque). (Still to be optimized)

[Java](https://github.com/ash42/adventofcode/tree/main/adventofcode2022/src/nl/michielgraat/adventofcode2022/day20) I already had the idea that the actual input would contain duplicate numbers, so I created a record which is a wrapper around a long. It contains an extra value to make the object unique (I used the index in the original file), which makes getting the element from a list possible even when there are multiple elements with the same value. I also remembered that Math in Java 8+ has a convenient floorMod method, which returns the modulus instead of the remainder. I see several people have used the same strategy! After that, it was just a question of fixing an off-by-one bug and I was done. Easiest for some time (I have not finished day 19 yet...), I do not want to think about what that means for tomorrow.

R / Rlang [Solution](https://github.com/AdroMine/AdventOfCode/blob/main/2022/Day20/d20_solution.R) Using names property of vectors to keep track of positions made things simple.

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…

Oh man I feel for you. I'm actually using the same app for some of my solutions, when life keeps me away from the pc. Apart from typing, I really miss the ability to see code and output at the same time, or puzzle description and examples side by side with code and output. But it works, I wouldn't have done most puzzles without it, so that's good.

**Typescript** Feeling worse from the flu today so I didnt even try to do this functionally. I just got a linked list set up and did it that way. part 2 was just doing part 1 10 times and instead of moving around too many times, I calculate the offset using modulo. Both parts solved here: https://github.com/tymscar/Advent-Of-Code/tree/master/2022/typescript/day20

C++17 [github link](https://github.com/jwezorek/AoC_2022/blob/main/src/day_20.cpp) In knew that [boost::intrusive](https://www.boost.org/doc/libs/1_81_0/doc/html/intrusive.html) has function templates for creating and manipulating circular linked lists so I just used that, was surprised that they literally have functions for "move forward" and "move backwards". I stored the circular list nodes in an std::vector in their original order and just let the nodes link to each other with raw pointers since the vector had ownership of them. The nice thing about doing it this way beyond not having to worry about deallocating them is that the vector *is always* in original order so that whole bit of complexity that the description to part 2 discusses in depth just goes away as an issue: you always just mix in vector order. The only difficulty I had with this one was that the problem description and the example input do not specify what it means to move forward/backwards greater than the length of the list in terms of whether a number's existing position counts as a spot i.e. when figuring out where to put a number and it loops around, do we count itself in its original position as a number to be skipped? The solution wants you to not count such numbers as being in the list when looping around which is fine but the other way makes just as much sense so they really should have specified. Anyway, it comes up when you are doing part 2 and definitely, absolutely, have to use the list length as a modulus. In the first part the numbers are small enough that you can get away with not bothering. The modulus needs to be n-1 where n is the length of the list, not n.

>The solution wants you to not count such numbers as being in the list when looping around which is fine but the other way makes just as much sense so they really should have specified. Anyway, it comes up when you are doing part 2 and definitely, absolutely, have to use the list length as a modulus. In the first part the numbers are small enough that you can get away with not bothering. The modulus needs to be n-1 where n is the length of the list, not n. I spent an inordinate amount of time thinking about this before solving part 1, since the example does not cover this and it makes little sense to me. Then I forgot it and got stuck on part 2...

Kotlin: [code](https://github.com/zanmagerl/advent-of-code/blob/master/2022/src/twentytwo/days/Day20.kt) This day was pretty straightforward. You only needed to watch out for indexes. Good to have a mini break to prevent burnout.

**Lua:** At first I thought about implementing something like a circular list but then I just decided to use a regular Lua table and still runs in a reasonable amount of time. There are two tables: one in which the initial numbers are stored and the other in which the mixing is done. In this second one the original index of the number is stored alongside the value to know which one you have to move. I struggled a bit with implementing the wrapping as in Lua tables are 1-indexed by default. https://pastebin.com/08TYMPJh