https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2022 day 20> :thread:
# advent-of-code
a
b
Seems like index 2 would become index 0 🤔
Copy code
1, 2, -2, -3, 0, 3, 4

-2 moves between 4 and 1:
1, 2, -3, 0, 3, 4, -2
e
That got me slowed down quite a while, too. In fact, it does not matter, since to get the answer you'll be computing positions relative to the position of 0, so the absolute positions in your list are not relevant. That is, [1, 2, -3, 0, 3, 4, -2] with -2 at the end and [-2, 1, 2, -3, 0, 3, 4] with -2 at the start are the same for the purpose of computing the answer.
m
Since the list is supposed to be circular, imagine the numbers arranged in a circle, there is no first or last element, just an order. When printing it out, you could choose to start at any element.
v
Hmm, didn't thought initially about numbers arranged in circle, just set index to 0 when it was last, and to last when its index became 0. Happy that it worked in the end.
s
I think I'm missing something obvious in the second part. Here's what I have for the 1st round of mixing: Initial state, as in the example: 
811589153, 1623178306, -2434767459, 2434767459, -1623178306, 0, 3246356612
811589153 % 7 = 4
, moving it 
4
to the right: 
0, 3246356612, 1623178306, -2434767459, 2434767459, -1623178306, *811589153*
1623178306 % 7 = 1
, moving 
1
to the right: 
0, 3246356612, -2434767459, *1623178306*, 2434767459, -1623178306, 811589153
-2434767459 % 7 = -5
, moving 
5
to the left: 
0, 3246356612, 1623178306, -*2434767459*, 2434767459, -1623178306, 811589153
2434767459 % 7 = 5
, moving 
5
to the right: 
0, 3246356612, 1623178306, *2434767459*, -2434767459, -1623178306, 811589153
-1623178306 % 7 = -1
, moving 
1
to the left: 
0, 3246356612, 1623178306, 2434767459, -*1623178306*, -2434767459, 811589153
`0 % 7 = 0`: 
0, 3246356612, 1623178306, 2434767459, -1623178306, -2434767459, 811589153
3246356612 % 7 = 2
, moving 
2
to the right, and here's my state after 1 round of mixing: 
0, 1623178306, 2434767459, *3246356612*, -1623178306, -2434767459, 811589153
But the example shows that after 1 round of mixing we should have: 
0, -2434767459, 3246356612, -1623178306, 2434767459, 1623178306, 811589153
r
That part caught me off guard too. Somehow I was initially thinking that there'd need to be a movement step to go from first to last position or last to first. The number of movements for an element to go full circle back to where it started is actually 
n_elements - 1
, but my natural thought was that a full circle would be moving it 
n_elements
times
m
It’s 
n_element
times, where the list it’s moving through does not contain the element that moves, otherwise there be two, one static in the list and a moving duplicate.
The natural thinking that it’s 
n_elements
is right, it’s just that you have to remember the element you are moving is no longer sitting there, so the list is one smaller!
r
@Sergei Petunin here's the step-by-step for part 2 on example input:
Copy code
initial: [811589153, 1623178306, -2434767459, 2434767459, -1623178306, 0, 3246356612]
[1623178306, -2434767459, 2434767459, -1623178306, 0, 811589153, 3246356612]
[-2434767459, 2434767459, -1623178306, 0, 1623178306, 811589153, 3246356612]
[2434767459, -1623178306, 0, -2434767459, 1623178306, 811589153, 3246356612]
[-1623178306, 0, -2434767459, 2434767459, 1623178306, 811589153, 3246356612]
[0, -2434767459, -1623178306, 2434767459, 1623178306, 811589153, 3246356612]
[0, -2434767459, 3246356612, -1623178306, 2434767459, 1623178306, 811589153]
k
@Sergei Petunin I guess the node should be moved (added after) 
value % (totalSize*-1*)
nodes. So it's 6 instead of 7
s
Shifting element 6 positions gets it to the same place, not 7 🤦‍♂️ Thanks, folks
j
I'm still struggeling with part1 moving stuff in negative direction, somehow my array ends up being shifted by 1
j
Sometimes I don't like Kotlin being strong typed (or maybe just how stdlib is implemented). How is it possible that 
Long % Int
returns 
Long
if the remainder should clearly be smaller than modulus so if modulus is 
Int
then the result should also be 
Int
? 🤔
@Jonathan Kolberg to be honest after struggling with calculating indices for `removeAt`/`insertAt` using standard structures I decided to implement my own double-linked circular list (i.e. elements with pointers to next/prev) and do the shifting myself. That simplified the code (in terms of readability) and also saved me the 
+/-1
headache
e
@Jan Durovec The return type of the remainder operator 
%
for longs is an unfortunate Java/C/C++ legacy. For this particular problem you should be using 
Long.mod(Int)
extension function that has the convenient return type of 
Int
and also does exactly what you need for the negative value, that is, it performs a proper mathematical modulus operation.
j
@Jan Durovec I think my problem is that I do not understand the move in the example, should the 4 not be moved 4 elements to the right by my understanding it should land between the 2 and -3?
Copy code
0 does not move:
1, 2, -3, 0, 3, 4, -2

4 moves between -3 and 0:
1, 2, -3, 4, 0, 3, -2
e
@Jonathan Kolberg 4 starts between 3 and -2 moves 1 to the right -> between -2 and 1 moves 1 to the right -> between 1 and 2 moves 1 to the right -> between 2 and -3 moves 1 to the right -> between -3 and 0
s
Both parts work on the example but don't work on the input, did anyone have that?
j
@Sergei Petunin yeah my code works on example not on my input.. I probably have a bug or something Edit: OH FFS, in the real input, the numbers repeat sometimes. Arrrgh.
s
You don't need to shift not only the 0 number, but also for any number where 
n % (size - 1) == 0
e
I wrapped everything in Box (to maintain distinct object identities) and throw them all in an Array
I started by trying to work out the backpermutations but couldn't. thankfully the input is small enough that just doing it directly is fine
I also didn't bother storing the multiplied numbers for part 2, since that would have required me to bump my data type size :p
a
using object ID to track the original order is smart! I ended up wrapping in a data class that held 
originalIndex
as well as the value. And then went through the indices, looking up the element with that originalIndex and moving it 😄
r
Works for testInput, but fails for real input. Probably some bug in the code, i used circular doubly linkedlist and then i find 1000th etc.. values from zeroth node (node with value zero)
s
I think a key difference between the test and the real input is that the real input contains multiples of 
±(n-1)
which are not supposed to shift. E.g. my input was 5000 numbers long, and there was the number 
-9998
r
Ahh, that did the trick. Thanks.
I was under the assumption, its a circular array, it has go to round, and eventually it will stop at point and size doesn't matter.
Math.floorMod()
came handy.
e
no need for Java 
Math.floorMod()
, just use Kotlin's own 
.mod()
k
in the end you just need to dettach and attach at destination
p
https://github.com/tKe/aoc-22/blob/main/kt/src/main/kotlin/year2022/Day20.kt Implemented my own basic triple-linked list for both iteration order and rearrangement.
Copy code
year 2022 day 20 part 1
	 Default took 48.874454ms: 13967
year 2022 day 20 part 2
	 Default took 644.260733ms: 1790365671518
p
Pretty happy with my solution today: https://github.com/PaulWoitaschek/AdventOfCode/blob/main/src/main/kotlin/de/woitaschek/aoc/year2022/Day20.kt The idea that made the re-ordering finally click in my mind was to just remove the item, then rotate the list by it’s number and then just add it back to it’s position
My rotation logic is like a sushi table. You pick an item up, wait until 2 dishes have passed and then put it down.
o
I am absolutely devastated how long such a seemingly simple game has got me working on it. I was getting really, really mad this morning at me, my horrible code, my drawings on paper - it is amazing how this cute little thing throws off so many people. Who else struggled???
r
Same, i spent too much of time debugging this one https://kotlinlang.slack.com/archives/C87V9MQFK/p1671539603855729?thread_ts=1671512450.647679&amp;cid=C87V9MQFK on real input. I also wasn't sure what 
mix
means for part-2 as i hadn't read the whole problem for part 1 and had just looked at the sample input and output 😄
e
I had an easy time with today's, I was just slow due to oversleeping. but I think a lot of it comes down to picking an easy representation - IMO, just sliding things around in array like I'm doing is conceptually much easier than working with linked lists
the only thing I did differently than the puzzle text is to never wrap around the end of the array, and prefer to slide a contiguous center portion instead - so the indices end up looking different, but everything is in the relatively correct place
p
No it's not. It was roasting my mind for an hour.
https://github.com/PaulWoitaschek/AdventOfCode/blob/af00586bb49b3345973c905891b88e95dddaee77/src/main/kotlin/de/woitaschek/aoc/year2022/Day20.kt#L38 This is where it clicked for me. That's something I can easily imagine. Take, rotate, put back to the same spot
e
I think this is pretty simple: it was at index 
i
, you want it at index 
j
, so just move everything in-between up or down by one (depending on whether it's going down or up) and then put it in https://github.com/ephemient/aoc2022/blob/main/kt/src/commonMain/kotlin/com/github/ephemient/aoc2022/Day20.kt#L39-L40
p
Interesting - I took a different approach for my array-based solution: https://github.com/tKe/aoc-22/blob/main/kt/src/main/kotlin/year2022/Day20.kt#L89-L122 I didn’t mix the input array, I mix an index of the original indices - that way the 
indexOf
equalities stay unique.
e
yes, permuting the indices only is a good idea. if I were trying to squeeze more performance out of this, I'd try that or a single flat primitive array (would require a bit of extra code to manage packing/unpacking it though)
t
Stupid duplicates in the list burned me. Bah. • Blog • Code
e
hah yeah, that was one of the first things I checked for before writing code
Copy code
$ wc -l input.txt
5000
$ sort input.txt | uniq | wc -l
3649
t
I just blindly started writing code thinking it was easy and then just could not get a sensible answer for part 1. haha. Figured it out eventually.
e
hard to remember what was going on at midnight, but I think one of my bugs (which luckily didn't take too long to squash) resulted in only iterating over items that were physically after the first. I don't remember how I managed to do that though lol
21 Views
Open in Slack
PreviousNext
Powered by