ShareMyScreen/AdventOfCode/2022/17/PyroclasticFlowJP
Entire solution
i17=: freads '17.txt'
NB. Part 1: how high after 2022 blocks fell?
NB. block el coordinates (x=0 is closest to floor (hence flip |.), y=0 is closest to left wall)
bl=: ($#:I.@,)@:|.@:#:&.> (,15);2 7 2;1 1 7;1 1 1 1;3 3 NB. blocks
tetris=: {{ NB. x: number of blocks to drop; y:i17; straightforward simulation.
j=. _1 1{~'<>' i. }: y NB. parse jet pushes in coords
f=. ($#:I.@,) 1 7$1 NB. init field (0 is floor) in coords
'bn ji'=. 0 NB. set block num & jet index
bc=. 4 2+"1 bn{::bl NB. block coord
while. bn<x do.
NB. L/R if possible
if. f (+./@:e.~ +: (0&> +./@:+. 6&<)@:({:"1)@]) bu=. (0,ji{j) +"1 bc do. bc=.bu end.
NB. down:
if. f +./@:e.~ bu=._1 0 +"1 bc do. NB. hit block, stay
NB. discard all from field below full line if present.
if. *./ (i. 6) e. f ({:"1@[ #~ e.&:({."1)) bc do.
f=. f ([ #~ (>: <./)&:({."1)) bc
end.
NB. update fl to include block coords
f=.f,bc NB.f \:~@, bc
NB. next block, inc block num
bc=. (bl{::~5|bn=.>:bn)+"1(4+>./{."1 f),2
else. bc=. bu end. NB. if not, drop
ji=. (#j)&|@:>: ji NB. get next jet direction
end.
>./{."1 f NB. Highest block
}}
NB. Part 2: now for the first 1e12 rocks :/
cyctetris =: {{
NB. do tetris as before, but keep heights and see after which number of blocks we get a repeat in differences
j=. _1 1{~'<>' i. }: y NB. jet pushes in coords
f=. ($#:I.@,) 1 7$1 NB. init field (0-2 is floor)
'bn ji'=. 0 NB. set block num & jet index
bc=. 4 2+"1 bn{::bl NB. init block coord
height=. 0$0 NB. placeholder for heights
while. bn<x do.
NB. L/R: move if not occupied and in bounds
if. f(+./@:e.~ +: (0&> +./@:+. 6&<)@:({:"1)@]) bu=. (0,ji{j) +"1 bc do. bc=.bu end.
NB. down: if no block down
if. f+./@:e.~ bu=._1 0 +"1 bc do. NB. hit block, stay
NB. if block closed room entirely (i.e. all columns occupied in at least one location), discard previous block coords
if. *./ (i.6) e. f({:"1@[ #~ e.&:({."1)) bc do.
f=. f ([ #~ (>: <./)&:({."1)) bc
else.
NB. update f to include current block coords
f=.f,bc
end.
NB. next block, inc block num
bc=. (bl{::~5|bn=.>:bn)+"1 (4+>./{."1 f),2
NB. add height record
height=. height,>./{."1 f NB. on full f, not fneigh as it might be too deep to capture the top
NB. every 1000 blocks, check whether cycle
if. 0=1000|bn do.
NB. based on height, find cycles
for_mu. (#bl) ([ * [: i.&.<: <.@%~) 3<.@%~ #height do.
NB. cycle if tailing boxes repeat 2 times or more
if. 2<:+/hi=.*./\.2-:/\hb=.(,.,~mu)];._3]2-~/\0,height do.
NB. could find shortest preamble length, but unnecessary.
NB. height before cycles
hp=. +/ , hb {.~ >: hi i: 0
NB. height per cycle
hc=. +/ hlb=._1 { hb
NB. # full cycles
nfc=. mu <.@:%~ np=.x-mu*hi i. 1
NB. # of blocks in remainder
nr =. np-mu*nfc
NB. height of remainder
hrem=. nr +/@{. hlb
hp+(hc*nfc)+hrem return.
end.
end.
end.
else. bc=. bu end. NB. if not stopped, drop
ji=.(#j)&|@:>: ji NB. increase jet push counter
end.
NB. reached block count before cycle discovered
{:height
}}
part1=:2022&tetris
part2=:1e12&cyctetris
(part1;part2)i17 NB. get solutions for parts 1 and 2
Part 1
Part 1 asks for simulating a sort of Tetris game, and finding out how high the stack of blocks ends up being. Each block gets pushed left and right by volcanic jets as it falls, left and right (if the block can move). Both the block types and the jet directions wrap around if the end is reached. Part 1 asks for the height after 2022 blocks have dropped, this is well in reach for a simple simulation.
I store the floor and all blocks already fallen as list of occupied coordinates.
bl=: ($#:I.@,)@:|.@:#:&.> (,15);2 7 2;1 1 7;1 1 1 1;3 3 NB. block types
The simulation verb tetris takes as left argument the number of blocks to drop, and as right argument the input:
tetris=: {{ NB. x: number of blocks to drop; y:i17; straightforward simulation.
j=. _1 1{~'<>' i. }: y NB. parse jet pushes in coords
f=. ($#:I.@,) 1 7$1 NB. initialise field (0 is floor) in coords height, L/R
'bn ji'=. 0 NB. set block num & jet index
bc=. 4 2+"1 bn{::bl NB. falling block coords
while. bn<x do. NB. drop the required number of blocks
NB. L/R if possible
if. f (+./@:e.~ +: (0&> +./@:+. 6&<)@:({:"1)@]) bu=. (0,ji{j) +"1 bc do. bc=.bu end.
NB. down:
if. f +./@:e.~ bu=._1 0 +"1 bc do. NB. hit block, stay
NB. discard all from field below full line if present, and add bc
if. *./ (i. 6) e. f ({:"1@[ #~ e.&:({."1)) bc do.
f=. f (],~[ #~ (>: <./)&:({."1)) bc
else.
f=. f,bc NB. add current block to field, as it's done
end.
NB. next block, inc block num
bc=. (bl{::~5|bn=.>:bn)+"1(4+>./{."1 f),2
else. bc=. bu end. NB. if not, drop
ji=. (#j)&|@:>: ji NB. get next jet direction
end.
>./{."1 f NB. Highest block
}}
The checks in the first if. ... end. construct create a shifted version bu of the falling block coordinates bc and keeps it if none of the following is true (+:):
- any updated block coordinate is already in the field of floor and fallen blocks:
f +./@:e.~ bu - any updated block second coordinates goes out of the side bounds [0, 6]:
f (0&> +./@:+. 6&<)@:({:"1)@] bu
The second if. condition checks whether to stop, or whether the block can move down (else). If the block stops, I check whether it completes an entire line, and if so, discard all coordinates in the field below it, as they cannot be reached anymore. For part 1, this optimisation is not great (like 20% faster), as it's triggered only once, but for part 2 it becomes more relevant (almost 4 times faster). Both cases of this if. add bc to f as the block has finished falling. After this, the block number is incremented, the next block is selected and its coordinates set to show at the correct location, i.e. on the 4th line above the previous, and at square 2 step from the left wall.
In any case, if the block down movement is complete, the next jet index is loaded, and the loop continues. I tried a solution using integers to store blocked squares: the units store the left/right coordinate, and the tens and up store the height. While it was marginally faster for part 1 faster it was a whole lot slower for part 2; it seems faster lookups don't outweigh the cost of splitting numbers in digits.
Part 2
Part 2 asks for doing the same but for 1e12 blocks. As this is clearly too much to simulate, there has to be a cycle: Part 2 follows the same scheme as part 1, but when a block lands and the block number is a multiple of 1000, I check if a cycle is present. I didn't really have a clue how to formally do this, so I settled for the following heuristic, inserted after selecting the next block to be dropped:
...
NB. add height record
height=. height,>./{."1 f
NB. every 1000 blocks, check whether cycle
if. 0=1000|bn do.
for_mu. (#bl) ([ * [: i.&.<: <.@%~) 3<.@%~ #height do.
NB. cycle if tailing boxes repeat 2 times or more
if. 2<:+/hi=.*./\.2-:/\hb=.(,.,~mu)];._3]2-~/\0,height do.
NB. height before cycles
hp=. +/ , hb {.~ >: hi i: 0
NB. height per cycle
hc=. +/ hlb=._1 { hb
NB. # full cycles
nfc=. mu <.@:%~ np=.x-mu*hi i. 1
NB. # of blocks in remainder
nr =. np-mu*nfc
NB. height of remainder
hrem=. nr +/@{. hlb
hp+(hc*nfc)+hrem return.
end.
end.
end.
...
I keep the heights after every dropped block, and every 1000 dropped blocks, I check whether there are any cycles of lengthsmu of multiples of 5 (since there are 5 blocks) that repeat at least twice, so up to 3 <.@%~ #height. For each, I check whether the pair-wise differences of the height, when packed together in slices of length mu (saved in hb), and check when at least two tailing repetitions are present (the indices of the repetitions being saved as hi for further use), i.e. at least the last 3 length-mu slices are the same. If so, it means we ran into a cycle of length mu. From there I need to figure out the following:
- pre-cycle height hp, which is the sum of the first mu-length height differences we kept;
- the height per cycle hc, which is the sum of the last mu-length slice of hb (stored as hlb);
- number of full cycles nfc;
- height of the blocks in the remainder hrem, i.e. the last non-complete cycle before arriving at 1e12;
Then, the final height is hp + (nfc * hc) + hrem. While this works in just over 2s, it feels a bit heavy handed, and there is likely a better solution.