2012-04-11 12:00:00 UTC

# Reverse a change

Status: Passed
Results: 113888 (cyc: 10, node: 3615)
CPU Time: 64.919
Score: 11464.4
Submitted at: 2012-04-07 21:11:55 UTC
Scored at: 2012-04-07 21:14:09 UTC

Current Rank: 793rd (Highest: 1st )
Based on: Random tidy (diff)
Basis for: Just checking (diff)
Basis for: More Random (diff)

Code
```function [board, orientation] = solver(tiles, boardSize)

ntiles      = size(tiles,1);
nrow = boardSize(1);
ncol = boardSize(2);
nElem       = nrow*ncol;
board       = zeros(boardSize);
cs          = [1 2 3 4; 2 3 4 1; 3 4 1 2; 4 1 2 3];
played = tiles;
numUnplayed = ntiles-nElem;

if numUnplayed>0
sums = sum(tiles,2);
[~,si] = sort(sums);
played(si(1:numUnplayed),:) =  Inf(numUnplayed,4);
ntiles=nElem;
height=nrow;
else
height=max(min(ceil(sqrt(ntiles)), nrow),ceil(ntiles/ncol));
end

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

b =cat(3,board,board,board,board,board,board,board, board, board);

o = ones(size(tiles,1), 9);

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

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

for i=[4 0]
[b(:,:,i+2),o(:,i+2),~] = place(2:height-1,2:ncol-1,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles,  cs,nrow,ncol);
[b(:,:,i+3),o(:,i+3),~] = place(height-1:-1:2,2:ncol-1,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles,  cs,nrow,ncol);
[b(:,:,i+4),o(:,i+4),~] = place(2:height-1,ncol-1:-1:2,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles,  cs,nrow,ncol);
[b(:,:,i+1),o(:,i+1),~] = place(height-1:-1:2,ncol-1:-1:2,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles , cs,nrow,ncol);
end

S = 8;
if nElem < 1000
[b(:,:,9),o(:,9)] = MichaelC(height,last(2), tiles, played, o(:,9), ntiles, cs,nrow,ncol);
S = S + 1;
[b(:,:,10 ), o(:,10 )] = picky(tiles, boardSize,nrow,ncol,cs);
[b(:,:,11), o(:,11)] = calibrating_pure(tiles, boardSize,nrow,ncol);
S = S + 2;
if nElem < 200
[b(:,:,12), o(:,12)] = werner(tiles, boardSize,nrow,ncol);
S = S + 1;
end

end

overall  = zeros(S,1);
parfor i=1:S
overall(i) = overallScore(b(:,:,i),nrow,ncol,o(:,i),tiles, cs);
end
[~,mo] = min(overall);
board = b(:,:,mo);
orientation = o(:,mo);

%disp(['  Mejor SOLUCION SOLVER_' num2str(mo) ])

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)=tiles(board(y,x),cs(orientation(board(y,x)),:))';
tile((y-1)*4+1:y*4,x)=tmp(cs(orientation(board(y,x)),:),board(y,x));
end
end
end
internal    = 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))));
external    = sum(tile(4:4:end,1))+sum(tile(2:4:end,end))+sum(tile(end-1,1:end))+sum(tile(1,1:end));
out_tiles   = 1:size(tiles,1);
in_tiles    = board(board>0);
out_tiles(in_tiles) = [];
notplayed   = sum(sum(tiles(out_tiles,:)));
score       = internal + external + notplayed;
end

function [board, ort, lst] = MichaelC(height, width, tiles, list, orientation, ntiles, cs,nrow,ncol)
all_indices = reshape(1:(height*width),height,width);
center_x = width/2 + 0.5;
center_y = height/2 + 0.5;
cols = ceil(all_indices/height);
rows = mod(all_indices-1,height)+1;
dist_center = sqrt((cols - center_x).^2 + (rows - center_y).^2);
[~, sort_index] = sort(dist_center(:));
loop_order = flipud(sort_index)';
tile_sums = sum(tiles,2);

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

ort = orientation;
lst = list;
L   = size(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);

grid  = ones(L,1)*[n e s w];
for i=4:-1:1
score(:,i) = sum(int32(abs(lst(:,cs(:,i))-grid)),2);
end
[ms, t] = min(score);
ms_i = find(ms == min(ms));
if length(ms_i) > 1
rand_i = ceil(rand(1)*length(ms_i));
o = ms_i(rand_i);
else
[~ , o] = min(ms);
end
t = t(o);

ort(t) = o;
brd(y,x)=t;
lst(t,:)=inf(1,4);
end
end
board(1:height,1:width) = brd;
end

function [brd, ort, lst] = place(rowRange, colRange, board, tiles, list, orientation, ntiles,   cs,nrow,ncol)
k = 1;
brd = board;
ort = orientation;
lst = list;
L   = size(lst,1);
tile_sums = sum(tiles,2);
for y=rowRange
for x=colRange
if (brd(y,x)==-1)
[n,e,s,w] = findBoundaries(brd, tiles, ort, y, x, cs,nrow,ncol);
%                [t, o] = findBestTile(lst, L, n, e, s, w, cs);

%
grid  = ones(L,1)*[n e s w];
for i=4:-1:1
score(:,i) = sum(int32(abs(lst(:,cs(:,i))-grid)),2);
end
[ms, t] = min(score);
[~ , o] = min(ms);
t = t(o);

ort(t) = o;
brd(y,x)=t;
lst(t,:)=inf(1,4);
k = k + 1;
if (k > ntiles)
return;
end
end
end
end
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
value = 0;
else
if board(row,col) == -1
value = nan;
elseif board(row,col) == 0
value = 0;
else
value  = tiles(board(row,col),cs(orientation(board(row,col)),id));

end
end
end

function [board, orientation] = picky(tiles, boardSize,nrow,ncol,cs )

nt = size(tiles,1);
board = zeros(boardSize);

nb = nrow*ncol;
orientation = ones(nt,1);

unused = true(1,nt);
rt = zeros(size(tiles,1),4,4);
for i=1:4
rt(:,:,i) = tiles(:,cs(:,i));
end
goalN = nan(boardSize);
goalN(1,:) = 0;
goalS = nan(boardSize);
goalS(end,:) = 0;
goalE = nan(boardSize);
goalE(:,end) = 0;
goalW = nan(boardSize);
goalW(:,1) = 0;
tsum = sum(tiles,2);

% greedily pick tiles
for i = 1:min(nb,nt)
goal = [goalN(i),goalE(i),goalS(i),goalW(i)];
for j = 4:-1:1
hd = bsxfun(@minus,rt(unused,:,j),goal);
hd(isnan(hd)) = 0;
hs{j} = sum(abs(hd),2);
end;
hsm = cat(2,hs{:});
hsm(hsm~=min(hsm(:))) = inf;
%hsm(hsm~=min(min(hsm))) = inf;
hsm = bsxfun(@minus,hsm,tsum(unused));
%[~,pick] = min(hsm(:));
%[pick,ori] = ind2sub([nt-i+1,4],pick);
[pick,ori] = find(hsm==min(min(hsm)),1,'first');
pick = find(unused,pick);
pick = pick(end);
board(i) = pick;
orientation(pick) = ori;
unused(pick) = false;

% update goals
if (i+nrow <= nb)
goalW(i+nrow) = rt(pick,2,ori);
end;
if (mod(i,nrow) ~= 0)
goalN(i+1) = rt(pick,3,ori);
end;
end;
end

function [board, orientation] = calibrating_pure(tiles, boardSize,nrows,ncols)

board = zeros(boardSize);
orientation = ones(size(tiles,1), 1);
boarde = board;

ntiles = size(tiles, 1);

%     [~, tilesperm] = sort(sum(tiles, 2), 'descend');
%     tiles = tiles(tilesperm, :);

% Kudos to Martin F. for quadrupling tiles
tiles = [tiles; tiles(:,[2:4,1]); tiles(:,[3:4,1:2]); tiles(:,[4,1:3])];

tilestaken = false(4*ntiles, 1);

% place initial tile

boarde(nrows,1) = 4;

f = nextfield();

while ~isempty(f) && ~all(tilestaken);
nextrow = f(1);
nextcol = f(2);

tix = findbesttilefor(nextrow, nextcol,tiles,board,nrows,ncols,tilestaken,false);

placetile(tix, nextrow, nextcol);

f = nextfield();
end

function ret = nextfield()
[v, ix] = max(boarde(:));
if v; ret = [mod(ix-1,nrows)+1, ceil(ix/nrows)];
%             fprintf(' %d %d\n', ret(1), ret(2));
else  ret = [];
end
%         assert(isempty(ret) || (ret(1) > 0 && ret(1) <= nrows && ret(2) > 0 && ret(2) <= ncols));
end

function placetile(tileix, row, col)
board(row, col) = tileix;
boarde(row, col) = 0;

method4a(tileix, row, col);method4b(  row, col);method4c(  row, col);

poptile(tileix);

function method4a(tileix, row, col)
% pricy stones + diagonal bonus
if row >   1   && ~board(row-1,col  ); boarde(row-1, col  ) = boarde(row-1, col  ) + tiles(tileix, 1); end;
if row < nrows && ~board(row+1,col  ); boarde(row+1, col  ) = boarde(row+1, col  ) + tiles(tileix, 3); end;
if col >   1   && ~board(row  ,col-1); boarde(row  , col-1) = boarde(row  , col-1) + tiles(tileix, 4); end;
if col < ncols && ~board(row  ,col+1); boarde(row  , col+1) = boarde(row  , col+1) + tiles(tileix, 2); end;
end
function method4b(  row, col)
if row >   1   && col >   1   && ~board(row-1,col-1); boarde(row-1, col-1) = boarde(row-1, col-1) + 0.1; end;
if row >   1   && col < ncols && ~board(row-1,col+1); boarde(row-1, col+1) = boarde(row-1, col+1) + 0.1; end;
end
function method4c(  row, col)
if row < nrows && col >   1   && ~board(row+1,col-1); boarde(row+1, col-1) = boarde(row+1, col-1) + 0.1; end;
if row < nrows && col < ncols && ~board(row+1,col+1); boarde(row+1, col+1) = boarde(row+1, col+1) + 0.1; end;
end

function poptile(tileix )
ix = mod(tileix-1, ntiles)+1;
o = ceil(tileix/ntiles);
orientation(ix) = o;
tilestaken(ix+ntiles*(0:3), :) = true;
end
end

boardzeros = board == 0;
board = mod(board-1, ntiles)+1;
board(boardzeros) = 0;

end

function m = mynansum(m, d)
m(isnan(m)) = 0;
m = sum(m, d);
end

function [board orientation] = werner(tiles, boardSize,nrows,ncols)

board = zeros(boardSize);
orientation = ones(size(tiles,1), 1);

ntiles = size(tiles, 1);
tiles = [tiles; tiles(:,[2:4,1]); tiles(:,[3:4,1:2]); tiles(:,[4,1:3])];
tilestaken = false(4*ntiles, 1);

boarde = board;
boarde(1,1) = 4;

f = nextfield();

while ~isempty(f) && ~all(tilestaken);
nextrow = f(1);
nextcol = f(2);
tix = findbesttilefor(nextrow, nextcol,tiles,board,nrows,ncols,tilestaken,true);
placetile(tix, nextrow, nextcol);
f = nextfield();
end

function ret = nextfield()
[v, ix] = max(boarde(:));
if v;ret = ixtorc(ix);else ret = [];end
end

function ret = ixtorc(ix)
ret = [mod(ix-1,nrows)+1, ceil(ix/nrows)];
end

function placetile(tileix, row, col)
board(row, col) = tileix;
boarde(row, col) = 0;

placetile1(tileix, row, col );
placetile2(  row, col );
placetile3(   row, col );

poptile(tileix );
function placetile1(tileix, row, col )
if row >   1   && ~board(row-1,col  ); boarde(row-1, col  ) = boarde(row-1, col  ) + tiles(tileix, 1); end;
if row < nrows && ~board(row+1,col  ); boarde(row+1, col  ) = boarde(row+1, col  ) + tiles(tileix, 3); end;
if col >   1   && ~board(row  ,col-1); boarde(row  , col-1) = boarde(row  , col-1) + tiles(tileix, 4); end;
if col < ncols && ~board(row  ,col+1); boarde(row  , col+1) = boarde(row  , col+1) + tiles(tileix, 2); end;
end

function placetile2(   row, col)
if row >   1   && col >   1   && ~board(row-1,col-1); boarde(row-1, col-1) = boarde(row-1, col-1) + 0.1; end;
if row >   1   && col < ncols && ~board(row-1,col+1); boarde(row-1, col+1) = boarde(row-1, col+1) + 0.1; end;
end

function placetile3(   row, col)
if row < nrows && col >   1   && ~board(row+1,col-1); boarde(row+1, col-1) = boarde(row+1, col-1) + 0.1; end;
if row < nrows && col < ncols && ~board(row+1,col+1); boarde(row+1, col+1) = boarde(row+1, col+1) + 0.1; end;
end

function poptile(tileix  )
ix = mod(tileix-1, ntiles)+1;
orientation(ix) =ceil(tileix/ntiles);
tilestaken(ix+ntiles*(0:3), :) = true;
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)
if r > 1;
if board(r-1,c) > 0; nv = tiles(board(r-1,c), 3);
else                 nv = nan;
end
else                     nv = 0;
end
if r < nrows;
if board(r+1,c) > 0; sv = tiles(board(r+1,c), 1);
else                 sv = nan;
end
else                     sv = 0;
end
if c > 1;
if board(r,c-1) > 0; wv = tiles(board(r,c-1), 2);
else                 wv = nan;
end
else                     wv = 0;
end
if c < ncols;
if board(r,c+1) > 0; ev = tiles(board(r,c+1), 4);
else                 ev = nan;
end
else                     ev = 0;
end

v = [nv, ev, sv, wv];
if flag
tilecosts(tilestaken) = inf;
[~, ret] = min(tilecosts-sum(tiles,2).*1e-6);
else
tilecosts = bsxfun(@minus, tiles, v);
tilecosts = abs(tilecosts);
tilecosts = mynansum(tilecosts, 2);
tilecosts(tilestaken) = inf;

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

end```