/*
Bowls and Oranges problem in Picat.
From BitTorrent Developer Challenge
http://www.bittorrent.com/company/about/developer_challenge
"""
You have 40 bowls, all placed in a line at exact intervals of
1 meter. You also have 9 oranges. You wish to place all the oranges
in the bowls, no more than one orange in each bowl, so that there are
no three oranges A, B, and C such that the distance between A and B is
equal to the distance between B and C. How many ways can you arrange
the oranges in the bowls?.
"""
Via http://surana.wordpress.com/2011/06/01/constraint-programming-example/
This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
import cp.
main => time2(go).
go =>
N = 40, % number of bowls
M = 9, % number of oranges
X = new_list(M),
X :: 1..N,
all_different(X),
% all_distinct(X),
increasing(X),
% increasing2(X),
foreach(I in 1..M, J in 1..M, K in 1..M, I < J, J < K)
X[J]-X[I] #!= X[K]-X[J]
end,
% solution: 7555794,
All=solve_all([], X), % 26.1s 12882858 backtracks
writeln(All.length).
%
% fail driven approach
%
go2 ?=>
get_global_map().put(count,0),
N = 40, % number of bowls
M = 9, % number of oranges
X = new_list(M),
X :: 1..N,
all_different(X),
% all_distinct(X),
increasing(X),
% increasing2(X),
foreach(I in 1..M, J in 1..M, K in 1..M, I < J, J < K)
X[J]-X[I] #!= X[K]-X[J]
end,
solve(X),
% solve([ff,split], X),
get_global_map().put(count, get_global_map().get(count)+1),
% println(get_global_map().get(count)),
fail.
% print the counts
go2 =>
println(get_global_map().get(count)),
nl.
increasing(List) =>
foreach(I in 2..List.length) List[I-1] #=< List[I] end.
increasing2([]) ?=> true.
increasing2([_]) ?=> true.
increasing2([X,Y|Xs]) =>
X #=< Y,
increasing2(Xs).