Yes, the second part was again pretty trivial, at least when, as in
J, you can
use the power operation.
I seem to have solved it on my iPad, running iOS 12.5.5, which is too
obsolete to
support Ian Clark's new J902 version, so it's stuck in J701, so not up
to {{ }} and
lots more.
I can never remember the tessellation idiom when I need it, so I
ravelled the
octopuses, there are exactly 100, and set up a global array of
neighbours.
Here are some:
7 {. nbrs NB. I've removed the horizontal box chars, as alignment fails
|1 10 11|0 2 10 11 12|1 3 11 12 13|2 4 12 13 14|3 5 13 14 15|4 6 14 15
16|5 7 15 16 17|
(20 + i.4) { nbrs
|10 11 21 30 31|10 11 12 20 22 30 31 32|11 12 13 21 23 31 32 33|12 13 14
22 24 32 33 34|
I won't bore you with their derivation, but I suppose this is the main
difference between my
approach and Raul's - I don't need a "propagate" function, at the
expense of a global boxed
list of coordinates.
Here's the step function much as I wrote it - the name was all my own
work! - there was no
need to soup it up for speed or space given the small size of the problem.
step =: 3 : 0
if. */ 0 = y do.
y
return.
end.
d =. >: y NB. Initial increment to "energy"
done=. ''
while. 10 e. d do.
j10 =. I. 10 = d NB. indices of flashers
i10 =. j10 -.~ ; j10 { nbrs NB. indices of their neighbours
done=. ~. done, j10
c10 =. #/.~ i10 NB. count up flashes seen by those nbrs
i10 =. ~. i10
d10 =. 10 <. c10 + i10 { d
d =. d10 i10 } d NB. could be cleaner!
d =. 0 done } d
end.
d
)
I didn't wrap the application of step for part 1. Here's the example
result:
$ex NB. the data is ravelled...
100
+/0=,step^:(i.11) ex
204
As I said, part 2 is trivial for J-users:
<:#step^:a: ex NB. on the sample data again
195
On 01/01/2022 00:17, Raul Miller wrote:
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.
--
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
