1waffle1
|
  |
| Joined: 16 Oct 2007 |
| Total Posts: 16381 |
|
|
| 08 May 2013 06:16 PM |
I propose an efficiency competition.
Whoever can solve the largest number of hailstone sequences in the shortest amount of time wins.
The hailstone sequence is the sequenced produced by a number under the rules of the Collatz conjecture: If the number is even, divide by two; if the number is odd, multiply by 3 and add 1; repeat until you reach 1 (and for every positive integer, you will always reach 1.)
(by far not optimal) example of a solution:
local f = os and os.time or tick local t = f() local s = 0 for i = 1, math.huge do local n = i repeat if n%2 == 0 then n=n/2 else n=n*3+1 end until n == 1 if f()>=t+2 then s=s+2 print(i.." solved in "..s.." seconds ("..math.floor(i/s).." solved per second)") end end |
|
|
| Report Abuse |
|
|
dekkonot
|
  |
| Joined: 22 Dec 2010 |
| Total Posts: 6685 |
|
|
| 08 May 2013 06:18 PM |
...?
~ Non simpliciter Latinam legere ~ |
|
|
| Report Abuse |
|
|
1waffle1
|
  |
| Joined: 16 Oct 2007 |
| Total Posts: 16381 |
|
|
| 08 May 2013 06:19 PM |
if f()>=t+2 then s=s+2 t=f() |
|
|
| Report Abuse |
|
|
1waffle1
|
  |
| Joined: 16 Oct 2007 |
| Total Posts: 16381 |
|
|
| 08 May 2013 06:19 PM |
| Are you so confused that you have lost the ability to use words? Is something wrong? |
|
|
| Report Abuse |
|
|
dekkonot
|
  |
| Joined: 22 Dec 2010 |
| Total Posts: 6685 |
|
|
| 08 May 2013 06:21 PM |
I was confused slightly, but then I read it again and got the 3 words I missed.
~ Non simpliciter Latinam legere ~ |
|
|
| Report Abuse |
|
|
|
| 08 May 2013 06:47 PM |
| This is a very poorly phrased question, because you could simply precompute one string and print it out. Logical simiplifications would include something which is more or less this, so you can't prohibit the behavior of memoizing.. |
|
|
| Report Abuse |
|
|
|
| 08 May 2013 06:55 PM |
My overcomplicated function:
n = (((1/((n/2%1)*4))^(-1)/1*n)*1+(n/2%1+0.5)*n+((((1/((n/2/2%1)*4))^(-1)/1*(n/2))*1+(n/2/2%1+0.5)*(n/2))%1*2*1/.75))
So
n = math.random(100,500)
while n<3 do n = (((1/((n/2%1)*4))^(-1)/1*n)*1+(n/2%1+0.5)*n+((((1/((n/2/2%1)*4))^(-1)/1*(n/2))*1+(n/2/2%1+0.5)*(n/2))%1*2*1/.75)) end
n = (((1/((n/2%1)*4))^(-1)/1*n)*1+(n/2%1+0.5)*n+((((1/((n/2/2%1)*4))^(-1)/1*(n/2))*1+(n/2/2%1+0.5)*(n/2))%1*2*1/.75))
And yeah, I know this is definitely not the prettiest or most efficient code for this, but math is fun. |
|
|
| Report Abuse |
|
|
|
| 08 May 2013 06:56 PM |
Just realized that I could automate that last line by changing the condition.
n = math.random(100,500)
while n~=1 do n = (((1/((n/2%1)*4))^(-1)/1*n)*1+(n/2%1+0.5)*n+((((1/((n/2/2%1)*4))^(-1)/1*(n/2))*1+(n/2/2%1+0.5)*(n/2))%1*2*1/.75)) end |
|
|
| Report Abuse |
|
|
1waffle1
|
  |
| Joined: 16 Oct 2007 |
| Total Posts: 16381 |
|
|
| 08 May 2013 07:07 PM |
@Arceus Your over-complicated function is completely irrelevant to the competition.
@Blue Saving a string and then printing it is not solving the sequences. Solving the sequences in order to generate the string is. |
|
|
| Report Abuse |
|
|
cntkillme
|
  |
| Joined: 07 Apr 2008 |
| Total Posts: 44956 |
|
|
| 08 May 2013 07:09 PM |
More efficient:
This.That.All.None.At.Nine.PM.Then.Psych.Who.Cares.What.You.Say = -56 |
|
|
| Report Abuse |
|
|
|
| 08 May 2013 07:39 PM |
local t = os.clock local p = print
local n; local s = t(); for n = 1, math.huge do if n%1000 == 0 then p(n - 1 .. " @ " .. t() - s); end while n ~= 1 do if n%2 == 0 then n = n*.5 else n = n*3 + 1 end end end
|
|
|
| Report Abuse |
|
|
|
| 08 May 2013 07:40 PM |
| 1waffle1: It's exactly the same thing. If a function is deterministic, "optimization" should preevaluate it and substitute in the constant. Which is why this isn't a well defined problem. |
|
|
| Report Abuse |
|
|
1waffle1
|
  |
| Joined: 16 Oct 2007 |
| Total Posts: 16381 |
|
|
| 08 May 2013 07:59 PM |
| You can't solve the answer to a mathematical problem without using math to calculate the answer. That line seems clear and defined (oxymoron?). |
|
|
| Report Abuse |
|
|
|
| 08 May 2013 08:04 PM |
Let me explain.... Let's say we're trying to optimize the factorial function.
function fac(n) if n == 0 then return 1; end return fac(n-1) * n; end
You could get a linear boost for getting the factorial of N by memoizing values:
local t = {[0]=1,1,2,6,24,120,720} function fac(n) return t[n] or (n * fac(n-1)); end
And by increasing the length of 't', it will CONTINUE to get faster.
Now, here's a point. If you had asked "make the fastest function which will print the factorial of 100," if this list extended past length 100, then it would run in constant time. If we were asked for the 1000th prime, the logical program is this: print(7919);
Anything else is wasting time in computing the constant when we KNOW it will become 7919. |
|
|
| Report Abuse |
|
|
oxcool1
|
  |
| Joined: 05 Nov 2009 |
| Total Posts: 15444 |
|
| |
|
1waffle1
|
  |
| Joined: 16 Oct 2007 |
| Total Posts: 16381 |
|
|
| 08 May 2013 08:08 PM |
| If you list all of the hailstone sequences and then print how many you have and divide it by zero and say you solved them then you're just being dishonest. It would take more effort to cheat. |
|
|
| Report Abuse |
|
|
1waffle1
|
  |
| Joined: 16 Oct 2007 |
| Total Posts: 16381 |
|
|
| 08 May 2013 08:27 PM |
My solution seems like it would be hard to out-do.
Each number is eventually going to end up as 1. If, somewhere along the sequence, you end up with a number lower than the one you started with, you know you've already calculated it and can skip the rest of the calculations and move on to the next number. This means you can skip every even number. If you multiply an odd number by 3 and add 1, the result is going to be even, so you can divide it by 2 in the same iteration.
Roblox is stupid and thinks my code is full of profanity, so here is only the results of it.
11m solved in 2 seconds (5m/s) 24m solved in 4 seconds (6m/s) 37m solved in 6 seconds (6m/s) 50m solved in 8 seconds (6m/s) 64m solved in 10 seconds (6m/s) 77m solved in 12 seconds (6m/s) 88m solved in 14 seconds (6m/s) 98m solved in 16 seconds (6m/s) 109m solved in 18 seconds (6m/s) 122m solved in 20 seconds (6m/s) 135m solved in 22 seconds (6m/s) 148m solved in 24 seconds (6m/s) 162m solved in 26 seconds (6m/s) 176m solved in 28 seconds (6m/s) 190m solved in 30 seconds (6m/s) |
|
|
| Report Abuse |
|
|
|
| 08 May 2013 08:28 PM |
"Your over-complicated function is completely irrelevant to the competition."
My function follows the guidelines and completes the goal. How is it irrelevant? |
|
|
| Report Abuse |
|
|
1waffle1
|
  |
| Joined: 16 Oct 2007 |
| Total Posts: 16381 |
|
|
| 08 May 2013 08:43 PM |
| The while loop never ends, you're only checking one number, and after the first few iterations, it starts coming up with decimals. |
|
|
| Report Abuse |
|
|
|
| 08 May 2013 08:49 PM |
| I'm not seeing that behavior. Are you changing the code? |
|
|
| Report Abuse |
|
|
|
| 08 May 2013 08:57 PM |
| Oh, yep, I'm seeing it now. |
|
|
| Report Abuse |
|
|
1waffle1
|
  |
| Joined: 16 Oct 2007 |
| Total Posts: 16381 |
|
|
| 08 May 2013 09:27 PM |
| 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 |
|
|
| Report Abuse |
|
|
|
| 08 May 2013 09:38 PM |
> If, somewhere along the sequence, you end up with a number lower than the one you started with, you know you've already calculated it and can skip the rest of the calculations and move on to the next number.
I know they'll all end up with 1, so I'll skip the calculations since I know the solution to every single one already. :D |
|
|
| Report Abuse |
|
|
1waffle1
|
  |
| Joined: 16 Oct 2007 |
| Total Posts: 16381 |
|
| |
|
|
| 08 May 2013 11:22 PM |
717167973 solved in 60 seconds (12010568 solved per second)
I dun tink we will find one that cycles e.e |
|
|
| Report Abuse |
|
|