| Code: | function W = solver(board)
padSize = 3;
% pad board
[M,N] = size(board);
board_padded = zeros(M+2*padSize, N+2*padSize);
board_padded(padSize+1:M+padSize, padSize+1:N+padSize) = board;
board = board_padded;
M = M + 2*padSize;
N = N + 2*padSize;
% initialize matrix with pins and connections
boardMod = board;
% get index of pin positions
pinIndex = find(board);
pinValues = board(pinIndex); %#ok
% get number of pins with a given value
pinValuesUnique = unique(pinValues);
nrOfSamePins = histc(pinValues, pinValuesUnique);
nrOfGroups = length(pinValuesUnique);
% decide with which pin value to start
pinGroupValues = pinValuesUnique .* nrOfSamePins;
[ignore, sortIndex] = sort(pinGroupValues, 1, 'descend'); %#ok
% get move codebook
[moveCodebook, col] = getmovecodebook__(M);
% loop over pin values
connMatrix = zeros(0,2);
for groupNr = 1:nrOfGroups
groupPinValue = pinValuesUnique(sortIndex(groupNr));
groupPinsIndex = pinIndex(pinValues == groupPinValue);
groupSize = length(groupPinsIndex);
groupConnect = zeros(groupSize);
[groupPinRows, groupPinCols] = ind2sub__(M, groupPinsIndex);
% loop over current group (all pins of current value)
for pin1Nr = 1:groupSize-1
pin1Index = groupPinsIndex(pin1Nr);
% get vector of move ends
moveEnds = pin1Index + moveCodebook(:, col.move);
% find order for working down pins by distance relation
distanceVector = ...
abs(groupPinRows(pin1Nr+1:end) - groupPinRows(pin1Nr)) + ...
abs(groupPinCols(pin1Nr+1:end) - groupPinCols(pin1Nr));
% loop over other pins
[ignore, sortIndex2] = sort(distanceVector);
for pin2Nr = pin1Nr + sortIndex2' % pin1Nr+1:groupSize
pin2Index = groupPinsIndex(pin2Nr);
if groupConnect(pin1Nr, pin2Nr)
% pins are already connected indirectly
continue
end
moveIndex = (pin2Index == moveEnds);
% loop over possible moves
for moveNr = find(moveIndex')
% check if required fields are free
nrOfFree = moveCodebook(moveNr, col.free);
if nrOfFree > 0
freePinIndex = pin1Index + moveCodebook(moveNr, col.ind:(col.ind+nrOfFree-1));
boardModTmp = boardMod(freePinIndex);
moveValid = ~any(boardModTmp ~= 0 & boardModTmp ~= -groupPinValue);
else
moveValid = 1;
end
if moveValid
% get current moves
currConns = pin1Index + getconnections__(moveCodebook(moveNr,:), col);
% check if any moves goes outside the original board
currMoves = convertConns__(currConns, M);
if any(currMoves(:, 1) <= padSize) || ...
any(currMoves(:, 1) >= M - padSize + 1) || ...
any(currMoves(:, 2) <= padSize) || ...
any(currMoves(:, 2) >= N - padSize + 1)
moveValid = 0;
end
end
if moveValid
% save moves
connMatrix = [connMatrix; currConns]; %#ok
% mark points as occupied
boardMod(currConns(2:end,1)) = -groupPinValue;
% mark pins as connected
groupConnect(pin1Nr, pin2Nr) = 1;
groupConnect(pin2Nr, pin1Nr) = 1;
% update connection matrix
groupConnect(:,pin2Nr) = groupConnect(:,pin2Nr) | groupConnect(:,pin1Nr);
groupConnect(:,pin1Nr) = groupConnect(:,pin1Nr) | groupConnect(:,pin2Nr);
groupConnect(pin2Nr,:) = groupConnect(pin2Nr,:) | groupConnect(pin1Nr,:);
groupConnect(pin1Nr,:) = groupConnect(pin1Nr,:) | groupConnect(pin2Nr,:);
% leave loop over possible moves
break
end
end
end
end
end
% remove duplicates
connMatrix = unique(connMatrix, 'rows');
% convert linear indices to row-column indices
W = convertConns__(connMatrix, M);
% consider padding
W = W - padSize;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [moveCodebook, col] = getmovecodebook__(M)
col.move = 1;
col.fwd = 2;
col.free = 3;
col.ind = 4;
moveCodebook = [
% mv fwd free indices...................
1 1 0 0 0 0 0 0 0; % one down
M 1 0 0 0 0 0 0 0; % one right
2 1 1 1 0 0 0 0 0; % two down
2*M 1 1 M 0 0 0 0 0; % two right
M-1 1 1 -1 0 0 0 0 0; % one up, one right
M-1 1 1 M 0 0 0 0 0; % one right, one up
M+1 1 1 1 0 0 0 0 0; % one down, one right
M+1 1 1 M 0 0 0 0 0; % one right, one down
3 1 2 1 2 0 0 0 0; % three down
3*M 1 2 M 2*M 0 0 0 0; % three right
2*M+1 1 2 M 2*M 0 0 0 0; % two right, one down (1)
2*M+1 1 2 M M+1 0 0 0 0; % two right, one down (2)
2*M+1 1 2 1 M+1 0 0 0 0; % two right, one down (3)
M+2 1 2 1 2 0 0 0 0; % one right, two down (1)
M+2 1 2 1 M+1 0 0 0 0; % one right, two down (2)
M+2 1 2 M M+1 0 0 0 0; % one right, two down (3)
4 1 3 1 2 3 0 0 0; % four down
4*M 1 3 M 2*M 3*M 0 0 0; % four right
2*M 1 3 -1 M-1 2*M-1 0 0 0; % two right with a loop (1)
2*M 1 3 1 M+1 2*M+1 0 0 0; % two right with a loop (2)
2 1 3 M M+1 M+2 0 0 0; % two down with a loop (1)
2 1 3 -M -M+1 -M+2 0 0 0; % two down with a loop (2)
2*M-2 1 3 M 2*M 2*M-1 0 0 0; % two right, two up (1)
2*M-2 1 3 M M-1 2*M-1 0 0 0; % two right, two up (2)
2*M-2 1 3 M M-1 M-2 0 0 0; % two right, two up (3)
2*M-2 1 3 -1 M-1 2*M-1 0 0 0; % two right, two up (4)
2*M-2 1 3 -1 -2 M-2 0 0 0; % two right, two up (5)
2*M+2 1 3 M 2*M 2*M+1 0 0 0; % two right, two down (1)
2*M+2 1 3 M M+1 2*M+1 0 0 0; % two right, two down (2)
2*M+2 1 3 M M+1 M+2 0 0 0; % two right, two down (3)
2*M+2 1 3 1 M+1 2*M+1 0 0 0; % two right, two down (4)
2*M+2 1 3 1 2 M+2 0 0 0; % two right, two down (5)
5 1 4 1 2 3 4 0 0; % five down
5*M 1 4 M 2*M 3*M 4*M 0 0; % five right
];
moveCodebook = addmirrors__(moveCodebook, col);
% compute forward index
moveCodebook(:, col.fwd) = moveCodebook(:, col.move) > 0;
if 0
plotcodebook(moveCodebook, col, M);
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function moveCodebook = addmirrors__(moveCodebook, col)
[nOfRows, nOfCols] = size(moveCodebook);
colIndex = [col.move, col.ind:nOfCols];
rowIndex = nOfRows+1:2*nOfRows;
moveCodebook = [moveCodebook; moveCodebook];
moveCodebook(rowIndex, colIndex) = -moveCodebook(rowIndex, colIndex);
rowIndex = reshape([1:nOfRows; nOfRows+1:2*nOfRows], 2*nOfRows, 1);
moveCodebook = moveCodebook(rowIndex,:);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function plotcodebook(moveCodebook, col, M)
mm = round((M-1)/2);
A = zeros(M);
index = mm*(M+1);
A(index) = 1;
for row=1:size(moveCodebook, 1)
conn = index + getconnections__(moveCodebook(row, :), col);
moves = convertConns__(conn, M);
wiringGUI(A, moves);
pause(1);
%keyboard
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function conn = getconnections__(moveCode, col)
conn = zeros(moveCode(col.free)+1, 2);
% set start and end points
try
conn(:,1) = [0; moveCode(1, col.ind:(col.ind+moveCode(1, col.free)-1))'];
catch
keyboard
end
conn(:,2) = [conn(2:end,1); moveCode(1, col.move)];
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function W = convertConns__(connMatrix, M)
[r1, c1] = ind2sub__(M, connMatrix(:,1));
[r2, c2] = ind2sub__(M, connMatrix(:,2));
W = [r1 c1 r2 c2];
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [r, c] = ind2sub__(M, k)
r = (rem(k - 1, M)) + 1;
c = (k - r) ./ M + 1;
|