function [board, orientation] = solver(tiles, boardSize)
ntiles = size(tiles,1);
board = zeros(boardSize);
orientation = ones(ntiles, 1);
iNRow = boardSize(1);
iNCol = boardSize(2);
% Define the spiral fill type (+1 => OutsideIn or -1 => InsideOut)
% +1 and -1 define an ascending or descending sort of the tiles by their mean value
iSpiralSpin = -1;
% 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
[mTilesMeanSorted, aTilesMeanOrder] = sortrows(mTilesMean, [iSpiralSpin*5]);
% 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;
if iSpiralSpin == +1
% 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
else
[boardExt, orientationExt, ~, indicesPlaced] = fxPlaceTilesSpiralOut(tilesExt,indicesToPlace,indicesInBoard,boardExt,orientationExt);
indicesInBoard = [indicesInBoard indicesPlaced];
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
orientation = orientationOrig;
% orientationFinalOrig = orientationOrig;
% orientationFinalOrig = orientationFinal;
% orientation = tilesOrder(orientationFinalOrig);
for i = 1:length(orientation)
orientation(tilesOrder(i)) = orientationFinal(i);
end
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 [board, orientation, tilesLeft, indicesPlaced] = fxPlaceTilesSpiralOut(tiles,indicesToPlace,indicesInBoard,board,orientation)
% Original number of (non-zero) tiles to place
ntiles = length(indicesToPlace);
% Board size
boardSize = size(board);
iNRow = boardSize(1);
iNCol = boardSize(2);
[iDimMin, iDimMinIndex] = min(boardSize);
[iDimMax, iDimMaxIndex] = max(boardSize);
% All possible permutations of the tile indices
mPerm = [1 2 3 4; 2 3 4 1; 3 4 1 2; 4 1 2 3];
% Default maximum move in each direction with which the spiral starts
iMoveMaxI = 1;
iMoveMaxJ = 1;
% Define the start position which should be the 'middle' tile
startI = ceil(iDimMin/2);
startJ = startI;
if iDimMin ~= iDimMax
if iDimMinIndex == 1
% Update maximum move in the longer direction
iMoveMaxJ = iDimMax - iDimMin;
else
% Update maximum move in the longer direction
iMoveMaxI = iDimMax - iDimMin;
end
end
fprintf('iMoveMaxI = %d, iMoveMaxJ = %d\n', iMoveMaxI, iMoveMaxJ);
i = startI;
j = startJ;
% Count of the tiles placed
iTileCount = 1;
% Count of the moves in each direction
iMoveCountI = 0;
iMoveCountJ = 0;
% Flag that stops the loop
bPlace = true;
% Start eastward
direction = 1;
while bPlace
fprintf('\ti=%d, j=%d, iTileCount=%d\n', i, j, iTileCount);
if board(i,j) == 0
board(i,j) = indicesToPlace(iTileCount);
%% 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
% Only use the non-zero values of aValuesAdj because we are filling the spiral inside out, so
% unless we are at the last row or column to fill, the next round of the spiral will fill in the
% zero-valued adjacent cells.
aValuesUse = find(aValuesAdj);
mError = mTilePerm(:,aValuesUse) - repmat(aValuesAdj(aValuesUse),[4 1]);
dError = sum(abs(mError),2);
[~, iOrientation] = min(dError);
orientation(indicesToPlace(iTileCount)) = iOrientation;
% Increase the tile count
iTileCount = iTileCount + 1;
end
% Move to the next cell in the spiral where the next tile will be placed
switch direction
case 1,
j = j + 1;
iMoveCountJ = iMoveCountJ + 1;
case 2,
i = i + 1;
iMoveCountI = iMoveCountI + 1;
case 3,
j = j - 1;
iMoveCountJ = iMoveCountJ + 1;
case 4,
i = i - 1;
iMoveCountI = iMoveCountI + 1;
otherwise
disp('Invalid Direction');
end
if (direction == 2 || direction == 4) && iMoveCountI == iMoveMaxI
direction = mod(direction,4) + 1;
iMoveCountI = 0;
% The spiral increases in the vertical direction next time
iMoveMaxI = iMoveMaxI + 1;
fprintf('\tNext direction = %d\n', direction);
end
if (direction == 1 || direction == 3) && iMoveCountJ == iMoveMaxJ
direction = mod(direction,4) + 1;
iMoveCountJ = 0;
% The spiral increases in the horizontal direction next time
iMoveMaxJ = iMoveMaxJ + 1;
fprintf('\tNext direction = %d\n', direction);
end
if iTileCount > ntiles || i < 1 || i > iNRow || j < 1 || j > iNCol
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
|
