I've been working on various Project Euler problems in J, and I seem to
always get stuck whenever a problem requires excessive/lengthy recursion.
In particular, I've been working on problem number 14, which asks what
starting value (under 1 million) produces the longest Collatz sequence.
Now, I started out writing some silly procedural code, mostly to get a
handle on what I was trying to do. Don't bother deciphering it too
carefully:
PE14=: 3 : 0
NB. length is a list of 1 followed by <:y zeroes
length=: $. multmask~ <: y
usedNums=: 1
for_i. i. &. <: y do.
collatz=: 1 $ i
while. -. usedNums e.~ {: collatz do.
collatz=: collatz , nextColl {: collatz
end.
indices=: <: }: collatz
oldLength=: length {~ <: {: collatz
newLengths=: |. >: oldLength + i. # indices
mask=: indices < # length
indices=: mask # indices
newLengths=: mask # newLengths
length=: (newLengths) indices} length
usedNums=: usedNums , >: indices
end.
>: (i. >./) length
)
It basically keeps track of how long each Collatz sequence is, and whenever
a new one is generated, it adds the existing length value to however many
new numbers are added to the front end.
Anyway, that was too slow, and then the adverb M. was recommended to me.
That led me to this new verb:
PE14=: >: @ $: @ (-: ` (>: @ (3&*)) @. (2&|)) ` 1: @. (1&=) M."0
One would have to pass in >: i. y to this one and find the largest length
from that list.
It works, but it seems to take just as long as my procedural verb to
complete. By the time any significantly large ceiling is specified, the J
terminal crashes. I have a feeling that, although slightly more terse, this
new verb is no better than the previous one.
Is there any other method in J to make recursion more efficient? How might
I make the J terminal more tolerant to extended periods of computation? Am
I thinking about this problem in an incorrect manner?
Thank you for taking the time to respond to this!
--
-Neill
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
