... missed the worm

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

orientation = ones(size(tiles,1), 1);
ntiles      = size(tiles,1);
nElem       = boardSize(1)*boardSize(2);
board       = zeros(boardSize);
cs          = [1 2 3 4; 2 3 4 1; 3 4 1 2; 4 1 2 3];
played      = discardUnplayed(ntiles-nElem, tiles);

if (ntiles-nElem<0)
    height=min([ceil(sqrt(ntiles)) boardSize(1)]);
    if (ntiles/boardSize(2))>height
        height=ceil(ntiles/boardSize(2));
    end
else
    ntiles=nElem;
    height=boardSize(1);
end

for k=1:ntiles
    [y,x]=ind2sub([height,boardSize(2)],k);
    board(y,x)=-1;
end
last = [y,x];

for i=8:-1:1
    b(:,:,i) = board;
    o(:,i) = orientation;
end

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

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

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

[b(:,:,9 ), o(:,9 )] = picky(tiles, boardSize);
[b(:,:,10), o(:,10)] = calibrating_pure(tiles, boardSize);

overall  = zeros(10,1);
for i=1:10
    overall(i) = overallScore(b(:,:,i),o(:,i),tiles, cs);
end
[~,mo] = min(overall);
board = b(:,:,mo);
orientation = o(:,mo);

%disp(['  Mejor SOLUCION SOLVER_' num2str(mo) '. diff9 = ' num2str(num2str(overall(9) - overall(mo),'%d '))])

end

function [score] = overallScore(board, orientation, tiles, cs)
    
    boardSize=size(board);
    tile = zeros(boardSize(1)*4,boardSize(2));
    tmp = tiles.';
    for y = 1:boardSize(1)
        for x = 1:boardSize(2)
            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 [brd, ort, lst] = place(rowRange, colRange, board, tiles, list, orientation, ntiles, boardSize, cs)
    k = 1;
    brd = board;
    ort = orientation;
    lst = list;
    L   = size(lst,1);
    for y=rowRange
        for x=colRange
            if (brd(y,x)==-1)
                [n,e,s,w] = findBoundaries(brd, tiles, ort, y, x, boardSize, cs);
                [t, o] = findBestTile(lst, L, n, e, s, w, cs);
                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 tiles = discardUnplayed(numUnplayed, tiles)

if numUnplayed>0
    sums = sum(tiles,2);
    for i = 1:numUnplayed
        [~, m]=min(sums);
        tiles(m,:)=inf(1,4);
        sums(m)=inf;
    end
end
end

function [tile, orientation] = findBestTile(list, L, north, east, south, west, cs)

score = int32(zeros(L,4));

grid  = ones(L,1)*[north east south west];
for i=1:4
    score(:,i) = sum(int32(abs(list(:,cs(:,i))-grid)),2);    
end
[ms, t          ] = min(score);
[~ , orientation] = min(ms);
tile              = t(orientation);
end

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

function value = boundary(board,tiles,orientation,row,col,id,boardSize,cs)
   
    if row<1 || col<1 || row>boardSize(1) || col>boardSize(2)
        value = 0;
    else
        if board(row,col) == -1
            value = nan;
        elseif board(row,col) == 0
            value = 0;            
        else
            tile  = tiles(board(row,col),cs(orientation(board(row,col)),:));
            value = tile(id);
        end
    end
end

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

nt = size(tiles,1);
board = zeros(boardSize);
nrow = boardSize(1);
ncol = boardSize(2);
nb = nrow*ncol;
orientation = ones(nt,1);

unused = true(1,nt);
rt{4} = circshift(tiles,[0 1]);
rt{3} = circshift(tiles,[0 2]);
rt{2} = circshift(tiles,[0 3]);
rt{1} = tiles;
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);

% adjust goals

% 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{j}(unused,:),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{ori}(pick,2);
    end;
    if (mod(i,nrow) ~= 0)
        goalN(i+1) = rt{ori}(pick,3);
    end;
end;
end