MATLAB Answers

Puzzler: Quickly tell if two absolute indices (a,b) are four connected for n x m matrix.

1 view (last 30 days)
function flag = isFourConnected(a,b,n,m)
%
% a,b: indices of interest a ~= b
% n,m: size of matrix of interest
%
% flag: True if indices a and b are four connected
% in a matrix of size n x m
%
%
% Your code here
Note, this code should use no toolboxes, and should be reasonably quick as this function will be called many times. Reasonably quick is up to debate as the rest of the code forms.
  10 Comments

Sign in to comment.

Accepted Answer

David Young
David Young on 1 Sep 2011
function flag = isFourConnected(a,b,n,m)
%
% a,b: indices of interest a ~= b
% n,m: size of matrix of interest
%
% flag: True if indices a and b are four connected
% in a matrix of size n x m
%
d = abs(a-b);
flag = d == n || (d == 1 && mod(min(a,b), n));
end
  3 Comments

Sign in to comment.

More Answers (5)

Fangjun Jiang
Fangjun Jiang on 1 Sep 2011
Circle-shifting neighbors are considered connected.
function flag = isFourConnected(a,b,n,m)
%
% a,b: indices of interest a ~= b
% n,m: size of matrix of interest
%
% flag: True if indices a and b are four connected
% in a matrix of size n x m
%
%
% Your code here
[x,y]=ind2sub([n,m],[a;b]);
xdiff=abs(x(1)-x(2));
ydiff=abs(y(1)-y(2));
flag = ((xdiff==0) && (ydiff==1) || (ydiff==m-1)) || ...
((ydiff==0) && (xdiff==1) || (xdiff==n-1));
A little test script. All other entries so far didn't pass this test.
clc;
TestVector={6,7,4,5
6,10,4,5
1,4,4,5
1,17,4,5};
for k=1:size(TestVector,1)
if isFourConnected(TestVector{k,:})~=true
disp(k);beep;
end
end
  1 Comment
Doug Hull
Doug Hull on 1 Sep 2011
clever, I like it! First in also! Thanks (will accept after a few hours to let more people at it!)

Sign in to comment.


Walter Roberson
Walter Roberson on 1 Sep 2011
function flag = isFourConnected(a,b,n,m)
%
% a,b: indices of interest a ~= b
% n,m: size of matrix of interest
%
% flag: True if indices a and b are four connected
% in a matrix of size n x m
%
%
flag = abs(a-b)==n || (floor(a/n)==floor(b/n) && abs(a-b)==1);
  3 Comments

Sign in to comment.


Oleg Komarov
Oleg Komarov on 1 Sep 2011
I assume a,b,m,n always numeric and integer values > 1
function flag = isFourConnected(a,b,n,m)
% a,b : indices of interest a ~= b
% m,n : size of matrix of interest
% flag: True if indices a and b are four connected
% in a matrix of size n x m
d = a-b; flag = d == n || d == -n || (d == 1 && mod(a,n) ~= 1) || (d == -1 && mod(b,n) ~= 1);
  4 Comments

Sign in to comment.


Bruno Luong
Bruno Luong on 1 Sep 2011
function flag = isFourConnected(a,b,n,m)
% 10 arithmetic operations by pair
c = max(a,b);
d = min(a,b);
e = c - d;
flag = (e==1 & mod(d,n)) | (e==n & c>n);
  2 Comments
Bruno Luong
Bruno Luong on 1 Sep 2011
I believe I had one redundant test in the earlier code:
function flag = isFourConnected(a,b,n,m)
% 8 arithmetic operations by pair
c = max(a,b);
d = min(a,b);
e = c - d;
flag = (e==1 & mod(d,n)) | (e==n);

Sign in to comment.


Daniel Shub
Daniel Shub on 2 Sep 2011
I am not sure what to do about circle-shifting neighbors so I have two answers.
function flag = isFourConnected(a,b,n,m)
%
% a,b: indices of interest a ~= b
% n,m: size of matrix of interest
%
% flag: True if indices a and b are four connected
% in a matrix of size n x m
%
%
% Your code here
% Using ind2sub might be faster.
col = mod([a(:), b(:)]-1, n)+1;
row = ceil([a(:), b(:)]/n);
%[col, row] = ind2sub([n, m], [a(:), b(:)]);
flag = reshape(mod(abs(diff(col, 1, 2)), n-2)+mod(abs(diff(row, 1, 2)), m-2) == 1, size(a));
% if circle shifted points are not connected:
% flag = reshape(abs(diff(col, 1, 2))+abs(diff(row, 1, 2)) == 1, size(a));

Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!