% Matlab script for creating sequence A316667 on The On-Line Encyclopedia of Integer Sequences
% By Daniel Karssen 2018

close all
clear all
clc

%% Settings
createFiles = true;
maxSteps = 1e5;

OEISnum = 'a316667';
move = 'knight';
board = 'spiral';
condition = 'none';

%% Set parameter based on move and board
% moves
switch move
    case 'knight'
        dx = [ 2  2 -2 -2  1  1 -1 -1];
        dy = [ 1 -1  1 -1  2 -2  2 -2];
    case {'king','queen'}
        dx = [ 1  1  1 -1 -1 -1  0  0];
        dy = [ 0  1 -1  0  1 -1  1 -1];
    case {'bishop','diastep'}
        dx = [ 1  1 -1 -1];
        dy = [ 1 -1  1 -1];
    case {'rook','sidestep'}
        dx = [ 1  0 -1  0];
        dy = [ 0  1  0 -1];
    otherwise
        error('Undefined move')
end
if any(strcmp(move,{'queen','bishop','rook'}))
    dx = (1:maxSteps*2)'*dx; dx = dx(:);
    dy = (1:maxSteps*2)'*dy; dy = dy(:);        
end

% board
switch board
    case 'diagonally'
        % board numbering
        xy2num = @(x,y) (x+y-2).*(x+y-1)/2 + y;
        xyvalid = @(x,y) x>0 & y>0;

        % start point
        x0 = 1;
        y0 = 1;
    case 'spiral'
        % board numbering
        xy2num = @(x,y) SpiralNumbering(x,y);
        xyvalid = @(x,y) true(size(x));
        
        % start point
        x0 = 0;
        y0 = 0;
    otherwise
        error('Undefined board')
end
switch condition
    case 'none'
        cond = @(x,y,num) true(size(num));
    case 'prime'
        cond = @(x,y,num) isprime(num);
    otherwise
        error('Undefined condition')
end
%% Creating the sequence
seqNum = [];
seqX = [];
seqY = [];
finite = false;
for s=1:maxSteps
    % add current square to sequence
    seqX(end+1) = x0;
    seqY(end+1) = y0;
    seqNum(end+1) = xy2num(x0,y0);
    
    % apply all possible moves
    x = x0 + dx;
    y = y0 + dy;
    
    % remove any not valid squares
    valid = xyvalid(x,y);
    x(~valid) = [];
    y(~valid) = [];
    
    % determine number of possible squares to move to
    num = xy2num(x,y);
    
    % select all unvisited squares to are on the board that meet the condition
    sel = ~ismember(num,seqNum) & cond(x,y,num);
    
    % break if no potential squares are available  
    if (~any(sel))
        finite = true;
        disp('STOPPED')
        break
    end
    
    % select available square with lowest number as next square
    num(~sel) = inf;
    [~, index] = min(num);
    x0 = x(index);
    y0 = y(index);
end

%% Figure 1 - start of sequence
xy_max = 5;
sPlot = find(~(abs(seqX)<=xy_max & abs(seqY)<=xy_max),1)-1;
hFig1 = figure;
hold on
plot3(seqX(1),seqY(1),1,'ro')
plot3(seqX(sPlot),seqY(sPlot),sPlot,'rx')
patch([seqX(1:sPlot) nan],[seqY(1:sPlot) nan],[1:sPlot nan],[1:sPlot nan],'EdgeColor','interp','FaceColor','none')
set(gca,'Ydir', 'reverse', 'XAxisLocation', 'Top')
legend('n=1',sprintf('n=%i',sPlot),'Location','southeast')
axis equal
switch board
    case 'diagonally'
        xlim([0 xy_max+1]);
        ylim([0 xy_max+1]);
    case 'spiral'
        xlim([-xy_max-1 xy_max+1]);
        ylim([-xy_max-1 xy_max+1]);
end
        

for x=-xy_max:xy_max
    for y=-xy_max:xy_max
        if xyvalid(x,y)
            text(x,y,num2str(xy2num(x,y)),'HorizontalAlignment','center')
        end
    end
end 

if createFiles
    saveas(hFig1,[OEISnum '.svg']);
end

%% Figure 2 - whole sequence
if finite
    hFig2 = figure;
    hold on
    plot3(seqX(1),seqY(1),1,'ro')
    plot3(seqX(end),seqY(end),numel(seqY),'rx')
    patch([seqX nan],[seqY nan],[1:numel(seqY) nan],[1:numel(seqY) nan],'EdgeColor','interp','FaceColor','none')
    set(gca,'Ydir', 'reverse', 'XAxisLocation', 'Top')
    legend('n=1',sprintf('n=%i',numel(seqY)),'Location','southeast')
    axis equal
    xlim([min(seqX)-1 max(seqX)+1])
    ylim([min(seqY)-1 max(seqY)+1])
    
    if createFiles
        saveas(hFig2,[OEISnum '_fig2.svg']);
    end
end

%% Print sequence info
seqString = sprintf('%i, ',seqNum);
maxChr = 260;
i = find(seqString==',' & 1:numel(seqString)<=maxChr,1,'last');
seqString = seqString(1:i-1);
fprintf(['###### ' OEISnum ' ######\n']);
fprintf(['Move: ' move '\n']);
fprintf(['Board: ' board '\n']);
fprintf(['Condition: ' condition '\n']);
fprintf(['Data: ' seqString '\n']);
if finite
   fprintf('Sequence finite, at step %i, square %i is visited, after which there are no unvisited squares within one move.\n',numel(seqNum),seqNum(end));
end
fprintf(['#####################\n'])


%% Create b-file
if createFiles
    fid = fopen(['b' OEISnum(2:end) '.txt'],'w');
    fprintf(fid,'%i %i\r\n',[1:numel(seqNum); seqNum]);
    fclose(fid);
end