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

CatsAreComing?

by Sergey Y.

Status: Passed
Results: 108152 (cyc: 10, node: 4322)
CPU Time: 70.508
Score: 10911.5
Submitted at: 2012-04-11 15:39:49 UTC
Scored at: 2012-04-11 16:49:51 UTC

Current Rank: 1st (Highest: 1st )
Based on: Defense (diff)

Comments
Nuwan Ganganath
11 Apr 2012
Congratulations!
Oleg Komarov
11 Apr 2012
Congratulations here too! You really deserved it.
James White
11 Apr 2012
Congrats! Nice improvement... so simple too.
Vitor Yano
12 Apr 2012
Congratulations Sergey!
krishnarjuna rao
23 May 2012
congrates
Kevin
22 Aug 2012
can you describe what it does?
Please login or create a profile.
Code
function [board, orientation] = solver(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;

sums = sum(tiles,2);
if numUnplayed > 0
    [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

[overall ord]=sort(overall);
b=b(:,:,ord);
o=o(:,ord);

for q=1:2
[b(:,:,q),o(:,q)]=localopt(b(:,:,q), o(:,q),tiles,cs,nrow,ncol);
overall(q) = overallScore(b(:,:,q),nrow,ncol,o(:,q),tiles, cs);
end
[trash,mo] = min(overall);
board = b(:,:,mo);
orientation = o(:,mo);


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;
    end
    pv(id)=0;
    pv(jd)=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)';

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

if ntiles < height*width
    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;
elseif board(row,col) == -1
    value = nan;
else
    value = tiles(board(row,col),cs(orientation(board(row,col)),id));
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