Hello
For part 2, I implemented a chinese remainder theorem dyad, built from
extended euclid gcd.
https://en.wikipedia.org/wiki/Chinese_remainder_theorem
egcd =: 4 : 0 NB. extended gcd
'a b c d s t' =. 1 0 0 1,x,y
while. r =. t - s*q =. <. t%s do.
c =. t [ a =. c-q*a [ t =. a
d =. t [ b =. d-q*b [ t =. b
s =. r [ t =. s
end. a,b,s assert. s = (a*x) + b*y
)
crt =: 4 : 0 NB. chinese remainder theorem
's t g'=.m egcd n['b n'=.y['a m'=.x
(<.m*n%g) (|,[) (a*n*t)+&(%&g) (b*m*s) assert. 0 = g | a-b
)
crt/ can then solve systems of equations where items are lists of
integer constraint followed by modulus.
If there are suggestions for better style/implementations I'd be
curious to hear advice.
Joseph
On 12/14/20, David Lambert <[email protected]> wrote:
> https://adventofcode.com/2020/day/13
> Part 2.
>
> I understand the problem sufficiently to solve the examples. I fear the
> run time of my program, which counts upward in increments of the maximum
> value starting from some residue, will take too long for the actual data.
> Please offer suggestions for a direct solution.
>
> Thanks, and be well. Dave.
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
