Finish 2012-04-11 12:00:00 UTC

final key

by Yi Cao

Status: Passed
Results: 108258 (cyc: 9, node: 4246)
CPU Time: 66.566
Score: 10915.5
Submitted at: 2012-04-11 15:56:07 UTC
Scored at: 2012-04-11 18:12:02 UTC

Current Rank: 3rd (Highest: 3rd )

Comments
Please login or create a profile.
Code
function [board, orientation] = defsolver(tiles, boardSize)

[board,orientation,solved,nrow,ncol,ntiles,nElem] = board_perfect_snake(boardSize,tiles);
if solved;return;end

cs=hankel(1:4,0:3);
played = tiles;
numUnplayed = ntiles-nElem;

if numUnplayed > 0
    sums = sum(tiles,2);
%     maxs = min(tiles,[],2);
%     [~,si] = sortrows([sums maxs],[1 2]);
    [sorted,si] = sort(sums);
	numUnplayedp1=numUnplayed+1;
    equals = find(sorted(numUnplayedp1)==sorted);
    if nnz(sorted(numUnplayedp1) == sorted(numUnplayedp1:end)) ~= length(equals)
        temp_si = si(equals);
        [trash,mi] = sort(max(tiles(temp_si,:),[],2));
        si(equals(end:-1:1))= temp_si(mi);
    end
    played(si(1:numUnplayed),:) = Inf(numUnplayed,4);
    ntiles=nElem;
    height=nrow;
else
%    height=max(min(ceil(sqrt(ntiles)), nrow),ceil(ntiles/ncol));
    height=ceil(max(min(sqrt(ntiles), nrow),ntiles/ncol));
end

[y,x]=ind2sub([height,ncol],1:ntiles);
ind = sub2ind(boardSize,y,x);
board(ind) = -1;
last = x(end);

b =repmat(board,[1,1,18]);
o = ones(size(tiles,1), 18);

NZ0 = prod(played,2);

heightn1=height-1;
[b(:,:,1),o(:,1),list] = place([1 height],1:last,b(:,:,1),played,played,o(:,1),ntiles, cs,nrow,ncol,false,NZ0);
[b(:,:,1),o(:,1),list] = place(height:-1:1,[last 1],b(:,:,1),played,list,o(:,1),ntiles, cs,nrow,ncol,false,NZ0);
newList(:,:,1) = list;

[b(:,:,2),o(:,2),list] = place(height:-1:1,last,b(:,:,2),played,played,o(:,2),ntiles, cs,nrow,ncol,false,NZ0);
[b(:,:,2),o(:,2),list] = place(height,1:last,b(:,:,2),played,list,o(:,2),ntiles, cs,nrow,ncol,false,NZ0);
[b(:,:,2),o(:,2),list] = place(1:heightn1,1,b(:,:,2),played,list,o(:,2),ntiles, cs,nrow,ncol,false,NZ0);
[b(:,:,2),o(:,2),list] = place(1,2:last,b(:,:,2),played,list,o(:,2),ntiles, cs,nrow,ncol,false,NZ0);
newList(:,:,2) = list;

ncoln1=ncol-1;
for i=[2 5]
    c = floor(i/5) + 1;
    [b(:,:,i+1),o(:,i+1)] = place(heightn1:-1:2,ncoln1:-1:2,b(:,:,c),played,newList(:,:,c),o(:,c),ntiles , cs,nrow,ncol,true,NZ0);
    [b(:,:,i+2),o(:,i+2)] = place(2:heightn1,2:ncoln1,b(:,:,c),played,newList(:,:,c),o(:,c),ntiles, cs,nrow,ncol,true,NZ0);
    [b(:,:,i+3),o(:,i+3)] = place(2:heightn1,ncoln1:-1:2,b(:,:,c),played,newList(:,:,c),o(:,c),ntiles, cs,nrow,ncol,true,NZ0);
end

[b(:,:,9),o(:,9)] = place(heightn1:-1:2,2:ncoln1,b(:,:,2),played,newList(:,:,2),o(:,2),ntiles, cs,nrow,ncol,true,NZ0);

[b(:,:,1),o(:,1)] = place(height:-1:1,1:ncol,b(:,:,12),played,played,o(:,12),ntiles,cs,nrow,ncol,-1,NZ0);
[b(:,:,2 ), o(:,2 )] = calibrating_pure_werner(played, boardSize,nrow,ncol,nrow,true);
 

if nElem < 1000

    for Sii = 10:17
	 
        [b(:,:,Sii),o(:,Sii)] = BiswasMichaelC(height,last, played, played, o(:,Sii), ntiles, cs,nrow,ncol);
    end


   
    S=17;
    if nElem < 200

        S = 18;
        [b(:,:,S ), o(:,S )] = calibrating_pure_werner(tiles, boardSize,nrow,ncol,1,false);
     
    end
end

overall = zeros(S,1);
parfor i=1:S
    overall(i) = overallScore(b(:,:,i),nrow,ncol,o(:,i),tiles, cs);
end

[trash,mo] = min(overall);
[board,orientation]=localopt(b(:,:,mo), o(:,mo),tiles,cs,nrow,ncol);




end



function [board,orientation,gain]=localopt(board, orientation,tiles,cs,r,c)
gain=0;
n = size(tiles,1);
didx = [3;4;1;2];
uidx = [1;2;3;4];
lidx = [4;1;2;3];
ridx = [2;3;4;1];
bp = board>0;
bt = board(bp);
te = [zeros(1,4);tiles];
oe = [1;orientation];
ub = [zeros(1,c);board(1:end-1,:)];
db = [board(2:end,:);zeros(1,c)];
lb = [zeros(r,1) board(:,1:end-1)];
rb = [board(:,2:end) zeros(r,1)];
ut = ub(bp)+1;
dt = db(bp)+1;
lt = lb(bp)+1;
rt = rb(bp)+1;
np1=n+1;
nv = [te(ut(:)+(didx(oe(ut))-1)*(np1)),...
      te(rt(:)+(lidx(oe(rt))-1)*(np1)),...
      te(dt(:)+(uidx(oe(dt))-1)*(np1)),...
      te(lt(:)+(ridx(oe(lt))-1)*(np1))];
bt=bt(:);
bv = tiles(bt(:,ones(1,4))+(cs(orientation(bt),:)-1)*n);
zeros401=zeros(4,1);
zeros1016=zeros(1,16);
zeros404=zeros(4);
for i=1:2
pv = sum(abs(bv-nv),2);
[mpv,id]=max(pv);

while mpv
    bid=bt(id);
    bid1=bid+1;
    pv(id)=0;
    obid = orientation(bid);
    bx = tiles(bid,:);
    p0 = sum(abs(bx(cs)-nv(id+zeros401,:)),2);
    [pmin,ido]=min(p0);
    gain=gain+(p0(obid)-pmin);



    if p0(obid)>pmin
        bv(id,:)=bx(cs(ido,:));
        orientation(bid)=ido;

        u1=ut==bid1;
        d1=dt==bid1;
        l1=lt==bid1;
        r1=rt==bid1;
        nv(u1,1) = tiles(bid,didx(ido));
        nv(d1,3) = tiles(bid,uidx(ido));
        nv(l1,4) = tiles(bid,ridx(ido));
        nv(r1,2) = tiles(bid,lidx(ido));
        L=u1|d1|l1|r1;
        pv(L) = sum(abs(bv(L,:)-nv(L,:)),2);
    end
    [mpv,id]=max(pv);
end
pv = sum(abs(bv-nv),2);
[mpv,id]=max(pv);
N=numel(pv);
tv = tiles(bt,:);
k=0;


while mpv>0
    bid = bt(id);
    bid1=bid+1;




    nvid = zeros1016;
    nvid(:) = nv(id+zeros401,:);
    u1=ut==bid1;
    d1=dt==bid1;
    l1=lt==bid1;
    r1=rt==bid1;
    L=~(u1|d1|l1|r1);
    L(id)=false;
    qv = Inf(N,4);
    qv(L,:) = reshape(sum(reshape(abs(tv(L,cs)-nvid(ones(sum(L),1),:)),[],4),2),[],4);
    [iv,to] = min(qv(:));
    jd = mod(to-1,N)+1;
    bjd = bt(jd);
    bjd1=bjd+1;
    % objd = orientation(bjd);
    jo = ceil(to/N);
    nvjd = nv(jd+zeros401,:);
    bvid = zeros404;
    bvid(:) = tiles(bid,cs);
    [jv,io]=min(sum(abs(bvid - nvjd),2));
    jpv = sum(abs(bv(jd,:) - nv(jd,:)));
    if iv+jv < mpv+jpv
        bt(jd) = bid;
        bt(id) = bjd;
        orientation(bid) = io;
        orientation(bjd) = jo;
        board(bp)=bt;
        bv(id,:) = tv(jd,cs(jo,:));
        bv(jd,:) = tv(id,cs(io,:));
        bx = tv(id,:);
        tv(id,:) = tv(jd,:);
        tv(jd,:) = bx;
        nv(u1,1) = tiles(bjd,didx(jo));
        nv(d1,3) = tiles(bjd,uidx(jo));
        nv(l1,4) = tiles(bjd,ridx(jo));
        nv(r1,2) = tiles(bjd,lidx(jo));
        u2=ut==bjd1;
        d2=dt==bjd1;
        l2=lt==bjd1;
        r2=rt==bjd1;
        nv(u2,1) = tiles(bid,didx(io));
        nv(d2,3) = tiles(bid,uidx(io));
        nv(l2,4) = tiles(bid,ridx(io));
        nv(r2,2) = tiles(bid,lidx(io));
        L=u1|d1|l1|r1|u2|d2|l2|r2;
        pv(L) = sum(abs(bv(L,:)-nv(L,:)),2);
        uid = ut==bid1;
        ujd = ut==bjd1;
        ut(uid) = bjd1;
        ut(ujd) = bid1;
        did = dt==bid1;
        djd = dt==bjd1;
        dt(did) = bjd1;
        dt(djd) = bid1;
        lid = lt==bid1;
        ljd = lt==bjd1;
        lt(lid) = bjd1;
        lt(ljd) = bid1;
        rid = rt==bid1;
        rjd = rt==bjd1;
        rt(rid) = bjd1;
        rt(rjd) = bid1;
        k=k+1;
        pv(jd)=0;
    end
    pv(id)=0;
    [mpv,id]=max(pv);
end
end
end
function score = overallScore(board,nrow,ncol, orientation, tiles, cs)

tile = zeros(nrow*4,ncol);
tmp = tiles.';
for y = 1:nrow
    for x = 1:ncol
        if board(y,x)
            tile((y-1)*4+1:y*4,x)=tmp(cs(orientation(board(y,x)),:),board(y,x));
        end
    end
end

out_tiles = 1:size(tiles,1);
in_tiles = board(board>0);
out_tiles(in_tiles) = [];

score = sum(sum(abs(tile(5:4:end,1:end)-tile(3:4:end-4,1:end))))+ ...
    sum(sum(abs(tile(2:4:end,1:end-1)-tile(4:4:end,2:end))))+ ...
    sum(tile(4:4:end,1))+sum(tile(2:4:end,end))+sum(tile(end-1,1:end))+ ...
    sum(tile(1,1:end))+sum(sum(tiles(out_tiles,:)));
end

function [board, ort, lst] = BiswasMichaelC(height, width, tiles, lst, ort, ntiles, cs,nrow,ncol)



[cols,rows]=meshgrid(1:width,1:height);
center_x = width/2 + 0.5;
center_y = height/2 + 0.5;







dist_center = ((cols - center_x).^2 + (rows - center_y).^2).^(1/2.3);
dist_center = dist_center + rand(size(dist_center))*0.03; %param
% [trash, sort_index] = sort(dist_center(:));
% loop_order = flipud(sort_index)';
[~, loop_order] = sort(dist_center(:)','descend');

board = zeros(nrow,ncol);
brd = zeros(height,width)-1;

if ntiles < height*width
    loop_order(loop_order<1 | loop_order > ntiles) = [];
%     loop_order(~ismember(loop_order,1:ntiles)) = [];
    brd(ntiles+1:end) = 0;
end
score = inf(size(lst,1),1,4);
mst   = ~isinf(lst(:,1));
for ii = loop_order
    y = rows(ii);
    x = cols(ii);
    if (brd(y,x)==-1)
        [n,e,s,w] = findBoundaries(brd, tiles, ort, y, x, cs,height,width);
        
        nesw = cat(3, [n e s w], [w n e s], [s w n e],[e s w n]);
        score=score+inf;
        score(mst,:,:) = sum(abs(int32(bsxfun(@minus,lst(mst,:),nesw))),2);
        
        [ms, o] = find(score==min(score(:)));
        which = round(rand*(length(ms)-1)+1);
        t = ms(which);
        
        ort(t) = o(which);
        brd(y,x) = t;
%        lst(t,:) = inf(1,4);
        mst(t)   = false;
    end
    lst(~mst,:) = inf;
end
board(1:height,1:width) = brd;
end

function [brd, ort, lst] = place(rowRange, colRange, brd, tiles, lst, ort, ntiles, cs,nrow,ncol,flag,NZ)
k     = 1;
score = inf(size(lst,1),1,4);
mst   = ~isinf(lst(:,1));
for y=rowRange
    for x=colRange
        if (brd(y,x)==-1)
            [n,e,s,w] = findBoundaries(brd, tiles, ort, y, x, cs,nrow,ncol);
            nesw  = cat(3, [n e s w], [w n e s], [s w n e],[e s w n]);
            score = score+inf;
            score(mst,:,:) = sum(abs(int32(bsxfun(@minus,lst(mst,:),nesw))),2);
            
            [TT, O] = find(score==min(score(:)));
            %
            if flag==-1
                idx_t = ceil(length(TT)/1.5);%round(rand*(length(ms)-1)+1);
            elseif flag
                [trash,idx_t] = max(NZ(TT));
            else
                [trash,idx_t] = min(NZ(TT));
            end
            t = TT(idx_t);
            ort(t) = O(idx_t);
            brd(y,x)=t;
%            lst(t,:)= inf(1,4);
            mst(t)  = false;     
            k = k + 1;
            if (k > ntiles)
                return;
            end
        end
    end
end
lst(~mst,:)=inf;
end

function [north, east, south, west] = findBoundaries(board, tiles, orientation, row, col, cs,nrow,ncol)
north = boundary(board, tiles, orientation, row-1,col ,3, cs,nrow,ncol );
south = boundary(board, tiles, orientation, row+1,col ,1, cs,nrow,ncol );
west = boundary(board, tiles, orientation, row ,col-1,2, cs,nrow,ncol );
east = boundary(board, tiles, orientation, row ,col+1,4, cs,nrow,ncol );
end

function value = boundary(board, tiles, orientation, row,col,id, cs,nrow,ncol )

if row<1 || col<1 || row>nrow || col>ncol || board(row,col) == 0
    value = 0;
else
    brc=board(row,col);
    if brc == -1
        value = nan;
    else
        value = tiles(brc,cs(orientation(brc),id));
    end
end

end

function [board, orientation] = calibrating_pure_werner(tiles, boardSize,nrows,ncols,w,flag)
board       = zeros(boardSize,'single');
ntiles      = size(tiles, 1);
orientation = ones(ntiles, 1);
tiles       = [tiles; tiles(:,[2:4,1]); tiles(:,[3:4,1:2]); tiles(:,[4,1:3])];
tilestaken  = false(4*ntiles, 1);
boarde      = board;
boarde(w,1) = 4;


[v, ix]     = max(boarde(:));
nextrow     = mod(ix-1,nrows)+1;
nextcol     = ceil(ix/nrows) ;

while v && ~all(tilestaken);
    tix = findbesttilefor(nextrow, nextcol,tiles,board,nrows,ncols,tilestaken,flag);
    placetile(tix, nextrow, nextcol)

    [v, ix]     = max(boarde(:));
    nextrow     = mod(ix-1,nrows)+1;
    nextcol     = ceil(ix/nrows) ;
end







     function placetile(tileix, row, col)
        board(row, col) = tileix;
        boarde(row, col) = 0;
        rowm1=row > 1;
        colm1= col > 1;
        rowmnrows=row < nrows;
        colmncols=col < ncols;
        rowp1=row+1;
        colp1=col+1;
        coln1=col-1;
        rown1=row-1;
        
        placetile1(tileix, row, col,rowm1,colm1,rowmnrows,colmncols,rowp1,rown1,colp1,coln1 )
        placetile2( rowm1 ,colmncols,colm1, rown1,colp1,coln1)
        placetile3( colm1,rowmnrows ,colmncols,rowp1 ,colp1,coln1)
        
        ix              = mod(tileix-1, ntiles)+1;
        orientation(ix) = ceil(tileix/ntiles);
        tilestaken(ix+ntiles*(0:3), :) = true;
        
        function placetile1(tileix, row, col,rowm1,colm1,rowmnrows,colmncols,rowp1,rown1,colp1,coln1 )
            if rowm1 && ~board(rown1,col); boarde(rown1, col ) = boarde(rown1, col ) + tiles(tileix, 1); end;
            if rowmnrows && ~board(rowp1,col ); boarde(rowp1, col ) = boarde(rowp1, col ) + tiles(tileix, 3); end;
            if colm1 && ~board(row ,coln1); boarde(row , coln1) = boarde(row , coln1) + tiles(tileix, 4); end;
            if colmncols && ~board(row ,colp1); boarde(row , colp1) = boarde(row , colp1) + tiles(tileix, 2); end;
        end
        
        function placetile2( rowm1,colmncols,colm1, rown1,colp1,coln1)
            if rowm1 && colm1 && ~board(rown1,coln1); boarde(rown1, coln1) = boarde(rown1, coln1) + 0.1; end;
            if rowm1 && colmncols && ~board(rown1,colp1); boarde(rown1, colp1) = boarde(rown1, colp1) + 0.1; end;
        end
        
        function placetile3( colm1,rowmnrows,colmncols,rowp1, colp1,coln1)
            if rowmnrows && colm1 && ~board(rowp1,coln1); boarde(rowp1, coln1) = boarde(rowp1, coln1) + 0.1; end;
            if rowmnrows && colmncols && ~board(rowp1,colp1); boarde(rowp1, colp1) = boarde(rowp1, colp1) + 0.1; end;
        end
    end
boardzeros        = board == 0;
board             = mod(board-1, ntiles)+1;
board(boardzeros) = 0;
end

function ret = findbesttilefor(r, c,tiles,board,nrows,ncols,tilestaken,flag)
  function myret=spycat(x,y,z,tiles,board)
        if board(x,y) > 0; myret = tiles(board(x,y), z);
        else myret = nan;
        end
    end 

v = zeros(1,4);
if r > 1;
    v(1) = spycat(r-1,c , 3,tiles,board);
end
if c < ncols;
    v(2)= spycat(r,c+1,4,tiles,board)  ;
end
if r < nrows;
    v(3) = spycat(r+1,c,1,tiles,board);
end
if c > 1;
    v(4)=spycat(r,c-1,2,tiles,board) ;
end

 mask = ~isnan(v);
    tilecosts = sum(abs(bsxfun(@minus, tiles(:,mask), v(mask))), 2);
    tilecosts(tilestaken) = inf;
if flag




    [trash, ret] = min(tilecosts - 1e-10*sum(tiles(:, isnan(v)), 2));
else
    [trash, ret] = min(tilecosts-sum(tiles,2).*1e-6);
end

end

% Richard routines
function [board,orientation,solved,nr,nc,numtiles,nrnc]=board_perfect_snake(boardSize,tiles)
% check for perfect unique board
solved=false;
board = zeros(boardSize,'single');
numtiles=size(tiles,1);

orientation = ones(numtiles, 1);

[nr nc]=size(board);
nrnc=nr*nc;
if numtiles~=nrnc,return;end

 

% minimum required #tiles with a zero
if size(find( tiles==0),1)<2*(nr+nc-2),return;end % No solution

otiles=tiles;

[tv,orientation,otiles,valid]= ...
    find_corner(tiles,otiles,orientation);
if ~valid,return;end
board(1)=tv; % 2 pts

for i=1:nr
    
    if i>1
        tile=board(i-1);
        
        [board,orientation,otiles,valid]= ...
            find_tiles(board,orientation,tiles,otiles,i,1,nrnc,tile,3);
        % [board,orientation,otiles,valid]= ...
        % first_column(board,orientation,otiles,tiles,i,j,nelem,tile,edge);
        if ~valid,return;end
        
    end % i>1
    
    for j=2:nc
        tile=board(i,j-1);
        
        [board,orientation,otiles,valid]= ...
            find_tiles(board,orientation,tiles,otiles,i,j,nrnc,tile,2);
        if ~valid,return;end
        
    end % j 2:nc
    
end % i 1:nr

solved=true;

end


function [tv,orientation,otiles,valid]= ...
    find_corner(tiles,otiles,orientation)

valid=false;
cs=[4 1 2 3]; % 4 pts define outside

for i=1:4
    adj= tiles(:,i) + tiles(:,cs(i) );
    tv=find(adj==0,1); % Corner found
    if ~isempty(tv)
        orientation(tv)=i;
        otiles(tv,:)=rot_tile(i,tiles(tv,:)); % or to i 2 pts
        valid=true;
        return; % corner found and rotated to position
    end
end

% No corner found
end % find corner

function [one_tile]=rot_tile(rot,tile)
one_tile=circshift(tile,[0 1-rot]);
end

function [board,orientation,otiles,valid]= ...
    find_tiles(board,orientation,tiles,otiles,i,j,nrnc,tile,ul)













% [board,orientation,otiles,valid]= ...
% first_column(board,orientation,otiles,tiles,i,j,nrnc,tile,UL);

valid=false; % could remove valid=false from returns

tvec=find(otiles==otiles(tile,ul));
if size(tvec,1)~=2,return;end % Non Unique solutions
tvecn1=tvec-1;
tnum=mod(tvecn1,nrnc)+1;
trot=floor((tvecn1)/nrnc)+1;


if tnum(1)~=tile % use
    tv=tnum(1);
    rot=trot(1);
else % use 2nd
    tv=tnum(2);
    rot=trot(2);
end

% for found pushed to L(4) 4:1,3:4,2:3,1:2
if j>1 % doing rows
    rot = mod(rot,4)+1;
end
board(i,j)=tv;
otiles(tv,:)=rot_tile(rot,tiles(tv,:));
orientation(tv)=rot;

valid=true;
end