Introduction:
Summer evenings may be so borings, we all know the “lazy dog layed on sofa” habit takes over! So why not gettin involved into an as3 contest?
Contest’s name comes from the well know trash-movie, with a lower time limit (15seconds is the time before flash player goes in timeout).
So, what are you suppose to do? Write code that solve the following problem in less than 15seconds.
Well, the main aim of the contest is to reach the lowest time, the upperbound limit is just to let you know that a brutal force approach will not work this time!
Updates:
Deadline moved to 16th August
Goals of the contest:
1.Share knowledge
2.Recognize math as still a key skill, even on the daily work (i’ll come back on this as much as i can)
3.Get a chance to try a “think-before-code” approach to a complex problem.
4.Spend, I hope happy, hours on Optimizations, Data Structures and Algorithm complexity Topics.
Contest topic:
In math, as in Science in general, there are some still not solved problems.This means that we can’t give an answer to a particular question.
One of this problems comes from Lothar Collatz. His conjecture asks if for every n (with n an integer number) the iteration
always returns to 1. Actually this is formally undecidable even if there was (and still there is) a high number of mathematic minds that keep trying to give the problem an answer.
For your luck, this is not the contest’s task.
Contest task:
Using the Collatz rule, and starting for ie with 11, we generate the following sequence:
11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
we can call this a chain of 15 steps that leads to 1.
Write a function
collatz(upperBound:Number):Number
returned value i need the number N < upperBound that produces the longest chain between all the numbers from 1 to upperBound. Submissions Testing:
Every submission will test with Grant Skinner Performance Test v.2
There will be just a call to the funzion like collatz(n) where n will be a secret number (between 5 and 11 millions). The reason why this number will keep secret till the end of the contest is to avoid specific assumptions (that are in somehow possible, knowing the starting number).
The test will run on a MacBookPro 2006 (2.3ghz – 2gb ram), on flash player (regular not debugger version) 10.1.53.64
With daily upgrade, i’ll publish the results from submitters, like this way: nicolabortignon – 14.999ms. Top five positions will not display the timing, this means that all the top 5 positions timing is < than 6th. Top 5 positions will not order, so we will know the winner (and top 3) only at the end of the contest. I hope this push you to keep searching for a better solution even if you are on top.
I warmly suggest you not to share the entire submitted code, since the contest will be close; i really like instead to see you discussing (here on comments or wherever you prefear) about the work in progress so feel free to exchange suggestions.
Sumbissions Rules (inspired by mikechambers):
- Code must be sended to (info[at]nicolabortignon .com) by 24:00, PST, Sunday, August
8th.16th - Code must be written in ActionScript 3.
- All .as file must including the Name and contact information from the author.
- Code must be release under an MIT license (includer on the header of the main .as file)
- Try to comment out as much clear as you can the code
- If the value returned from the function is wrong, submission will not get in consideration
- Code that dosn’t compile will automaticly exclude the author from the contest (so pls double check if it compiles before sending).
- Code must authoring on Flash CS3 or aboves (Flex dependency will not allow).
- External Libraries included in the code must be attached to the submission.
- Code cannot require any additional tools, pre or post processing steps.
- Code will publish at the end of the contest.
- Devs may submit more than once and less than 5 times (this should let you change your mind on the approach, but not too many times).
Suggestions:
As said, brutal force is not a competitive solution, btw you can start from that (setting your player timeout over 15s)
Many papers, documents, even books, were written on this topic, usually some of them suggest algorithms to solve the problem. Try to use this resources in the right way, not paste and copy: i’m quite sure that lots of submitted proposal will more optimized that the general algorithms proposed in that references. So i can say that a thief approach will not put you on top.
Finally keep in mind that we don’t need the most elegant code, we just need the fastest :)