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

DudaElf

by Chris Garry

Status: Passed
Results: 125830 (cyc: 5, node: 1620)
CPU Time: 74.499
Score: 12634.3
Submitted at: 2012-04-06 21:47:52 UTC
Scored at: 2012-04-06 21:50:42 UTC

Current Rank: 1038th (Highest: 45th )
Based on: FlipCat5 (diff)

Comments
Chris Garry
06 Apr 2012
run-time optimization
Please login or create a profile.
Code
function [board, orientation] = solver(tiles, boardSize)
orientation = ones(size(tiles,1), 1);
ntiles = size(tiles,1);
board = zeros(boardSize);

played = discardUnplayed(ntiles-numel(board), tiles);

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

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

    b(:,:,1) = board;
    o(:,1) = orientation;
    b(:,:,2) = board;
    o(:,2) = orientation;
    b(:,:,3) = board;
    o(:,3) = orientation;
    b(:,:,4) = board;
    o(:,4) = orientation;
    b(:,:,5) = board;
    o(:,5) = orientation;
    b(:,:,6) = board;
    o(:,6) = orientation;
    b(:,:,7) = board;
    o(:,7) = orientation;
    b(:,:,8) = board;
    o(:,8) = orientation;


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

list = played;

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


newList(:,:,2) = list;


for i=[0 4]
    [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);
    [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);
    [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);
    [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);
end


    overall(1) = overallScore(b(:,:,i),o(:,i),tiles);
    overall(2) = overallScore(b(:,:,i),o(:,i),tiles);
    overall(3) = overallScore(b(:,:,i),o(:,i),tiles);
    overall(4) = overallScore(b(:,:,i),o(:,i),tiles);
    overall(5) = overallScore(b(:,:,i),o(:,i),tiles);
    overall(6) = overallScore(b(:,:,i),o(:,i),tiles);
    overall(7) = overallScore(b(:,:,i),o(:,i),tiles);
    overall(8) = overallScore(b(:,:,i),o(:,i),tiles);


[~,mo] = min(overall);
board = b(:,:,mo);
orientation = o(:,mo);

end

function [score] = overallScore(board, orientation, tiles)
    cs = [1 2 3 4; 2 3 4 1; 3 4 1 2; 4 1 2 3];
    boardSize=size(board);
    tile = zeros(boardSize(1)*4,boardSize(2));
    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)),:))';
            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));
    score = internal + external;
end

function [brd, ort, lst] = place(rowRange, colRange, board, tiles, list, orientation, ntiles)
    k = 1;
    brd = board;
    ort = orientation;
    lst = list;
    for y=rowRange
        for x=colRange
            if (brd(y,x)==-1)
                [n,e,s,w] = findBoundaries(brd, tiles, ort, y, x);
                [t, o] = findBestTile(lst, n, e, s, w);
                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 played = discardUnplayed(numUnplayed, tiles)
played = tiles;
if numUnplayed>0
    sums = sum(tiles,2);
    [~,si] = sort(sums);
    played(si(1:numUnplayed),:) =  Inf(numUnplayed,4);
end
end

function [tile, orientation] = findBestTile(list, north, east, south, west)
    score = int32(zeros(size(list,1),4));
    cs = [1 2 3 4; 2 3 4 1; 3 4 1 2; 4 1 2 3];
    grid = ones(size(list,1),1)*[north east south west];
    
        temp = int32(abs(list(:,cs(:,1))-grid));
        score(:,1) = sum(temp,2);
        
        temp = int32(abs(list(:,cs(:,2))-grid));
        score(:,2) = sum(temp,2);
        
        temp = int32(abs(list(:,cs(:,3))-grid));
        score(:,3) = sum(temp,2);
        
        temp = int32(abs(list(:,cs(:,4))-grid));
        score(:,4) = sum(temp,2);
    
    
    [ms, t] = min(score);
    [~, orientation] = min(ms);
    tile = t(orientation);

end

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

function [value] = boundary(board,tiles,orientation,row,col,id)
    cs = [1 2 3 4; 2 3 4 1; 3 4 1 2; 4 1 2 3];
    try
        if (board(row,col)==0)
            value = 0;
        elseif (board(row,col)==-1)
            value = nan;
        else
            tile = tiles(board(row,col),cs(orientation(board(row,col)),:));
            value = tile(id);
        end
    catch
        value = 0;
    end
end