Doug’s MATLAB Video Tutorials

September 25th, 2008

Puzzler: Cleverness needed

I have been working on a side project and I found I needed the following algorithm:

MATLAB puzzler

Given a binary five by five matrix, I need to find the ‘1′ value that is in the position that has the lowest value in the spiral map above. I call that the target square. Once that target is found, then I need to return a delta x and delta y that will get me closer to that target. Delta x and delta y must be taken relative to the center square, and can only be from the set [-1, 0, 1].

As an example, given the matrix:

MATLAB puzzler

The ‘1′ in the (2,2) position in the matrix is the target because it maps to 9, and the other two ‘1′ values map to larger values, 11 and 18. From here, the delta x is -1 and delta y is 1.

If the target was 18, then the values would have been delta x of 0 and delta y of -1.

A final edge case, if the input matrix were all zeros, then delta x and delta y should be chosen randomly, but still pulled from the set [-1, 0, 1].

This is not a particularly difficult algorithm to program if you use 25 if, elseif statements. However, I am looking to be a bit more clever with this. Please post your solution in the comments, make it a function of this form:

[deltaX, deltaY] = puzzler(inMatrix)

As always with these puzzlers, be sure to use the proper tags in the comments.


<pre> <code>
[deltaX, deltaY] = puzzler(inMatrix)
%% All the code so someone can just copy and paste it from the comments.
</code> </pre>

By Doug Hull

11:12 UTC | Posted in Topic: Puzzler | Permalink |

You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.

21 Responses to “Puzzler: Cleverness needed”

Mark replied on September 25th, 2008 at 12:25 UTC :


function [dx dy] = puzzler(in)
if all(in(:) == 0)
    dx = ceil(3*rand) - 2 ;
    dy = ceil(3*rand) - 2 ;
    return
end

weight = [ 24 25 10 11 12 ; ...
           23  9  2  3 13 ; ...
           22  8  1  4 14 ; ...
           21  7  6  5 15 ; ...
           20 19 18 17 16 ] ; 

m = min(weight(logical(in))) ;
[dy dx] = ind2sub(size(weight), find(weight == m)) ;
dx = dx - 3 ;
dx = max(-1, min(dx, 1)) ;
dy = -(dy - 3) ;
dy = max(-1, min(dy, 1)) ;

Stefan replied on September 25th, 2008 at 13:00 UTC :

What’s the logic in having the jump between the 9-10 valued cells being diagonal? I’m more interested in generating the spiral square for an arbitrary matrix size.

david replied on September 25th, 2008 at 13:00 UTC :

ah, beaten to the finish line. had the same idea for the spiral, slightly different for dx dy.

 

function [deltaX, deltaY] = puzzler(inMatrix)

%spiral positions
spiralMatrix = [
	24 25 10 11 12;
	23  9  2  3 13;
	22  8  1  4 14;
	21  7  6  5 15;
	20 19 18 17 16];

%deltas.
deltaVals = [-1 -1 0 1 1];
deltaXMatrix = deltaVals(ones(1,5), :);
deltaYMatrix = flipud( deltaXMatrix');

%is nonempty
if nnz(inMatrix ~= 0)
	lowest = min( nonzeros(spiralMatrix .* inMatrix ));
	%pick element in the same position from delta matrices
	deltaX = sum((spiralMatrix(:) == lowest) .* deltaXMatrix(:));
	deltaY = sum((spiralMatrix(:) == lowest) .* deltaYMatrix(:));
else
	deltaX = floor(rand*3) - 1;
	deltaY = floor(rand*3) - 1;
end

ST replied on September 25th, 2008 at 14:57 UTC :

Hi,

This code is similar to what has been posted before. The computation of deltaX and deltaY is more rigorous than what is needed for this particular problem. But it is more easily ported to the case of any arbitrary sized square matrix.

Note: The spiral matrix I use is slightly different from what Doug specified. The difference comes when you go from 9 to 10. Not sure why you go from 9 to 10 the way you do. If needed, the spiral matrix “spMat” can be hard coded as given in the problem.

 
function [deltaX, deltaY] = puzzler(inMatrix)

[r,c] = find(inMatrix);
if(isempty(r))
    deltaX = ceil(3*rand) - 2;
    deltaY = ceil(3*rand) - 2;
    return;
end

% Generation of the spiral matrix (Note: Spiral matrix generated here is
% slightly different that what Doug wants. Different going from 9 to 10
spMat = flipud(spiral(5)');
pivot = [3 3]; % Pivot location or the reference location, in this case (3,3)
nVect = [repmat([-1; 0; 1],3,1) kron([-1; 0; 1],ones(3,1))];

[minVal, minIdx] = min(spMat(sub2ind(size(spMat),r,c)));
nHood = repmat(pivot,size(nVect,1),1) + nVect;
[minDist, minDistIdx] = min(sqrt(sum((repmat([r(minIdx) c(minIdx)],size(nHood,1),1) - nHood).^2,2)));

deltaX = nVect(minDistIdx(1),2);
deltaY = -nVect(minDistIdx(1),1);

dhull replied on September 25th, 2008 at 15:28 UTC :

Some great solutions here.

To answer ST and Stefan, the reason I am using a different spiral is that the target directly above is the most important in each of the rings.

I have been taking these solutions in and have made one that fits my style the best:


function [deltaX, deltaY] = puzzler(inMatrix)
%test with >>[x,y] = puzzler(round(rand(5)))
inMatrix %display input for testing
%
%spiral positions
spiralMatrix = [
	24 25 10 11 12;
	23  9  2  3 13;
	22  8  1  4 14;
	21  7  6  5 15;
	20 19 18 17 16];
%
if nnz(inMatrix >= 1) %at least one target
	lowest = min(nonzeros(spiralMatrix .* inMatrix));
    [r,c]  = find(spiralMatrix == lowest);
    %deltas.
    deltaValsR = [ 1  1 0 -1 -1];
    deltaValsC = [-1 -1 0  1  1];
	deltaX = deltaValsC(c);
	deltaY = deltaValsR(r);
else %no targets
	deltaX = floor(rand*3) - 1;
	deltaY = floor(rand*3) - 1;
end

ST replied on September 25th, 2008 at 15:48 UTC :

So here is the function that can work on any arbitrary-sized binary square input matrix. How one defines the “center square”, or what I call “pivot”, for a square matrix with even number of rows and columns is an issue. I just choose the center of the even matrix based on where the indexing starts in the spiral matrix that I use in my code, just to keep it simple.

So, the center square location for an NxN matrix is:

N Odd: (ceil(N/2) , ceil(N/2))
N Even: (floor(N/2)+1 , ceil(N/2))

Other center locations can be chosen too, if the code can start the spiral indexing from that location. Well, in that case maybe we can make the pivot location as one of the inputs, although it will have to be one of the central locations for the spiral indexing to continue without a break and cover all the elements.

 
function [deltaX, deltaY] = puzzler(inMatrix)

[r,c] = find(inMatrix);
if(isempty(r))
    deltaX = ceil(3*rand) - 2;
    deltaY = ceil(3*rand) - 2;
    return;
end

% Generation of the spiral matrix (Note: Spiral matrix generated here is
% slightly different that what Doug wants. Different going from 9 to 10
spMat = flipud(spiral(size(inMatrix,1))');
pivot = [floor(size(inMatrix,1)/2)+1 ceil(size(inMatrix,2)/2)];
nVect = [repmat([-1; 0; 1],3,1) kron([-1; 0; 1],ones(3,1))];

[minVal, minIdx] = min(spMat(sub2ind(size(spMat),r,c)));
nHood = repmat(pivot,size(nVect,1),1) + nVect;
idxRem = find(nHood(:,1)  size(inMatrix,1)...
    & nHood(:,2)  size(inMatrix,2));
nHood(idxRem) = []; nVect(idxRem) = [];
[minDist, minDistIdx] = min(sqrt(sum((repmat([r(minIdx) c(minIdx)],size(nHood,1),1) - nHood).^2,2)));

deltaX = nVect(minDistIdx(1),2);
deltaY = -nVect(minDistIdx(1),1);

Yi Cao replied on September 25th, 2008 at 16:05 UTC :

 
[deltaX, deltaY] = puzzler(inMatrix)
% Using lookup tables to solve the probelm
%spiral positions
spiralMatrix = [
	24 25 10 11 12;
	23  9  2  3 13;
	22  8  1  4 14;
	21  7  6  5 15;
	20 19 18 17 16];
dX=repmat([-1 -1 0 1 1],5,1);
dY=rot90(dX);
[dum,idx]=min(spiralMatrix(inMatrix));
deltaX=dX(idx);
deltaY=dY(idx);

dhull replied on September 25th, 2008 at 16:16 UTC :

Yi,

I have tried the above solution, but it does not give the correct answers. I think the idea is correct, but when using min, you are not getting the unique result that you expect.

Also, it does not take into account the edge case of no target existing.

Doug

Matt Fig replied on September 25th, 2008 at 17:04 UTC :

Here is my solution. I like it because it is simple and fast. I think I got all those indices correct!

 
[deltaX, deltaY] = puzzler(a)
idxa = [13,12,17,18,19,14,9,8,7,11,16,21,22,23,24,25,20,15,10,5,4,3,2,1,6];
dxidx = [0,0,1,1,1,0,-1,-1,-1,0,1,1,1,1,1,1,1,0,-1,-1,-1,-1,-1,-1,-1];
dyidx = [0,1,1,0,-1,-1,-1,0,1,1,1,1,1,0,-1,-1,-1,-1,-1,-1,-1,0,1,1,1];
idx = find(a(idxa),1);
dx = dxidx(idx);
dy = dyidx(idx);

Matt Fig replied on September 25th, 2008 at 17:14 UTC :

Oops, looks like I missed the edge requirement too. This does it.

 
[deltaX, deltaY] = puzzler(a)
if any(a(:))
idxa = [13,12,17,18,19,14,9,8,7,11,16,21,22,23,24,25,20,15,10,5,4,3,2,1,6];
dxidx = [0,0,1,1,1,0,-1,-1,-1,0,1,1,1,1,1,1,1,0,-1,-1,-1,-1,-1,-1,-1];
dyidx = [0,1,1,0,-1,-1,-1,0,1,1,1,1,1,0,-1,-1,-1,-1,-1,-1,-1,0,1,1,1];
idx = find(a(idxa),1);
dx = dxidx(idx);
dy = dyidx(idx);
else
    dx = -1 + floor(rand*3);
    dy = -1 + floor(rand*3);
end

Daniel Armyr replied on September 26th, 2008 at 02:41 UTC :

There is a spiral command in basic matlab? I thought the challenge was to code that particular pattern….

Oh well, seems you guys allready solved it far enough as is still interesting.

–DA
Daniel Armyr replied on September 26th, 2008 at 02:52 UTC :

Speaking of which, the spiral function seems to exist and have embedded help coments, but it does not seem to exist in the doc. Sneaky there…..

Adam replied on September 26th, 2008 at 09:31 UTC :

 
function [dX dY] = puzzler(inMatrix)

    mSp = [
    	24 25 10 11 12;
    	23  9  2  3 13;
    	22  8  1  4 14;
    	21  7  6  5 15;
    	20 19 18 17 16];

    % find smallest point
    ind = find(inMatrix .* mSp);
    pts = mSp(ind);

    % if empty make random point
    if isempty(pts)
        dX = floor(3*rand)-1;
        dY = floor(3*rand)-1;

    % not empty so find deltas
    else
        [r c] = find(spiralMatrix == min(pts));

        dX = sign(c-3);
        dY = sign(3-r);
    end
end

Pros:
Scalable
Doesn’t generate big matrix

Cons:
Uses find twice, possibly slow

~Adam

dhull replied on September 26th, 2008 at 13:03 UTC :

Matt,

It is always interesting to see how people solve the problem. Yours is a little different from the rest. It took me a while to understand what IDXA was. Then I figured out it was the absolute indices of the matrix in preferred order. The rest follows from that. This makes the problem a short look-up table type of problem

While it makes the code a little harder to visualize, it does make for very clean code. There are always trade-offs.

Doug

PS. You never actually define your outputs in the function, not do you have the function keyword, but the ideas are there.
dhull replied on September 26th, 2008 at 13:04 UTC :

Daniel,

Spiral is not documented as such, because it is not a MATLAB function, it is a MALTAB demo:

>> which spiral
C:\Program Files\MATLAB\R2008a\toolbox\matlab\demos\spiral.m

These are treated differently, even thought this demo happens to be useful as a stand alone function also.

Doug
Matt Fig replied on September 26th, 2008 at 14:02 UTC :

Doug,

You caught me! I must have copied your formatting example from above, then pasted my function in the middle. I think I remember seeing two ‘function declarations’ and deleting one. I must have erased mine instead of yours! Oh, well, you get that the function declaration should look like:

function [dx,dy] = puzzler(a)

I would be interested to see if one could come up with a fast way to get idxa for any size input, and if that is faster than some of the other scalable submissions. The other two “lookup vectors” should be easy enough to generate. Interesting…

Marc replied on September 26th, 2008 at 17:45 UTC :

So I’m a little late to the party. What I came up with was pretty much what everyone else came up with.

 
%% All the code so someone can just copy and paste it from
%% the comments.

function [deltax, deltay] = puzzler(matrixin)

% puzzler 9/26/08

values25 = [ 24 25 10 11 12;
            23 9 2 3 13;
            22 8 1 4 14;
            21 7 6 5 15;
            20 19 18 17 16;];

bigdeltax = [-1*ones(5,2) zeros(5,1) ones(5,2)];
bigdeltay = flipud(bigdeltax');

hits = values25(matrixin==1);
idx = find(values25==min(hits));

deltax = bigdeltax(idx);
deltay = bigdeltay(idx);

if sum(matrixin) == 0
    deltax = floor(2.9*rand(1))-1;;
    deltay = floor(2.9*rand(1))-1;
end

Marc replied on September 26th, 2008 at 18:44 UTC :

for those who really want to tackle the problem of creating spiral matrices…

compare a recursive approach like this, to the classic for-loop approach in spiral.m. I think a recursive approach like this is far and away easier to understand for a problem like this. Memorywise, it’s a tad wasteful, and it’s not as fast. But it’s readable.



function s = myspiral(n)
% returns spiral matrix (recursive method)
% MYSPIRAL(n) is an n-by-n matrix with elements ranging
%   from 1 to n^2 in a rectangular spiral pattern.
% see also spiral.m

if n == 1
    s = 1;
    return
end

if n == 2
    s = [4 1; 3 2];
    return
end

% now, do outer loop, and recursively solve inner parts

mymax = n^2;
mymin = ((n-2)^2)+1;
mynum = mymax:-1:mymin;

s = zeros(n,n);

%left
s(:,1) = mynum(1:n);
mynum(1:n) = []; %chop away used numbers as we go
%bottom
s(end, 2:end) = mynum(1:(n-1));
mynum(1:(n-1)) = [];
%top
s(1,2:(n-1)) = fliplr(mynum(round(length(mynum)/2)+1:end));
mynum(round(length(mynum)/2)+1:end) = [];
%right
s(1:n-1, n) = flipud(mynum(:));

% recurse to middle

s(2:n-1, 2:n-1) = myspiral(n-2);

Yi Cao replied on September 27th, 2008 at 11:03 UTC :

Doug,

Thanks for pointing out errors in my original code. I should test it before posting. Anyway, here is the version with corrections. It has been tested, hence should be correct.

 
function [deltaX, deltaY] = puzzler(inMatrix)
% Using lookup tables to solve the probelm
if isempty(inMatrix(inMatrix>0))
    deltaX=ceil(3*rand)-2;
    deltaY=ceil(3*rand)-2;
    return
end
%spiral positions
spiralMatrix = [
	24 25 10 11 12;
	23  9  2  3 13;
	22  8  1  4 14;
	21  7  6  5 15;
	20 19 18 17 16];
dX=repmat([-1 -1 0 1 1],5,1);
dY=rot90(dX);
idx=spiralMatrix==min(spiralMatrix(inMatrix>0));
deltaX=dX(idx);
deltaY=dY(idx);

Oliver Woodford replied on February 16th, 2009 at 15:53 UTC :

If you happen to want to do this for every pixel in a binary image then you can do something different to the methods suggested above, which I think will work out being faster, because it involves a multiplication which could be done over an image using conv2:

function [deltaX, deltaY] = puzzler(inMatrix)
% Our arbitrary order - could be anything
order = [24 25 10 11 12;
         23  9  2  3 13;
         22  8  1  4 14;
         21  7  6  5 15;
         20 19 18 17 16];
% Compute multiplication matrix - powers of two means highest bit indicates
% highest in the order
M = 2 .^ (numel(order) - order);
% Multiply with the input - for an image this can be achieved with a
% convolution
M = M(:)' * inMatrix(:);
% Special case
if M == 0
    deltaX = -3;
    deltaY = -3;
    return;
end
% Compute highest set bit
[M M] = log2(M);
% Compute offsets in X and Y
deltaX = [-1 -2 -2 -2 -2 -2 -1 0 1 2 2 2 2 2 1 0 -1 -1 -1 0 1 1 1 0 0];
deltaY = [-2 -2 -1 0 1 2 2 2 2 2 1 0 -1 -2 -2 -2 -1 0 1 1 1 0 -1 -1 0];
deltaY = deltaY(M);
deltaX = deltaX(M);

In fact, I use exactly this trick in my print2im function on the FEX.

Bradley replied on March 11th, 2009 at 12:56 UTC :

This solution uses a method different to those above, and so may be of interest. It uses ‘angle’ to determine which square is the correct target, without needing to construct any spiral matrices.
It should work for any size input matrix (although I’ve only tested 5×5, and even-edged matrices will assume a starting point for the spiral at one of the cells near the centre).

The code assumes that inMatrix is of type logical.

 
[deltaX, deltaY] = puzzler(inMatrix)

halfsize = floor(length(inMatrix)/2);  %a vector of possible distances from the centre
[X,Y] = meshgrid(-halfsize:halfsize,-(-halfsize:halfsize));
therange = max( abs(X), abs(Y) );  %the distance of each point from the centre
orientation = Angle(-Y + i*X); %Is a maximum vertically and decreases clockwise.
closest = find( therange == min(therange(inMatrix)) & inMatrix ); %removes all non-closest elements of inMatrix
[direction,index] = max(orientation(closest)); %finds the element we want to move towards
%Find whether the X,Y coordinates of our target are >0 or <0.
deltaX = sign(X(closest(index)));
deltaY = sign(Y(closest(index)));

These postings are the author's and don't necessarily represent the opinions of The MathWorks.

MATLAB Central Terms of Use

NOTICE: Any content you submit to MATLAB Central, including personal information, is not subject to the protections which may be afforded information collected under other sections of The MathWorks, Inc. Web site. You are entirely responsible for all content that you upload, post, e-mail, transmit or otherwise make available via MATLAB Central. The MathWorks does not control the content posted by visitors to MATLAB Central and, does not guarantee the accuracy, integrity, or quality of such content. Under no circumstances will The MathWorks be liable in any way for any content not authored by The MathWorks, or any loss or damage of any kind incurred as a result of the use of any content posted, e-mailed, transmitted or otherwise made available via MATLAB Central. Read the complete Terms prior to use.

Problems? Suggestions? Contact us at files@mathworks.com

Site Help
Patents
Trademarks
Privacy Policy
Preventing Piracy
RSS

Doug’s MATLAB Video Tutorials

September 25th, 2008

Puzzler: Cleverness needed

21 Responses to “Puzzler: Cleverness needed”

Leave a Reply

About

Subscribe

Links

Categories

Recent Comments

Blog Admin

MATLAB Central Terms of Use