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

1 次查看（过去 30 天）

Doug Hull 2011-9-1

1
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/14958-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.

10 个评论
显示 8更早的评论隐藏 8更早的评论

Fangjun Jiang 2011-9-2

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

Walter Roberson 2011-9-2

Did anyone run timing tests on the survivors?

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

David Young 2011-9-1

4
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/14958-puzzler-quickly-tell-if-two-absolute-indices-a-b-are-four-connected-for-n-x-m-matrix#answer_20340

在 MATLAB Online 中打开

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 个评论
显示 1更早的评论隐藏 1更早的评论

Andrei Bobrov 2011-9-2

Hi David! +1

David Young 2011-9-3

Thanks Doug!

请先登录，再进行评论。

更多回答（5 个）

Fangjun Jiang 2011-9-1

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/14958-puzzler-quickly-tell-if-two-absolute-indices-a-b-are-four-connected-for-n-x-m-matrix#answer_20335

在 MATLAB Online 中打开

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 个评论
显示 -1更早的评论隐藏 -1更早的评论

Doug Hull 2011-9-1

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

请先登录，再进行评论。

Walter Roberson 2011-9-1

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/14958-puzzler-quickly-tell-if-two-absolute-indices-a-b-are-four-connected-for-n-x-m-matrix#answer_20341

在 MATLAB Online 中打开

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 个评论
显示 1更早的评论隐藏 1更早的评论

Walter Roberson 2011-9-1

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

David Young 2011-9-1

Neat

请先登录，再进行评论。

Oleg Komarov 2011-9-1

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/14958-puzzler-quickly-tell-if-two-absolute-indices-a-b-are-four-connected-for-n-x-m-matrix#answer_20338

在 MATLAB Online 中打开

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 个评论
显示 2更早的评论隐藏 2更早的评论

Oleg Komarov 2011-9-1

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

Walter Roberson 2011-9-1

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

请先登录，再进行评论。

Bruno Luong 2011-9-1

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/14958-puzzler-quickly-tell-if-two-absolute-indices-a-b-are-four-connected-for-n-x-m-matrix#answer_20346

在 MATLAB Online 中打开

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 个评论
显示无隐藏无

Walter Roberson 2011-9-1

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 2011-9-1

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 2011-9-2

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/14958-puzzler-quickly-tell-if-two-absolute-indices-a-b-are-four-connected-for-n-x-m-matrix#answer_20374

在 MATLAB Online 中打开

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