Author Topic: Programming Contest  (Read 10588 times)

0 Members and 1 Guest are viewing this topic.

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