fid = fopen('input.txt');
s={};
while 1
    str = fgetl(fid);
    if str==-1; break;end
    s(end+1,:) = {str};
end

% extract cart positions
c = []; % row from top, column from left,heading (N,E,S,W = 1,2,3,4),turnIdx (1,2,3),hasCrashed]
for i=1:size(s,1)

    p1 = strfind(s{i},'^');
    p2 = strfind(s{i},'v');
    p3 = strfind(s{i},'<');
    p4 = strfind(s{i},'>');

    for j=1:length(p1)
        c = [c;[i,p1(j)],1,1,0];
        s{i}(p1(j)) = '|';
    end

    for j=1:length(p2)
        c = [c;[i,p2(j)],3,1,0];
        s{i}(p2(j)) = '|';
    end

    for j=1:length(p3)
        c = [c;[i,p3(j)],4,1,0];
        s{i}(p3(j)) = '-';
    end

    for j=1:length(p4)
        c = [c;[i,p4(j)],2,1,0];
        s{i}(p4(j)) = '-';
    end
end

% parse grid
% no path   = 0
% -         = 1
% |         = 2
% /         = 3
% \         = 4
% +         = 5

g = zeros(size(s,1),length(s{1}));
for i=1:size(s,1)

    for j = 1:length(s{i})

        if strcmp(s{i}(j),'-')
            g(i,j) = 1;
        end
        if strcmp(s{i}(j),'|')
            g(i,j) = 2;
        end
        if strcmp(s{i}(j),'/')
            g(i,j) = 3;
        end
        if strcmp(s{i}(j),'\')
            g(i,j) = 4;
        end
        if strcmp(s{i}(j),'+')
            g(i,j) = 5;
        end

    end

end


%main loop over ticks
t = 0;
crash  = false;
while ~crash
    t=t+1;

    % loop over cart in correct order
    c = sortrows(c);
    for i = 1:size(c,1)

        x = c(i,1);
        y = c(i,2);
        h = c(i,3);
        t = c(i,4);

        % -         = 1
        % |         = 2
        % /         = 3
        % \         = 4
        % +         = 5

        switch g(x,y)
            case 1
                if h==2
                    c(i,2) = y+1;
                else
                    c(i,2) = y-1;
                end
            case 2
                if h==1
                    c(i,1) = x-1;
                else
                    c(i,1) = x+1;
                end
            case 3 % /
                if h==1
                    c(i,3) = 2;
                    c(i,2) = c(i,2) + 1;
                end
                if h==2
                    c(i,3) = 1;
                    c(i,1) = c(i,1) - 1;
                end
                if h==3
                    c(i,3) = 4;
                    c(i,2) = c(i,2) - 1;
                end
                if h==4
                    c(i,3) = 3;
                    c(i,1) = c(i,1) + 1;
                end

            case 4 %\
                if h==1
                    c(i,3) = 4;
                    c(i,2) = c(i,2) - 1;
                end
                if h==2
                    c(i,3) = 3;
                    c(i,1) = c(i,1) + 1;
                end
                if h==3
                    c(i,3) = 2;
                    c(i,2) = c(i,2) + 1;
                end
                if h==4
                    c(i,3) = 1;
                    c(i,1) = c(i,1) - 1;
                end
            case 5 %+
                if t==1
                    %turn left
                    c(i,3) = h-1;
                    if c(i,3)==0
                        c(i,3) = 4;
                    end

                    %update turn index
                    c(i,4) = 2;

                elseif t==2
                    %update turn index
                    c(i,4) = 3;

                elseif t==3
                    %turn right
                    c(i,3) = h+1;
                    if c(i,3)==5
                        c(i,3) = 1;
                    end

                    %update turn index
                    c(i,4) = 1;
                end

                %take step in new direction
                if c(i,3) == 1
                    c(i,1) = c(i,1)-1;
                elseif c(i,3) == 2
                    c(i,2) = c(i,2)+1;
                elseif c(i,3) == 3
                    c(i,1) = c(i,1)+1;
                elseif c(i,3) == 4
                    c(i,2) = c(i,2)-1;
                end



            otherwise
                disp('we shouldnt be here')



        end
        % check collision

        for m = 1:size(c,1)
            for n = 1:size(c,1)
                if m~=n
                    if c(m,1)==c(n,1) && c(m,2)==c(n,2) && c(m,5)==0 && c(n,5)==0
                        %disp('collision')
                        c(m,5)=1;
                        c(n,5)=1;
                        %disp([c(m,2)-1,c(m,1)-1])

                        %crash = true;
                        if sum(c(:,5))==16
                            h = find(c(:,5)==0);
                            disp([c(h,2)-1,c(h,1)-1])
                            pause
                        end

                    end
                end
            end
        end

    end

end