ShareMyScreen/AdventOfCode/2022/20/GrovePositioningSystemJP

The Problem << >>

This day was fun. A few gotcha's that strung me up a while, but after all not too involved.

Entire Solution

i20=: ".;._2 freads '20.txt'             NB. read and parse input list of numbers
to=: <. + i.@(+*)@:-~                    NB. "to" function both directions: e.g. 4 to 2 -> 4 3 2
mix=: {{                                 NB. x: #rounds; y: input; output: mixed numbers
  inds  =. i.@# y                        NB. indices into orig y
  NB. for each number, index pair
  for_i. ($~x*#) inds do.                NB. repetitions added for part 2
    se =.  (inds&i. ([,(<:#y)|+) {&y) i  NB. start and end of index range to rewrite
    sub=. to/  se                        NB. inds of subarray to be rotated.
    inds =. (1|.sub{inds) sub} inds      NB. rotate indices 
  end.
 inds{y                                  NB. return shuffled original values
}}
groveNB=:+/@({~ #|1000 2000 3000 + i.&0) NB. sum 1k,2k,3k numbers after 0
part1 =:[: groveNB 1 mix ]               NB. Grove number after indexing
NB. Part 2: multiply input with decryption key, the mix 10 times.
key=: 811589153
part2=: [: groveNB 10 mix key * ]        NB. Grove number after 10 rounds after decrypt
(part1;part2)i20                         NB. both part 1 and 2.

Solution

The input is a list of numbers that have to be "encrypted" by moving the position of each number in turn (i.e. in the order they were in the original list) to the start or end of the list by its value. The required result is the grove number by adding the 1000th, 2000th and 3000th number after the 0 after mixing them.

My first attempt stranded because I assumed values were unique. They are not. This means that I had to work on the indices in the original list, and shuffle those around, instead of the values.

For efficiency, I took a good look at what "moving" a number implies. It can be done by finding a sub-array starting at the current number, and ending the correct amount of places further. Rotating that array and replacing it implements the right shuffle. The amend overwrites the array in place.

A small hiccup in the calculation of the end index is that, due to cyclical indexing, the first and last position in the list are effectively the same. The effective list length is therefore one less than its original length, so when taking the modulo to account for wrapping around the edges, it should be modulo <:#y instead of #y. For instance moving x right in a list of length=3:

x A B > . A x B > A B x 

The last array (A B x) is equivalent to the first (x A B) because of the cyclical indexing. So moving numbers wraps after 1, instead of 2, as one might expect. For the same reason (I think), I noticed the array as shown in the explanation of the problem does not correspond to my array, but a rotated version thereof. This does not matter either due to the cyclical indexing.

After mixing the list, calculating the grove number is simply finding the indices, offset by i.&0 in the array, and summing them. Part 2 adds little more, and just required me to add a loop to do multiple rounds, and multiply the decryption key with the list of numbers.