Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Solution 81317

Submitted on 24 Apr 2012 by Kees Roos

Correct

28426Size
Leading solution size is 537.
This solution is locked. To view this solution, you need to provide a solution of the same size or smaller.

Test Suite

Test
Code Input and Output
1
Pass
 

                      

                    
2
Pass
 
%%
% test small connectivity matrix (3x3)
assert(isequal(mindist([1,3,2,3],[2,2,1,2]),[0 1 Inf;1 0 Inf;2 1 0]))
t0=clock;
D=mindist([1,3,2,3],[2,2,1,2]);
t1=etime(clock,t0)*1e3;
disp('Time (ms)');
disp(t1)
Time (ms)
    1.1050
3
Pass
 
%%
% test small connectivity matrix (10 vertices, 15 edges)
assert(isequal(mindist([10 5 5 7 7 3 3 4 6 6 1 8 7 1 10],[7 4 10 6 8 4 1 7 9 4 6 9 6 10 9]),[0 Inf Inf 2 Inf 1 2 3 2 1;Inf 0 Inf Inf Inf Inf Inf Inf Inf Inf;1 Inf 0 1 Inf 2 2 3 3 2;Inf Inf Inf 0 Inf 2 1 2 3 Inf;Inf Inf Inf 1 0 3 2 3 2 1;Inf Inf Inf 1 Inf 0 2 3 1 Inf;Inf Inf Inf 2 Inf 1 0 1 2 Inf;Inf Inf Inf Inf Inf Inf Inf 0 1 Inf;Inf Inf Inf Inf Inf Inf Inf Inf 0 Inf;Inf Inf Inf 3 Inf 2 1 2 1 0]))
t0=clock;
D=mindist([10 5 5 7 7 3 3 4 6 6 1 8 7 1 10],[7 4 10 6 8 4 1 7 9 4 6 9 6 10 9]);
t1=etime(clock,t0)*1e3;
disp('Time (ms)');
disp(t1)
Time (ms)
    1.0430
4
Pass
 
%%
% test small connectivity matrix (10 vertices, 30 edges)
assert(isequal(mindist([4 10 2 9 8 2 7 10 3 7 5 9 2 6 9 3 2 9 8 7 9 9 10 8 2 7 3 2 1 8],[2 6 9 4 3 1 4 8 10 5 4 6 5 5 7 4 7 1 4 4 3 8 5 7 5 4 7 3 4 1]),[0 2 3 1 3 4 3 4 3 4;1 0 1 2 1 2 1 2 1 2;3 2 0 1 2 2 1 2 3 1;2 1 2 0 2 3 2 3 2 3;3 2 3 1 0 4 3 4 3 4;4 3 4 2 1 0 4 5 4 5;3 2 3 1 1 4 0 4 3 4;1 2 1 1 2 3 1 0 3 2;1 2 1 1 2 1 1 1 0 2;2 3 2 2 1 1 2 1 4 0]))
t0=clock;
D=mindist([4 10 2 9 8 2 7 10 3 7 5 9 2 6 9 3 2 9 8 7 9 9 10 8 2 7 3 2 1 8],[2 6 9 4 3 1 4 8 10 5 4 6 5 5 7 4 7 1 4 4 3 8 5 7 5 4 7 3 4 1]);
t1=etime(clock,t0)*1e3;
disp('Time (ms)');
disp(t1)
Time (ms)
    1.5850
5
Pass
 
%%
% test medium connectivity matrix (100 vertices, 200 edges)
i=[17 21 97 93 63 87 68 14 40 12 30 60 45 63 55 43 71 74 32 66 48 27 10 80 1 50 36 40 100 35 84 75 93 94 79 49 6 6 60 24 80 43 60 41 64 87 1 17 44 63 6 89 15 70 74 48 69 68 63 24 77 82 48 69 33 50 100 90 37 29 10 62 61 87 69 6 45 27 77 8 100 94 77 26 8 72 59 4 4 36 59 47 9 60 95 88 15 27 32 50 51 42 40 76 22 32 68 39 46 82 32 27 15 39 75 63 33 63 63 91 64 43 13 10 2 56 10 62 45 24 44 58 80 2 44 98 80 92 31 97 76 82 48 68 5 100 91 65 65 90 77 96 95 44 84 4 29 85 25 99 26 75 47 2 47 64 63 4 83 73 63 26 56 99 9 98 47 7 82 53 86 84 66 40 83 76 69 86 74 60 18 99 69 3 10 35 85];
j=[6 27 87 92 2 77 23 12 86 60 81 18 14 69 98 84 91 76 12 81 22 81 4 26 25 27 56 39 52 20 56 92 21 37 61 100 24 67 34 76 77 90 46 25 76 69 44 94 65 9 80 28 56 39 65 68 37 51 12 1 64 21 98 50 46 99 86 21 46 99 99 81 16 60 80 20 88 74 68 15 72 55 28 67 11 31 24 39 85 35 64 42 65 87 45 95 78 59 49 13 61 30 28 31 28 35 13 74 13 7 94 60 2 40 74 93 38 18 91 84 25 29 72 36 98 12 41 28 31 54 73 71 49 29 43 82 10 46 8 91 30 80 54 26 83 46 84 51 17 20 78 7 50 30 58 58 27 30 36 15 42 54 32 13 80 89 4 50 56 88 16 98 49 24 91 72 55 77 65 83 79 12 82 70 93 19 95 35 62 98 51 70 48 68 56 28 6];
assert(isequal(interp2(mindist(i,j),[2 55 45 33 34 87 53 43 99 50],[90 66 53 41 94 68 94 38 23 76],'nearest'),[8,5,8,Inf,7,7,Inf,Inf,Inf,9]))
t0=clock;
D=mindist(i,j);
t1=etime(clock,t0)*1e3;
disp('Time (ms)');
disp(t1)
Time (ms)
   90.2320
6
Pass
 
%%
% Time-score evaluation
% test medium connectivity matrix (100 vertices, 200 edges)
rand('state',2);
n=100;m=200;
i=ceil(n*rand(1,m));
j=ceil(n*rand(1,m));
k=i==j;i(k)=[];j(k)=[];
I=ceil(n*rand(1,10));J=ceil(n*rand(1,10));
% first run for initialization
assert(isequal(interp2(mindist(i,j),I,J,'nearest'),[6 6 Inf 0 5 Inf 4 8 6 3]))
% second run for time evaluation
t0=clock;
D=mindist(i,j);
t1(1)=etime(clock,t0)*1e3;
% test large connectivity matrix (1000 vertices, 2000 edges)
rand('state',0);
n=1000;m=2000;
i=ceil(n*rand(1,m));
j=ceil(n*rand(1,m));
k=i==j;i(k)=[];j(k)=[];
I=ceil(n*rand(1,10));J=ceil(n*rand(1,10));
% first run for initialization
assert(isequal(interp2(mindist(i,j),I,J,'nearest'),[8 8 9 8 11 7 Inf 5 8 Inf]))
% second run for time evaluation
t0=clock;
D=mindist(i,j);
t1(2)=etime(clock,t0)*1e3;
% test large connectivity matrix (1000 vertices, 10000 edges)
rand('state',1);
n=1000;m=10000;
i=ceil(n*rand(1,m));
j=ceil(n*rand(1,m));
k=i==j;i(k)=[];j(k)=[];
I=ceil(n*rand(1,10));J=ceil(n*rand(1,10));
% second run for time evaluation
t0=clock;
D=mindist(i,j);
t1(3)=etime(clock,t0)*1e3;
assert(isequal(interp2(D,I,J,'nearest'),[3 4 3 4 4 3 3 2 3 3]))
% convert time to score
disp('Time (ms)');
disp(t1);
feval(@evalin,'caller',sprintf('score=%d',round(sum(t1))));
%fh=fopen('mindist.m','wt');
%fprintf(fh,'%s\n',repmat('1;',[1,ceil(sum(t1)/2)]));
%fclose(fh);
Time (ms)
   1.0e+04 *
    0.0107    0.8970    1.9349
score =
       28426