Google AI Contest: Literate version of the top scoring Haskell entry | Hacker News Reader

Google AI Contest: Literate version of the top scoring Haskell entry

jaspervdj.be

40 pointsdons10 comments

love the animation of the flood fill. made parsing of that part pretty much instantaneous.

So many of these coding challenges seem to be just straigtforward applications of constraint programming, I don't understand what all the hubbub is about. Install any old prolog/chr or constraint library and you're done. Haskell and c++ are a convoluted way to get to that.

There were 708 submissions, and glancing over them, they seem to be implemented in C++, Lisp, Haskell, Python, Java, C#, Perl, JavaScript, Ruby and even one in Go. None, from what I can see, were implemented in Prolog.

When 708 people who spent a significant amount of time solving a problem didn't do what you think is obvious, then perhaps your understanding of the problem isn't as complete as you think it is. Prolog is indeed good for constraint programming, but these programs needed to run in competition with one another. My guess is that a straight-forward Prolog solution isn't fast enough. And once you put enough cuts into the straight-forward solution to help the runtime prune decisions, maybe you'd be better off using something that's faster to begin with.

Constraint programming is not about prolog. It's a way of declaratively 'programming' constraints on a search. The combination of prolog and chr, prolog and clp, or constraint libraries that are available for most languages fits the bill, not prolog on it's own.

Perhaps the 708 people aren't familiar enough with constraint programming, just like most java programmers aren't familiar enough with functional programming.

Constraint programming involves providing constraints, and letting some sort of runtime search through the space to find a solution. This sacrifices runtime efficiency for programmer efficiency. Sometimes that's a good tradeoff. My guess is that when you need to produce an answer in less than one second - such as in this contest - it's not a good tradeoff.

In solving these problems you're creating an ad hoc search runtime that is likely slower or buggier than the well tested search runtimes in constraint programming implementations. The only things that really matter are your constraints for reducing the search space and the search strategy you use. When using finite domains (+,-,<,>,*,/ on integers) the implementations provided by constraint libraries are faster than anything you can easily create. There are a variety of search strategies already implemented (and that you can also tweak).

The likely explanation for the inelegant solutions in topcoder and this challenge are that constraint programming is hardly mentioned in undergraduate cs curriculum so even top students are unfamiliar with it.

Please read through the discussion around the winning entry, including what the winning coder and other participants have to say: http://news.ycombinator.com/item?id=1168289

The problem is one of combinatorial optimization (as are most of these 'hard' competitions), but the tools these students always start with are the slgorithms they learned from the algo courses. Constraint programming/automated planning are modern techniques used exactly for combinatorial optimization.

The winner's heuristics would have been part of the constraints and so would have been the first thing he tried and would be faster because they would have been pruned from the search tree and the solutions not evaluated (incidentally, this is the difference between constraint programming and prolog, in prolog you generate, as he did, and then test, while constraints prune and test). The iterative deepening search is known as breadth first search in prolog/constraint programming and would also be one of the first things you try.

The answer to the question "Why no Prolog?" is simpler, the organizers set up simple default guaranteed-to-compile "starter" packages for several languages. One surprise was that a Haskell package was included, though it used the antique ghc-6.8. The default way of entering the contest was simply to send back the unaltered starter program, and set about hacking and re-entering from there.

(I entered as the completest Haskell noob imaginable, and was surprised that by making the most elementary revision of the package (which gave your bot the bold strategy of going straight north til it crashed) I managed to place in the top 2/3s. Basically I told it, "if it's the wall, don't go there, take the first of the others available" -- maybe one or two other things. Every klutzy attempt at further 'intelligence' ran into time trouble since I don't yet have any feeling for that kind of optimization. So the package would be excluded as Timed Out if was too slow in too many contests. I consoled myself thinking: At least I my entries never suffered the indignity of the other rejection notice: Garbage Collected)

Competitions like this should be relabeled as who can reimplement constraint programming fastest and without bugs then.

Reply on news.ycombinator.com