5 ms·
Please read through the discussion around the winning entry, including what the winning coder and other participants have to say: http://news.ycombinator.com/it
by 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 agoThe 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.