1% BEGIN LICENSE BLOCK
2% Version: CMPL 1.1
3%
4% The contents of this file are subject to the Cisco-style Mozilla Public
5% License Version 1.1 (the "License"); you may not use this file except
6% in compliance with the License.  You may obtain a copy of the License
7% at www.eclipse-clp.org/license.
8% 
9% Software distributed under the License is distributed on an "AS IS"
10% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See
11% the License for the specific language governing rights and limitations
12% under the License. 
13% 
14% The Original Code is  CPViz Constraint Visualization System
15% The Initial Developer of the Original Code is  Helmut Simonis
16% Portions created by the Initial Developer are
17% Copyright (C) 2009-2010 Helmut Simonis
18% 
19% Contributor(s): 	Helmut Simonis, 4C, Univerity College Cork, Cork
20%			
21% 
22% END LICENSE BLOCK
23% ----------------------------------------------------------------------
24:-module(checker).
25
26:-export(top/0).
27
28:-lib(ic).
29:-lib(timeout).
30:-lib(lists).
31:-lib(hash).
32:-use_module('../visualize_tree').
33:-use_module('../lex_leq').
34:-use_module('../gcc').
35:-use_module('../bin_packing').
36
37:-local struct(boat(nr,index,cap,crew,sorting)).
38
39top:-
40        problem(11,Hosts,Guests,HostHash,GuestHash),
41        check(Hosts,Guests,5,HostHash,GuestHash,"results/PPP1_5.res"),
42        check(Hosts,Guests,6,HostHash,GuestHash,"results/PPP1_6.res"),
43        check(Hosts,Guests,7,HostHash,GuestHash,"results/PPP1_7.res"),
44        check(Hosts,Guests,8,HostHash,GuestHash,"results/PPP1_8.res"),
45        check(Hosts,Guests,9,HostHash,GuestHash,"results/PPP1_9.res"),
46
47        true.
48
49get_result(Stream,Matrix,NrPeriods,NrGuests,HostHash,GuestHash):-
50        read_token(Stream,NrPeriods,integer),
51        writeq(NrPeriods),nl,
52        read_token(Stream,NrGuests,integer),
53        writeq(NrGuests),nl,
54        (multifor([I,J],[1,1],[NrPeriods,NrGuests]),
55         param(Matrix,Stream,HostHash,GuestHash) do
56            read_token(Stream,Value,integer),
57%            writeln(Value),
58            hash_find(GuestHash,J,Guest),
59            hash_find(HostHash,Value,Value1),
60%            writeln(entry(I,J,Guest,Value,Value1)),
61            subscript(Matrix,[Guest,I],Value1)
62        ).
63        
64
65check(Hosts,Guests,NrPeriods,HostHash,GuestHash,ResultFile):-
66        writeq(Hosts),nl,
67        writeq(Guests),nl,
68        length(Hosts,NrHosts),
69        length(Guests,NrGuests),
70        dim(Matrix,[NrGuests,NrPeriods]),
71        Matrix[1..NrGuests,1..NrPeriods] :: 1..NrHosts,
72        open(ResultFile,read,Stream),
73        get_result(Stream,Matrix,NrPeriods,NrGuests,HostHash,GuestHash),
74        close(Stream),
75        writeln(read_result),
76        Width is NrPeriods + ((NrPeriods+2)//3)*(NrHosts+2),
77        Height is 3*11+4, 
78        Output="TMP",
79        create_visualization([output:Output,
80                              range_to:2000,
81                              width:Width,
82                              height:Height],Handle),
83        add_visualizer(Handle,
84                       domain_matrix(Matrix),
85                       [group:1,
86                        display:text]),
87        
88        (for(I,1,NrGuests),
89         param(Matrix,NrPeriods) do
90            collection_to_list(Matrix[I,1..NrPeriods],L),
91            writeln(L),
92            ic:alldifferent(Matrix[I,1..NrPeriods])
93        ),
94
95        (for(J,1,NrPeriods),
96         param(Matrix,NrHosts,NrPeriods,NrGuests,Guests,Hosts,Handle) do
97            make_bins(Hosts,Bins),
98            bin_packing(Matrix[1..NrGuests,J],Guests,Bins),
99            X is NrPeriods+2+((J-1)//3)*(NrHosts+2),
100            Y is ((J-1) mod 3)*13,
101            add_visualizer(Handle,
102                           vector(Bins),
103                           [group:other,
104                            x:X,
105                            y:Y])
106        ),
107        writeln(bins),
108        (for(I,1,NrGuests-1),
109         param(Matrix,NrGuests,NrPeriods) do
110            (for(I1,I+1,NrGuests),
111             param(Matrix,NrPeriods,I) do
112                card_eq(I,I1,Matrix[I,1..NrPeriods],
113                        Matrix[I1,1..NrPeriods],1)
114            )
115        ),
116        writeln(eq),
117        close_visualization(Handle).
118
119indices([],_,_,_,[]).
120indices([X|X1],N,J,K,[t(X,N,group(1,K-J))|T1]):-
121        N1 is N+1,
122        K1 is K+1,
123        indices(X1,N1,J,K1,T1).
124
125make_bins(HostCapacity,Bins):-
126        (foreach(Cap,HostCapacity),
127         foreach(B,Bins) do
128            B :: 0..Cap
129        ).
130
131card_eq(I,I1,Vector1,Vector2,Card):-
132        collection_to_list(Vector1,List1),
133        collection_to_list(Vector2,List2),
134        (foreach(X,List1),
135         foreach(Y,List2),
136         fromto(0,A,A+B,Term) do
137            #=(X,Y,B)
138        ),
139        (eval(Term) #=< Card ->
140            true
141        ;
142            writeln(eq(I,I1,List1,List2))
143        ).
144
145problem(Instance,HostCapacity,GuestSize,HostHash,GuestHash):-
146        hash_create(GuestHash),
147        hash_create(HostHash),
148        problem_data(Instance,List),
149        findall(boat{nr:Nr,cap:Cap,crew:Crew,sorting:Space},
150                (boat(Nr,Cap,Crew),
151                 Space is (Cap-Crew)*100+Crew,
152                 memberchk(Nr,List)),Hosts),
153        findall(boat{nr:Nr,cap:Cap,crew:Crew,sorting:Space},
154                (boat(Nr,Cap,Crew),
155                 Space is (Cap-Crew)*100+Crew,
156                 not memberchk(Nr,List)),Guests),
157        (foreach(boat{index:I},Guests),
158         count(I,1,_) do
159            true
160        ),
161        sort(sorting of boat,>=,Hosts,SortedHosts),
162        sort(crew of boat,>=,Guests,SortedGuests),
163        
164        guest_pattern(SortedGuests,GuestSize,GuestHash),
165        host_capacity(SortedHosts,HostCapacity,HostHash).
166
167host_capacity(Hosts,HostCapacity,HostHash):-
168        (foreach(boat{nr:Nr,cap:Cap,crew:Crew},Hosts),
169         count(J,1,_),
170         foreach(Capacity,HostCapacity),
171         param(HostHash) do
172            Capacity is Cap-Crew,
173            Nr1 is Nr-1,
174            writeln(host(Nr1,J)),
175            hash_add(HostHash,Nr1,J)
176        ).
177
178guest_pattern(Guests,Height,GuestHash):-
179        (foreach(boat{index:Nr,crew:Crew},Guests),
180         count(J,1,_),
181         foreach(Crew,Height),
182         param(GuestHash) do
183            writeln(guest(Nr,J)),
184            hash_add(GuestHash,Nr,J)
185        ).
186
187boat(1 , 6 , 2).
188boat(2 , 8 , 2).
189boat(3 , 12 , 2).
190boat(4 , 12 , 2).
191boat(5 , 12 , 4).
192boat(6 , 12 , 4).
193boat(7 , 12 , 4).
194boat(8 , 10 , 1).
195boat(9 , 10 , 2).
196boat(10 , 10 , 2).
197boat(11 , 10 , 2).
198boat(12 , 10 , 3).
199boat(13 , 8 , 4).
200boat(14 , 8 , 2).
201boat(15 , 8 , 3).
202boat(16 , 12 , 6).
203boat(17 , 8 , 2).
204boat(18 , 8 , 2).
205boat(19 , 8 , 4).
206boat(20 , 8 , 2).
207boat(21 , 8 , 4).
208boat(22 , 8 , 5).
209boat(23 , 7 , 4).
210boat(24 , 7 , 4).
211boat(25 , 7 , 2).
212boat(26 , 7 , 2).
213boat(27 , 7 , 4).
214boat(28 , 7 , 5).
215boat(29 , 6 , 2).
216boat(30 , 6 , 4).
217boat(31 , 6 , 2).
218boat(32 , 6 , 2).
219boat(33 , 6 , 2).
220boat(34 , 6 , 2).
221boat(35 , 6 , 2).
222boat(36 , 6 , 2).
223boat(37 , 6 , 4).
224boat(38 , 6 , 5).
225boat(39 , 9 , 7).
226boat(40 , 0 , 2).
227boat(41 , 0 , 3).
228boat(42 , 0 , 4 ).
229
230% problem 1-9  are from Symmetry breaking paper
231problem_data(1,[2,3,4,5,6,7,8,9,10,11,12,14,16]).
232problem_data(2,[3,4,5,6,7,8,9,10,11,12,13,14,16]).
233problem_data(3,[3,4,5,6,7,8,9,10,11,12,14,15,16]).
234problem_data(4,[3,4,5,6,7,8,9,10,11,12,14,16,25]).
235problem_data(5,[3,4,5,6,7,8,9,10,11,12,14,16,23]).
236problem_data(6,[3,4,5,6,7,8,9,10,11,12,15,16,25]).
237problem_data(7,[1,3,4,5,6,7,8,9,10,11,12,14,16]).
238problem_data(8,[3,4,5,6,7,8,9,10,11,12,16,25,26]).
239problem_data(9,[3,4,5,6,7,8,9,10,11,12,14,16,30]).
240% this is my favorite host selection
241problem_data(10,[1,2,3,4,5,6,7,8,9,10,11,12,14]).
242% problems 11-16 are problems 1-6 from Van Hentenryck/Michel
243problem_data(11,[1,2,3,4,5,6,7,8,9,10,11,12,16]).
244problem_data(12,[1,2,3,4,5,6,7,8,9,10,11,12,13]).
245problem_data(13,[1,3,4,5,6,7,8,9,10,11,12,13,19]).
246problem_data(14,[3,4,5,6,7,8,9,10,11,12,13,25,26]).
247problem_data(15,[1,2,3,4,5,6,7,8,9,10,11,19,21]).
248problem_data(16,[1,2,3,4,5,6,7,8,9,16,17,18,19]).
249
250problem_data(20,[3,4,5,6,7,8,9,10,11,12,16,39]).
251