Advent of Code 2022 part 5

Day 5

For part 1 we need to move crates around between several stacks, according to instructions like move 1 from 2 to 1, where crates can only be moved one at a time. I was a bit short of time, and after struggling a bit with APL just solved it in common lisp. I represented the stacks of crates as a vector of lists, then just had to pop from and push to each list to move containers around:

(loop for move in moves do
  (loop for i below (move-n move) do
    (push (pop (aref stacks (1- (move-from move))))
          (aref stacks (1- (move-to move))))))

For part 2 we got upgraded to be able to move several crates at once, which actually is more involved since we don’t have handy builtins to use, and when I found it getting a bit messy and repetitious I wrote a macro that implements the move in a setf-like manner where one just has to pass the “place” for the from and to stacks. I mostly cribbed the use of get-setf-expansion from this stackoverflow answer, which in turn was based on examples from On Lisp.

(defmacro move-items (from to n &environment env)
  "Destructively move the first N items from the FROM place to the TO place."
  (multiple-value-bind (from-vars from-forms from-var set-from access-from)
      (get-setf-expansion from env)
    (multiple-value-bind (to-vars to-forms to-var set-to access-to)
        (get-setf-expansion to env)
      `(let* (,@(mapcar #'list from-vars from-forms)
              ,@(mapcar #'list to-vars to-forms)
              (,(car to-var) (nconc (subseq ,access-from 0 ,n)
                                    ,access-to))
              (,(car from-var) (nthcdr ,n ,access-from)))
         ,set-to
         ,set-from))))

The solution loop is then the rather simple:

(loop for move in moves do
      (move-items (aref stacks (1- (move-from move)))
                  (aref stacks (1- (move-to move)))
                  (move-n move)))

Later I went back to APL, and solved the issue I was having, or at least worked around it, of trying to use @ to modify the “stack” vectors - I found if I took the first (⊃) element I got the string I expected. Otherwise I think it was pretty straighforward, at least to get the core logic working. Munging the input to get it into a workable arrangement felt clunky, which almost certainly means I was doing it the hard way. April doesn’t implement any recursion primitives except reduce, suggesting to just use CL for that, so I didn’t bother going further than just proving it worked for a couple moves:

in←('xDx')('NCx')('ZMP')
move←{[st;n;from;to]
  ({n↓⊃⍵}@from) ({(⌽n↑from⊃st) , ⊃⍵}@to) st}
st←{⍵~'x'}¨↓(⊃,/⍪¨in)       ⍝  NZ  DCM P
st←move[st;1;2;1]           ⍝  DNZ  CM P
st←move[st;3;1;3]           ⍝     CM  ZNDP

move2←{[st;n;from;to]
  ({n↓⊃⍵}@from) ({(n↑from⊃st) , ⊃⍵}@to) st}
st←{⍵~'x'}¨↓(⊃,/⍪¨in)        ⍝  NZ  DCM P
st←move2[st;1;2;1]           ⍝  DNZ  CM P
st←move2[st;3;1;3]           ⍝     CM  DNZP

I won’t try to explain what I ended up doing to get the input into st, which represents each stack of crates as a sub-vector. The more interesting part is the move function, which takes the current state and the data for one move (this function form is not standard APL, rather something April borrowed from k).

1. We first modify the “to” stack, by picking the “from” stack (from⊃st), taking the number of crates we’re moving (n↑ ...), then reversing their order (⌽ ...). We then append them onto the crates already there (... , ⊃⍵).
2. We then modify the “from” stack, by dropping the number of crates we moved ({n↓⊃⍵}@from ...).

To modify the solution for part 2, all we have to do is delete one character!

Day 6

For part 1 we need to find the first location in a character buffer where the preceeding four characters are all unique. This lent itself to a fairly straightforward APL solution, and a lovely demonstration how concise it can be (although I feel like I’m doing a couple unecessary structure manipulations):

{3+(+/ ¨ ≠ ¨ ↓⍉4 ((≢⍵)+1) ⍴ ⍵) ⍳ 4}

1. We first reshape the input into a 4x(len+1) array, because APL will keep repeating the input to fill the array, so we end up with columns representing each set of four contiguous characters (4 ((≢⍵)+1) ⍴ ...). For example:

{4 ((≢⍵)+1) ⍴ ⍵}'mjqjpqmgbljsphdztnvjfqwrcgsmlb'

mjqjpqmgbljsphdztnvjfqwrcgsmlbm
jqjpqmgbljsphdztnvjfqwrcgsmlbmj
qjpqmgbljsphdztnvjfqwrcgsmlbmjq
jpqmgbljsphdztnvjfqwrcgsmlbmjqj

2. We then transpose the array and split it into sub-arrays (↓⍉ ...), e.g.

↓⍉{4 ((≢⍵)+1) ⍴ ⍵}'mjqjpqmgbljsphdztnvjfqwrcgsmlb'

 mjqj  jqjp  qjpq  jpqm  pqmg  qmgb  mgbl  gblj  bljs  ljsp  jsph  ...

3. We then apply the unique function to each element (≠ ¨ ...), which gives us a boolean vector saying if the character at each index is the first occurance of that character, e.g.

≠ ¨ ↓⍉{4 ((≢⍵)+1) ⍴ ⍵}'mjqjpqmgbljsphdztnvjfqwrcgsmlb'

 1 1 1 0  1 1 0 1  1 1 1 0  1 1 1 1  1 1 1 1  1 1 1 1  1 1 1 1  ...

4. Finally we can sum each element (+/ ¨ ...) and find the index of the first element where the sum is four, which means all four characters were unique (... ⍳ 4). Then add three to get the location of the end of the marker string.

{3+(+/ ¨ ≠ ¨ ↓⍉4 ((≢⍵)+1) ⍴ ⍵) ⍳ 4}'mjqjpqmgbljsphdztnvjfqwrcgsmlb'

7

For part 2 we need to instead find the location of the first marker of fourteen unique characters, so I just paramaterized the solution from part 1, where len is the marker length, passed in from CL:

{(len-1)+(+/ ¨ ≠ ¨ ↓⍉len ((≢⍵)+1) ⍴ ⍵) ⍳ len}