%implementation of the second step of ACC '98
get_pattern_sets(PatternSet):-
	%Patterns is the set of all 38 legal patterns
	findall(P, get_patterns(P), Patterns), 

	%Home, Away, and Bye are the corresponding matrices from the Patterns.
	get_home(Patterns, Home), 
	get_away(Patterns, Away), 
	get_bye(Patterns, Bye), 

	%X represents the indexes of the selected patterns in a legal pattern set.
	X = [_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_],
	X in [0,1],
	sum(X) #= 9, 
	
	%make sure every day there are 4 teams that play home.
	transpose(Home, HT),
	day_constraints(HT, X, 4),

	%make sure every day there are 4 teams that play away.
	transpose(Away, AT),
	day_constraints(AT, X, 4),

	%make sure every day there is 1 team that has a bye.
	transpose(Bye, BT),
	day_constraints(BT, X, 1),
		
	%make sure that patterns that are not compatible are not put in a pattern set.
	numlist(1,38,PatternIndex),
	foreach(PatternIndex, foreach(PatternIndex, compatible_constraints(Patterns, X))),

	labeling(X),
	
	make_pattern(Home, X, HomePattern),
	make_pattern(Away, X, AwayPattern),
	make_pattern(Bye, X, ByePattern), 
	PatternSet = [HomePattern, AwayPattern, ByePattern]. 
	%writeln(PatternSet).

%selects from Matrice, the rows for which the corresponding elements of colum X are 1.
make_pattern(Matrice, X, Pattern):-make_pattern(Matrice, X, Pattern, []).
make_pattern([], _, Pattern, Pattern).
make_pattern([Row|Matrice], [X|Xs], Pattern, Acc):-
	(X == 1, !, 
	 RowElem = [Row], 
	 append(Acc, RowElem, Acc1);
	 Acc1 = Acc), 

	 make_pattern(Matrice, Xs, Pattern, Acc1).
	 
%from a Patterns structure selects the Home pattern (the first column)
get_home(Patterns, Home):-
	get_home(Patterns, Home, []).
get_home([], Home, Home).
get_home([P|Patterns], Home, Acc):-
	P = [H, _A, _B], 
	H_List = [H],
	append(Acc, H_List, Acc1),
	get_home(Patterns, Home, Acc1).


%from a Patterns structure selects the Away pattern (the second column)
get_away(Patterns, Away):-
	get_away(Patterns, Away, []).
get_away([], Away, Away).
get_away([P|Patterns], Away, Acc):-
	P = [_H, A, _B], 
	A_List = [A],
	append(Acc, A_List, Acc1),
	get_away(Patterns, Away, Acc1).

%from a Patterns structure selects the Bye pattern (the third column)
get_bye(Patterns, Bye):-
	get_bye(Patterns, Bye, []).
get_bye([], Bye, Bye).
get_bye([P|Patterns], Bye, Acc):-
	P = [_H, _A, B], 
	B_List = [B],
	append(Acc, B_List, Acc1),
	get_bye(Patterns, Bye, Acc1).

%for each day, the selected rows (selector X) sum to Sum
day_constraints([], _, _).
day_constraints([Row|Matrix], X, Sum):-
	scalar_product(X, Row, #=, Sum), 
	day_constraints(Matrix, X, Sum).

%Result is Matrice with added column List
add_column(Matrice, List, Result):- add_column(Matrice, List, Result, []).
add_column([], [], Result, Result).
add_column([Row|Matrice], [X|List], Result, Acc):-
	ElemList = [X],
	append( Row, ElemList, Row1),
	RowList = [Row1],
	append(Acc, RowList, Acc1),
	add_column(Matrice, List, Result, Acc1).
	
%If pattern A and pattern B are not compatible (there is no possible meeting date for corresponding teams),
%a constraint is added to not allow Pattern A and B to be chosen simultaneously.
compatible_constraints(Patterns, X, A, B):-
	(A < B,
	%writeln(A),
	%writeln(B),

	nth(A, Patterns, PatternA), 
	nth(B, Patterns, PatternB),

	PatternA = [HomeA, AwayA, _], 
	PatternB = [HomeB, AwayB, _],
	not_compatible(HomeA, AwayB),
	not_compatible(HomeB, AwayA)
	->
	nth(A, X, Xa), 
	nth(B, X, Xb),
	Xa + Xb #< 2; 
	true
	).

%two patterns are not compatible if for every day, two teams following this patterns cannot meet.
not_compatible([], []).
not_compatible([A|As], [B|Bs]):-
	((A = 0) ; (B =0)),
	not_compatible(As, Bs).