Author Topic: Programming Contest  (Read 12949 times)

0 Members and 1 Guest are viewing this topic.

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Programming Contest
« on: December 17, 2008, 12:42:38 am »
I was just thinking today that it'd be kinda cool if we had a friendly and informal programming contest amongst ourselves.  We could all come up with what we'd work on, but it would, of course, have to be something where we could develop a meaningful way to measure programs against each other.  For example, the time it takes to complete a case, number of cases solved per minute, or if it's an AI for a game or something, maybe we could do a tournament.

We could even do a series of programs or something.

Here are some ideas:

Sudoku solver
AI for simple games (ie, checkers, othello, etc)
Captcha solving
Anagrams
Automated theorem prover

Would anyone be interested in this?  I think it'd be fun!
« Last Edit: December 17, 2008, 02:04:14 am by Sidoh »

Offline Blaze

  • x86
  • Hero Member
  • *****
  • Posts: 7136
  • Canadian
    • View Profile
    • Maide
Re: Programming Contest
« Reply #1 on: December 17, 2008, 01:22:15 am »
I like the first two ideas, and would totally submit an entry.  :)
And like a fool I believed myself, and thought I was somebody else...

Offline Chavo

  • x86
  • Hero Member
  • *****
  • Posts: 2219
  • no u
    • View Profile
    • Chavoland
Re: Programming Contest
« Reply #2 on: December 17, 2008, 01:24:11 am »
Interested, but won't have the time until May :P

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Programming Contest
« Reply #3 on: December 17, 2008, 01:46:06 am »
Cool!  I'd be interested in doing a project over break, so if we get enough people interested in this, I'd love to get the plans rolling!

Any other suggestions?  I think the two Blaze said he was interested in would work really well.  We might want to reserve the AI until more people can participate.

Offline Blaze

  • x86
  • Hero Member
  • *****
  • Posts: 7136
  • Canadian
    • View Profile
    • Maide
Re: Programming Contest
« Reply #4 on: December 17, 2008, 01:52:14 am »
Captcha solving would be fun, too!  :)
And like a fool I believed myself, and thought I was somebody else...

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Programming Contest
« Reply #5 on: December 17, 2008, 02:03:52 am »
Oh yeah, that's a great idea.  I'll add it to the list.

Offline Blaze

  • x86
  • Hero Member
  • *****
  • Posts: 7136
  • Canadian
    • View Profile
    • Maide
Re: Programming Contest
« Reply #6 on: December 17, 2008, 02:11:15 am »
Or, for even more of a challenge, make a captcha that is solved by the fewest other people that is legible at least 70% of the time.  First round, people make Captcha Generators, second round we try to solve everyone elses (with at least a 25% success rate) (or as many as you can)!  :)
And like a fool I believed myself, and thought I was somebody else...

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Programming Contest
« Reply #7 on: December 17, 2008, 02:14:00 am »
Ah, that's a cool idea.  I think I'd have to go for something less ambitious for winter break, but I think that'd be really fun over summer or next semester if I have free time (lolololol).

Offline warz

  • Hero Member
  • *****
  • Posts: 1134
    • View Profile
    • chyea.org
Re: Programming Contest
« Reply #8 on: December 17, 2008, 01:35:26 pm »
I don't recall the name of it right now, but there's a 'game' where you program your own robot thing to do battles with others. The robots run on some game framework, but I think you program the AI and stuff. That could be fun.
http://www.chyea.org/ - web based markup debugger

Offline iago

  • Leader
  • Administrator
  • Hero Member
  • *****
  • Posts: 17914
  • Fnord.
    • View Profile
    • SkullSecurity
Re: Programming Contest
« Reply #9 on: December 17, 2008, 02:22:51 pm »
ooh, I want to write an anagram solver!

That is to say, I already wrote one that's totally awesomely fast. :)

Offline MyndFyre

  • Boticulator Extraordinaire
  • x86
  • Hero Member
  • *****
  • Posts: 4540
  • The wait is over.
    • View Profile
    • JinxBot :: the evolution in boticulation
Re: Programming Contest
« Reply #10 on: December 17, 2008, 03:14:11 pm »
I don't recall the name of it right now, but there's a 'game' where you program your own robot thing to do battles with others. The robots run on some game framework, but I think you program the AI and stuff. That could be fun.

Microsoft Robotics Studio?
I have a programming folder, and I have nothing of value there

Running with Code has a new home!

Our species really annoys me.

Offline Chavo

  • x86
  • Hero Member
  • *****
  • Posts: 2219
  • no u
    • View Profile
    • Chavoland
Re: Programming Contest
« Reply #11 on: December 17, 2008, 03:34:49 pm »
AI for battlebots? That takes all the fun out of it!!

Offline Warrior

  • supreme mac daddy of trolls
  • Hero Member
  • *****
  • Posts: 7503
  • One for a Dime two for a Quarter!
    • View Profile
Re: Programming Contest
« Reply #12 on: December 17, 2008, 04:06:20 pm »
It would not be a contest if I participated. I will keep it fair to everyone and stay out of this one.
One must ask oneself: "do I will trolling to become a universal law?" And then when one realizes "yes, I do will it to be such," one feels completely justified.
-- from Groundwork for the Metaphysics of Trolling

Offline warz

  • Hero Member
  • *****
  • Posts: 1134
    • View Profile
    • chyea.org
Re: Programming Contest
« Reply #13 on: December 17, 2008, 08:26:25 pm »
I don't recall the name of it right now, but there's a 'game' where you program your own robot thing to do battles with others. The robots run on some game framework, but I think you program the AI and stuff. That could be fun.

Microsoft Robotics Studio?

Well, no, it wasn't a MS thing.
http://www.chyea.org/ - web based markup debugger

Offline nslay

  • Hero Member
  • *****
  • Posts: 786
  • Giraffe meat, mmm
    • View Profile
Re: Programming Contest
« Reply #14 on: December 17, 2008, 11:08:11 pm »
I was just thinking today that it'd be kinda cool if we had a friendly and informal programming contest amongst ourselves.  We could all come up with what we'd work on, but it would, of course, have to be something where we could develop a meaningful way to measure programs against each other.  For example, the time it takes to complete a case, number of cases solved per minute, or if it's an AI for a game or something, maybe we could do a tournament.

We could even do a series of programs or something.

Here are some ideas:

Sudoku solver
AI for simple games (ie, checkers, othello, etc)
Captcha solving
Anagrams
Automated theorem prover

Would anyone be interested in this?  I think it'd be fun!
Probably shouldn't pick projects that could be PhD thesis topics.  I think the most reasonable projects you suggested are "AI for simple games" or "Anagrams".  Everything else is masters/PhD level work. 
An adorable giant isopod!

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Programming Contest
« Reply #15 on: December 17, 2008, 11:22:06 pm »
Sudoku solvers are not difficult to write.  Efficient brute force solvers are probably a bit harder to implement well, but I wouldn't be surprised if a good number of people here could write a good solver in some form of another.

Automated theorem proving isn't very difficult either.  It's another one where it's tricky to write one that is extensive, but it is by no means overly ambitious for someone who understands a few simple rules of propositional/prepositional logic.

Captcha solving is one where I'd be a bit at a loss, but that's because I have almost no background in graphics.  I'm pretty confident that after talking with some people and reading a book or two, I'd be able to write one that can solve fairly simple captchas (eg, not distorted very much).

Honestly, I don't think any of those would be good thesis topics, unless you're doing something really revolutionary.  I think all of the topics on the list have been beaten to death, and I've written everything on there except for an anagram and captcha solver.

Offline nslay

  • Hero Member
  • *****
  • Posts: 786
  • Giraffe meat, mmm
    • View Profile
Re: Programming Contest
« Reply #16 on: December 17, 2008, 11:52:32 pm »
Sudoku solvers are not difficult to write.  Efficient brute force solvers are probably a bit harder to implement well, but I wouldn't be surprised if a good number of people here could write a good solver in some form of another.
Soduku is an NP-complete problem.  The people who derive algorithms to efficiently solve them publish their results in papers.

Quote
Automated theorem proving isn't very difficult either.  It's another one where it's tricky to write one that is extensive, but it is by no means overly ambitious for someone who understands a few simple rules of propositional/prepositional logic.
I don't know what automated theorem proving entails, but it sure reminds me of computer algebra systems which are a product of symbolic computing.  This does not seem trivial.

Quote
Captcha solving is one where I'd be a bit at a loss, but that's because I have almost no background in graphics.  I'm pretty confident that after talking with some people and reading a book or two, I'd be able to write one that can solve fairly simple captchas (eg, not distorted very much).
Captcha classifications requires background in computer vision and machine learning to even begin to approach the problem.
Quote
Honestly, I don't think any of those would be good thesis topics, unless you're doing something really revolutionary.  I think all of the topics on the list have been beaten to death, and I've written everything on there except for an anagram and captcha solver.
Writing algorithms to solve soduku puzzles or classes of soduko puzzles efficiently is publishable material (which is worthy of a thesis). Captcha classification is not trivial either...a very accurate captcha classifier would be publishable material.
An adorable giant isopod!

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Programming Contest
« Reply #17 on: December 17, 2008, 11:58:12 pm »
Sudoku solvers are not difficult to write.  Efficient brute force solvers are probably a bit harder to implement well, but I wouldn't be surprised if a good number of people here could write a good solver in some form of another.
Soduku is an NP-complete problem.  The people who derive algorithms to efficiently solve them publish their results in papers.

Quote
Automated theorem proving isn't very difficult either.  It's another one where it's tricky to write one that is extensive, but it is by no means overly ambitious for someone who understands a few simple rules of propositional/prepositional logic.
I don't know what automated theorem proving entails, but it sure reminds me of computer algebra systems which are a product of symbolic computing.  This does not seem trivial.

Quote
Captcha solving is one where I'd be a bit at a loss, but that's because I have almost no background in graphics.  I'm pretty confident that after talking with some people and reading a book or two, I'd be able to write one that can solve fairly simple captchas (eg, not distorted very much).
Captcha classifications requires background in computer vision and machine learning to even begin to approach the problem.
Quote
Honestly, I don't think any of those would be good thesis topics, unless you're doing something really revolutionary.  I think all of the topics on the list have been beaten to death, and I've written everything on there except for an anagram and captcha solver.
Writing algorithms to solve soduku puzzles or classes of soduko puzzles efficiently is publishable material (which is worthy of a thesis). Captcha classification is not trivial either...a very accurate captcha classifier would be publishable material.

A reasonable brute force algorithm (ie, one without bugs) solves a sudoku in O(1) time.  It's a fixed size grid (9x9).  It's not an interesting problem in an academic circle (save for an exercise).  Generalized sudoku (which is not sudoku) is nxn, which is NP-complete.  I'd hope it's obvious that this is not what I'm proposing.

I'm not implying that any of these are trivial; I'm suggesting that they're feasible.  Automated theorem proving is difficult, and I wouldn't expect anyone to do half as well as prolog, but it's still not impossibly challenging.

I don't think that's true.  If you're given a reasonable sampling of what the captchas look like, I don't think it takes much more than a bit of background in graphics and probably some knowledge in OCR to solve them.  Making a generalized solver would be difficult, but again, this is not what I'm suggesting.

Offline nslay

  • Hero Member
  • *****
  • Posts: 786
  • Giraffe meat, mmm
    • View Profile
Re: Programming Contest
« Reply #18 on: December 18, 2008, 12:13:49 am »
Sudoku solvers are not difficult to write.  Efficient brute force solvers are probably a bit harder to implement well, but I wouldn't be surprised if a good number of people here could write a good solver in some form of another.
Soduku is an NP-complete problem.  The people who derive algorithms to efficiently solve them publish their results in papers.

Quote
Automated theorem proving isn't very difficult either.  It's another one where it's tricky to write one that is extensive, but it is by no means overly ambitious for someone who understands a few simple rules of propositional/prepositional logic.
I don't know what automated theorem proving entails, but it sure reminds me of computer algebra systems which are a product of symbolic computing.  This does not seem trivial.

Quote
Captcha solving is one where I'd be a bit at a loss, but that's because I have almost no background in graphics.  I'm pretty confident that after talking with some people and reading a book or two, I'd be able to write one that can solve fairly simple captchas (eg, not distorted very much).
Captcha classifications requires background in computer vision and machine learning to even begin to approach the problem.
Quote
Honestly, I don't think any of those would be good thesis topics, unless you're doing something really revolutionary.  I think all of the topics on the list have been beaten to death, and I've written everything on there except for an anagram and captcha solver.
Writing algorithms to solve soduku puzzles or classes of soduko puzzles efficiently is publishable material (which is worthy of a thesis). Captcha classification is not trivial either...a very accurate captcha classifier would be publishable material.

A reasonable brute force algorithm (ie, one without bugs) solves a sudoku in O(1) time.  It's a fixed size grid (9x9).  It's not an interesting problem in an academic circle (save for an exercise).  Generalized sudoku (which is not sudoku) is nxn, which is NP-complete.  I'd hope it's obvious that this is not what I'm proposing.
Well, I don't know or solve sodoku puzzles.  I only saw it mentioned in some journal so I misunderstood.
Quote
I'm not implying that any of these are trivial; I'm suggesting that they're feasible.  Automated theorem proving is difficult, and I wouldn't expect anyone to do half as well as prolog, but it's still not impossibly challenging.

I don't think that's true.  If you're given a reasonable sampling of what the captchas look like, I don't think it takes much more than a bit of background in graphics and probably some knowledge in OCR to solve them.  Making a generalized solver would be difficult, but again, this is not what I'm suggesting.
As with face detection, I imagine you would employ machine learning algorithms to classify captchas.  Train the algorithm on annotated captchas, then use the trained algorithm to classify unseen captchas.  If the captcha is simple, you might be able to do something else.
An adorable giant isopod!

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Programming Contest
« Reply #19 on: December 18, 2008, 12:29:30 am »
Yeah, on captchas, I don't expect we'd try anything more than really simple ones.

Actually, I'm very interested by machine learning.  I understand very little beyond the general concept, but I do plan to take a course in it before I graduate.  I'm taking the non-machine learning AI courses first.  They're not prerequisites, but they're offered before machine learning in the cycle.

Anyway!  Is anyone else interested?  I think it'd be ideal if we could get ~5+ people.
« Last Edit: December 18, 2008, 12:31:35 am by Sidoh »

Offline Camel

  • Hero Member
  • *****
  • Posts: 1703
    • View Profile
    • BNU Bot
Re: Programming Contest
« Reply #20 on: December 18, 2008, 02:40:26 pm »
http://csis.pace.edu/~bergin/karel.html

Did some projects with this years ago in middle school - various mathematical operations.

<Camel> i said what what
<Blaze> in the butt
<Camel> you want to do it in my butt?
<Blaze> in my butt
<Camel> let's do it in the butt
<Blaze> Okay!

Offline iago

  • Leader
  • Administrator
  • Hero Member
  • *****
  • Posts: 17914
  • Fnord.
    • View Profile
    • SkullSecurity
Re: Programming Contest
« Reply #21 on: December 18, 2008, 02:58:08 pm »
A few years ago I solved a moderate CAPTCHA with no fore knowledge. The easiest part was that it was numerical-only.

I used an AI type of solution by dividing the image into regions and checking what percentage of each region was black (that was after filtering out the noise). It got about 15% accuracy, which was pretty good.

Offline Chavo

  • x86
  • Hero Member
  • *****
  • Posts: 2219
  • no u
    • View Profile
    • Chavoland
Re: Programming Contest
« Reply #22 on: December 18, 2008, 03:00:37 pm »
15%? That's barely better than randomly guessing a digit ;)

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Programming Contest
« Reply #23 on: December 18, 2008, 03:16:33 pm »
15%? That's barely better than randomly guessing a digit ;)

Not considering it was almost certainly more than one digit.  If he was randomly guessing, it'd be (.1)^n, yes?

Offline iago

  • Leader
  • Administrator
  • Hero Member
  • *****
  • Posts: 17914
  • Fnord.
    • View Profile
    • SkullSecurity
Re: Programming Contest
« Reply #24 on: December 18, 2008, 06:50:33 pm »
It was 5 digits, so we brought it from 1/10,000 to 1500/10,000. Just a bit better..

Offline Chavo

  • x86
  • Hero Member
  • *****
  • Posts: 2219
  • no u
    • View Profile
    • Chavoland
Re: Programming Contest
« Reply #25 on: December 18, 2008, 09:19:40 pm »
I was joking, clown.

Offline MyndFyre

  • Boticulator Extraordinaire
  • x86
  • Hero Member
  • *****
  • Posts: 4540
  • The wait is over.
    • View Profile
    • JinxBot :: the evolution in boticulation
Re: Programming Contest
« Reply #26 on: December 18, 2008, 09:47:39 pm »
A reasonable brute force algorithm (ie, one without bugs) solves a sudoku in O(1) time.  It's a fixed size grid (9x9).  It's not an interesting problem in an academic circle (save for an exercise).  Generalized sudoku (which is not sudoku) is nxn, which is NP-complete.  I'd hope it's obvious that this is not what I'm proposing.
I don't believe that the algorithm solves a 9x9 grid in O(1)....  Unless you're meaning to say that it will do it in at most constant time, with the 1 being ALL of the possible combinations of numbers on the board....
I have a programming folder, and I have nothing of value there

Running with Code has a new home!

Our species really annoys me.

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Programming Contest
« Reply #27 on: December 18, 2008, 11:02:21 pm »
It's pretty clearly O(1).  Given any algorithm that solves a sudoku, you can do amortized analysis on it.  Since the size of the input is bounded, the worst you can do is based on how the algorithm approaches it.  If it's backtracking, you could probably end up doing something like 65^5, which is still O(1).

I wrote a backtracking solver a few months ago.  I did nothing in the way of heuristics (it's a CSP, so it'd be easy to implement most constrained variable / least constraining value), and it still solves 12-hint puzzles in less than 5 seconds.  I suspect implementing meaningful heuristics would down that to less than 1 second pretty easily.

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Programming Contest
« Reply #28 on: December 23, 2008, 03:57:05 pm »
I was joking, clown.

lol. 

Well, I'm probably going to try doing one of these things over the break to stay productive.  Blaze, you want to work on one as well?  If so, which one?

Offline zorm

  • Hero Member
  • *****
  • Posts: 591
    • View Profile
    • Zorm's Page
Re: Programming Contest
« Reply #29 on: December 26, 2008, 08:21:14 pm »
Why not spend your time doing the 30 day challenge or something like that?
"Frustra fit per plura quod potest fieri per pauciora"
- William of Ockham

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Programming Contest
« Reply #30 on: December 27, 2008, 01:06:03 am »
http://www.thirtydaychallenge.com/ This?

Looks interesting, but it's not really what I want to work on right now.

Offline Blaze

  • x86
  • Hero Member
  • *****
  • Posts: 7136
  • Canadian
    • View Profile
    • Maide
Re: Programming Contest
« Reply #31 on: December 27, 2008, 01:18:13 am »
I was joking, clown.

lol. 

Well, I'm probably going to try doing one of these things over the break to stay productive.  Blaze, you want to work on one as well?  If so, which one?

Whatever you want to do, I'll do.
And like a fool I believed myself, and thought I was somebody else...

Offline Warrior

  • supreme mac daddy of trolls
  • Hero Member
  • *****
  • Posts: 7503
  • One for a Dime two for a Quarter!
    • View Profile
Re: Programming Contest
« Reply #32 on: December 27, 2008, 01:21:02 am »
she said that ^
One must ask oneself: "do I will trolling to become a universal law?" And then when one realizes "yes, I do will it to be such," one feels completely justified.
-- from Groundwork for the Metaphysics of Trolling