ShareMyScreen/AdventOfCode/2022/09/RopeBridgeJP

The Problem << >>

Eventual entire solution

This solution corresponds to the final one described below. Part 1 in the next section describes how I got to the initial version.

i9  =: freads '09.txt'
NB. parse by lookup and do; convert to single steps
par    =: [: #~&:>/@|: [: (0j1+.@:^'DRUL'&i.@{.)&.>`(".&.>)"1&.|: ;:;._2
stepv  =: **(1&<. * 2 <: >./)@:|  NB. single step if tail based on difference with pos of head.
tailup =: (]+stepv@:-) {:         NB. update tail of rope (y) with new head (x)
step1  =:(+{.) ([,:tailup) ]      NB. single instruction on entire rope
part1  =: (  2 2$0) #@~.@({: F:. step1 par) ]
rope   =: (0$~[,2:) #@~.@({: F:. step2 par) ]
NB. one step; x: new op; y: coords
step2  =: ([+stepv@:-~)/\.&.|.@((+{.) , }.@])
part2  =: 10&rope
(part1;part2)i9

Parsing input

The input is a list of directions, given as letters D R U L for down, right, up and left, respectively, followed by the amount of steps to go in that direction. The two columns have to be treated separately.

I split each line in J words, which happen to coincide with how the columns are specified. The letters in the first column have to be looked up, and converted to coordinates to take a step in. This is handy with complex numbers, if directions are properly ordered ({. because ;: returns boxed literal lists, not atoms):

lookup=: (0j1 +.@:^ 'DRUL'&i.@{.)&.>

The second column should just be executed to give the right value for the length of the move in that direction. Taking this together with the right plumbing to make values reach the relevant verbs:

pari =: [: ;"1 [: lookup`(".&.>)"1&.|: ;:;._2 NB. i for initial

This initial version will be amended for the final version of the solution further down.

Part 1 initial solution

Day 9's first question is: given the input and a rope of two units long (I call them "head" and "tail"), how many squares does the tail visit when the head is moved as instructed by the input? The movement of the tail is such that it moves only if it is no longer on a square adjacent to the head.

This seems like a simulation problem, requiring to keep the state, executing each instruction when starting from a known initial state; an excellent fit for experimenting with Fold! Of the many variants, I think either fold single forward (F..) or fold multiple forward (F:.) fit the problem best: x u F.. v y executes it v x for each item it of x and u only on the final state. x u F:. v y differs only in that u is executed on the state for each iteration (the diagram on the page linked above explains it better than I can).

So I'll try u F.. v first, accumulating the locations of the entire rope in the v verb, which I call keep, and initially, I'd just take the count of the unique locations of the tails after the fold finishes (such that I can inspect the states before counting while debugging):

part1i =: (1 2 2$0)  #@~.@:({:"2)@(] F.. keep pari) ]
keep   =: ] , (inst {:) NB. keep previous states, add new one

Each instruction consist of {: x steps, with x being the instruction passed in. Each step updates the head based on the direction }: x and the current head {. y. The tail is updated based on the head and the current tail:

inst  =: stepi^:(>:@i.@{:@[) NB. single instruction on entire rope
stepi =: headup ([,:tailup) ]
headup=: }:@[ + {.@] NB. update head (y) with step (x)
tailup=: (]+stepv@:-) {: NB. update tail of rope (y) with new head (x)

The tail step is the same in all quadrants, just mirrored, so I do the step in the first quadrant (dx,dy >: 0), i.e. after applying | on the difference between head and tail, produce the right step (figured out after some experimenting) and multiply with the sign of the difference to flip it back to the right quadrant:

stepv=: * * (1&<. * 2 <: >./)@:| NB. x: new op; y: coords H,:coords T

Keeping all intermediate states allows easy visualisation of our rope:

vis =: ((i.@#@])`]`(0$~[:>:>./@])}])@(-"1<./) NB. visualisation, feed coordinate list
viewmat vis ,/ (1 2 2$0) ]F.. keep par i9     NB. result see on the side

Visualisation of the rope of part 1

Optimising part 1

When writing this text, I had another chance to play with this problem and optimise it as well as learn a thing or two about Fold (it's one of the first times I use it for something less trivial). Executing the same as part 1 but using F..'s u verb to select tails is quite a bit slower:

   part1a=: (1 2 2$0) #@~.@:({:"2 F..keep pari) ] NB. a for alternative
   10 timespacex 'part1i i9'
0.0551696 1.9344e6
   10 timespacex 'part1a i9'
0.152614 1.9344e6

Perhaps not such a surprise it's not leaner, since all state is still kept, but the slowdown is: {:"2 should still be executed only once.

Then it occurred to me that I was using Fold Single and keeping a lot of state only because the instructions have a variable number of steps. Simplifying the input to make single length steps only would:

• liberate me from keeping more state than the current location of each unit of rope,
• allow me to use Fold Multiple, which had always seemed to be the more natural way of dealing with this problem, and
• simplify the code substantially.

It also turns out to be faster than the previous solution:

   part1 =: (2 2$0) #@~.@({: F:. step1 par) ]
   par   =: ({:"1 # }:"1)@pari
   step1 =: (+{.) ([ ,: tailup) ]
   10&timespacex&> 'part1i i9';'part1 i9'
0.0550795  1.9344e6
0.0493647 2.12221e6

Part 2

Part two asks the same question, but for a rope of length 10. Initially, I had written it as (just as timing reference):

part2i =: (1 10 2$0) #@~.@:({:"2)@(] F.. keepb pari) ]
keepb  =: ] , (instb {:)
headup =: }:@[ + {.@]
instb  =: step2i^:(>:@i.@{:@[)
step2i =: ([+stepv@:-~)/\.&.|.@(headup , }.@])

The juicy part is the new single step verb step2i. It updates the head, then steps over each subsequent piece of rope, adjusting it to follow the preceding piece. The action of the adverb /\.(&.|.) can be demonstrated with the "between" verb below, which joins its arguments with a colon, and encloses the result in parentheses:

   between =: [: {{y[ct=:>:ct}} '(',')',~[,':',]
   ct=:0  NB. keep number of times betw is executed
   between/\.&.|. 'abcde'
a
(b:a)
(c:(b:a))
(d:(c:(b:a)))
(e:(d:(c:(b:a))))
   ct
5

J is smart enough to reuse the result of the previous run of between, so that it is only execute 5 times, rather than 5*(5-1)/2=10 times. Note that any inserted verb (u/) on a single argument is the same as ] (see the first line), that is, the head is not touched in one2. As can be seen, what comes left in the original series is seen as right argument by between: instead of (]+stepv@:-) in tailup for part 1, we have to write ([+stepv@:-~) in step2i.

For the fun of it, I wrote the part 2 solution incorporating the optimisation found for part 1 in such a way that it works for part 1 as well (actually for any length rope taken as x argument):

rope   =: (0$~[,2:) #@~.@({: F:. step2 par) ]
part2  =: 10&rope
step2  =: ([ + stepv@:-~)/\.&.|.@((+{.) , }.@])

As can be expected, the performance difference between the original and optimised version is larger for part 2, as it's state is a lot larger (10 rope units opposed to 2):

   10&timespacex&> 'part2i i9';'part2 i9'
0.297443 4.26707e6
0.188468 2.12246e6

However, this optimisation does not allow this nice visualisation, showing all rope positions, coloured by last time they were traversed (dark blue first):

viewmat vis ,/ (1 10 2$0) (] F.. keepb pari) i9 NB. result, see on the side

Visualisation of the rope of part 2

Just for the sake of it, we can also take a look at how the result evolves with increasing rope length:

load'plot'
NB. fun plot for ropes of length 1-20
'xcaption length;ycaption positions visited' plot (; rope&i9"0) >:i. 20

Plot of unique tail positions by rope length