[wellwell]

Hi there, i was trying out one of the tasks at project euler.
the task is as following: "The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?"

I try with the following:

laps=1
counter = 1
topnumber = 0
sequencelength=0
nextnumber = 0


def next(number)
	if(number%2 == 0)
	counter+=1
		 nextnumber =(number/2)
		 return true
		
	end
	if number==1
	return false
	end
	if(number%2!=0)
	counter+=1
	 nextnumber =(3*number+1)
	 return true
	end
end
while laps < 1000001
nextnumber=laps
	while(next(nextnumber))

	end
	if (counter > sequencelength)
	sequencelength = counter
	topnumber=laps
	counter = 1
	laps+=1
end

puts topnumber

I get 3 errors.
Line 26 and 28 gives "void value expression"
Line 34 gives "syntar error unexpected $end, nexpecting kEND"

How can I correct my errors, and is my idea even worth anything? thanks.

edit: just noticed a whole lot of things that are wrong.

This post has been edited by wellwell: 12 July 2011 - 04:34 PM

[wellwell]

After some adjustements of the code the error
"syntar error unexpected $end, nexpecting kEND" remains.

the new code is the following.

laps=1
counter = 1
topnumber = 0
sequencelength=0
nextnumber = 0
newone =true


def new(number)
	if(number%2 == 0)
	counter+=1
		 nextnumber =(number/2)
		 newone = true
		
	end
	if number==1
 newone = false
	end
	if(number%2!=0)
	counter+=1
	 nextnumber =(3*number+1)
	 newone = true
	end
end
while laps < 1000001
nextnumber=laps
	while(newone)
	new(nextnumber)

	end
	if (counter > sequencelength)
	sequencelength = counter
	topnumber=laps
	counter = 1
	laps+=1
end

any suggestions?

[sepp2k]

In ruby error messages, $end refers to the end of file and kEND refers to the keyword end. So the error message is telling you that ruby found the end of file when it expected the keyword end. In other words you're missing an end somewhere.

In this case you're opening a while loop in line 25 and opening an if statement in line 31, but you have only one end at the end. You'd need two: one to close the if and one to close the while.

Note that this would be much more easily apparent if you'd indent your code properly. I recommend using an editor which automatically indents your code.

[Karel-Lodewijk]

Since you asked for suggestions. You can make this a lot faster by tabeling. Every time you encounter value n that is smaller than you initial value, you will have already calculate how many steps it took from that number to get to one. So you can save a lot of computational time by doing not calculating it again. You can do this (in pseudocode)

hash = {}

every time you find a n, you do:
[code]
hash[n] = sequencelength

And while doing the steps, you do

if hash.include? n
  sequence_length = steps_done_so_far + hash[n]
end
and don't forget to put this value back into the hash.

By tabeling you can often make an algorithm much more efficient if it contains overlapping subproblems with very little thought. This kind of techniques fall under dynamic programming, look it up on wikipedia if you're interested.

This post has been edited by Karel-Lodewijk: 12 July 2011 - 09:50 PM