main

% this is my submission for the MATLAB puzzle:
% http://blogs.mathworks.com/videos/2009/07/28/puzzler-rules-of-the-new-game/
% 
% I have chosen for a flexible setup, the basic principle is this:
% 
% 1. generate all possible boards for a number ('lookAheadMoves') of moves
%    ahead.
% 2. use some criteria ('rankBoardMethod') to rank all possible outcomes
% 3. adjust the board with a number ('maxNewMoves') of the moves that lead
%    to the highest ranked outcome
% 4. continue 1 to 3 until board is solved or maximum moves is reached
% 
% you can play around with the number of alternative boards created, and 
% with the ranking method. If the number of alternative boards is very 
% high, the algorithm is guaranteed to find the optimal solution. With a 
% large number of colours (options) and a large board this becomes 
% computationally infeasible.
% 
% lookAheadMoves: keep this low, I suggest 1 to 5.
%   More look ahead' moves gives more optimized result, but exponentially 
%   increases computation time. Only high values (3..5) when numColors is 
%   low. On simple boards, eanough 'look ahead moves' will just give the
%   optimal solution, calculated by brute force
% 
% maxNewMoves: equal to or smaller than lookAheadMoves
%   maxNewMoves must be equal to or smaller than lookAheadMoves.
%   The higher the value, the shorter the computation
%   time (but probably results are worse too).
% 
% rankBoardMethod: choose from: 'greedy', 'convhull' and 'dilate'
%  'greedy'   just counts the number of pixels which belong to the
%             topleft area.
%  'convhull' alse takes the convex hull area into account
%  'dilate'   uses imdilate to favour solutions that rapidly increase the
%             area which can be potentially reached in a few steps ahead.
%             Is pretty hungry for cpu. Works best in large puzzles,
%             combined with a low value for 'lookAheadMoves'
% 
% Example solutions for board settings: 
%   maxMoves        =  150;
%   numColors       =  8;
%   numPixelsOnSide =  30;
%   setReproducableRandomState(12);
% 
% lookAheadMoves  =  1; 		          lookAheadMoves  =  4; 
% maxNewMoves     =  1; 		          maxNewMoves     =  3; 
% rankBoardMethod =  'dilate'; 		      rankBoardMethod =  'greedy'; 
% solved in 59 moves and 4.0253 seconds	  solved in 62 moves and 28.3534 seconds
% 
% lookAheadMoves  =  1; 		          lookAheadMoves  =  3; 
% maxNewMoves     =  1; 		          maxNewMoves     =  3; 
% rankBoardMethod =  'greedy'; 		      rankBoardMethod =  'convhull'; 
% solved in 73 moves and 0.47579 seconds  solved in 60 moves and 22.2409 seconds
% 
% lookAheadMoves  =  3; 
% maxNewMoves     =  2; 
% rankBoardMethod =  'dilate'; 
% solved in 54 moves and 76.2076 seconds

function main
clf

%% board difficulty
maxMoves        =  150;
numColors       =  8;
numPixelsOnSide =  30;
setReproducableRandomState(12);

%% solver 'intelligence'
lookAheadMoves  =  1; 
maxNewMoves     =  1; 
rankBoardMethod =  'dilate'; 

%% the code

board = defineBoard(numPixelsOnSide, numColors);

displayBoard(board, numColors)
tic
colorList = computerChoose(board, maxMoves, lookAheadMoves, maxNewMoves,rankBoardMethod);
solveTime = toc;
disp(['solved in ' num2str(numel(colorList)) ' moves and ' num2str(solveTime) ' seconds'])
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(0.1)

    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 colorList = computerChoose(board, maxMoves, lookAheadMoves, maxNewMoves,rankBoardMethod)
%Returns a sequence of moves that will solve the board from the current
%state

% make a waitbar
WB = waitbar(0,'solving board...');
% preallocate
colorList = NaN(1,maxMoves);
moves = 0;
%loop until solution
while 1
    % generate tryInput (array of possibilities to try).
    tryInput = getTryInput(board(1),unique(board),lookAheadMoves);
    if moves == 0;
        tryInput = tryInput(ismember(tryInput(:,1), [board(2,1) board(1,2)]),:); 
    end
    [alternativeBoards,tryInput] = getAlternativeBoards2(board,tryInput);
    if any(isnan(tryInput(:)))
        % there is a solution
        [ignore,bestBoard] = max(sum(isnan(tryInput),2));
        tryInput(sum(isnan(tryInput),2)==ignore,1:end-ignore);
        newMoves = sum(~isnan(tryInput(bestBoard,:)));
    else
        % determine which board is best
        switch rankBoardMethod
            case 'greedy'
                bestBoard = rankBoards1(alternativeBoards);
            case 'convhull'
                bestBoard = rankBoards2(alternativeBoards);
            case 'dilate'
                bestBoard = rankBoards3(alternativeBoards);
            otherwise
                error('unknown rankBoardMethod')
        end
        newMoves = maxNewMoves;
    end

    % update colorlist
    colorList(moves+1:moves+newMoves) = tryInput(bestBoard,1:newMoves);

    % update # moves
    moves = moves + newMoves;

    % check if maxMoves has been reached
    if moves>maxMoves
        colorList = -1;
        break
    end

    % update the board m steps
    for ii = 1:newMoves
        isTopLeft = bwlabel(board==board(1),4);
        isTopLeft = isTopLeft==1;
        newTopLeft = bwlabel(isTopLeft|board==tryInput(bestBoard,ii),4);
        newTopLeft = newTopLeft==1;
        board(newTopLeft) = tryInput(bestBoard,ii);
    end

    % update waitbar

    WB = waitbar(sum(newTopLeft(:))/numel(board),WB);
    % check if the board is ok.
    if length(unique(board))==1
        colorList(isnan(colorList))=[];
        close(WB)
        break
    end
end

function tryInput = getTryInput(topLeftVal,colors,n)
tryInput = colors(fullfact(repmat(length(colors),1,n)));
%reverse the matrix rows
tryInput = tryInput(:,n:-1:1);
%delete all where the first row is topLeftValue
tryInput(tryInput(:,1)==topLeftVal,:) = [];
% delete all entries where the same value is repeated
tryInput(any(diff(tryInput,1,2) == 0,2),:) = [];
% add a row of zeros (this is for checking if a solution is found)
tryInput(:,end+1) = 0;

function [alternativeBoards,tryInput] = getAlternativeBoards(board,tryInput)
% pre allocate
alternativeBoards = NaN([size(board),size(tryInput,1)]);

for ii = 1:size(tryInput,1)
    tempBoard = board;
    for jj = 1:size(tryInput,2)-1
        % determine what to update
        isTopLeft = bwlabel(tempBoard==tempBoard(1),4);
        isTopLeft = isTopLeft==1;
        newTopLeft = bwlabel(isTopLeft|tempBoard==tryInput(ii,jj),4);
        newTopLeft = newTopLeft==1;

        % update board
        tempBoard(newTopLeft)=tryInput(ii,jj);

        % check if solution is found
        if sum(newTopLeft(:)) == numel(board)
            tryInput(ii,jj+1:end) = NaN;
            break
        end

    end
    alternativeBoards(:,:,ii) = tempBoard;
end

function [alternativeBoards,tryInput] = getAlternativeBoards2(board,tryInput)
% pre allocate
alternativeBoards = NaN([size(board),size(tryInput,1)]);
for jj = 1:size(tryInput,2)-1
    for ii = 1:size(tryInput,1)
        if ii ~= 1
            if tryInput(ii,jj) == tryInput(ii-1,jj)
                alternativeBoards(:,:,ii) =  alternativeBoards(:,:,ii-1);
                continue
            end
        end
        if jj == 1
            tempBoard = board;
        else
            tempBoard = alternativeBoards(:,:,ii);
        end
        % determine what to update
        isTopLeft = bwlabel(tempBoard==tempBoard(1),4);
        isTopLeft = isTopLeft==1;
        newTopLeft = bwlabel(isTopLeft|tempBoard==tryInput(ii,jj),4);
        newTopLeft = newTopLeft==1;

        % update board
        tempBoard(newTopLeft)=tryInput(ii,jj);

        alternativeBoards(:,:,ii) = tempBoard;

        % check if solution is found
        if sum(newTopLeft(:)) == numel(board)
            tryInput(ii,jj+1:end) = NaN;
        end
    end
end


% simple solver, count elements
function  bestBoard = rankBoards1(alternativeBoards)
score = nan(size(alternativeBoards,3),1);
for ii = 1:size(alternativeBoards,3)
    board = alternativeBoards(:,:,ii); %#ok<COLND>
    isTopLeft = bwlabel(board==board(1),4);
    score(ii) = sum(sum(isTopLeft==1));
end
[ignore,bestBoard] = max(score);

% combinend qhull area and # elements method
function bestBoard = rankBoards2(alternativeBoards)
[x,y] = meshgrid(1:size(alternativeBoards(:,1,1),1),1:size(alternativeBoards(:,1,1),1));
score = nan(size(alternativeBoards,3),1);
for ii = 1:size(alternativeBoards,3)
    board = alternativeBoards(:,:,ii);
    isTopLeft = bwlabel(board==board(1),4);
    isTopLeft = isTopLeft==1;
    try
        [ignore,volume] = convhull(x(isTopLeft),y(isTopLeft));
    catch
        volume = 0;
    end
    isConnectedToTopLeft = imdilate(+isTopLeft,strel('diamond', 1),'same');
    score(ii) = sum(isConnectedToTopLeft(:))+4*volume;
end
[ignore,bestBoard] = max(score);


function bestBoard = rankBoards3(alternativeBoards)
score = nan(size(alternativeBoards,3),1);
for ii = 1:size(alternativeBoards,3)
    board = alternativeBoards(:,:,ii);
    isTopLeft = bwlabel(board==board(1),4);
    isTopLeft = isTopLeft==1;
    potential1     = imdilate(+isTopLeft,strel('diamond', 1),'same');
    potential2     = imdilate(+isTopLeft,strel('diamond', 3),'same');
    potential3     = imdilate(+isTopLeft,strel('diamond', 6),'same');
    % potential4     = imdilate(+isTopLeft,strel('diamond',10),'same');
    score(ii) = sum(sum(isTopLeft+2*potential1+4*potential2+8*potential3));%+16*potential4));
end
[ignore,bestBoard] = max(score);