Winner Yi Cao (Buy a ticket)

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

jacob's lair 8

by MJP

Status: Passed
Results: 42868.22 (cyc: 8)
CPU Time: 38.1234
Score: 4300.28
Submitted at: 2007-05-14 15:18:33 UTC
Scored at: 2007-05-14 15:19:43 UTC

Current Rank: 2185th

Comments
Please login or create a profile.
Code
function moves = solver(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)
        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;
    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