https://adventofcode.com/2021/day/18
For day 18, the puzzle was about "snailfish sums".
sample=:{{)n
[1,2]
[[1,2],3]
[9,[8,7]]
[[1,9],[8,5]]
[[[[1,2],[3,4]],[[5,6],[7,8]]],9]
[[[9,[3,8]],[[0,9],6]],[[[3,7],[4,9]],3]]
[[[[1,3],[5,3]],[[1,3],[8,7]]],[[[4,9],[6,9]],[[8,2],[7,3]]]]
}}
Each line here was a "snailfish number".
A snailfish number consists of pairs of regular numbers and/or pairs.
And, each snailfish number has five operations defined on it: reduce,
explode, split, addition and magnitude:
reduce is a stepwise operation. A reduce step means that the leftmost
regular number which is greater than 9 explodes, and the leftmost
element of a pair which has been nested inside four other pairs
explodes. reduce itself is reducestep^:_ and is a required operation
on all snailfish numbers.
explode is a single step operation on a pair of regular numbers which
turns it into a single 0 in its containing pair.. If there's regular
numbers to the left of the pair, the left value from the exploding
pair is added to the rightmost of those regular numbers. If there's
regular numbers to the right of the pair, the rightmost value from the
exploding pair is added to the leftmost of those regular numbers.
split is a single step operation on a single regular number, which
turns it into a pair: (<.,>.)@-:
addition combines two snailfish numbers into a pair (which is then reduced).
The magnitude of a regular number is that regular number. The
magnitude of an x,y pair is (3*magnitude x)+2*magnitude y
------------------------------------------
At first, it might seem that putting pairs in boxes is the right
approach here. However, that makes the "explode" operation extremely
complicated. So, instead, I used a two row array, where the first row
was nesting depth and the second row was regular numbers.
To convert the textual representation of snailfish numbers into this
form, I used:
use=: {{
depth=. +/\-/'[]'=/y
sel=. _1|.0 1 E.mask=.-.y e. '[,]'
vals=.".mask #inv mask#y assert. (+/sel)=#vals
(sel#depth),:vals
}}
Next, I implemented an explode which repeated until no depths were
greater than 4 and a split which continued until no regular numbers
were greater than 9 (exploding each step of the way when depth gets
deep enough).
NB. the leftmost deepest pair is always the first pair at that depth
explode=: {{
'depth vals'=. y
while. 4 < d=.>./depth do.
'j k'=.0 1+depth i.d
vec=. 0 0
loc=. j,k
mask=. k~:i.#vals
depth=. mask#(d-1) loc} depth
if. 0~:j do.
vec=. (+/vals{~j-1 0),vec
loc=. (j-1),loc
end.
if. k<(#vals)-1 do.
vec=. vec,+/vals{~k+0 1
loc=. loc,k+1
end.
vals=. mask#vec loc}vals
assert. depth -:&# vals
end.
depth,:vals
}}
NB. split always creates a pair one deeper than the number it replaces.
split=: {{
'depth vals'=. y
lim=. (#vals)-1
while. lim>: j=. vals i.&1@:> 9 do.
pair=. (<.,>.)-:j{vals
depth=.(d=.1+j{depth) (j+0 1)} depth#~rep=.1+j=i.#depth
vals=. pair (j+0 1)}vals#~rep
if. 4<d do.
'depth vals'=. explode depth,:vals
end.
lim=.(#vals)-1
end.
depth,:vals
}}
These routines are a bit verbose, but the problem specification
requires information be lost in a specific sequence, and I could not
think of how to parallelize that, nor could I figure out how to
further encode these operations numerically. (I did start to wish that
the jqt text editor would give me quick shortcuts to indent/outdent
blocks of code.)
Anyways, with these routines, reduce looks like this:
reduce=: {{
split explode y
}}
I do not need to use an expression of the form reduce^:_ because split
(and explode) already implement their own ^:_ mechanisms.
And, add looks like this:
add=: {{
reduce 1 0+x,.y
}}
And, magnitude looked like this:
magnitude=: {{
'depth vals'=. y
for_d. 1+i.->./{.y do.
sel=. d=depth
sums=. _2 +/\ (sel#vals) * f=.(+/sel)$3 2
selb=. sel#inv b=.2|f
mask=. (d>depth)+.selb
depth=. (d-1)<.mask#depth
vals=. mask #sums (I.selb)} vals
end.
}}
And, the part A implementation was:
a18=: {{
magnitude ;add~each/|.<@use;._2 y
}}
I used |. because the puzzle specified that addition proceeds from
left to right, and this kind of addition is not associative. It's also
not commutative, so I also had to use add~ instead of simply add, to
retain the original pair order here.
For part B, the problem was to find the largest magnitude from adding
two of the given sailfish numbers. So that was basically max reduce of
an outer produce
b18=: {{
fish=: <@use;._2 y
>./,magnitude@add every/~ fish
}}
FYI,
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
