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

Try # 2: Spiral In with Rotation

by Mariastro

Status: Passed
Results: 7654234 (cyc: 18, node: 1306)
CPU Time: 3.089
Score: 766248.0
Submitted at: 2012-04-11 14:37:14 UTC
Scored at: 2012-04-11 14:56:15 UTC

Current Rank: 1329th (Highest: 1201st )

Comments
Please login or create a profile.
Code
function [board, orientation] = solver(tiles, boardSize)

ntiles = size(tiles,1);
board = zeros(boardSize);
orientation = ones(ntiles, 1);
iNRow = boardSize(1);
iNCol = boardSize(2);

% Keep a copy of the original board, orientation and tiles (for restoration at the final step)
boardOrig = board;
orientationOrig = orientation;
tilesOrig = tiles;

% Possible permutations of the tile indices
mPerm = [1 2 3 4; 2 3 4 1; 3 4 1 2; 4 1 2 3];

%% Reduce the board size to the number of tiles when ntiles < numel(board) (=iNRow*iNCol)
% Only the number of rows is reduced, the number of columns is kept
%---- OPT: Can reduce the size of the board in square fashion to avoid less zeros at the borders!
aBoardSizeNew = boardSize;
if (ntiles < iNRow*iNCol)
    [iDimMin, iDimMinIndex] = min(boardSize);
    [iDimMax, iDimMaxIndex] = max(boardSize);
    % Shorten the size on the longest side and propose a square board. Then check if feasible.
    iDimMaxNew = ceil(sqrt(ntiles));
    iDimMinNew = min(ceil(sqrt(ntiles)),iDimMin);   % Upper bound the minimum length to the actual value
    if (ntiles/iDimMaxNew) < iDimMinNew
        iDimMinNew = min(ceil(ntiles/iDimMaxNew), iDimMin);
    else
        % This means that the maximum side is much larger than the minimum size so we can try reducing the
        % board through the minimum side first
        iDimMinNew = min(ceil(sqrt(ntiles)),iDimMin);   % Upper bound the minimum length to the actual value
        if (ntiles/iDimMinNew) < iDimMax
            iDimMaxNew = min(ceil(ntiles/iDimMinNew), iDimMax);
        end
    end
% OLD
%     if (ntiles/iDimMaxNew) < iDimMin
%         iDimMinNew = ceil(ntiles/iDimMaxNew);
%     end
% OLD
    aBoardSizeNew(iDimMinIndex) = iDimMinNew;
    aBoardSizeNew(iDimMaxIndex) = iDimMaxNew;
end
board = zeros(aBoardSizeNew);
fprintf('ntiles = %d, Board size(new) = [%d %d]\n', ntiles, size(board,1), size(board,2));

%% Get tiles statistics and add the mean to the tiles matrix (mTilesExt) for sorting 
sStats = fxComputeStats(tiles);
aMeanTiles = sStats.aMeanTiles;
%mMinTiles = sStats.mMinTiles;
mTilesMean = [tiles aMeanTiles];
% Sort by ascending mean
[~, aTilesMeanOrder] = sortrows(mTilesMean(:, [5]));
mTilesMeanSorted = mTilesMean(aTilesMeanOrder,:);
% Keep the original tiles and create the new tiles list based on the order given above
tiles = mTilesMeanSorted(:,1:4);
tilesOrder = aTilesMeanOrder;

%% Create a frame with zeros around the board
[boardExt, orientationExt, tilesExt] = fxAddFrameToBoard(board, orientation, tiles, 0);
% Number of tiles placed at the border of the extended board
iNTilesZero = size(tilesExt,1) - size(tiles,1);
indicesInBoard = 1:iNTilesZero;

%% Place the tiles in spiral fashion starting from the boundary after leaving out the tiles with smallest mean
% But first leave out the FIRST iNLeaveOut tiles that would not fit in the board if
% the number of tiles is larger than the number of cells in the board.
% Number of tiles to leave out.
iNLeaveOut = max(0,ntiles-numel(board));
% Indices in tilesExt of the tiles to place
iFirstTile = iNTilesZero + iNLeaveOut + 1;
iLastTile = ntiles + iNTilesZero;
indicesToPlace = iFirstTile:iLastTile;
% Start at the upper left corner of the original board
startI = 2;
startJ = 2;
while ~isempty(indicesToPlace)
    fprintf('startI = %d, startJ = %d\n', startI, startJ);
    [boardExt, orientationExt, tilesLeft, indicesPlaced] = fxPlaceTilesSpiral(tilesExt,indicesToPlace,indicesInBoard,boardExt,orientationExt,startI,startJ);
    indicesInBoard = [indicesInBoard indicesPlaced];
    if size(tilesLeft,1) > 0
        startI = startI + 1;
        startJ = startJ + 1;
        indicesToPlace = indicesInBoard(end)+1:iLastTile;
%        disp(indicesToPlace);
%        pause;
    else
        indicesToPlace = [];
    end
end

% Go back to the original board size and tile indices
boardFinal = max(0, boardExt(2:end-1, 2:end-1) - iNTilesZero);  % The number of added zero tiles is substracted
orientationFinal = orientationExt(iNTilesZero+1:end);           % The zero tiles are removed from the orientation array
% Restore tile indices in the board and in the tiles matrix
board = boardOrig;              % Initialize the final board matrix
boardFinalOrig = boardOrig;     % Make a copy of the above to make the computation clearer
boardFinalOrig(1:size(boardFinal,1),1:size(boardFinal,2)) = boardFinal;
% Replace the non-zero values in the board with the original indices of the tiles. Leave the zero values
% unchanged (of course, since they are just zeros => empty cells in the board)
mFilledCells = find(boardFinalOrig);
board(mFilledCells) = tilesOrder(boardFinalOrig(mFilledCells));
orientation = orientationFinal(tilesOrder) ;
tiles = tilesOrig;
fprintf('BoardSize = [%d %d], orientation = [%d %d], tiles = [%d %d]\n', size(board,1), size(board,2), size(orientation,1), size(orientation,2), size(tiles,1), size(tiles,2));

end

function sStats = fxComputeStats(tiles)
    dMeanAll = mean(tiles(:));
    dStdAll = std(tiles(:));
    aMeanTiles = mean(tiles,2);
    aStdTiles = std(tiles')';
    [aMinTiles, aMinTilesIndex] = min(tiles,[],2);
    [aMaxTiles, aMaxTilesIndex] = max(tiles,[],2);

    sStats = struct('dMeanAll', dMeanAll, ...
                    'dStdAll', dStdAll, ...
                    'aMeanTiles', aMeanTiles, ...
                    'aStdTiles', aStdTiles, ...
                    'mMinTiles', [aMinTiles, aMinTilesIndex], ...
                    'mMaxTiles', [aMaxTiles, aMaxTilesIndex]);
end

function [board, orientation, tilesLeft, indicesPlaced] = fxPlaceTilesSpiral(tiles,indicesToPlace,indicesInBoard,board,orientation,startI,startJ)

% Original number of (non-zero) tiles to place
ntiles = length(indicesToPlace);
% Board size
iNRow = size(board,1);
iNCol = size(board,2);

% All possible permutations of the tile indices
mPerm = [1 2 3 4; 2 3 4 1; 3 4 1 2; 4 1 2 3];

% Place the zero tiles on the border of the board
iTileCount = 1;
i = startI;
j = startJ;
bPlace = true;
% Fill in the first row first, then go south till the last row, then west to the first column and then
% back north.
direction = '1-East';
while bPlace
%     fprintf('\ti=%d, j=%d, iTileCount=%d\n', i, j, iTileCount);
    if board(i,j) == 0
        board(i,j) = indicesToPlace(iTileCount);
        if startI == 1 && startJ == 1
            % If we are filling the first outer circle, do not orient, because this is the frame
            orientation(indicesToPlace(iTileCount)) = 1;
        else
            %% Set the orientation of each tile
            % Compute the error with adjacent tiles
            mTilePerm = [tiles(board(i,j),mPerm(1,:)); ...
                         tiles(board(i,j),mPerm(2,:)); ...
                         tiles(board(i,j),mPerm(3,:)); ...
                         tiles(board(i,j),mPerm(4,:));];
            %-- Array with adjacent values at north, east, south, west (note that we take care of the
            %-- orientation/rotation of the adjacent tiles)
            %-- Note: Rotation = Orientation - 1 (thus if Orientation = 1 => Rotation = 0 => No rotation)
            % Initialize the orientation and adjacent values to 1 and 0 respectively, in case there is
            % still no tile placed in the adjacent board cells.
            iRotationNorth = 1;
            iRotationEast = 1;
            iRotationSouth = 1;
            iRotationWest = 1;
            aValuesAdj = zeros(1,4);
            if board(i-1,j) ~= 0, iRotationNorth = mod(orientation(board(i-1,j))-1,4); aValuesAdj(1) = tiles(board(i-1,j), mod(iRotationNorth+3-1,4) + 1); end
            if board(i,j+1) ~= 0, iRotationEast  = mod(orientation(board(i,j+1))-1,4); aValuesAdj(2) = tiles(board(i,j+1), mod(iRotationEast +4-1,4) + 1); end
            if board(i+1,j) ~= 0, iRotationSouth = mod(orientation(board(i+1,j))-1,4); aValuesAdj(3) = tiles(board(i+1,j), mod(iRotationSouth+1-1,4) + 1); end
            if board(i,j-1) ~= 0, iRotationWest  = mod(orientation(board(i,j-1))-1,4); aValuesAdj(4) = tiles(board(i,j-1), mod(iRotationWest +2-1,4) + 1); end
            mError = mTilePerm - repmat(aValuesAdj,[4 1]);
            dError = sum(abs(mError),2);
            [~, iOrientation] = min(dError);
            orientation(indicesToPlace(iTileCount)) = iOrientation;
% OLD
%           orientation = mMinTiles(indicesToPlace(iTileCount),2) - (border-1);
%           mPermIndex = mod(orientation-1,4) + 1;
%           mPerm(mPermIndex,:)
%           tiles(indicesToPlace(iTileCount),mPerm(mPermIndex,:))
% OLD
        end
        % Increase one to the tile count
        iTileCount = iTileCount + 1;
    end

    % Find the next cell in the spiral where the tile should be placed
    switch direction
        case '1-East',
            j = j + 1;
            if j > iNCol - startJ + 1
                j = iNCol - startJ + 1;
                i = min(i+1,iNRow-startI+1);
                direction = '2-South';
            end
        case '2-South',
            i = i + 1;
            if i > iNRow - startI + 1
                i = iNRow - startI + 1;
                j = max(startJ,j-1);
                direction = '3-West';
            end
        case '3-West',
            j = j - 1;
            if j < startJ
                j = startJ;
                i = max(startI,i-1);
                direction = '4-North';
            end
        case '4-North',
            i = i - 1;
            if i < startI
                i = startI;
                bPlace = false;
%                 fprintf('bplace, i = %d, j = %d, iTileCount = %d\n', i, j, iTileCount);
            end
        otherwise
            disp('Invalid Direction');
    end
    if iTileCount > ntiles
        bPlace = false;
    end
end
% Set the count to the number of tiles actually placed which is iTileCount-1
iTileCount = iTileCount - 1;
%fprintf('\tiTileCount = %d\n', iTileCount);

% % Number of tiles to leave out
% iNLeaveOut = max(0,ntiles-numel(board));
% % Set of tiles to place
% iFirstTile = iNTilesZero + iNLeaveOut + 1;
% iLastTile = ntiles + iNTilesZero;
% mTilesToPlace = tilesExt(iFirstTile:iLastTile,:);

% Store the tiles that are left to be placed
indicesPlaced = indicesToPlace(1:iTileCount);
aIndicesLeft = true([1 size(tiles,1)]);
aIndicesLeft([indicesInBoard indicesPlaced]) = false;
tilesLeft = tiles(aIndicesLeft,:);
%fprintf('\ttilesLeft = %d\n', size(tilesLeft,1));

return

end

function [boardExt, orientationExt, tilesExt] = fxAddFrameToBoard(board,orientation,tiles,value)

% Add a frame of zeros to the board for generalizing the placement of tiles
boardExt = zeros(size(board)+2);
iNRow = size(board,1);
iNCol = size(board,2);

% Extend the tiles matrix with as many rows as the number of cells in the frame of the board with 'value'
iNTilesFrame = (iNRow+iNCol+2)*2;
tilesExt = [repmat(value*ones([1 4]),[iNTilesFrame 1]); tiles];

% Extend the orientation with the added tiles
orientationExt = [ones(iNTilesFrame,1); orientation];

% Fill in the frame with the first tiles in tilesExt having all values equal to 'value'.
[boardExt, orientationExt, ~] = fxPlaceTilesSpiral(tilesExt,1:iNTilesFrame,[],boardExt,orientationExt,1,1);

end