I think that modelling with CLPFD this puzzle could be done with automaton/8.
In Prolog I would write
escape_zurg(T,S) :-
aggregate(min(T,S), (
solve([5,10,20,25], [], S),
sum_timing(S, T)), min(T,S)).
solve([A, B], _, [max(A, B)]).
solve(L0, R0, [max(A, B), C|T]) :-
select(A, L0, L1),
select(B, L1, L2),
append([A, B], R0, R1),
select(C, R1, R2),
solve([C|L2], R2, T).
sum_timing(S, T) :-
aggregate(sum(E), member(E, S), T).
that yields this solution
?- escape_zurg(T,S).
T = 60,
S = [max(5, 10), 5, max(20, 25), 10, max(10, 5)].
edit
well, automaton/8 is well beyond my reach...
let's start simpler: what could be a simple representation of state ?
on left/right we have 4 slots, that can be empty: so
escape_clpfd(T, Sf) :-
L0 = [_,_,_,_],
Zs = [0,0,0,0],
L0 ins 5\/10\/20\/25,
all_different(L0),
...
now, since the problem it's so simple, we can 'hardcode' the state change
...
lmove(L0/Zs, 2/2, L1/R1, T1), rmove(L1/R1, 1/3, L2/R2, T2),
lmove(L2/R2, 3/1, L3/R3, T3), rmove(L3/R3, 2/2, L4/R4, T4),
lmove(L4/R4, 4/0, Zs/ _, T5),
...
the first lmove/4 must shift 2 elements from left to right, and after it have done, we will have 2 zeros at left, and 2 at right. The timing (T1) will be max(A,B), where A,B are incognite by now.
rmove/4 is similar, but will 'return' in T2 the only element (incognito) it will move from right to left. We are encoding the evolution asserting the number of 0s on each side (seems not difficult to generalize).
Let's complete:
...
T #= T1 + T2 + T3 + T4 + T5,
Sf = [T1,T2,T3,T4,T5].
Now, rmove/4 is simpler, so let's code it:
rmove(L/R, Lz/Rz, Lu/Ru, M) :-
move_one(R, L, Ru, Lu, M),
count_0s(Ru, Rz),
count_0s(Lu, Lz).
it defers to move_one/5 the actual work, then applies the numeric constraint we hardcoded above:
count_0s(L, Z) :-
maplist(is_0, L, TF),
sum(TF, #=, Z).
is_0(V, C) :- V #= 0 #<==> C.
is_0/2 reifies the empty slot condition, that is makes countable the truth value. It's worth to test it:
?- count_0s([2,1,1],X).
X = 0.
?- count_0s([2,1,C],1).
C = 0.
?- count_0s([2,1,C],2).
false.
Coding move_one/5 in CLP(FD) seems difficult. Here Prolog nondeterminism seems really appropriate...
move_one(L, R, [Z|Lt], [C|Rt], C) :-
select(C, L, Lt), is_0(C, 0),
select(Z, R, Rt), is_0(Z, 1).
select/3 it's a pure predicate, and Prolog will backtrack when labeling will need...
There is no minimization, but that is easy to add after we get the solutions.
So far, all seems 'logical' to me. But, of course...
?- escape_clpfd(T, S).
false.
So, here be dragons...
?- spy(lmove),escape_clpfd(T, S).
% Spy point on escape_zurg:lmove/4
* Call: (9) escape_zurg:lmove([_G12082{clpfd = ...}, _G12164{clpfd = ...}, _G12246{clpfd = ...}, _G12328{clpfd = ...}]/[0, 0, 0, 0], 2/2, _G12658/_G12659, _G12671) ? creep
Call: (10) escape_zurg:move_one([_G12082{clpfd = ...}, _G12164{clpfd = ...}, _G12246{clpfd = ...}, _G12328{clpfd = ...}], [0, 0, 0, 0], _G12673, _G12674, _G12661) ? sskip
... etc etc
Sorry, will post a solution if I'll get some spare time to debug...
edit there were several bugs... with this lmove/4
lmove(L/R, Lz/Rz, Lu/Ru, max(A, B)) :-
move_one(L, R, Lt, Rt, A),
move_one(Lt, Rt, Lu, Ru, B),
count_0s(Lu, Lz),
count_0s(Ru, Rz).
at least we start getting solutions (added variables to interface to label from outside...)
escape_clpfd(T, Sf, L0) :- ...
?- escape_clpfd(T, S, Vs), label(Vs).
T = 85,
S = [max(5, 10), 10, max(10, 20), 20, max(20, 25)],
Vs = [5, 10, 20, 25] ;
T = 95,
S = [max(5, 10), 10, max(10, 25), 25, max(25, 20)],
Vs = [5, 10, 25, 20] ;
...
edit
the code above works, but is painfully slow:
?- time((escape_clpfd(60, Sf, L0),label(L0))).
% 15,326,054 inferences, 5.466 CPU in 5.485 seconds (100% CPU, 2803917 Lips)
Sf = [max(5, 10), 10, max(20, 25), 5, max(5, 10)],
L0 = [5, 10, 20, 25]
with this change to move_one/5:
move_one([L|Ls], [R|Rs], [R|Ls], [L|Rs], L) :-
L #\= 0,
R #= 0.
move_one([L|Ls], [R|Rs], [L|Lu], [R|Ru], E) :-
move_one(Ls, Rs, Lu, Ru, E).
I have better performance:
?- time((escape_clpfd(60, Sf, L0),label(L0))).
% 423,394 inferences, 0.156 CPU in 0.160 seconds (97% CPU, 2706901 Lips)
Sf = [max(5, 10), 5, max(20, 25), 10, max(5, 10)],
L0 = [5, 10, 20, 25]
then, adding to lmove/4
... A #< B, ...
i get
% 233,953 inferences, 0.089 CPU in 0.095 seconds (94% CPU, 2621347 Lips)
Sf = [max(5, 10), 5, max(20, 25), 10, max(5, 10)],
the whole it's still a lot slower than my pure Prolog solution...
edit
other small improvements:
?- time((escape_clpfd(60, Sf, L0),maplist(#=,L0,[5,10,20,25]))).
% 56,583 inferences, 0.020 CPU in 0.020 seconds (100% CPU, 2901571 Lips)
Sf = [max(5, 10), 5, max(20, 25), 10, max(5, 10)],
where all_different/1 has been replaced by
...
chain(L0, #<),
...
Another improvement: counting both side for zeros is useless: removing (arbitrarly) one side in both lmove and rmove we get
% 35,513 inferences, 0.014 CPU in 0.014 seconds (100% CPU, 2629154 Lips)
Sf = [max(5, 10), 5, max(20, 25), 10, max(5, 10)],
edit
Just for fun, here is the same pure (except aggregation) Prolog solution, using a simple deterministic 'lifting' of variables (courtesy 'lifter'):
:- use_module(carlo(snippets/lifter)).
solve([A, B], _, [max(A, B)]).
solve(L0, R0, [max(A, B), C|T]) :-
solve([C|select(B, select(A, L0, °), °)],
select(C, append([A, B], R0, °), °),
T).
btw, it's rather fast:
?- time(escape_zurg(T,S)).
% 50,285 inferences, 0.065 CPU in 0.065 seconds (100% CPU, 769223 Lips)
T = 60,
S = [max(5, 10), 5, max(20, 25), 10, max(10, 5)].
(the absolute timing is not so good because I'm running a SWI-Prolog compiled for debugging)
