/*
Dinesman's multiple-dwelling problem in Picat.
From
http://rosettacode.org/wiki/Dinesman%27s_multiple-dwelling_problem
"""
The task is to solve Dinesman's multiple dwelling problem but in a way that most
naturally follows the problem statement given below. Solutions are allowed (but
not required) to parse and interpret the problem text, but should remain flexible
and should state what changes to the problem text are allowed. Flexibility and
ease of expression are valued.
Examples may be be split into "setup", "problem statement", and "output" sections
where the ease and naturalness of stating the problem and getting an answer,
as well as the ease and flexibility of modifying the problem are the primary concerns.
Example output should be shown here, as well as any comments on the examples flexibility.
The problem
Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an
apartment house that contains only five floors. Baker does not live on the
top floor. Cooper does not live on the bottom floor. Fletcher does not live
on either the top or the bottom floor. Miller lives on a higher floor than
does Cooper. Smith does not live on a floor adjacent to Fletcher's. Fletcher
does not live on a floor adjacent to Cooper's. Where does everyone live?
"""
Model created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
import util.
import cp.
main => go.
go =>
dinesman_cp,
dinesman1,
dinesman2a,
dinesman2b,
nl.
% CP approach
dinesman_cp =>
println(dinesman_cp),
N = 5,
X = [Baker, Cooper, Fletcher, Miller, Smith],
X :: 1..N,
all_different(X),
% Baker does not live on the fifth floor.
Baker #!= 5,
% Cooper does not live on the first floor.
Cooper #!= 1,
% Fletcher does not live on either the fifth or the first floor.
Fletcher #!= 5,
Fletcher #!= 1,
% Miller lives on a higher floor than does Cooper.
Miller #> Cooper,
% Smith does not live on a floor adjacent to Fletcher'.
abs(Smith-Fletcher) #> 1,
% Fletcher does not live on a floor adjacent to Cooper's.
abs(Fletcher-Cooper) #> 1,
solve(X),
println([baker=Baker, cooper=Cooper, fletcher=Fletcher, miller=Miller, smith=Smith]).
%
% The constraints (non CP approach)
%
% floors: 1: bottom .. 5: top floor
%
constraints([B,C,F,M,S]) =>
B != 5, % Baker not top floor
C != 1, % Cooper not bottom floor
F != 1, F != 5, % Fletcher not botton nor top floor
M > C, % Miller higher floor than Cooper
not adjacent(S, F), % Smith and Fletcher not adjacent
not adjacent(F, C). % Fletcher and Cooper not adjacent
adjacent(A,B) => abs(A-B) == 1.
% Non-CP approach, using permutations
dinesman1 =>
println(dinesman1),
foreach([B,C,F,M,S] in permutations(1..5), constraints([B,C,F,M,S]))
println([baker=B, cooper=C, fletcher=F, miller=M, smith=S])
end.
% using my_alldifferent1
dinesman2a =>
println(dinesman2a),
T = 1..5,
foreach(B in T, C in T, F in T, M in T, S in T)
if my_alldifferent1([B,C,F,M,S]), constraints([B,C,F,M,S]) then
println([baker=B, cooper=C, fletcher=F, miller=M, smith=S])
end
end.
% using my_alldifferent2
dinesman2b =>
println(dinesman2b),
T = 1..5,
foreach(B in T, C in T, F in T, M in T, S in T)
if my_alldifferent1([B,C,F,M,S]), constraints([B,C,F,M,S]) then
println([baker=B, cooper=C, fletcher=F, miller=M, smith=S])
end
end.
% count the number of different values
my_alldifferent1(L) =>
L.length == L.remove_dups().length.
my_alldifferent2(L) =>
foreach(I in L, J in L)
if I < J then
L[I] != L[J]
end
end.