24 hour contest ideas
The [url="http://forums.nvidia.com/index.php?showtopic=102349"]Engineyard contest[/url] was interesting in its design, since it was set up as a "do it any way you like, just post the best answer before time is up."
That really created a lot of tension and drama.. it felt very much like a contest with a goal in sight and leaders to watch.
A programming contest where you submit code to be run on a standardized machine doesn't have the same drama, though it can be set up to be close. (Think of collegiate programming contests with a "judge server" you submit to.

Unfortunately, EngineYard won't be running any more contests like that (the next one is going to be a Ruby programming challenge.)

But could we make our own, perhaps inspired in format by the Engineyard challenge: short duration, easy to score, no penalty for reporting progress as early as you can, no limits on HOW you produce the result, and every submission publicly visible (perhaps via Twitter).

Now, like the EngineYard contest, there would be an advantage to a team or person with a big cluster or many GPUs. But so what? It was fun even when the winners had lots of machines anyway.
Also there's no reason that the winners had to use CUDA... CPU or Javascript or hand calculators are OK. The Engineyard contest had AWESOME entries with javascript which had no chance of winning but was just cool in general.

Designing the contest is tricky.. you need something that has an entry that is short to post, easy to verify, and impossible to "max out" so there's always some new score that might improve over the current leader's.

Also the problem itself should likely be simple.. something that can be coded in an hour if you want to make a simple entry, but likely will require more work to do efficiently.
Finally the problem should be unique enough that there's no prebuilt tools for solving it.. requiring at least a little programming from some teams to attack it.

Just for brainstorming, here's two ideas:

1) Travelling salesmen. A salesman must visit N clients in any order. The salesman wants the shortest total travel length. Unfortunately his clients move every day. The judge gives a big list of perhaps 50 clients, and for each of 50 days an XY position of that client. The salesman travels from client to client, one trip per day. Score is the total length of the salesman's travels.
This is nice since it's not a normal Travelling salesman problem with known algorithms or libraries, a solution is easy to Twitter, the score is easy to compute, and there likely is no way to find the optimal value.

2) Factoring. Inspired by the RSA factoring challenges.
The judge posts a list of numbers from about 2^50 to 2^200. Each number is the product of two primes. Winner of the contest is the person who factors the largest number before the end of the contest's 24 hours. You need a little strategy to decide which number you attack! Pick too low and you'll be beaten. Pick too high and you may not finish in time. And in either case, you need to watch other entries since if someone posts a better score than what you're working on, you need to abandon your work and quickly pick a more challenging number!
This is a very pure and elegant problem, but unfortunately there's a lot of complex and powerful libraries already published, so this would become more of a "who has better computers" contest.
Perhaps someone might brainstorm some kind of variant that would need to be custom coded, though.


Yes, this post is just for brainstorming.. I don't know what company would sponsor prizes! But by having some interesting ideas, maybe we could encourage some companies to run such attention-getter contests. The Engineyard quick one-day twitter framework would make it quite lightweight to judge and administrate. It's clear that Engineyard got a lot of publicity and traffic for the trivial cost of two iPhones!
The Engineyard contest was interesting in its design, since it was set up as a "do it any way you like, just post the best answer before time is up."

That really created a lot of tension and drama.. it felt very much like a contest with a goal in sight and leaders to watch.

A programming contest where you submit code to be run on a standardized machine doesn't have the same drama, though it can be set up to be close. (Think of collegiate programming contests with a "judge server" you submit to.



Unfortunately, EngineYard won't be running any more contests like that (the next one is going to be a Ruby programming challenge.)



But could we make our own, perhaps inspired in format by the Engineyard challenge: short duration, easy to score, no penalty for reporting progress as early as you can, no limits on HOW you produce the result, and every submission publicly visible (perhaps via Twitter).



Now, like the EngineYard contest, there would be an advantage to a team or person with a big cluster or many GPUs. But so what? It was fun even when the winners had lots of machines anyway.

Also there's no reason that the winners had to use CUDA... CPU or Javascript or hand calculators are OK. The Engineyard contest had AWESOME entries with javascript which had no chance of winning but was just cool in general.



Designing the contest is tricky.. you need something that has an entry that is short to post, easy to verify, and impossible to "max out" so there's always some new score that might improve over the current leader's.



Also the problem itself should likely be simple.. something that can be coded in an hour if you want to make a simple entry, but likely will require more work to do efficiently.

Finally the problem should be unique enough that there's no prebuilt tools for solving it.. requiring at least a little programming from some teams to attack it.



Just for brainstorming, here's two ideas:



1) Travelling salesmen. A salesman must visit N clients in any order. The salesman wants the shortest total travel length. Unfortunately his clients move every day. The judge gives a big list of perhaps 50 clients, and for each of 50 days an XY position of that client. The salesman travels from client to client, one trip per day. Score is the total length of the salesman's travels.

This is nice since it's not a normal Travelling salesman problem with known algorithms or libraries, a solution is easy to Twitter, the score is easy to compute, and there likely is no way to find the optimal value.



2) Factoring. Inspired by the RSA factoring challenges.

The judge posts a list of numbers from about 2^50 to 2^200. Each number is the product of two primes. Winner of the contest is the person who factors the largest number before the end of the contest's 24 hours. You need a little strategy to decide which number you attack! Pick too low and you'll be beaten. Pick too high and you may not finish in time. And in either case, you need to watch other entries since if someone posts a better score than what you're working on, you need to abandon your work and quickly pick a more challenging number!

This is a very pure and elegant problem, but unfortunately there's a lot of complex and powerful libraries already published, so this would become more of a "who has better computers" contest.

Perhaps someone might brainstorm some kind of variant that would need to be custom coded, though.





Yes, this post is just for brainstorming.. I don't know what company would sponsor prizes! But by having some interesting ideas, maybe we could encourage some companies to run such attention-getter contests. The Engineyard quick one-day twitter framework would make it quite lightweight to judge and administrate. It's clear that Engineyard got a lot of publicity and traffic for the trivial cost of two iPhones!

#1
Posted 08/12/2009 03:57 AM   
I like the idea of travelling salesman. But how do we know you don't already have a CUDA implementation ready to go, SPWorley? :)
I like the idea of travelling salesman. But how do we know you don't already have a CUDA implementation ready to go, SPWorley? :)

#2
Posted 08/12/2009 03:22 PM   
[quote name='Simon Green' post='577393' date='Aug 12 2009, 08:22 AM']I like the idea of travelling salesman. But how do we know you don't already have a CUDA implementation ready to go, SPWorley? :)[/quote]

So when does the contest start then?

It is true.. programmers like puzzles. As soon as I thought of the problem my brain started wondering how I'd attack it in practice.

Some funny knapsack variation might also be effective.. easy to score, impossible to get optimal. You'd have to invent a funky variant that standard libraries wouldn't deal with easily.
[quote name='Simon Green' post='577393' date='Aug 12 2009, 08:22 AM']I like the idea of travelling salesman. But how do we know you don't already have a CUDA implementation ready to go, SPWorley? :)



So when does the contest start then?



It is true.. programmers like puzzles. As soon as I thought of the problem my brain started wondering how I'd attack it in practice.



Some funny knapsack variation might also be effective.. easy to score, impossible to get optimal. You'd have to invent a funky variant that standard libraries wouldn't deal with easily.

#3
Posted 08/12/2009 03:41 PM   
Scroll To Top