From J Wiki
Jump to navigation Jump to search

The Problem << >>

After the last problem most anything would be a relief. This looks like a simple simulation.

Since the pieces can move left and right and get stuck in weird shapes with unpredictable protuberances, I will model the whole stack. 2000 cycles shouldn't take long. I start a script.

NB. pieces are relative to bottom-left corner, with the topmost cell last
pieces =: (0,.i. 4); (_2 ]\ 0 1 1 0 1 1 1 2 2 1);(_2 ]\ 0 0 0 1 0 2 1 2 2 2);(0,.~ i. 4);(_2 ]\0 0 0 1 1 0 1 1)

NB. read next jet direction in the cyclic sequence.
getjet =: {{ jets {~ jetx =: (#jets) | >: jetx }}  NB. nilad.  

NB. See if a proposed move would result in a collision
collision =: {{  NB. x is piece, y is new position -  board is implied
+./ (x +"1 y) (<"1@[ { ]) board   NB. any spaces filled already?

run =: {{   NB. y is number of cycles to simulate.  Clears board.  Result is hwmk
jetx =: _1  NB. wraparound counter for jet pattern
hwmk =: 0  NB. highest filled cell
board =: 1 , 1 ,.~ ((4*y) , 7) $ 0  NB. the stack, with a boundary at right and bottom.  Bottom at 0 to convert height to 1-origin
piecex =. _1   NB. cyclic piece number
for. i. y do.
  piece =. pieces {::~ piecex =. 5 | >: piecex  NB. get next piece  to drop
  pos =. (hwmk+4),2  NB. drop point
  while. do.
    NB. move left-right according to jet
    if. -. piece collision npos =. pos + 0,getjet'' do. pos =. npos end.  NB. move LR if not blocked
    NB. move down
    if. piece collision npos =. pos + _1 0 do. break. end.  NB. stop moving if drop blocked
    pos =. npos
  NB. Resting place found, update board and drop point
  board =: 1 (pos +"1 piece)} board
  hwmk =. hwmk >. pos +&{. {: piece  NB. get y of last cell, update if new max

Reading in the test input is trivial. I'll convert it to integer moves left or right.

   ]jets =: _1 1 {~ '>' = wd'clippaste'
1 1 1 _1 _1 1 _1 1 1 ...

I test on the first rock. After fixing the bugs I end up with the script shown above.

   ' *' {~ }:"1 |. board {.~ >: run 1

I keep only the valid rows of the board, reverse them top-to-bottom, discard the right-hand boundary, and convert to characters for easy reading. That's the right result, and I also get the right result on a few others. Finally,

   run 2022

Part 2 asks for a trillion cycles. I might be able to slip out for a cup of coffee while this is running.

Obviously there must be a cycle, and I need to find the length. There are two cyclic processes going on, the rock selection and the jets, and they will both have to repeat at the same time. In addition, there is the state of the rock pile: perhaps that has to match too, at least as far down as there are gaps. If I were being paid for this I would worry about the rock pile, but I hope I can pocket my star by looking only at the rocks and jets.

There may be a non-cyclic run-in prefix that I have to skip over. To get the lay of the land I will print some state information when the jets start a cycle. I modify the loop just a bit:

for_p. i. y do.
  while. do.
    NB. move left-right according to jet
    jet =. getjet''
    if. jetx=0 do. qprintf'p piecex hwmk ((hwmk+4),0)-pos ' end.

qprintf is a handy verb to print the value of an expression. It is in the format/printf addon which my startup script loads.

   run 200
p=0 piecex=0 hwmk=0 ((hwmk+4),0)-pos=0 _2
p=8 piecex=3 hwmk=15 ((hwmk+4),0)-pos=3 _3
p=14 piecex=4 hwmk=23 ((hwmk+4),0)-pos=2 _4
p=22 piecex=2 hwmk=39 ((hwmk+4),0)-pos=3 _3
p=29 piecex=4 hwmk=51 ((hwmk+4),0)-pos=6 _4
p=36 piecex=1 hwmk=61 ((hwmk+4),0)-pos=2 _4
p=43 piecex=3 hwmk=70 ((hwmk+4),0)-pos=4 _2
p=49 piecex=4 hwmk=78 ((hwmk+4),0)-pos=4 _2
p=57 piecex=2 hwmk=92 ((hwmk+4),0)-pos=3 _3
p=64 piecex=4 hwmk=104 ((hwmk+4),0)-pos=6 _4
p=71 piecex=1 hwmk=114 ((hwmk+4),0)-pos=2 _4
p=78 piecex=3 hwmk=123 ((hwmk+4),0)-pos=4 _2
p=84 piecex=4 hwmk=131 ((hwmk+4),0)-pos=4 _2
p=92 piecex=2 hwmk=145 ((hwmk+4),0)-pos=3 _3
p=99 piecex=4 hwmk=157 ((hwmk+4),0)-pos=6 _4
p=106 piecex=1 hwmk=167 ((hwmk+4),0)-pos=2 _4
p=113 piecex=3 hwmk=176 ((hwmk+4),0)-pos=4 _2
p=119 piecex=4 hwmk=184 ((hwmk+4),0)-pos=4 _2
p=127 piecex=2 hwmk=198 ((hwmk+4),0)-pos=3 _3
p=134 piecex=4 hwmk=210 ((hwmk+4),0)-pos=6 _4
p=141 piecex=1 hwmk=220 ((hwmk+4),0)-pos=2 _4
p=148 piecex=3 hwmk=229 ((hwmk+4),0)-pos=4 _2
p=154 piecex=4 hwmk=237 ((hwmk+4),0)-pos=4 _2

I was hoping for this. After a 3-line run-in, we are at a cycle that is 35 rocks long (calculated from p) and adds height of 53 (from hwmk). The values of piecex and pos, which describe the falling rock, show that they are exact cycles.

I could run it much longer and verify that the cycle has no dependence on the state of the rock pile, but I'm feeling lucky.

   0 35 #: 1000000000000
28571428571 15
   run 15+35
   78 + 28571428570 * 53

1000000000000 is 28571428571 cycles of 35 with 15 left over. 15 is still in the run-in, so I calculate the height at a point in the cycle, and add the height for all the cycles. Check.