3 ms·

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

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.

scott_s 17y ago
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.
- marshallp 17y ago
  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.
  - scott_s 17y ago
    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 http://news.ycombinator.com/item?id=1168289
    - marshallp 17y ago
      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.

scott_s 17y ago

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.

marshallp 17y ago
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.
- scott_s 17y ago
  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 http://news.ycombinator.com/item?id=1168289
  - marshallp 17y ago
    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.