clc
clear
close all

tic
disp('starting...')

% Manually extracted from input
myTicket = [83,53,73,139,127,131,97,113,61,101,107,67,79,137,89,109,103,59,149,71];

% Note: Manually split input file into 'rules' and 'other tickets'
x = importdata('rules.txt');
L = size(x,1);
R=[];
for i=1:L
    str = x{i};
    z   = strsplit(str,{': ',' or '});
    N1  = strsplit(z{2},'-');
    N2  = strsplit(z{3},'-');
    R   = [R;[str2double(N1{1}),str2double(N1{2})]];
    R   = [R;[str2double(N2{1}),str2double(N2{2})]];
end

invalidSum          = 0;
y                   = importdata('input.txt'); % only other tickets
invalidTicketRow    = zeros(size(y,1),1);
for r=1:size(y,1)
    for c=1:size(y,2)
        valid = 0;
        for j=1:size(R,1)
            if y(r,c)>=R(j,1) && y(r,c)<=R(j,2)
                valid = 1;
            end
        end
        if valid==0
            invalidSum = invalidSum + y(r,c);
            invalidTicketRow(r) = 1;
        end
    end
end
disp(invalidSum) % Part A

%Remove invalid tickets
y = y(~invalidTicketRow,:);

% Build matrix M with rules in rows and ticketfield in columns. A true
% entry in M means the ticket field follows a rule.
for rule = 1:20
    for ticketField = 1:20
       if all((y(:,ticketField) >= R((2*rule)-1,1) & y(:,ticketField) <= R((2*rule)-1,2)) | (y(:,ticketField) >= R(2*rule,1) & y(:,ticketField) <= R(2*rule,2)))
           M(rule,ticketField)=true;
       end
    end
end
disp(M)

order=zeros(1,20);
for i=1:20
    r = find(sum(M,2)==1);
    c = find(M(r,:));
    order(r)=c;
    M(:,c)=false;
end

format long
disp(myTicket(order(1))*myTicket(order(2))*myTicket(order(3))*myTicket(order(4))*myTicket(order(5))*myTicket(order(6)))

toc
disp('Finished')