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

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.

[Fangjun Jiang]

I need clarification regarding "absolute indices" and "four connected". Can you give a numerical example?

[Fangjun Jiang]

I think I figured it out now. Every element in a matrix has four connected, left, right, top, bottom. Absolute indices means linear indices or single indices.

[Doug Hull]

@Fangjun

Correct!

[Walter Roberson]

is a point considered to be 4 connected to itself?

[Doug Hull]

@Walter:

good edge case. Editing question to deal with this.

[the cyclist]

Which, if any, of the input arguments does the function need to be vectorizable across?

[Fangjun Jiang]

How about circle-shifting neighbors? Should isFourConnected(1,4,4,5) and isFourConnected(1,17,4,5) all be true?

[Andrei Bobrov]

for three-dimensional array

d = abs(a-b);

flag = d == n || d == n*m || (d == 1 && mod(min(a,b), n));

[Fangjun Jiang]

@andrei, your code above returns false for both (1,4,4,5) and (1,17,4,5)

[Walter Roberson]

Did anyone run timing tests on the survivors?

Answer 1

[David Young]

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

[Walter Roberson]

Interesting way to code the top vs bottom boundary condition.

[Andrei Bobrov]

Hi David! +1

[David Young]

Thanks Doug!

Answer 2

[Fangjun Jiang]

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

[Doug Hull]

clever, I like it! First in also! Thanks (will accept after a few hours to let more people at it!)

Answer 3

[Walter Roberson]

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

[Walter Roberson]

Saving a repeated calculation to a variable isn't always faster once you take the JIT into account.

That's my excuse, and I'm sticking to it :-)

[Walter Roberson]

flag = abs(a-b)==n || (abs(a-b)==1 && floor(a/n)==floor(b/n));

[David Young]

Neat

Answer 4

[Oleg Komarov]

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

[Walter Roberson]

df would be 1 for bottom of column vs top of next column

[Oleg Komarov]

Argh...

[Oleg Komarov]

Can't find any other valid solution to ensure bottom vs top not 4 conn except the ones already proposed.

[Walter Roberson]

Tossing something together: diff(mod(sort([a,b]),n))<0

Answer 5

[Bruno Luong]

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]

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]

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

Answer 6

[Daniel Shub]

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