users-prolog
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

question on fd_minimize and if fd var bindings are created on disjunctio


From: Adam Russell
Subject: question on fd_minimize and if fd var bindings are created on disjunctions
Date: Fri, 17 Dec 2021 19:22:57 -0500
User-agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Firefox/68.0 SeaMonkey/2.53.10.1

In one of the 2021 Advent of Code puzzles the requirement is to find the
lowest cost traversal of a maze. The actual problem statement is at https://adventofcode.com/2021/day/15

Rather than just, say, implement A* I thought I'd try something a little different. My thought was to represent the indices of the grid as fd vars and the movements within the grid as constraints. The code to do this is http://paste.debian.net/hidden/70acfece/ which is to act on the input http://paste.debian.net/hidden/ce112fda/

This works for this 10x10 test input. I get the answer 40 which is the minimal cost path. Trying it out on a larger input and gprolog crashes. Since I have access to a system with considerable memory I figured I could just increase CSTRSZ to some large limit, but gprolog will not accept too large a value for CSTRSZ without just crashing at the start. Is there an internal hard coded limit to how high this may be set?

I figured since this approach seems to work OK, besides the limit on CSTRSZ I would just re-implement the constraints using SWI-Prolog's clpfd since SWI seems happier about allowing the user to set arbitrarily high memory allocation sizes. I did that but then found SWI would not yield a correct answer!

I posted a question on this to the SWI forums and one possible explanation given there is that for this part of the code which restricts the possible movements through the maze

            (M #= A rem LS,  M #\= 1, B #= A - 1); %LEFT
            (M #= A rem LS,  M #> 0,  B #= A + 1); %RIGHT
            (A #> LS,             B #= A - LS);         %UP
            (A #=< MaxN,     B #= A + LS)       %DOWN

that gprolog is (correctly! in my opinion) creating an fd var binding
for each part of the disjunction but SWI's clpfd is not.

I suppose that would explain why gprolog yields an optimally minimal answer but blasts through the CSTRSZ limitations, and SWI does not yield a minimal answer at all.

That all seems plausible, but is that in fact true? Or is there something else at work here?




reply via email to

[Prev in Thread] Current Thread [Next in Thread]