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 85186

Submitted on 3 May 2012 by Kees Roos

Correct

4647Size
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)
   23.0740
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.6760
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.9680
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)
   36.9210
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+03 *
    0.0369    1.1289    3.4813
score =
        4647