clc
clear
close all

tic
disp('starting...')

x = importdata('input.txt');
L = size(x,1);
for i=1:L/11
    z = x{(i-1)*11+1};
    T(i,1).ID   =  str2double(z(6:9));
    T(i,1).p    =  cell2mat(x((i-1)*11+2:(i-1)*11+11,:))=='#';
end

for i=1:size(T,1)
    x = T(i).p;
    % find number of connecting pieces for x
    connectedID = [];
    for j=1:size(T,1)
        if j==i
            continue
        end

        z=shareEdge(x,T(j).p);
        if z
            connectedID(end+1,1) = T(j).ID;
        end
    end
    T(i).connectedID = connectedID;
end

z=[];
for i=1:size(T,1)
    if size(T(i).connectedID,1)==2
        z = [z,T(i).ID];
    end
    T(i).aligned = false;
end
format long
disp(prod(z)) % Answer Part a

% align pieces
allAligned = false;
while ~allAligned

    T(1).aligned = true;
    for i=1:size(T,1)
        if T(i).aligned
            for j=1:size(T(i).connectedID,1)
                idxK = ID2idx(T,T(i).connectedID(j));
                if ~T(idxK).aligned
                    T(idxK).p       = alignPieces(T(i).p,T(idxK).p);
                    T(idxK).aligned = true;
                end
            end
        end
    end

    %Check if all aligned:
    allAligned = true;
    for i=1:size(T,1)
        if ~T(i).aligned
            allAligned = false;
            break
        end
    end
end

% Find direction of pieces relative to each other
for i=1:size(T,1)
    T(i).connectedIDpos = [];
    for j=1:size(T(i).connectedID,1)
        idxK = ID2idx(T,T(i).connectedID(j));
        T(i).connectedIDpos(j,1) = getRelativePosition(T(i).p,T(idxK).p);
    end
end

% Fit pieces together:
% Start with North-West corner, i.e. the piece that has only East and South
% neighbour
for i=1:size(T,1)
    z = T(i).connectedIDpos;
    if length(z)==2 && any(z==2) && any(z==3)
        M(1,1) = T(i).ID;
        break
    end
end

% Find pieces connecting to the east
r = 1;
c = 1;
while 1
    c = c + 1;
    z = find(T(ID2idx(T,M(r,c-1))).connectedIDpos==2);
    if isempty(z)
        %reached end of the row
        break
    else
        M(r,c) =  T(ID2idx(T,M(r,c-1))).connectedID(z);
    end
end

while 1
    % Next row
    z = find(T(ID2idx(T,M(r,1))).connectedIDpos==3);

    if isempty(z)
        %reached end of the column
        break
    else
        r = r+1;
        M(r,1) = T(ID2idx(T,M(r-1,1))).connectedID(z);

        % Find pieces connecting to the east
        c = 1;
        while 1
            c = c + 1;
            z = find(T(ID2idx(T,M(r,c-1))).connectedIDpos==2);
            if isempty(z)
                %reached end of the row
                break
            else
                M(r,c) =  T(ID2idx(T,M(r,c-1))).connectedID(z);
            end
        end

    end
end

% remove edges
for i=1:size(T,1)
    z       = T(i).p;
    T(i).p  = z(2:end-1,2:end-1);
end

% Build pixelmap
P = false(size(M,1)*size(T(1).p,1),size(M,2)*size(T(1).p,2));

for r=1:size(M,1)
    for c=1:size(M,1)
        P((r-1)*8+1:r*8,(c-1)*8+1:c*8) = T(ID2idx(T,M(r,c))).p;
    end
end

% Monster
M       = false(3,20);
M(1,:)  = '                  # '=='#';
M(2,:)  = '#    ##    ##    ###'=='#';
M(3,:)  = ' #  #  #  #  #  #   '=='#';

N1 = findMonsters(P,M);
N2 = findMonsters(rot90(P,1),M);
N3 = findMonsters(rot90(P,2),M);
N4 = findMonsters(rot90(P,3),M);

N5 = findMonsters(fliplr(P),M);
N6 = findMonsters(rot90(fliplr(P),1),M);
N7 = findMonsters(rot90(fliplr(P),2),M);
N8 = findMonsters(rot90(fliplr(P),3),M);

N = max([N1,N2,N3,N4,N5,N6,N7,N8]);
disp(sum(sum(P)) - N * sum(sum(M))) % Answer Part b

toc
disp('Finished')

% functions:
function z=shareEdge(x,y)
z = false;

if all(x(1,:)==y(1,:)) || all(x(1,:)==y(end,:)) || all(x(1,:)==y(:,1)') || all(x(1,:)==y(:,end)') || ...
        all(x(end,:)==y(1,:)) || all(x(end,:)==y(end,:)) || all(x(end,:)==y(:,1)') || all(x(end,:)==y(:,end)') || ...
        all(x(:,1)==y(1,:)') || all(x(:,1)==y(end,:)') || all(x(:,1)==y(:,1)) || all(x(:,1)==y(:,end)) || ...
        all(x(:,end)==y(1,:)') || all(x(:,end)==y(end,:)') || all(x(:,end)==y(:,1)) || all(x(:,end)==y(:,end))
    z = true;
    return
end

y = fliplr(y);

if all(x(1,:)==y(1,:)) || all(x(1,:)==y(end,:)) || all(x(1,:)==y(:,1)') || all(x(1,:)==y(:,end)') || ...
        all(x(end,:)==y(1,:)) || all(x(end,:)==y(end,:)) || all(x(end,:)==y(:,1)') || all(x(end,:)==y(:,end)') || ...
        all(x(:,1)==y(1,:)') || all(x(:,1)==y(end,:)') || all(x(:,1)==y(:,1)) || all(x(:,1)==y(:,end)) || ...
        all(x(:,end)==y(1,:)') || all(x(:,end)==y(end,:)') || all(x(:,end)==y(:,1)) || all(x(:,end)==y(:,end))
    z = true;
    return
end

y = flipud(y);

if all(x(1,:)==y(1,:)) || all(x(1,:)==y(end,:)) || all(x(1,:)==y(:,1)') || all(x(1,:)==y(:,end)') || ...
        all(x(end,:)==y(1,:)) || all(x(end,:)==y(end,:)) || all(x(end,:)==y(:,1)') || all(x(end,:)==y(:,end)') || ...
        all(x(:,1)==y(1,:)') || all(x(:,1)==y(end,:)') || all(x(:,1)==y(:,1)) || all(x(:,1)==y(:,end)) || ...
        all(x(:,end)==y(1,:)') || all(x(:,end)==y(end,:)') || all(x(:,end)==y(:,1)) || all(x(:,end)==y(:,end))
    z = true;
    return
end
end

function yNew = alignPieces(x,y)
% aligns y to x
yNew = y;

for k=0:3
    y = rot90(yNew,k);
    if all(y(end,:)==x(1,:)) || all(y(:,1)==x(:,end)) || all(y(1,:)==x(end,:)) || all(y(:,end)==x(:,1))
        yNew = y;
        return
    end
end

yNew = fliplr(yNew);
for k=0:3
    y = rot90(yNew,k);
    if all(y(end,:)==x(1,:)) || all(y(:,1)==x(:,end)) || all(y(1,:)==x(end,:)) || all(y(:,end)==x(:,1))
        yNew = y;
        return
    end
end
end

function z = getRelativePosition(x,y)
z = 0;
if all(y(end,:)==x(1,:))
    z = 1;
    return
end
if all(y(1,:)==x(end,:))
    z = 3;
    return
end
if all(y(:,end)==x(:,1))
    z = 4;
    return
end
if all(y(:,1)==x(:,end))
    z = 2;
    return
end
end

function idx = ID2idx(T,ID)
idx=-1;
for i=1:size(T,1)
    if T(i).ID==ID
        idx = i;
        return
    end
end
end

function N = findMonsters(P,M)
% returns number of monster found
N=0;
for r=1:(size(P,1)-size(M,1)+1)
    for c = 1:(size(P,2)-size(M,2)+1)
        if all(all( (M & P(r:r+size(M,1)-1,c:c+size(M,2)-1)) == M))
            N=N+1;
        end
    end
end
end