Winner Yi Cao (Buy a ticket)

Finish 2007-05-16 12:00:00 UTC

jacob's lair 9

by MJP

Status: Passed
Results: 40459.57 (cyc: 16)
CPU Time: 114.446
Score: 4663.16
Submitted at: 2007-05-14 16:24:37 UTC
Scored at: 2007-05-14 16:26:49 UTC

Current Rank: 2557th

Comments
Please login or create a profile.
Code
function moves=solver(board)

moves1=solverrecgood(board);
score1=grade(board,moves1);
moves2=solverrecgoodmetric(board);
score2=grade(board,moves2);
moves3=solvertwibak(board);
% moves3=winnertwi(board);
score3=grade(board,moves3);
if (score1 < score2) && (score1 < score3)
    moves=moves1;
elseif (score2 < score1) && (score2 < score3)
    moves=moves2;
else
    moves=moves3;
end


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function moves = solvertwibak(board)
% % MOVES = SOLVER(BOARD) Solitaire solver.
% %
% % MOVES -> [row_from,column_from,row_to,column_to]
% %
% % The MATLAB Contest Team
% % April, 2007

% moves2=solverHannes(board);
% if (size(moves1)~=size(moves2)) || (moves1~=moves2)
%     display('different');
% end
rand('state',0);
movesBest=solverMe(board,0);
scoreBest=grade(board,movesBest);
for i=1:3
    moves=solverMe(board,0.05);
    score=grade(board,moves);
    if (score<scoreBest)
        scoreBest=score;
        movesBest=moves;
    end
end
moves=movesBest;

function moves=solverMe(board,perc)
[m,n]=size(board);
mp=m+4;
np=n+4;
padBoard=-1*ones(mp,np);
padBoard(3:end-2,3:end-2)=board;
padBoardNoZeros=padBoard;
padBoardNoZeros(find(padBoard<=0))=1;
padBin=padBoard./padBoardNoZeros;
dest=find(padBoard==0);
maybe=[];
moves=[];
moveCnt=0;

for i=1:size(dest,1)
    this=dest(i);
    % Format of valid
    % valid(2)/not(anything else)   src  jump_over  dest  score  direction_from(1 fron top, 2 from right etc)
    maybe=[maybe; padBin(this-1)+padBin(this-2) this-2 this-1 this padBoard(this-1)-padBoard(this-2) 1];
    maybe=[maybe; padBin(this+1)+padBin(this+2) this+2 this+1 this padBoard(this+1)-padBoard(this+2) 3];
    maybe=[maybe; padBin(this-mp)+padBin(this-2*mp) this-2*mp this-mp this padBoard(this-mp)-padBoard(this-2*mp) 4];
    maybe=[maybe; padBin(this+mp)+padBin(this+2*mp) this+2*mp this+mp this padBoard(this+mp)-padBoard(this+2*mp) 2];
end

valid=maybe(find(maybe(:,1)==2),:);
moves=[0 0 0 0];

prevPeg=0;
doAgain=1;
totalScore=0;
restoreScore=0;
restorePoint=1;
while doAgain

    % Make best move
    [scores,indices]=sort(valid(:,5),'descend');
    if ~isempty(scores)
        if (rand(1)<perc && size(scores,1) > 1)
            scores(1)=scores(2);
            indices(1)=indices(2);
        end
        if (scores(1)<0) && (totalScore>restoreScore)
            restoreScore=totalScore;
            restorePoint=size(moves,1);
        end
        if (scores(1) > 8000)
            scores(1)=scores(1)-10000;
        end
        totalScore=totalScore+scores(1);
        thisInd=indices(1);
        from = valid(thisInd,2);
        over = valid(thisInd,3);
        to = valid(thisInd,4);
        rpadsrc=mod(from,mp)-2;
        cpadsrc=(from-rpadsrc-2)/mp-1;
        rpaddest=mod(to,mp)-2;
        cpaddest=(to-rpaddest-2)/mp-1;
        moves = [moves; rpadsrc cpadsrc rpaddest cpaddest];
        padBin(from)=0;
        padBin(over)=0;
        padBin(to)=1;
        padBoard(to)=padBoard(from);
        padBoard(from)=0;
        padBoard(over)=0;
        % Remove entries in valid move table that are no longer possible
        for x = 1 : size(valid,1)
            if (valid(x,3)==from)||(valid(x,3)==over)||(valid(x,2)==over)||(valid(x,2)==from)||(valid(x,4)==to)
                valid(x,1)=0;
            end
        end

        % Add all valid moves into spot where move is made from
        valid=[valid; padBin(from-1)+padBin(from-2) from-2 from-1 from padBoard(from-1)-padBoard(from-2) 1];
        valid=[valid; padBin(from+1)+padBin(from+2) from+2 from+1 from padBoard(from+1)-padBoard(from+2) 3];
        valid=[valid; padBin(from-mp)+padBin(from-2*mp) from-2*mp from-mp from padBoard(from-mp)-padBoard(from-2*mp) 4];
        valid=[valid; padBin(from+mp)+padBin(from+2*mp) from+2*mp from+mp from padBoard(from+mp)-padBoard(from+2*mp) 2];
        % Add all valid moves into spot that is jumped over
        valid=[valid; padBin(over-1)+padBin(over-2) over-2 over-1 over padBoard(over-1)-padBoard(over-2) 1];
        valid=[valid; padBin(over+1)+padBin(over+2) over+2 over+1 over padBoard(over+1)-padBoard(over+2) 3];
        valid=[valid; padBin(over-mp)+padBin(over-2*mp) over-2*mp over-mp over padBoard(over-mp)-padBoard(over-2*mp) 4];
        valid=[valid; padBin(over+mp)+padBin(over+2*mp) over+2*mp over+mp over padBoard(over+mp)-padBoard(over+2*mp) 2];
        % Add all valid moves out of destination
        valid=[valid; 2*padBin(to-1)+3*padBin(to-2) to to-1 to-2 10000+padBoard(to-1) 1];
        valid=[valid; 2*padBin(to+1)+3*padBin(to+2) to to+1 to+2 10000+padBoard(to+1) 3];
        valid=[valid; 2*padBin(to-mp)+3*padBin(to-2*mp) to to-mp to-2*mp 10000+padBoard(to-mp) 4];
        valid=[valid; 2*padBin(to+mp)+3*padBin(to+2*mp) to to+mp to+2*mp 10000+padBoard(to+mp) 2];
        % Add all moves jumping over destination
        valid=[valid; 6-4*padBin(to-1)+padBin(to+1) to-1 to to+1 padBoard(to)-padBoard(to-1) 1];
        valid=[valid; 6-4*padBin(to+1)+padBin(to-1) to+1 to to-1 padBoard(to)-padBoard(to+1) 3];
        valid=[valid; 6-4*padBin(to-mp)+padBin(to+mp) to-mp to to+mp padBoard(to)-padBoard(to-mp) 4];
        valid=[valid; 6-4*padBin(to+mp)+padBin(to-mp) to+mp to to-mp padBoard(to)-padBoard(to+mp) 2];
        % Remove all invalid entries
        valid=valid(find(valid(:,1)==2),:);
    else
        doAgain=0;
    end
end

if totalScore>restoreScore
    return
else
    moves=moves(1:restorePoint,:);
    return
end

function score = grade(board,moves)

[m,n] = size(board);
tb = @(p) all([p>0 p<=[n m] ~rem(p,1)]);
moves = round(moves(1:min(nnz(board>0),end),:));
score = sum(board(board(:)>0));
lastPeg = [-1 -1];
for i = 1:size(moves,1)
    f = moves(i,[2 1]);
    t = moves(i,[4 3]);
    if tb(f) && board(f(2),f(1))>0 % valid pick
        score = score + any(lastPeg-f).*board(f(2),f(1));
        lastPeg = f;
        mp = (f+t)/2;
        if tb(t) && board(t(2),t(1))==0 && all(sort(abs(f-t))==[0 2]) ...
                && board(mp(2),mp(1))>0 % valid move
            lastPeg = t;
            score = score - board(mp(2),mp(1));
            board(t(2),t(1)) = board(f(2),f(1));
            board([f(2) mp(2)],[f(1) mp(1)]) = 0;
        end
    else
        lastPeg = [0 0];
    end
end



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function moves = solverrecgood(board)

moves=dorec(board);

function moves = dorec(board)
[m,n]=size(board);
mp=m+4;
np=n+4;
padBoard=-1*ones(mp,np);
padBoard(3:end-2,3:end-2)=board;
padBoardNoZeros=padBoard;
padBoardNoZeros(find(padBoard<=0))=1;
padBin=padBoard./padBoardNoZeros;


dest=find(padBoard==0);
maybe=zeros(4*size(dest,1),6);
moveCnt=1;
for i=1:size(dest,1)
    this=dest(i);
    % Format of valid
    % valid(2)/not(anything else)   src  jump_over  dest  score  direction_from(1 fron top, 2 from right etc)
    maybe(moveCnt,:)=[padBin(this-1)+padBin(this-2) this-2 this-1 this padBoard(this-1)-padBoard(this-2) 1];
    maybe(moveCnt+1,:)=[padBin(this+1)+padBin(this+2) this+2 this+1 this padBoard(this+1)-padBoard(this+2) 3];
    maybe(moveCnt+2,:)=[padBin(this-mp)+padBin(this-2*mp) this-2*mp this-mp this padBoard(this-mp)-padBoard(this-2*mp) 4];
    maybe(moveCnt+3,:)=[padBin(this+mp)+padBin(this+2*mp) this+2*mp this+mp this padBoard(this+mp)-padBoard(this+2*mp) 2];
    moveCnt=moveCnt+4;
end

restoreScore=0;
valid=maybe(find(maybe(:,1)==2),:);
moves=[0 0 0 0];
restoreMoves=[0 0 0 0];
score=0;
totJumps=0;
totChains=0;
while ~isempty(valid)
    [chainMoves,scoreRet]=clearChain(padBoard,padBin,valid,mp,np,1);
    totJumps=totJumps+size(chainMoves,1);
    totChains=totChains+1;
    if (scoreRet<0) && (score>=restoreScore)
%     scoreRet=scoreRet-1;
%     if (scoreRet<0) && (score>=restoreScore)
        restoreScore=score;
        restoreMoves=moves;
    end
    [padBoard,padBin,valid,chainMoves]=doMoves(padBoard,padBin,valid,chainMoves);
    moves=[moves; chainMoves];
    score=score+scoreRet;
end

avgChainLength=totJumps/totChains;
if (score>restoreScore)
    moves=moves(find(moves(:,1)>0),:);
else
    moves=restoreMoves(find(restoreMoves(:,1)>0),:);
end

function [chainMoves,scoreRet,depthRet]=clearChain(padBoard,padBin,valid,mp,np,depth)

scoreMax=-10000;
chainMoves=[0 0 0];
nextMoves=zeros(4,4);
for i=1:size(valid,1)
    scoreChain=0;
    newBin=padBin;
    newBoard=padBoard;
    source=valid(i,2);
    over=valid(i,3);
    dest=valid(i,4);
    newBin([source;over])=0;
    newBin(dest)=1;
    scoreThis=newBoard(over)-newBoard(source);
    newBoard([source;over;dest])=0;
%     scoreThis=newBoard(over)/newBoard(source);
%     newBoard(dest)=newBoard(source);
%     newBoard([source;over])=0;
    nextMoves(1,:)=[newBin(dest-1)+3*newBin(dest-2) dest dest-1 dest-2];
    nextMoves(2,:)=[newBin(dest+1)+3*newBin(dest+2) dest dest+1 dest+2];
    nextMoves(3,:)=[newBin(dest-mp)+3*newBin(dest-2*mp) dest dest-mp dest-2*mp];
    nextMoves(4,:)=[newBin(dest+mp)+3*newBin(dest+2*mp) dest dest+mp dest+2*mp];
    nextMoves=nextMoves(find(nextMoves(:,1)==1),:);
    depthRet=depth;
    if ~isempty(nextMoves)
        [chainMoves,scoreChain,depthRet]=clearChain(newBoard,newBin,nextMoves,mp,np,depth+1);
    end
    scoreTotal=scoreThis+scoreChain;
    if scoreTotal>scoreMax
        scoreMax=scoreTotal;
        bestMoves=[source over dest; chainMoves];
        bestDepth=depthRet;
    end
end
if (depth==1)
    chainMoves=bestMoves(1:bestDepth,:);
else
    chainMoves=bestMoves;
end
scoreRet=scoreMax;
depthRet=bestDepth;


function [padBoard,padBin,valid,retMoves]=doMoves(padBoard,padBin,valid,chainMoves)

retMoves=[0 0 0 0];
[mp,np]=size(padBoard);
for i=1:size(chainMoves,1)
    from = chainMoves(i,1);
    over = chainMoves(i,2);
    to = chainMoves(i,3);
    rpadsrc=mod(from,mp)-2;
    cpadsrc=(from-rpadsrc-2)/mp-1;
    rpaddest=mod(to,mp)-2;
    cpaddest=(to-rpaddest-2)/mp-1;
    retMoves = [retMoves; rpadsrc cpadsrc rpaddest cpaddest];
    padBin(from)=0;
    padBin(over)=0;
    padBin(to)=1;
    padBoard(to)=padBoard(from);
    padBoard(from)=0;
    padBoard(over)=0;
    % Remove entries in valid move table that are no longer possible
    for x = 1 : size(valid,1)
        if (valid(x,3)==from)||(valid(x,3)==over)||(valid(x,2)==over)||(valid(x,2)==from)||(valid(x,4)==to)
            valid(x,1)=0;
        end
    end

    % Add all valid moves into spot where move is made from
    valid=[valid; padBin(from-1)+padBin(from-2) from-2 from-1 from padBoard(from-1)-padBoard(from-2) 1];
    valid=[valid; padBin(from+1)+padBin(from+2) from+2 from+1 from padBoard(from+1)-padBoard(from+2) 3];
    valid=[valid; padBin(from-mp)+padBin(from-2*mp) from-2*mp from-mp from padBoard(from-mp)-padBoard(from-2*mp) 4];
    valid=[valid; padBin(from+mp)+padBin(from+2*mp) from+2*mp from+mp from padBoard(from+mp)-padBoard(from+2*mp) 2];
    % Add all valid moves into spot that is jumped over
    valid=[valid; padBin(over-1)+padBin(over-2) over-2 over-1 over padBoard(over-1)-padBoard(over-2) 1];
    valid=[valid; padBin(over+1)+padBin(over+2) over+2 over+1 over padBoard(over+1)-padBoard(over+2) 3];
    valid=[valid; padBin(over-mp)+padBin(over-2*mp) over-2*mp over-mp over padBoard(over-mp)-padBoard(over-2*mp) 4];
    valid=[valid; padBin(over+mp)+padBin(over+2*mp) over+2*mp over+mp over padBoard(over+mp)-padBoard(over+2*mp) 2];
    % Add all valid moves out of destination
    valid=[valid; 2*padBin(to-1)+3*padBin(to-2) to to-1 to-2 10000+padBoard(to-1) 1];
    valid=[valid; 2*padBin(to+1)+3*padBin(to+2) to to+1 to+2 10000+padBoard(to+1) 3];
    valid=[valid; 2*padBin(to-mp)+3*padBin(to-2*mp) to to-mp to-2*mp 10000+padBoard(to-mp) 4];
    valid=[valid; 2*padBin(to+mp)+3*padBin(to+2*mp) to to+mp to+2*mp 10000+padBoard(to+mp) 2];
    % Add all moves jumping over destination
    valid=[valid; 6-4*padBin(to-1)+padBin(to+1) to-1 to to+1 padBoard(to)-padBoard(to-1) 1];
    valid=[valid; 6-4*padBin(to+1)+padBin(to-1) to+1 to to-1 padBoard(to)-padBoard(to+1) 3];
    valid=[valid; 6-4*padBin(to-mp)+padBin(to+mp) to-mp to to+mp padBoard(to)-padBoard(to-mp) 4];
    valid=[valid; 6-4*padBin(to+mp)+padBin(to-mp) to+mp to to-mp padBoard(to)-padBoard(to+mp) 2];
    % Remove all invalid entries
    valid=valid(find(valid(:,1)==2),:);
end


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function moves = solverrecgoodmetric(board)

moves=dorec2(board);

function moves = dorec2(board)
[m,n]=size(board);
mp=m+4;
np=n+4;
padBoard=-1*ones(mp,np);
padBoard(3:end-2,3:end-2)=board;
padBoardNoZeros=padBoard;
padBoardNoZeros(find(padBoard<=0))=1;
padBin=padBoard./padBoardNoZeros;


dest=find(padBoard==0);
maybe=zeros(4*size(dest,1),6);
moveCnt=1;
for i=1:size(dest,1)
    this=dest(i);
    % Format of valid
    % valid(2)/not(anything else)   src  jump_over  dest  score  direction_from(1 fron top, 2 from right etc)
    maybe(moveCnt,:)=[padBin(this-1)+padBin(this-2) this-2 this-1 this padBoard(this-1)-padBoard(this-2) 1];
    maybe(moveCnt+1,:)=[padBin(this+1)+padBin(this+2) this+2 this+1 this padBoard(this+1)-padBoard(this+2) 3];
    maybe(moveCnt+2,:)=[padBin(this-mp)+padBin(this-2*mp) this-2*mp this-mp this padBoard(this-mp)-padBoard(this-2*mp) 4];
    maybe(moveCnt+3,:)=[padBin(this+mp)+padBin(this+2*mp) this+2*mp this+mp this padBoard(this+mp)-padBoard(this+2*mp) 2];
    moveCnt=moveCnt+4;
end

restoreScore=0;
valid=maybe(find(maybe(:,1)==2),:);
moves=[0 0 0 0];
restoreMoves=[0 0 0 0];
score=0;
totJumps=0;
totChains=0;
while ~isempty(valid)
    [chainMoves,scoreRet]=clearChain2(padBoard,padBin,valid,mp,np,1);
    totJumps=totJumps+size(chainMoves,1);
    totChains=totChains+1;
    scoreRet=scoreRet-1;
%     if (scoreRet<0) && (score>=restoreScore)
    if (scoreRet<0) && (score>=restoreScore)
        restoreScore=score;
        restoreMoves=moves;
    end
    [padBoard,padBin,valid,chainMoves]=doMoves2(padBoard,padBin,valid,chainMoves);
    moves=[moves; chainMoves];
    score=score+scoreRet;
end

avgChainLength=totJumps/totChains;
if (score>restoreScore)
    moves=moves(find(moves(:,1)>0),:);
else
    moves=restoreMoves(find(restoreMoves(:,1)>0),:);
end

function [chainMoves,scoreRet,depthRet]=clearChain2(padBoard,padBin,valid,mp,np,depth)

scoreMax=-10000;
chainMoves=[0 0 0];
nextMoves=zeros(4,4);
for i=1:size(valid,1)
    scoreChain=0;
    newBin=padBin;
    newBoard=padBoard;
    source=valid(i,2);
    over=valid(i,3);
    dest=valid(i,4);
    newBin([source;over])=0;
    newBin(dest)=1;
%     scoreThis=newBoard(over)-newBoard(source);
%     newBoard([source;over;dest])=0;
    scoreThis=newBoard(over)/newBoard(source);
    newBoard(dest)=newBoard(source);
    newBoard([source;over])=0;
    nextMoves(1,:)=[newBin(dest-1)+3*newBin(dest-2) dest dest-1 dest-2];
    nextMoves(2,:)=[newBin(dest+1)+3*newBin(dest+2) dest dest+1 dest+2];
    nextMoves(3,:)=[newBin(dest-mp)+3*newBin(dest-2*mp) dest dest-mp dest-2*mp];
    nextMoves(4,:)=[newBin(dest+mp)+3*newBin(dest+2*mp) dest dest+mp dest+2*mp];
    nextMoves=nextMoves(find(nextMoves(:,1)==1),:);
    depthRet=depth;
    if ~isempty(nextMoves)
        [chainMoves,scoreChain,depthRet]=clearChain2(newBoard,newBin,nextMoves,mp,np,depth+1);
    end
    scoreTotal=scoreThis+scoreChain;
    if scoreTotal>scoreMax
        scoreMax=scoreTotal;
        bestMoves=[source over dest; chainMoves];
        bestDepth=depthRet;
    end
end
if (depth==1)
    chainMoves=bestMoves(1:bestDepth,:);
else
    chainMoves=bestMoves;
end
scoreRet=scoreMax;
depthRet=bestDepth;


function [padBoard,padBin,valid,retMoves]=doMoves2(padBoard,padBin,valid,chainMoves)

retMoves=[0 0 0 0];
[mp,np]=size(padBoard);
for i=1:size(chainMoves,1)
    from = chainMoves(i,1);
    over = chainMoves(i,2);
    to = chainMoves(i,3);
    rpadsrc=mod(from,mp)-2;
    cpadsrc=(from-rpadsrc-2)/mp-1;
    rpaddest=mod(to,mp)-2;
    cpaddest=(to-rpaddest-2)/mp-1;
    retMoves = [retMoves; rpadsrc cpadsrc rpaddest cpaddest];
    padBin(from)=0;
    padBin(over)=0;
    padBin(to)=1;
    padBoard(to)=padBoard(from);
    padBoard(from)=0;
    padBoard(over)=0;
    % Remove entries in valid move table that are no longer possible
    for x = 1 : size(valid,1)
        if (valid(x,3)==from)||(valid(x,3)==over)||(valid(x,2)==over)||(valid(x,2)==from)||(valid(x,4)==to)
            valid(x,1)=0;
        end
    end

    % Add all valid moves into spot where move is made from
    valid=[valid; padBin(from-1)+padBin(from-2) from-2 from-1 from padBoard(from-1)-padBoard(from-2) 1];
    valid=[valid; padBin(from+1)+padBin(from+2) from+2 from+1 from padBoard(from+1)-padBoard(from+2) 3];
    valid=[valid; padBin(from-mp)+padBin(from-2*mp) from-2*mp from-mp from padBoard(from-mp)-padBoard(from-2*mp) 4];
    valid=[valid; padBin(from+mp)+padBin(from+2*mp) from+2*mp from+mp from padBoard(from+mp)-padBoard(from+2*mp) 2];
    % Add all valid moves into spot that is jumped over
    valid=[valid; padBin(over-1)+padBin(over-2) over-2 over-1 over padBoard(over-1)-padBoard(over-2) 1];
    valid=[valid; padBin(over+1)+padBin(over+2) over+2 over+1 over padBoard(over+1)-padBoard(over+2) 3];
    valid=[valid; padBin(over-mp)+padBin(over-2*mp) over-2*mp over-mp over padBoard(over-mp)-padBoard(over-2*mp) 4];
    valid=[valid; padBin(over+mp)+padBin(over+2*mp) over+2*mp over+mp over padBoard(over+mp)-padBoard(over+2*mp) 2];
    % Add all valid moves out of destination
    valid=[valid; 2*padBin(to-1)+3*padBin(to-2) to to-1 to-2 10000+padBoard(to-1) 1];
    valid=[valid; 2*padBin(to+1)+3*padBin(to+2) to to+1 to+2 10000+padBoard(to+1) 3];
    valid=[valid; 2*padBin(to-mp)+3*padBin(to-2*mp) to to-mp to-2*mp 10000+padBoard(to-mp) 4];
    valid=[valid; 2*padBin(to+mp)+3*padBin(to+2*mp) to to+mp to+2*mp 10000+padBoard(to+mp) 2];
    % Add all moves jumping over destination
    valid=[valid; 6-4*padBin(to-1)+padBin(to+1) to-1 to to+1 padBoard(to)-padBoard(to-1) 1];
    valid=[valid; 6-4*padBin(to+1)+padBin(to-1) to+1 to to-1 padBoard(to)-padBoard(to+1) 3];
    valid=[valid; 6-4*padBin(to-mp)+padBin(to+mp) to-mp to to+mp padBoard(to)-padBoard(to-mp) 4];
    valid=[valid; 6-4*padBin(to+mp)+padBin(to-mp) to+mp to to-mp padBoard(to)-padBoard(to+mp) 2];
    % Remove all invalid entries
    valid=valid(find(valid(:,1)==2),:);
end