generic image
Processing...
  • Games
  • Catalog
  • Develop
  • Robux
  • Search in Players
  • Search in Games
  • Search in Catalog
  • Search in Groups
  • Search in Library
  • Log In
  • Sign Up
  • Games
  • Catalog
  • Develop
  • Robux
   
ROBLOX Forum » Game Creation and Development » Scripters
Home Search
 

Re: Efficiency competition

Previous Thread :: Next Thread 
1waffle1 is online. 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 is not online. dekkonot
Joined: 22 Dec 2010
Total Posts: 6685
08 May 2013 06:18 PM
...?

~ Non simpliciter Latinam legere ~
Report Abuse
1waffle1 is online. 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 is online. 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 is not online. 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
BlueTaslem is not online. BlueTaslem
Joined: 11 May 2008
Total Posts: 11060
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
ArceusInator is not online. ArceusInator
Joined: 10 Oct 2009
Total Posts: 30553
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
ArceusInator is not online. ArceusInator
Joined: 10 Oct 2009
Total Posts: 30553
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 is online. 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 is not online. 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
UnknownForgotten is not online. UnknownForgotten
Joined: 02 Jan 2011
Total Posts: 6
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
BlueTaslem is not online. BlueTaslem
Joined: 11 May 2008
Total Posts: 11060
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 is online. 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
BlueTaslem is not online. BlueTaslem
Joined: 11 May 2008
Total Posts: 11060
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 is not online. oxcool1
Joined: 05 Nov 2009
Total Posts: 15444
08 May 2013 08:04 PM
"oxymoron"
wut?
Report Abuse
1waffle1 is online. 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 is online. 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
ArceusInator is not online. ArceusInator
Joined: 10 Oct 2009
Total Posts: 30553
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 is online. 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
ArceusInator is not online. ArceusInator
Joined: 10 Oct 2009
Total Posts: 30553
08 May 2013 08:49 PM
I'm not seeing that behavior. Are you changing the code?
Report Abuse
ArceusInator is not online. ArceusInator
Joined: 10 Oct 2009
Total Posts: 30553
08 May 2013 08:57 PM
Oh, yep, I'm seeing it now.
Report Abuse
1waffle1 is online. 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
xXxMoNkEyMaNxXx is not online. xXxMoNkEyMaNxXx
Joined: 03 Oct 2008
Total Posts: 3120
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 is online. 1waffle1
Joined: 16 Oct 2007
Total Posts: 16381
08 May 2013 10:31 PM
prove it.
Report Abuse
xXxMoNkEyMaNxXx is not online. xXxMoNkEyMaNxXx
Joined: 03 Oct 2008
Total Posts: 3120
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
Previous Thread :: Next Thread 
Page 1 of 1
 
 
ROBLOX Forum » Game Creation and Development » Scripters
   
 
   
  • About Us
  • Jobs
  • Blog
  • Parents
  • Help
  • Terms
  • Privacy

©2017 Roblox Corporation. Roblox, the Roblox logo, Robux, Bloxy, and Powering Imagination are among our registered and unregistered trademarks in the U.S. and other countries.



Progress
Starting Roblox...
Connecting to Players...
R R

Roblox is now loading. Get ready to play!

R R

You're moments away from getting into the game!

Click here for help

Check Remember my choice and click Launch Application in the dialog box above to join games faster in the future!

Gameplay sponsored by:
Loading 0% - Starting game...
Get more with Builders Club! Join Builders Club
Choose Your Avatar
I have an account
generic image