Good day:
I've been struggling a couple weeks long to solve Project Euler
problem 14 in a reasonable time, but the best I can get takes much
much longer in my machine. Several hours.
Well, my current solution is this:
collatz =. verb define
if. 1= y do. y return. end.
if. 0= 2|y do. y=. -:y else. y=.>:3*y end.
)
reduceTable=. verb define
NB. y is expected to be a 2-row table
NB. with starting numbers on first row
NB. and a number in the collatz sequence on the 2nd.
if. 1= $1{y do. y return. end.
NB. nmemonics / definicions
range =. 0{y
seq =. 1{y
NB. operations
NB. compute the following number in the collatz sequence for each of
NB. the candidates. Take off the table a candidate if it appears in the
NB. sequence of any other candidate (as they are for sure not the
NB. ones with the longest sequence).
seq =. (aux=: -.(range e. aux)+.(aux e. 1 2 4))# aux=: collatz"0 seq
range=. aux#range
NB. reconstruction
range ,: seq
)
reduceTable^:_ ,:~ >:i.1e6
NB. another attempt
reducirLista =. verb define
memo =. 1 1
list =. }. list=.>:i.y
while. 1<#list do.
NB. compute the collatz sequence for the next number
c =. collatz^:(<_) {. list
NB. take out of the list of candidates ... (vid supra).
list =. (list -.@:e. c)#list
NB. remember the canditate and it's collatz sequence lenght.
memo =. memo, ,: ({.,#)c
end.
)
By reading spoilers, it seems the way to go is through memoization.
Despite my attempts with M. here and there, I have found no satisfying
solution (satisfying = fast).
Can someone point me to a different approach and to a memoization with
J tutorial?
Regards,
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
