Yes, a nice insight, I suppose, but only nice, and by no means
necessary!
Many Project Euler problems require this sort of thing in the tool-box!
Also, some sort of counting of cases is often nearly essential for PE.
One of my finite arithmetic routines, written pre-{{ ... }}
NB. Matrix x to high power y modulo m
NB. (adapted from Roger Hui, perhaps...)
mMpower =: 1 : 0
:
M =. = i.# M0 =. x
b =. #:y
mm =. <.@:(m| +/ . *)
while.#b do.
if. {:b do. M =. M0 mm M end.
M0 =. mm~ M0 NB. square it
b =. }:b
end.
M
)
Set the modulus to 0 here:
count 3 4 3 2 1
0 1 1 2 1 0 0 0 0
+/(count 3 4 3 2 1) +/ . * (mat1(0 mMpower) 80) NB. mat1 as Raul's
9x9 matrix
5934
+/(count 3 4 3 2 1) +/ . * (mat1(0 mMpower) 256)
26984457539
Advent of Code problems are, mostly, nothing like as demanding of
computer resources as PE. The time improvement is pretty irrelevant
here:
ts'+/(+/ . *)&mat1^:256 ct' [ ct =: count 3 4 3 1 2
5.5e_5 3008
ts'+/ct +/ . * mat1(0 mMpower) 256'
2.17e_5 8512
(Once we've counted the different classes of fish, it's also pretty
irrelevant
how many are in the 300 samples.)
But it's good to practise for when we DO need the technique.
Cheers,
Mike
On 27/12/2021 14:39, Raul Miller wrote:
That's a really good insight.
Conceptually, this would be
1 (<0 6)}(=/1|.])i.9
0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1 0
But we want to multiply on the right (for ^:) instead of on the left.
So, instead
M=: |:1 (<0 6)}(=/1|.])i.9
or
M=: 1 (<6 0)}(=/~1|.])i.9
+/M+/ .*^:256 <:#/.~(i.9),3,4,3,1,2
26984457539
Or, squaring M, 8 times:
+/(+/ .*~^:8 M)+/ .*<:#/.~(i.9),3,4,3,1,2
26984457539
Actually, the squaring technique would have allowed us to left
multiply our representation of the updates:
+/(<:#/.~(i.9),3,4,3,1,2)+/ .*+/ .*~^:8]1(<0 6)}(=/1|.])i.9
26984457539
Pretty concepts.
Thanks,
--
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
