On this input http://paste.debian.net/hidden/78d86c08/ this GNU Prolog code http://paste.debian.net/hidden/1bfbf7ee/ returns a correct answer of 40.
This SWI-Prolog code against the same input does not return a correct answer. http://paste.debian.net/hidden/b4dae451/
Perhaps I am mistranslating from GNU to SWI? Anyone see what might be wrong with the SWI code? Or maybe I am misunderstanding something more fundamental about the SWI clpfd solver?
(This is related to Advent of Code 2021 Day 15 if you haven’t worked that yet and want to avoid spoilers. This is the first one I’ve really gotten stuck on. My thinking was that GNU’s implementation of fd_minimize with branch and bound would do the hard part of the traversal for me. Which it indeed does for small inputs but GNU has some internal size limitations around the number of constraints, which SWI apparently does not, which is why I switched. GNU crashes on large inputs because of this. I think SWI might work, except SWI is not giving the same solution for small test inputs.)
1 Like
FWIW, I used two different approaches for day 15 – a very naive algorithm that works very well with SWI’s mode-directed tabling and then A* for the second part, when the tabling approach took almost a minute (here, if you’re interested).
In any case, I’m not sure why this isn’t working…I see that it gives an answer that’s close but inaccurate. My guess is that the disjunction in travel/5 means that it isn’t actually setting up four different possible bindings of the attributed variables to minimize, but just picking one, then backtracking, meaning that it will find a solution, but doesn’t necessarily know that it needs to backtrack to find a better one.
Indeed, trying that out, I see it leaves a choicepoint…trying other solutions is taking quite a while, but I suppose would eventually find another route.
Interesting! And presumably GNU is setting up four different possible bindings which is why it finds the optimal solution this way, but also explains why it blasts through its hard coded limit for the number of constraints.
For the Advent of Code I generally always try and use these puzzles as an excuse for trying something new and this seemed like a fun idea. I am actually happy that it sort of works!
You misunderstand, I originally wrote this in GNU Prolog which has none of those libraries. The point of my question was about the clpfd abilities of GNU and SWI, not SWI’s catalog of modules.
While many people these days use DCGs for any general list handling I don’t necessarily use them in that way all the time. Although I more or less agree with their broader use in this way, it’s more fun to me to write the recursion.