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

1 view (last 30 days)
Doug Hull 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
%
%
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.
Fangjun Jiang on 2 Sep 2011
@andrei, your code above returns false for both (1,4,4,5) and (1,17,4,5)
Walter Roberson on 2 Sep 2011
Did anyone run timing tests on the survivors?

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 CommentsShow 1 older commentHide 1 older comment
Andrei Bobrov on 2 Sep 2011
Hi David! +1
David Young on 3 Sep 2011
Thanks Doug!

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
%
%
[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
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!)

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 CommentsShow 1 older commentHide 1 older comment
Walter Roberson on 1 Sep 2011
flag = abs(a-b)==n || (abs(a-b)==1 && floor(a/n)==floor(b/n));
David Young on 1 Sep 2011
Neat

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);
Oleg Komarov on 1 Sep 2011
Can't find any other valid solution to ensure bottom vs top not 4 conn except the ones already proposed.
Walter Roberson on 1 Sep 2011
Tossing something together: diff(mod(sort([a,b]),n))<0

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);
Walter Roberson on 1 Sep 2011
This might or might not be slightly faster:
c = sort([a,b]);
e = c(2)-c(1);
flag = (e==1 & mod(c(1),n)) | (e==m & c(2)>n);
Or if you prefer your original structure, then instead of max/min, you could use
c = max(a,b);
d = a + b - c;
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);

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
%
%
% 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));