2012-04-11 12:00:00 UTC

# More Picky ?

Status: Passed
Results: 112494 (cyc: 10, node: 4407)
CPU Time: 61.41
Score: 11338.8
Submitted at: 2012-04-08 02:52:34 UTC
Scored at: 2012-04-08 02:54:33 UTC

Current Rank: 720th (Highest: 1st )
Based on: More ? (diff)
Basis for: Old ways (diff)
Basis for: Longer Run.. (diff)
Basis for: TweakyC (diff)

Code
```function [board, orientation] = solver(tiles, boardSize)
% Clone of Nuwan 2012-04-08 00:31:26

board       = zeros(boardSize);

%board = zeros(boardSize);
%[nr nc]=size(board);
%numtiles=size(tiles,1);
%orientation = ones(size(tiles,1), 1);

%if ntiles==nElem % Do Perfect Unique Board Check
[board,orientation,solved]=board_perfect_snake(board,tiles);
if solved,return;end
%end
% End of Main routine Richard add

ntiles      = size(tiles,1);
nrow = boardSize(1);
ncol = boardSize(2);
nElem       = nrow*ncol;

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);
[sorted,si] = sort(sums);
equals = find(sorted(numUnplayed+1)==sorted);
if(length(find(sorted(numUnplayed+1)==sorted(numUnplayed+1:end)))~=length(equals))
temp_si = si(equals);
[~,mi] = sort(min(tiles(temp_si,:),[],2));
for i=1:length(equals)
si(equals(end+1-i))= temp_si(mi(i));
end
end
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,board,board,board,board,board);
o = ones(size(tiles,1), 18);
S=0;
[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(:,:,2),o(:,2),list] = place(height:-1:1,last(2),b(:,:,2),played,played,o(:,2),ntiles,  cs,nrow,ncol);
[b(:,:,2),o(:,2),list] = place(height,1:last(2),b(:,:,2),played,list,o(:,2),ntiles,  cs,nrow,ncol);
[b(:,:,2),o(:,2),list] = place(1:height-1,1,b(:,:,2),played,list,o(:,2),ntiles,  cs,nrow,ncol);
[b(:,:,2),o(:,2),list] = place(1,2:last(2),b(:,:,2),played,list,o(:,2),ntiles,  cs,nrow,ncol);
newList(:,:,2) = list;
for i=[2 6]
c = floor(i/6) + 1;
[b(:,:,i+1),o(:,i+1),~] = place(height-1:-1:2,ncol-1:-1:2,b(:,:,c),played,newList(:,:,c),o(:,c),ntiles , cs,nrow,ncol);
[b(:,:,i+2),o(:,i+2),~] = place(2:height-1,2:ncol-1,b(:,:,c),played,newList(:,:,c),o(:,c),ntiles,  cs,nrow,ncol);
[b(:,:,i+3),o(:,i+3),~] = place(height-1:-1:2,2:ncol-1,b(:,:,c),played,newList(:,:,c),o(:,c),ntiles,  cs,nrow,ncol);
[b(:,:,i+4),o(:,i+4),~] = place(2:height-1,ncol-1:-1:2,b(:,:,c),played,newList(:,:,c),o(:,c),ntiles,  cs,nrow,ncol);
end
[b(:,:,S+1 ), o(:,S+1 )] = picky(tiles, boardSize,nrow,ncol,cs);
[b(:,:,S+2 ), o(:,S+2 )] = calibrating_pure(tiles, boardSize,nrow,ncol);
S = 11;
[b(:,:,S),o(:,S),~] = placeRand(1:height,1:ncol,b(:,:,S),played,played,o(:,S),ntiles,cs,nrow,ncol);

if nElem < 1000
for ii = 1:4
[b(:,:,S+ii),o(:,S+ii)] = MichaelC(height,last(2), tiles, played, o(:,S+ii), ntiles, cs,nrow,ncol);
end
S = S + 4;

if nElem < 200
[b(:,:,S+1), o(:,S+1)] = 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);

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);
dist_center = dist_center + rand(size(dist_center))*0.01;
[~, 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, 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);
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 [brd, ort, lst] = placeRand(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);
[ms, o] = find(score==min(score(:)));
which = ceil(length(ms)/2);%round(rand*(length(ms)-1)+1);
t = ms(which);

ort(t) = o(which);
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

function [board,orientation,solved]=board_perfect_snake(board,tiles)
% check for perfect unique board
solved=false;
orientation = ones(size(tiles,1), 1);

[nr nc]=size(board);
nrnc=nr*nc;
%numtiles=size(tiles,1);

ptiles=prod(tiles,2); % search for zeros to count edge/corner pieces

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

otiles=tiles;
%gtiles=ones(numtiles,1); % Unused tiles

[board,orientation,otiles,valid]= ...
find_corner(board,otiles,tiles,orientation);
if valid==false,return;end

for i=1:nr

if i>1
tile=board(i-1,1);

[board,orientation,otiles,valid]= ...
find_tiles(board,orientation,otiles,tiles,i,1,nrnc,tile,3);
%  [board,orientation,otiles,valid]= ...
%      first_column(board,orientation,otiles,tiles,i,j);
if valid==false,return;end

end % i>1

for j=2:nc
tile=board(i,j-1);

[board,orientation,otiles,valid]= ...
find_tiles(board,orientation,otiles,tiles,i,j,nrnc,tile,2);
if valid==false,return;end

end % j 2:nc

end % i 1:nr

solved=true;

%brd_score=board_scr(board,orientation,tiles);
end

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

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

% Find a corner  %
tv=find(adj==0,1); % corner found No rotation
if isempty(tv)
found=false;
for i=2:4
if ~isempty(tv)
orientation(tv)=i;
otiles(tv,:)=rot_tile(orientation(tv),tiles(tv,:));
found=true;
break; % corner found and rotated to position
end
end
if ~found,return;end % No Zero corners
end

board(1,1)=tv;

valid=true;
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,otiles,tiles,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

goal=otiles(tile,ul);
tvec=find(otiles==goal);
if size(tvec,1)~=2,return;end % Non Unique solutions
% Have two solution - one already used
tnum=mod(tvec-1,nrnc)+1;
trot=floor((tvec-1)/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
if rot==4
rot=1;
else
rot=rot+1;
end
end
board(i,j)=tv;
otiles(tv,:)=rot_tile(rot,tiles(tv,:));
orientation(tv)=rot;

valid=true;
end % fill rows```