So... looking at my implementation for day 18, I was a bit dissatisfied.
To some extent, the code is noisey because the specifications are a
bit arbitrary. (That's not at all unusual, of course.)
That said, it's possible to take advantage of some regularities in
what we're doing here.
First off, it's possible to express the sailfish parser more concisely.
use=: {{
N=.-.y e. '[,]'
((1 0 E.-.N)#+/\-/'[]'=/y)|:@,.".N}' ',:y
}}
This is basically the same algorithm I was using previously, but with
fewer names involved. I am not sure whether this is an improvement,
but I am also not sure that the people who can't work out what this
does would be able to work out what the earlier version did, either...
Next, for the explode operation, there's two fundamental components.
There's the part where a value is added into an adjacent pair, and
there's the part where we zero out the original pair into a single
number.
The addition part, for just the left hand side, might look like this:
blastL=: }:"1 + 0 ,: 1 }. -@{:@$ {. {:@,
This will reduce the length of that segment by 1:
$blastL i.2 1
2 0
$blastL i.2 5
2 4
And, it preserves the values in the first row, and adds the final two
numbers in the second row (assuming that there are two such numbers):
blastL i.2 4
0 1 2
4 5 13
For the other side, we can use reverse:
blastR=:blastL&.:(|."1)
In other words, if we have a sailfish S whose offending depth has an
index of 3, we would want blastL 4 {."1 S for the left side, and
blastR 3 }."1 S for the right side. We also need a centerpiece to put
between these two segments. And, since we'll be using ^:_ we need an
identity operation when we're done exploding the fish.
For the identity operation, we can throw an error and then use blast
::], this means that we can use i. to find the blast target and { to
construct the centerpiece. This combination will throw an error when
we're done.
Also, the structure of hooks favors putting a calculated value on the
right. So we can instead use (blast ::[ target)^:_
That gives us:
blastC=: 1 0 * _1 + {"1~
blast=: blastL@({."1~ >:) ,. blastC ,. blastR@(}."1~ >:)
btarget=: (i. 5 >. >./)@{.
explode=:(blast ::[ btarget)^:_
And, testing this against examples, it seems to provide the specified
level of fish destruction. For example:
use '[[[[[9,8],1],2],3],4]'
5 5 4 3 2 1
9 8 1 2 3 4
explode use '[[[[[9,8],1],2],3],4]'
4 4 3 2 1
0 9 2 3 4
----
For split, we're going the other direction. Instead of going for the
deepest pair, though, we're going for the leftmost multidigit number:
ctarget=: (9&< i. 1:)@{:
Once we have that, it's straightforward to chop that number in two and
to glue on the surrounding pieces of fish (which we then explode):
chop=: {."1 ,. (>:@[,:(<.,>.)@-:@])/@:({"1) ,. }.@}."1
split=: explode@(chop~ ::[ ctarget)^:_
And, this seems to work, also:
explode '[[[[4,3],4],4],[7,[[8,4],9]]]' (1 0 + ,.)&use '[1,1]'
4 4 3 3 4 4 2 2
0 7 4 15 0 13 1 1
split explode '[[[[4,3],4],4],[7,[[8,4],9]]]' (1 0 + ,.)&use '[1,1]'
4 4 3 4 4 4 4 2 2
0 7 4 7 8 6 0 8 1
And, actually, because of how split works, we do not need to
"pre-explode" our fish.
split '[[[[4,3],4],4],[7,[[8,4],9]]]' (1 0 + ,.)&use '[1,1]'
4 4 3 4 4 4 4 2 2
0 7 4 7 8 6 0 8 1
So we do not need a separate reduce verb -- split does that job.
This gives us:
add=: [: split 1 0 + ,.
Finally, we need a magnitude operation. This one puzzled me for a bit
-- and then I realized. I can refactor the steps of the magnitude
operation into a length preserving arithmetic stage and a length
reducing structural phase.
First, though, I need to identify the deepest columns:
mmask=: (= >./)@{.
Then, I can do the multiply by 2 and 3 and add part on the deepest
pairs. I throw in infinity as a placeholder here, so that the result
is the same length as the argument:
mfill=: _ (,@,.) _2 +/@:*&2 3\ ]
I will later need to clean out those infinities:
mclean=: #"1~ _ > {:
Now, a single step in the magnitude calculation looks like this:
mag=:mclean@((*"1 -.) + (* <:@{.)~ ,: ] #inv mfill@:(# {:)~) mmask
And, I perform one of those steps for each of the depth values in the fish:
magnitude=: [:{: mag^:(>./@{.)
This leaves me with the same a18 and b18 expressions as I had previously:
a18=: {{
magnitude ;add~each/|.<@use;._2 y
}}
b18=: {{
fish=: <@use;._2 y
>./,magnitude@add every/~ fish
}}
...
Now, of course, some people might be wondering: is it really an
advantage to split factor the magnitude operation like that?
And, I think that the answer is arguably: yes.
There's a few examples worth thinking about here -- but it all relates
back to hardware constraints. When we are parallelizing (for example,
porting an algorithm to a GPU), length preserving calculations let us
ship components of an expression to general purpose chunks of
computational hardware. The length preserving aspect means that
there's a simple (1:1) mapping between the "before" and "after" value
indices.
Now, obviously, being an optimization, this isn't what we always want
to do. But I think it's a useful exercise, even if this particular
example is a bit ... fishy.
FYI,
--
Raul
On Fri, Jan 7, 2022 at 8:25 PM Raul Miller <rauldmil...@gmail.com> wrote:
>
> 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
