Puzzler: Quickly tell if two absolute indices (a,b) are four connected for n x m matrix.
1 visualización (últimos 30 días)
Mostrar comentarios más antiguos
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 comentarios
Fangjun Jiang
el 2 de Sept. de 2011
@andrei, your code above returns false for both (1,4,4,5) and (1,17,4,5)
Respuesta aceptada
David Young
el 1 de Sept. de 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 comentarios
Más respuestas (5)
Fangjun Jiang
el 1 de Sept. de 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
Walter Roberson
el 1 de Sept. de 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 comentarios
Walter Roberson
el 1 de Sept. de 2011
flag = abs(a-b)==n || (abs(a-b)==1 && floor(a/n)==floor(b/n));
Oleg Komarov
el 1 de Sept. de 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 comentarios
Oleg Komarov
el 1 de Sept. de 2011
Can't find any other valid solution to ensure bottom vs top not 4 conn except the ones already proposed.
Bruno Luong
el 1 de Sept. de 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 comentarios
Walter Roberson
el 1 de Sept. de 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
el 1 de Sept. de 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
el 2 de Sept. de 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));
0 comentarios
Ver también
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!