main

function main
clc
clf

currentMove     =  0;
maxMoves        =  10 %22 % 30 % 36
numColors       =  6;
numPixelsOnSide =  5 %12 % 17 % 22

setReproducableRandomState()

board = defineBoard(numPixelsOnSide, numColors);

displayBoard(board, numColors)

colorList = computerChoose(board, currentMove, [], maxMoves, numColors)

displayAnimation(board, numColors, colorList)

function reproSeed = setReproducableRandomState(reproSeed)
% Leave semicolon off of call with no input to see the time based seed.  
% Use seed as input to function to use prior seed.

if nargin == 0
    %set seed so if an error occurs, I can reproduce and debug
    c = clock;
    reproSeed = c(6);
end

rand('seed', reproSeed);

function board = defineBoard(numPixelsOnSide, numColors)
board = ceil(rand(numPixelsOnSide)*numColors);

function displayBoard(board, numColors, next)

if nargin == 2
    next = [];
end
    clf
    subplot(1,3,[1:2])
    image(board)
    colormap(jet(numColors))
    axis off
    colorbar
    axis equal
    
    if ~isempty(next)
        subplot(1,3,3)
        image(next)
        axis off
        title ('Next Color')
    end

function displayAnimation(board, numColors, colorList)

displayBoard(board, numColors, colorList(1))

for i = 1 : numel(colorList)  
    pause
    
    board = flood(colorList(i), board);
    if i < numel(colorList)
        
        nextColor = colorList(i + 1);
    else
        cla
        nextColor = [];
    end
    
    displayBoard(board, numColors, nextColor)
end

function board = flood(color, board)

if isempty(color) %startup condition
    return
end

connectedComponents = findConnected(board);

board(connectedComponents) = color;

function vi = findConnected(board)
%vi  is the list of indices that are 4 connected to first element of the
%matrix by the same color.

% Code created here:
%http://blogs.mathworks.com/videos/2009/06/17/puzzler-find-four-connected-c
%omponent-to-element-1-of-2-d-matrix/#comments
sizeBoardEdge = size(board,1);

oldColor = board(1,1);
    boardPath = round(zeros(sizeBoardEdge));
    updated=1;
    while updated==1
        updated=0;
        for row=1:sizeBoardEdge
            for col=1:sizeBoardEdge
                    if row==1 && col==1 && boardPath(row,col)==0  ...
                        || board(row,col)== oldColor && row>1             && boardPath(row-1,col  )~=0 && boardPath(row,col)==0 ...
                        || board(row,col)== oldColor && col>1             && boardPath(row  ,col-1)~=0 && boardPath(row,col)==0 ...
                        || board(row,col)== oldColor && col<sizeBoardEdge && boardPath(row  ,col+1)~=0 && boardPath(row,col)==0 ...
                        || board(row,col)== oldColor && row<sizeBoardEdge && boardPath(row+1,col  )~=0 && boardPath(row,col)==0;
                    
                        boardPath(row,col) = 1;
                        updated=1;
                        
                    end
            end
        end
    end

    vi = find(boardPath==1);
    
function lastColor = computerChoose(board, currentMove, choice, maxMoves, numColors)
%Returns a sequence of moves that will solve the board from the current
%state
if currentMove > maxMoves
    %fail
    %disp('.')
    lastColor = -1;
    return
end    

currentMove = currentMove + 1;

board = flood(choice, board);


if isBoardSolved(board)
    %win
    lastColor = choice;
    return
end

choiceList = getRankedList(board, choice);

for i = 1:numel(choiceList)
    lastColor = computerChoose(board, currentMove, choiceList(i), maxMoves, numColors);
    if lastColor(end) ~= -1
        i %displays what number in the ordered list this was...
        if lastColor(1) ~= choiceList(i) %do not repeat, happens on first recursion
            lastColor = [choiceList(i) lastColor];
        end
        return
    end
end

function choiceList = getRankedList(board, priorChoice)

colorsUsed = unique(board);

for i = 1:numel(colorsUsed)
    floodSize(i) = getNewSize(colorsUsed(i), board);
end

[foo, colorListIndex] = sort(floodSize, 'descend');

choiceList = colorsUsed(colorListIndex);

if ~isempty(priorChoice)
    choiceList(choiceList == priorChoice) = [];    
end
    
function flagDone = isBoardSolved(board)

if all(board(:) == board(1))
    flagDone = 1;
else
    flagDone = 0;
end
 
function floodSize = getNewSize(color, board)

board = flood(color, board);
connectedComponents = findConnected(board);

floodSize = nnz(connectedComponents);