fid     = fopen('input.txt');
part1   = false; % set to false for part 2
s       = {};
while 1
    str = fgetl(fid);
    if str==-1; break;end
    s(end+1,:) = {str};
end
fclose(fid);

% 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];
    end

    for j=1:length(p2)
        c = [c;[i,p2(j)],3,1,0];
    end

    for j=1:length(p3)
        c = [c;[i,p3(j)],4,1,0];
    end

    for j=1:length(p4)
        c = [c;[i,p4(j)],2,1,0];
    end
end

% parse grid:  / = 3, \ = 4, + = 5
g = zeros(size(s,1),length(s{1}));
for i=1:size(s,1)
    for j = 1:length(s{i})
        switch s{i}(j)
            case '/'
                g(i,j) = 3;
            case '\'
                g(i,j) = 4;
            case '+'
                g(i,j) = 5;
        end
    end
end

%main loop over ticks
crash = false;
while ~crash

    % loop over carts 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);

        % / = 3, \ = 4, + = 5
        % First change heading:
        switch g(x,y)
            case 3 % /
                switch h
                    case 1
                        c(i,3) = 2;
                    case 2
                        c(i,3) = 1;
                    case 3
                        c(i,3) = 4;
                    case 4
                        c(i,3) = 3;
                end
            case 4 %\
                switch h
                    case 1
                        c(i,3) = 4;
                    case 2
                        c(i,3) = 3;
                    case 3
                        c(i,3) = 2;
                    case 4
                        c(i,3) = 1;
                end
            case 5 %+
                switch t
                    case 1
                        c(i,3) = h-1;
                        if c(i,3)==0
                            c(i,3) = 4;
                        end
                        c(i,4) = 2;
                    case 2
                        c(i,4) = 3;
                    case 3
                        c(i,3) = h+1;
                        if c(i,3)==5
                            c(i,3) = 1;
                        end
                        c(i,4) = 1;
                end
        end

        % Then take a step:
        switch c(i,3)
            case 1
                c(i,1) = c(i,1)-1;
            case 2
                c(i,2) = c(i,2)+1;
            case 3
                c(i,1) = c(i,1)+1;
            case 4
                c(i,2) = c(i,2)-1;
        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
                        c(m,5) = 1;
                        c(n,5) = 1;
                        if part1
                            disp([c(m,2)-1,c(m,1)-1]) % Part1
                            crash = true;
                        else % Part2
                            if sum(c(:,5))==16
                                disp([c(c(:,5)==0,2)-1,c(c(:,5)==0,1)-1]) % Part2
                                crash = true;
                            end
                        end
                    end
                end
            end
        end
    end
end