https://adventofcode.com/2021/day/11
The story for the day 11 puzzle is that we have 100 octopuses (10
rows, 10 columns) which are flashing, each with an intensity level
which is a single digit number:
sample=:".@>;._2{{)n
5483143223
2745854711
5264556173
6141336146
6357385478
4167524645
2176841721
6882881134
4846848554
5283751526
}}
The 'flashing' algorithm being applied here is:
(1) increment every octopus's intensity by 1.
(2) every octopus flashes when its intensity increases past 9.
(3) every flash increases the intensity of the eight adjacent
octopuses by 1. Adjacent, here, means horizontally adjacent or
vertically adjacent or diagonally adjacent.
(4) Iterate steps 2 and 3 until no more octopuses increase their
intensity past 9.
(5) Every octopus which flashed has its intensity set to zero.
This algorithm is a single "step" in a time sequence.
The problem for part A was to count the total number of flashes in the
first 100 steps.
My initial implementation was rather messy. Here's a cleaned up version:
First, I needed a way of propagating those 1s from adjacent flashes.
Note that we can simplify here, because we do not care about the exact
intensity of an octopus which has already flashed.
propagate=: [:+/"1 (1,:3 3) ,;._3 pad
pad=: 0,0,.0,~0,.~]
With that, I could build my step function:
step=: {{
mask=.1"0 y
next=. 1+y
while. 1 e.,extra=. 9<next*mask do.
prop=. propagate extra*mask
mask=. mask * 0=extra
next=. next+prop
end.
mask*next
}}
It seems like I ought to be able to make that simpler, but I keep
stumbling over my need to determine whether an adjacent octopus had
incremented past 9 previously or not.
That said, the last line could have been:
(* <:&9) next
Anyways, with a step function, my part A solution looked like:
aoc11a=:{{
+/0=,step^:(1+i.100) y
}}
But
aoc11a=: {{+/0=,step^:(i.101) y}}
would have worked just as well.
The second part of the puzzle was to determine which step had all of
the octopuses flash simultaneously. I just brute forced that:
aoc11b=: {{
k=. 0
next=. y
while. -.*/0=,next do.
next=. step next
k=. k+1
end.
}}
Though this would have also worked:
more=: 0=*/@,@:=&0
#}.step^:more^:a: sample
195
I think that the "tricky" part for this puzzle was buried in part A,
where we had to count those flashes, because of the way they
propagated.
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
