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 
Ha!Hey!Hah!. That’s always funny see programmers smash into math. I’ll try to make something on the paper before start coding ..
[...] This post was mentioned on Twitter by Andreas Renberg, Nicola Bortignon. Nicola Bortignon said: #GoneIn15Seconds an #as3 contest … let the challange starts ! http://twurl.nl/h5vbqu enjoy
[...]
I had a wonderfully beautiful solution that used recursion, and for numbers less than 100,000 it worked magnificently!
Then I got up in the millions and got a stack overflow.
Hi Andreas, as you point it out, recursion may not the right way for bigger values (since recursive called functions may overflow the stack of the flash player), even if i love to write recursive functions, they are so elegant.
Back to the problem, since we not know how many step a number generates in the chain to 1 ( if we knew it means that we solved the main math problem
), we can’t really do an analysis in the usual manner.
The main idea behind this topic is to make a learning algorithm, that means, let the algorithm learn from his past results. If you look to the chain generated by the number 11 and the number 13, there is a common path to the number 1, this means that we don’t need to compute twice the path …
hope this is a good hint to start with
Yep, that was exactly what I was doing.
But some number in the 100,000+ realm went through more than 4,000 something UNIQUE numbers (ie, hadn’t been calculated before). I have been trying to adapt the function to work as a loop instead, but it’s just not the same.
Darn, and I will be gone all weekend, so hopefully I have time to get my submission tinkered out and in when I get back on Sunday. How many results are in so far? Any chance in extending it two days to leave room for more submissions?
Hola,happy to see you back.
) there’s not problem on delaying deadline.
Actually there are only two submission (mine and one from a collegue i forced to submit
as i told in the main post, is not a matter of who’s the best (not really) it’s just a good opportunity to face problems that are not usual in common developer life. So, let’z move deadline to 16 august.
About the problem itself, let me tell some minor tips.
- At any iteration we can point out that the number is even, if not, next iteration it will be for sure (a number multiplyed by 3 plus 1 is always even)
- Problem can be approached from the top or from the bottom of the range, this leads to two different ideas, from top, you can easily reduce the range to examinate, from buttom you can do certain consideration on which value are possible to skip, since there will be for sure a longest chain.
- Even if dosn’t exist a formula to easily calculate the number of elements of the succession for each number, there is an empiric demonstration on the range of value of the chains
here an interesting image on the distribution of the first billion ….
The first one-billion total stopping times. The horizontal axis is n, and the vertical axis is the total stopping time of n.
I can tell you btw that the longest chain under 10.000.000 is around 700 value.
can’t add more
Anyway, I wrote the alternative code (the one that uses loops and stacks rather than recursion) entirely on paper while stuck in the back seat with two little children (which I believe is a feat in itself!), and when typing it up and compiling it, it worked perfectly…
… for numbers less than 100,000. Now there is no longer the issue with a stack overflow. But yet it still isn’t working for me! I am clueless at the moment as to what the cause could be. Perhaps one of the numbers is going beyond the maximum allowed limits for “ints”, wreaking havoc and confusion to the rest of the code?
If the longest chain is as you say a 700 value, I shouldn’t even have gotten a stack overflow, and the code should have run just fine. So there must be something wrong somewhere…
Anyway, thanks a lot for this challenge. I’m actually enjoying this, although, at the moment it’s a bit frustrating and I’m using your comments section to vent.
Found it.
It was one specific number that was being evil, Mr “113384″ wouldn’t let me pass. Tomorrow I will track down WHY, but it seems like more people than just me don’t like that number:
http://www.google.com/#&q=113384+collatz
Hi Andreas, well thanx for beeing part of this first attempt to contest. as you saw not many submission this time, so i will turn the post aim into an informative post.
As you pointed out you get into a int limitation, that is the direct consequence of how calculators represent the argument is really interesting, and this will be for sure a topic i would like to get into as soon as i get time.
Back to the topic, the problem i submit (the entire collatz conjecture) was just an excuse to mark some interesting subtopics:
- recursion is not always the choice (even if elegant )
- repetitive math calc should be optimized ( from basics bitwise optimization to hard coded memoization)
- ppl are used to think that last generation cpu can handle all the common days problem, even if this is not a “common days”, the basic idea behind is really simply, and not so far from a real problem.
- last but not least some mathematical assumption can help to reduce the problem (for exemple, assuming 10.000.000 as the upper bound, we can say that all the even numbers lead to a smaller number,on the other hands we can say that all odd number can be triggered only by number that are 1/3 and at the end we know that an odd number always leads to an even number: let’z mix this 3 things together and you can reduce the range of calculation between 10.000.000 and 3.333.333 that is reasonable 33% less time required).
A more detailed description with some interesting tricks around the collatz conjecture will come shortly as un upgrade with this post (and i must say that quite all comes from great mathematics minds from past).
so at the end of this first try, i must say andreas you are my moral winner. since looks like you get into the problem, discovered some low level interesting things, and change your mind while trying to resolve the problem! Hope you enjoyed!
Best Nick
Buy:Arimidex.Prednisolone.Zyban.Human Growth Hormone.Zovirax.Mega Hoodia.Valtrex.Petcam (Metacam) Oral Suspension.Accutane.Synthroid.Actos.Retin-A.100% Pure Okinawan Coral Calcium.Lumigan.Prevacid.Nexium….