ShareMyScreen/AdventOfCode/2022/23/UnstableDiffusion

From J Wiki
Jump to navigation Jump to search

The Problem << >>

This looks like a simple simulation. I will simulate each step as described in the problem. Since the number of elves is limited and the board is not, I will keep track of the elves' positions only. I will read them from the sample input:

   ]lines =. '#'&= onaoclines
0 0 0 0 1 0 0
0 0 1 1 1 0 1
1 0 0 0 1 0 1
0 1 0 0 0 1 1
1 0 1 1 1 0 0
1 1 0 1 0 1 1
0 1 0 0 1 0 0
   ]elves =. ($ #: I.@,) lines
0 4
1 2
1 3
...

($ #: I.@,) is a standard J idiom for finding the index lists of 1 in an array: flatten the array into a list, find the positions of the 1s, then convert those to positions in the array.

Now to pound out the simulation. I start a script.

NB. simulate diffusion
NB. The 12 cells we inspect for all-empty (there are overlaps).  If we find all 3 empty,
NB. we try to move to the first of the three
looks =: 4 3 2 $ (,_1,.0 _1 1) , (,1,.0 _1 1) , (,0 _1 1,._1) , (,0 _1 1,.1)
sim =: {{  NB. x is starting elf positions, y is # turns to run, result is # empty cells in rectangle
poss =. x   NB. current positions of all elves
rlooks =. looks  NB. our current look priority
for. i. y do.   NB. for each move requested
  NB. See what positions are filled; find the first empty set for each elf, 4 if none; fetch offset to request
  reqofst =. (>./@,"2 * (0 0 ,~ {."2 rlooks) {~ i."2&0 0 0) (poss +"1/ rlooks) e. poss
  NB. convert offsets to position to request; zero shared requests; apply moves to get new positions
  poss =. poss ([ + ] * [: (i.~ = i:~) +) reqofst  NB. accept requests made only once
  rlooks =. 1 |. rlooks   NB. change direction priority for next time
end.
NB. return size of area, minus number of elves
(#poss) -~ */ >: (>./ - <./) poss
NB. for testing, return a picture of the board
'#' (poss -"1 <./ poss)} (>:(>./-<./)poss) $ '.'
}}

(poss +"1/ rlooks) combines the nx2 table poss and the 4x3x2 brick looks to produce a nx4x3x2 array of candidate positions. These are looked up in poss to give a nx4x3 array of fill status for each square each elf looks at. Then I look in each elf's results for the first 0 0 0 which will be where the elf requests. I translate this back to a (y,x) offset: each elf's request.

Then I convert the request offsets to request positions, and create a mask of the unique ones (which I detect as those values whose earliest occurrence is the same as its latest occurrence). I multiply the offset by the mask to convert duplicate requests to 0 0, i. e. a request not to move. Then I make all the moves.

For testing purposes I display the board to check against the example. After fixing a missing ~, I get a display.

   elves sim 10
......#.....
..........#.
.#.#..#.....
.....#......
..#.....#..#
#......##...
....##......
.#........#.
...#.#..#...
............
...#..#..#..

Then after inserting the code to make no move if a elf has no neighbors (>./@,"2 * in the repaired version shown above), I get the right display.

   elves sim 10
110

With the debug line removed, I get the right result too.

In part 2 I have to count the number of rounds till there is no change. That's easy: it will be when all the requested moves are all 0. [It is impossible for two or more elves to exchange places during a turn.] The changes are:

...
sim =: {{  NB. x is starting elf positions, y is unused, result is number of rounds
...
r =. 0  NB. round number
while. do.   NB. until no change found
  r =. >: r  NB. advance round number and convert to 1-origin
...
  if. 0 = +./@, 0 ~: reqofst do. break. end.  NB. exit if no move requested
...
r
}}