Winner Yi Cao (Buy a ticket)

2007-05-16 12:00:00 UTC

by srach

Status: Passed
Results: 40541.22 (cyc: 12)
CPU Time: 50.6278
Score: 4081.26
Submitted at: 2007-05-12 13:09:21 UTC
Scored at: 2007-05-12 13:11:06 UTC

Current Rank: 1600th
Based on: T.S. Eliot (diff)

Code
```function moves = solver(board)

[m,n] = size(board);
COUNT = sum(board(:)>0); % check the number of pegs on the board
vd = all(board == -1,1);
d = [0 find(vd) n+1];
for i = 1:numel(d)-1
if ~any(any(board(:,d(i)+1:d(i+1)-1)==0))
board(:,d(i)+1:d(i+1)-1) = -1;
end;
end;
hd = all(board == -1,2);
d = [0;find(hd);m+1];
for i = 1:numel(d)-1
if ~any(any(board(d(i)+1:d(i+1)-1,:)==0))
board(d(i)+1:d(i+1)-1,:) = -1;
end;
end;

fill = COUNT/m*n;
if (COUNT< 320)&&(fill < 0.68)
tb = board;
ntb=ones(size(tb,1)+4,size(tb,2)+4) * -1;
ntb(3:end-2,3:end-2)= tb;
[rows,cols] = size(ntb);
count=0;

value_average = mean(ntb(logical(ntb>0)));
edge_weight = value_average*0;
blob_weight = value_average*0;
moves=solveri(ntb);
else
board0 = board;
[m,n] = size(board0); % find dims of input board
[i,j]=find(ones(m,n)); % create an index listing of board elements

I = [i;i;i;i];  % vector of 4 repeats of row coords
J = [j;j;j;j]; % vector of 4 repeats of col coords
K = [i;i;i-2;i+2]; % vector of row cords, row cords, 2 rows above, 2 rows below
L = [j-2;j+2;j;j]; % vector of 2 cols before, 2 cols past, col cords, col cords
% [I J K L] would be a matrix of ALL potential moves for this board

K1=[i;i;i-4;i+4]; % vector of row cords, row cords, 4 rows above, 4 rows below
L1=[j-4;j+4;j;j]; % vector of 4 cols before, 4 cols past, col cords, col cords
% if a move from [I J] to [K L] were done, [K L K1 L1] is the potential next colinear moves

K2=[i-2;i+2;i-2;i+2]; % vector of 2 rows above, 2 rows below repeated twice
L2=[j-2;j+2;j+2;j-2];  % vector of 2 cols before, 2 cols past, 2 cols past, 2 cols before
% if a move from [I J] to  [K L] were done, [K L K2 L2] is the half of the potential next orthogonal moves

K3=[i+2;i-2;i-2;i+2]; % vector of 2 rows below, 2 rows above, 2 rows above, 2 rows below
L3=[j-2;j+2;j-2;j+2]; % vector of 2 cols before, 2 cols past repeated twice
% if a move from [I J] to [K L] were done, [K L K3 L3] is the other half of the potential next orthogonal moves

h = (K>0 & K<=m & L>0 & L<=n); % find indexes of moves that stay within overall bounds of board after 1st jump
I=I(h); % remove moves that jump off the board after 1st jump
J=J(h); % remove moves that jump off the board after 1st jump
K=K(h); % remove moves that jump off the board after 1st jump
L=L(h); % remove moves that jump off the board after 1st jump
K1=K1(h); % remove moves that jump off the board after 1st jump
K2=K2(h); % remove moves that jump off the board after 1st jump
K3=K3(h); % remove moves that jump off the board after 1st jump
L1=L1(h); % remove moves that jump off the board after 1st jump
L2=L2(h); % remove moves that jump off the board after 1st jump
L3=L3(h); % remove moves that jump off the board after 1st jump

F=I+(J-1)*m; % convert source spot coordinates [I J] into single index value
T=K+(L-1)*m; % convert destination spot coordinates [K L] into single index value
M=(F+T)*0.5; % calculate the index value of the spot that would be jumped if did move [I J K L]

h=board0(F)>=0&board0(M)>=0&board0(T)>=0; % find indexes of moves that don't involve offlimits (-1) areas
I=I(h); % remove moves that involve offlimits areas
J=J(h); % remove moves that involve offlimits areas
K=K(h); % remove moves that involve offlimits areas
L=L(h); % remove moves that involve offlimits areas
F=F(h); % remove moves that involve offlimits areas
T=T(h); % remove moves that involve offlimits areas
M=M(h); % remove moves that involve offlimits areas
K1=K1(h); % remove moves that involve offlimits areas
K2=K2(h); % remove moves that involve offlimits areas
K3=K3(h); % remove moves that involve offlimits areas
L1=L1(h); % remove moves that involve offlimits areas
L2=L2(h); % remove moves that involve offlimits areas
L3=L3(h); % remove moves that involve offlimits areas

h1 = (K1>0 & K1<=m & L1>0 & L1<=n); % find indexes of moves that stay within overall bounds of board after 2nd colinear jump
h2 = (K2>0 & K2<=m & L2>0 & L2<=n); % find indexes of moves that stay within overall bounds of board after 2nd orthogonal jump
h3 = (K3>0 & K3<=m & L3>0 & L3<=n);% find indexes of moves that stay within overall bounds of board after 2nd orthogonal jump

T1=T;T2=T;T3=T; % create dups of 1st jump destination spot coordinates
T1(h1)=K1(h1)+(L1(h1)-1)*m; % convert 2nd colinear jump destination spot coordinates into single index value - note invalid jumps are kept in index but not converted
T2(h2)=K2(h2)+(L2(h2)-1)*m; % convert 2nd ortho jump destination spot coordinates into single index value - note invalid jumps are kept in index but not converted
T3(h3)=K3(h3)+(L3(h3)-1)*m; % convert 2nd ortho jump destination spot coordinates into single index value - note invalid jumps are kept in index but not converted
M1=(T+T1)*0.5; % calculate the index value of the spot that would be jumped if did move [K L K1 L1]
M2=(T+T2)*0.5; % calculate the index value of the spot that would be jumped if did move [K L K2 L2]
M3=(T+T3)*0.5; % calculate the index value of the spot that would be jumped if did move [K L K3 L3]

CV = zeros(size(M1)); % make a dup of colinear jumps
P=board0(:)>0; % search for all pegs on board
N=sum(P); % count number of pegs
MV = [I J K L]; % create first possible move list
[mv1,v1]=subsoltweak(board0);

if COUNT > 320
ddlist = [2.1 1 0.592];
elseif COUNT > 200
ddlist = [ 4 2.1    1    0.7692    0.592    0.4762 0.254];
elseif COUNT > 100
ddlist = [8 4 2.1    1    0.7692    0.592    0.4762 0.254 0.1];
else
ddlist = [ 8 4 2.1    1    0.7692    0.592    0.4762 0.254 0.1 0.05];
end

for dd = ddlist % repeat over the iteration weightings
[mv2,v2] = subsol(board0,dd); %  calculate moves and scores of moves with nested function
if v2>v1, % check if new score is better than last score
mv1=mv2; % if so, adopt move list
v1=v2; % update best score
end
end
moves=mv1; % output best move list
end;

function moves=solveri(scores)

board = scores;
zz = find(board>0);
balls=numel(zz);
moves = zeros(balls,4);

bufsize = balls*4;
cellbuf = zeros(bufsize,1);
valbuf = zeros(bufsize,1);
movebuf = zeros(bufsize,1);
hopbuf = zeros(bufsize,1);

last_move = 0;
score = 0;
last_pos = 0;
last_score = 0;
depth = 10;

hop_max = 0;
hop_cnt = 0;
hop_list=hopbuf;

[cell_list,value_list,move_list] = CalculateMoves(board);

while 1
% find highest value moves
if isempty(cell_list),break;end

FindHops(board,cell_list,move_list,value_list);
if (hop_max~=0)&&(hop_cnt>2)
for zh=1:hop_cnt-1
cell_list = [cell_list;hop_list(zh)];
move_list = [move_list;hop_list(zh+1)];
value_list = [value_list;hop_max];
DoMove(numel(cell_list));
end
else
%find moves that create hops
[hop_values,pos]=sort(value_list,'descend');
value_list = hop_values;
cell_list=cell_list(pos);
move_list=move_list(pos);
for zh=1:min(depth,numel(cell_list))
[newB,newS,newC,newM,newV] = ProcessMove(board,scores,zh,cell_list,move_list,value_list);
FindHops(newB,newC,newM,newV);
hop_values(zh) = hop_values(zh) + hop_max;
end
[max_val,pos]=max(hop_values);
DoMove(pos);
end

if (count==balls)
break;
end
end

moves = moves(1:last_pos,:);

function DoMove(pos)
max_cell = cell_list(pos);
max_move = move_list(pos);
count = count+1;
moves(count,:) = [mod(max_cell-2,rows),ceil(max_cell/rows)-2,mod(max_move-2,rows),ceil(max_move/rows)-2];

brem = (max_cell+max_move)/2;
score = score + scores(brem);
if (max_cell ~= last_move)
score = score - scores(max_cell);
end
if (score > last_score)
last_pos=count;
last_score=score;
end;

[board,scores,cell_list,move_list,value_list] = ProcessMove(board,scores,pos,cell_list,move_list,value_list);
last_move = max_move;
end

function FindHops(board,Lcells,Lmoves,Lvalues)
hop_max=0;
for zi=1:numel(Lcells)
hopbuf(1)=Lcells(zi);
FindHopTree(board,Lcells(zi),Lmoves(zi),Lvalues(zi),2);
end
end

function FindHopTree(B,src,dst,n,cnt)
B(dst)=B(src);
B((src+dst)/2)=0;
B(src)=0;

%save hop
hopbuf(cnt)=dst;

if (B(dst+2)==0)
hs=B(dst+1);
if hs>0
FindHopTree(B,dst,dst+2,n+hs,cnt+1);
end
end

if (B(dst-2)==0)
hs=B(dst-1);
if hs>0
FindHopTree(B,dst,dst-2,n+hs,cnt+1);
end
end

if (B(dst+2*rows)==0)
hs=B(dst+rows);
if hs>0
FindHopTree(B,dst,dst+2*rows,n+hs,cnt+1);
end
end

if (B(dst-2*rows)==0)
hs=B(dst-rows);
if hs>0
FindHopTree(B,dst,dst-2*rows,n+hs,cnt+1);
end
end

%end of hop chain -- check for max and save route
if n>hop_max
hop_max = n;
hop_cnt = cnt;
hop_list(1:cnt)=hopbuf(1:cnt);
end
end

function n=CalculateBall(board,src,dst,n)
pop=(src+dst)/2;
if board(pop)>0
if ~board(dst)
if board(src)>0
pass=board(pop)-board(src);
if edges(src)
pass=pass+edge_weight;
end
neighbor = [board(dst+1);board(dst-1);board(dst+rows);board(dst-rows)];
neighbor = sum(neighbor>0)-1;
if (neighbor>0)
pass=pass+neighbor*blob_weight;
else
end
n=n+1;
valbuf(n)=pass;
cellbuf(n)=src;
movebuf(n)=dst;
end
end
end
end

function n=CalculateHole(board,dst,src,n)
pop=(src+dst)/2;
if board(pop)>0
if board(src)>0
if edges(src)
pass=board(pop)-board(src)+edge_weight;
else
pass=board(pop)-board(src);
end
neighbor = [board(dst+1);board(dst-1);board(dst+rows);board(dst-rows)];
neighbor = sum(neighbor>0)-1;
if (neighbor>0)
pass=pass+neighbor*blob_weight;
else
end
n=n+1;
valbuf(n)=pass;
cellbuf(n)=src;
movebuf(n)=dst;
end
end
end

function Lmoves=EliminateMove(Lcells,Lmoves,src,dst)
rem_src=find(Lcells==src);
Lmoves(rem_src(logical(Lmoves(rem_src)==dst)))=0;
end

function [new_cell_list,new_value_list,new_move_list] = CalculateMoves(board)
zb = find(board>0);
zz = find(board==0);
n=0;
if numel(zz)<numel(zb)
for zi=1:numel(zz)
i=zz(zi);
n=CalculateHole(board,i,i-2,n);
n=CalculateHole(board,i,i+2,n);
n=CalculateHole(board,i,i-rows*2,n);
n=CalculateHole(board,i,i+rows*2,n);
end
else
for zi=1:numel(zb)
i=zb(zi);
n=CalculateBall(board,i,i-2,n);
n=CalculateBall(board,i,i+2,n);
n=CalculateBall(board,i,i-rows*2,n);
n=CalculateBall(board,i,i+rows*2,n);
end
end
new_cell_list=cellbuf(1:n);
new_value_list=valbuf(1:n);
new_move_list=movebuf(1:n);
end

function [B,S,Lcells,Lmoves,Lvalues]=ProcessMove(B,S,pos,Lcells,Lmoves,Lvalues)
src = Lcells(pos);
dst = Lmoves(pos);
pop = (src+dst)/2;
B(dst)=B(src);
B(pop)=0;
B(src)=0;
S(dst)=S(src);
S(pop)=0;
S(src)=0;

u = src-pop;
if (abs(u)==1)
v=rows;
else
v=1;
end

Lmoves(logical(Lmoves==dst))=0;
Lmoves(logical(Lcells==src))=0;
Lmoves(logical(Lcells==pop))=0;
Lmoves=EliminateMove(Lcells,Lmoves,src-v,src+v);
Lmoves=EliminateMove(Lcells,Lmoves,src+v,src-v);
Lmoves=EliminateMove(Lcells,Lmoves,src-v-u,src+v-u);
Lmoves=EliminateMove(Lcells,Lmoves,src+v-u,src-v-u);
[Lmoves,rem_dst]=sort(Lmoves,'descend');
Lcells=Lcells(rem_dst);
Lvalues=Lvalues(rem_dst);
ncnt=find(Lmoves==0);
ncnt=ncnt(1);
Lcells=Lcells(1:ncnt-1);
Lvalues=Lvalues(1:ncnt-1);
Lmoves=Lmoves(1:ncnt-1);

n=0;
n=CalculateBall(B,src-3*u,src-u,n);
n=CalculateBall(B,src+2*v-u,src-u,n);
n=CalculateBall(B,src+2*v,src,n);
n=CalculateBall(B,src+2*u,src,n);
n=CalculateBall(B,src-2*v,src,n);
n=CalculateBall(B,src-2*v-u,src-u,n);
n=CalculateBall(B,dst,dst-2*u,n);
n=CalculateBall(B,dst,dst-2*v,n);
n=CalculateBall(B,dst,dst+2*v,n);
clf=src-v-2*u;
crt=src+v-2*u;
if ~B(clf)
n=CalculateBall(B,crt,clf,n);
end
if ~B(crt)
n=CalculateBall(B,clf,crt,n);
end

if (n>0)
if (ncnt>1)
Lcells = [Lcells;cellbuf(1:n)];
Lmoves = [Lmoves;movebuf(1:n)];
Lvalues = [Lvalues;valbuf(1:n)];
else
Lcells=cellbuf(1:n);
Lvalues=valbuf(1:n);
Lmoves=movebuf(1:n);
end
end
end

end

function [moves,v]=subsol(board,d)
moves=zeros(N-1,4); % preallocate maximum possible move list based on number of pegs
v0=zeros(N-1,1); % preallocate maximum size of score list
Bzero = ~board;  % create inverse board where 1 is a hole and every else is a zero, including offlimits
Bpos  = board>0; % create board with pegs all as 1 and everything else 0
hs = (Bpos(F) & Bzero(T) & Bpos(M)); % search for moves where source is peg, destination is hole and jumped spot is peg
h = find(hs); % extract indexes of valid moves
t=1; % init move list index
while ~isempty(h)
CV(:)=0; % init all possible 2nd jumps B to 0
h0=hs&h1; % compare possible colinear jumps with valid 1st jumps
Mtemp=M1(h0); %find indexes of 2nd jumped peg
CV(h0)=board(Mtemp).*(Bpos(Mtemp)&Bzero(T1(h0))); %find 2nd jumped peg B score (colinear), check if dest is hole and jumped is peg
h0=hs&h2; % compare possible ortho1 jumps with valid 1st jumps
Mtemp=M2(h0); %find indexes of 2nd jumped peg
CV(h0)=max(CV(h0),board(Mtemp).*(Bpos(Mtemp)&Bzero(T2(h0))));  %find 2nd jumped peg B score (ortho1), check if dest is hole and jumped is peg
h0=hs&h3; % compare possible ortho2 jumps with valid 1st jumps
Mtemp=M3(h0); %find indexes of 2nd jumped peg
CV(h0)=max(CV(h0),board(Mtemp).*(Bpos(Mtemp)&Bzero(T3(h0)))); %find 2nd jumped peg B score (ortho2), check if dest is hole and jumped is peg
if t>1
c=h(F(h)==T0); % find indexes of jumps with source peg that is same as last one moved
else
c=[]; % else zero out c
end
if ~isempty(c) % if any current 2 jump moves contain the last peg
C0=board(M(c)); % seed possible 2nd jumps B with jumped peg value for all jumps the match last jump end
[v,k]=max(C0+CV(c)*d); % add jumped peg to 2nd jump and find best 2 move jump
v0(t)=C0(k); % extract score of best 1st jump score
k=c(k);  % extract index of best 2 move jump
else
V=board(M(h))-board(F(h)); % calculate score for all valid 1st moves
[v,k]=max(V+CV(h)*d); % add 1st move score to 2nd jump scores and find best 2 move jump
v0(t)=V(k); %extract score of best 1st double jump
k=h(k); % extract index of first move
end
moves(t,:) = MV(k,:); % add best move (1st jump) to movelist
T0=T(k); % extract 1st jump destination spot
t=t+1; % increment move count
board(T0)=board(F(k)); % update destination spot with source spot peg
board(F(k))=0; % zero out source spot peg
board(M(k))=0; % zero out jumped spot peg
Bzero = ~board; % create updated inverse board
Bpos  = board>0; % create updated peg only board
hs = (Bpos(F) &Bzero(T) & Bpos(M)); % search for valid moves in new board
h = find(hs); % extract indexes of valid moves
end
v0=cumsum(v0); % create cumulative sum of scores in movelist
[v,t]=max(v0); % extract location of best cumulative score
moves = moves(1:t,:); % output moves up to best location

end

function [moves,v]=subsoltweak(board)
moves=zeros(N-1,4); % preallocate maximum possible move list based on number of pegs
v0=zeros(N-1,1); % preallocate maximum size of score list
Bzero = ~board;  % create inverse board where 1 is a hole and every else is a zero, including offlimits
Bpos  = board>0; % create board with pegs all as 1 and everything else 0
hs = (Bpos(F) & Bzero(T) & Bpos(M)); % search for moves where source is peg, destination is hole and jumped spot is peg
h = find(hs); % extract indexes of valid moves
t=1; % init move list index
while ~isempty(h)
CV(:)=0; % init all possible 2nd jumps B to 0
if t>1
c=h(F(h)==T0); % find indexes of jumps with source peg that is same as last one moved
else
c=[]; % else zero out c
end
if ~isempty(c) % if any current 2 jump moves contain the last peg
C0=board(M(c)); % seed possible 2nd jumps B with jumped peg value for all jumps the match last jump end
[v,k]=max(C0);
v0(t)=C0(k); % extract score of best 1st jump score
k=c(k);  % extract index of best 2 move jump
else
V=board(M(h))-board(F(h)); % calculate score for all valid 1st moves
[v,k]=max(V+CV(h)); % add 1st move score to 2nd jump scores and find best 2 move jump
v0(t)=V(k); %extract score of best 1st double jump
k=h(k); % extract index of first move

end
moves(t,:) = MV(k,:); % add best move (1st jump) to movelist
T0=T(k); % extract 1st jump destination spot
t=t+1; % increment move count
board(T0)=board(F(k)); % update destination spot with source spot peg
board(F(k))=0; % zero out source spot peg
board(M(k))=0; % zero out jumped spot peg
Bzero = ~board; % create updated inverse board
Bpos  = board>0; % create updated peg only board
hs = (Bpos(F) &Bzero(T) & Bpos(M)); % search for valid moves in new board
h = find(hs); % extract indexes of valid moves
end
v0=cumsum(v0); % create cumulative sum of scores in movelist
[v,t]=max(v0); % extract location of best cumulative score
moves = moves(1:t,:); % output moves up to best location
end
end```