%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% This encoding has two major parts:
%
% - determining which "areas" are in the given input figure
%
% - trying to find a configuration of the blocks that exactly covers
%   those areas
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% input is of the form
% sides(n)
% coord(1, X1, Y1), ... coord(n, Xn, Yn)
% where Xi is in [0,8] and Yi is in [0,6]

xcoord(0..8).
ycoord(0..6).

% An "area" is one of the four triangle-quarters of a 1x1 square
%                                               _
%   |\  (left),      (bottom),  /|  (right),   \ /  (top)
%   |/           /_\            \|
%
% The above are configurations 0,1,2,3
%
% An area is specified by the X,Y coordinate of the lower left corner,
% and its configuration (0-3)

area_type(0..3).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Part 1:
% Now we determine which "areas" are in the given input figure
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% We determine inclusion by looking along the row that the area 
% is in, and counting how many sides of the given figure 
% appear to the left of the area.  If the number is odd, then 
% the area is in the figure.

segment_no(1..N) :- sides(N).

segment(I, X1,Y1, X2,Y2) :- coord(I,X1,Y1), coord(I+1,X2,Y2).
segment(N, X1,Y1, X2,Y2) :- coord(N,X1,Y1), coord(1,X2,Y2), sides(N).

segment_ordered_ycoord(N, Y1, Y2) :- segment(N,X1,Y1,X2,Y2), Y1 <=Y2.
segment_ordered_ycoord(N, Y2, Y1) :- segment(N,X1,Y1,X2,Y2), Y2 <=Y1.

segment_first(I, X1,Y1) :- segment(I, X1,Y1, X2,Y2).
%segment_second(I, X2,Y2) :- segment(I, X1,Y1, X2,Y2).

% Four segment types: /, |, \, _
segment_type(I, 1) :- segment(I, X1,Y1, X2,Y2), Y1-Y2 == X1-X2. %slope=1
segment_type(I, 2) :- segment(I, X1,Y1, X2,Y2), X1 == X2.       % |
segment_type(I, 3) :- segment(I, X1,Y1, X2,Y2), Y1-Y2 == X2-X1. %slope=-1
segment_type(I, 4) :- segment(I, X1,Y1, X2,Y2), Y1 == Y2.       % _

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% For each area, check if segments are along the same row and before it

% segments of type 1: /
before(I, X,Y,A) :- 
	xcoord(X), ycoord(Y), area_type(A),
	(A #mod 3) == 0, % for areas of type 0 and 3
	segment_type(I, 1), 
	segment_first(I, X1, Y1),
	segment_ordered_ycoord(I, Ylower, Yhigher),
	Ylower <= Y, Y < Yhigher, % segment relevant to row
	(Y+1) <= (Y1-X1)+X. % segment to the left
before(I, X,Y,A) :- 
	xcoord(X), ycoord(Y), area_type(A),
	(A #mod 3) != 0, % for areas of type 1 and 2
	segment_type(I, 1),
	segment_first(I, X1, Y1),
	segment_ordered_ycoord(I, Ylower, Yhigher),
	Ylower <= Y, Y < Yhigher, % segment relevant to row
	Y <= (Y1-X1)+X. % segment to the left

% segments of type 2: |
before(I, X,Y,A) :- 
	xcoord(X), ycoord(Y), area_type(A),
	segment_type(I, 2),
	segment_first(I, X1, Y1),
	segment_ordered_ycoord(I, Ylower, Yhigher),
	Ylower <= Y, Y < Yhigher, % segment relevant to row
	X1 <= X. % segment to the left

% segments of type 3: \
before(I, X,Y,A) :- 
	xcoord(X), ycoord(Y), area_type(A),
	A <= 1, % for areas of type 0 and 1
	segment_type(I, 3),
	segment_first(I, X1, Y1),
	segment_ordered_ycoord(I, Ylower, Yhigher),
	Ylower <= Y, Y < Yhigher, % segment relevant to row
	Y >= (Y1+X1)-X. % segment to the left
before(I, X,Y,A) :- 
	xcoord(X), ycoord(Y), area_type(A),
	A >= 2, % for areas of type 2 and 3
	segment_type(I, 3),
	segment_first(I, X1, Y1),
	segment_ordered_ycoord(I, Ylower,Yhigher),
	Ylower <= Y, Y < Yhigher, % segment relevant to row
	(Y+1) >= Y1+X1-X. % segment to the left

% (segments of type 4 are flat (_) so they don't matter)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

in(X,Y,A) :- 
	area_type(A), xcoord(X), ycoord(Y), segment_no(N),
	N{ before(I,X,Y,A): segment_no(I) }N, N #mod 2 == 1.

% Debugging: If we want to count the areas in the figure
% piece(1..252).
% num_in(M) :- 
%	M{in(X,Y,A) : area_type(A) :  xcoord(X) : ycoord(Y)}M, piece(M).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Part 2:
% Now we generate block configurations and check whether 
% there's one that covers the "areas" in the given figure.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% The blocks we can use, given in the problem description

size_block(1,3, 0,0, 4,0, 2,2). %%% Large triangle 
size_block(2,3, 0,0, 4,0, 2,2). %%% Large triangle 
size_block(3,3, 0,0, 2,0, 0,2). %%% Medium triangle
size_block(4,3, 0,0, 2,0, 1,1). %%% Small triangle 
size_block(5,3, 0,0, 2,0, 1,1). %%% Small triangle 
size_block(6,4, 0,0, 1,-1, 2,0, 1,1). %%% Square 
size_block(7,4, 0,0, 1,1,  1,3, 0,2). %%% Parallelogram

block(1..7).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Area elements that make up the blocks
block_element(1,0,0,1). block_element(1,0,0,2).
block_element(1,1,0,A) :- area_type(A).
block_element(1,2,0,A) :- area_type(A).
block_element(1,3,0,0). block_element(1,3,0,1).
block_element(1,1,1,1). block_element(1,1,1,2).
block_element(1,2,1,0). block_element(1,2,1,1).

block_element(2,X,Y,A) :- 
	xcoord(X), ycoord(Y), area_type(A), block_element(1,X,Y,A).

block_element(3,0,0,A) :- area_type(A).
block_element(3,1,0,0). block_element(3,1,0,1).
block_element(3,0,1,0). block_element(3,0,1,1).

block_element(4,0,0,1). block_element(4,0,0,2).
block_element(4,1,0,0). block_element(4,1,0,1).

block_element(5,X,Y,A) :- 
	xcoord(X), ycoord(Y), area_type(A), block_element(4,X,Y,A).

block_element(6,0,-1,2). block_element(6,0,-1,3).
block_element(6,1,-1,0). block_element(6,1,-1,3).
block_element(6,0, 0,1). block_element(6,0, 0,2).
block_element(6,1, 0,0). block_element(6,1, 0,1).

block_element(7,0,0,0). block_element(7,0,0,3). 
block_element(7,0,1,A) :- area_type(A).
block_element(7,0,2,1). block_element(7,0,2,2). 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Angles are 0-7, meaning how many ccw-turns of 45 degrees are performed
% on a block.  (Turning the block around the 0,0 point.)
%
% But wait!  We can only have 90-degree turns when the figure 
% coordinates are integers.  Otherwise the horizontal and/or vertical 
% edges of the blocks become non-integer lengths (irrational, 
% actually) and then the blocks can't cover up the figure "exactly".

%angle(0..7).
angle(0). angle(2). angle(4). angle(6).

% output is of the form 
% put(1, X1, Y1, A1) ... put(n, Xn, Yn, An)

1{put(B,X,Y,Ang) : xcoord(X) : ycoord(Y) : angle(Ang)}1 :- block(B).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% an area (X,Y,A) is in block B (where the block is put)
in_block(B,X,Y,A1) :-
	xcoord(X), ycoord(Y),
	block_element(B,X1,Y1,A1),
	put(B,Xoffset,Yoffset,0),
        X == Xoffset + X1,
        Y == Yoffset + Y1.
in_block(B,X,Y,A) :-
	xcoord(X), ycoord(Y), area_type(A),
	block_element(B,X1,Y1,A1),
	put(B,Xoffset,Yoffset,2),
	A == (A1 + 1) #mod 4,
        X == Xoffset - Y1 -1,
        Y == Yoffset + X1.
in_block(B,X,Y,A) :-
	xcoord(X), ycoord(Y), area_type(A),
	block_element(B,X1,Y1,A1),
	put(B,Xoffset,Yoffset,4),
	A == (A1 + 2) #mod 4,
        X == Xoffset - X1 -1,
        Y == Yoffset - Y1 -1.
in_block(B,X,Y,A) :-
	xcoord(X), ycoord(Y), area_type(A),
	block_element(B,X1,Y1,A1),
	put(B,Xoffset,Yoffset,6),
	A == (A1 + 3) #mod 4,
        X == Xoffset + Y1,
        Y == Yoffset - X1 -1.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% no overlaps allowed
:- in_block(B,X,Y,A), in_block(B1,X,Y,A), B != B1.

% each are in the figure must be covered by a block
covered(X,Y,A) :- in_block(B,X,Y,A).
:- in(X,Y,A), not covered(X,Y,A).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%#hide.
%#show put/4.
%#show in/3.
%#show in_block/4.



