Programming Contest

[Sidoh]

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!

[Blaze]

I like the first two ideas, and would totally submit an entry. 

[Chavo]

Interested, but won't have the time until May

[Sidoh]

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.

[Blaze]

Captcha solving would be fun, too! 

[Sidoh]

Oh yeah, that's a great idea.  I'll add it to the list.

[Blaze]

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)! 

[Sidoh]

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).

[warz]

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.

[iago]

ooh, I want to write an anagram solver!

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

[MyndFyre]

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?

[Chavo]

AI for battlebots? That takes all the fun out of it!!

[Warrior]

It would not be a contest if I participated. I will keep it fair to everyone and stay out of this one.

[warz]

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.

[nslay]

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. 

[Sidoh]

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.

[nslay]

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.

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.

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.

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.

[Sidoh]

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.

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.

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.

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.

[nslay]

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.

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.

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.

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.

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.

[Sidoh]

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.

[Camel]

http://csis.pace.edu/~bergin/karel.html

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

[iago]

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.

[Chavo]

15%? That's barely better than randomly guessing a digit

[Sidoh]

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?

[iago]

It was 5 digits, so we brought it from 1/10,000 to 1500/10,000. Just a bit better..

[Chavo]

I was joking, clown.

[MyndFyre]

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....

[Sidoh]

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.

[Sidoh]

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?

[zorm]

Why not spend your time doing the 30 day challenge or something like that?

[Sidoh]

http://www.thirtydaychallenge.com/ This?

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

[Blaze]

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.

[Warrior]

she said that ^