Programs to Remember

By Lucio Cetto and the MATLAB Contest Team.

We made this compilation of some of the interesting entries in the MATLAB Golf Contest. With seven holes and hundreds of entries, there were too many to choose from, so we focused on just a few entries from the final four holes. For each entry, we preserved the logic of the algorithm, but we changed some obfuscated lines to more comprehensible MATLAB code and added some comments. There are some amazingly clever algorithms here. We hope that you'll be able to use some of these ideas in your own M-code.

Infection: Claus Still shows his mastery of cell-matrix-cell conversions
Infection: A clever approach by A. Skvortsov using matrix multiplication
Infection: Other examples:
Heaviest Box: A skillful use of statistics by François Glineur
Heaviest Box: Examples
Pathfinder: Per Rutquist's elegant variation of the Dijkstra algorithm.
Pathfinder: Examples
Snake: Winning entry by Nicke finds a hole in our test suite
Snake: John Arthur proposed a "randomized" alternative
Snake: Examples
Appendix: Plotting Code

Infection: Claus Still shows his mastery of cell-matrix-cell conversions

clear
a = {'Anne','Bob','Alan','Michael','Lucy','Gus','Ross'};
b = 1;

"FSec 4" by Claus Still:

type submission13319.m

a=upper(a)
for i=';;;'
  d([a{b} 91])=1;
  b=any(d(char(a)'));
end
c=find(b);

Expanded for clarity:

% the virus is case-insensitive
a = upper(a);
% logical index of infected letters
d = zeros(double('Z'),1);

% three spreads of the virus
for i = 1:3
    % given the infected people (b) set the infected letters (d)
    d([a{b}]) = 1;
    % find the logical indexes for infected people
    b = any(d(char(a)'));
end

% find the indexes of the infected people
c = find(b)

c =

     1     3     4     5     6

Infection: A clever approach by A. Skvortsov using matrix multiplication

clear
a = {'Anne','Bob','Alan','Michael','Lucy','Gus','Ross'};
b = 1;

"Matrix Lab" by Alexey Skvortsov:

type submission13366

for k=1:numel(a)
q(k,upper(a{k}))=1
end
q=(q*q')^3
c=find(q(b,:))

Expanded for clarity:

for k=1:numel(a)
    % prepares a letter occurrence table, every row corresponds to
    % every person and every column to every letter in the ASCII code
    q(k,upper(a{k})) = 1;
end
% matrix with the pairwise common letters
Q = q*q';
% matrix multiplication propagates non-zero entries to the row-columns
q = Q^3;
% find the columns with non zero-entries in b
c = find(q(b,:))

c =

     1     3     4     5     6

plot_solution('infection',a,b,c,Q,[1 4 1 2 2 3 3],[1 1 2 1 2 2 1])

Infection: Other examples:

clear
a = {'Anne','Bob','Alan','Michael','Lucy','Gus','Ross'};
b = 2;

infection_solver
plot_solution('infection',a,b,c,Q,[1 4 1 2 2 3 3],[1 1 2 1 2 2 1])

clear
a={'lmLMAlm','bonopa','zFz','CBeqfQ','RED', ...
    'gds','xICGgH','Viwiji','Juk','TkH','YyYyY'};
b=1;

infection_solver
plot_solution('infection',a,b,c,Q, ...
    [1 1 1 2 3 3 2 1 2 3 2],[1 2 3 2 2 3 3 4 4 4 1])

clear
a={'lmLMAlm','bonopa','zFz','CBeqfQ','RED', ...
    'gds','xICGgH','Viwiji','Juk','TkH','YyYyY'};
b=8;

infection_solver
plot_solution('infection',a,b,c,Q, ...
    [1 1 1 2 3 3 2 1 2 3 2],[1 2 3 2 2 3 3 4 4 4 1])

Heaviest Box: A skillful use of statistics by François Glineur

clear
a = [1 2 3 4 4 4; 2 5 5 5 5 4; 2 5 5 5 5 4; 1 4 4 5 5 2; 1 3 3 5 5 100];
a_original = a;

"FDA12.01" by François Glineur:

type submission13790.m

x=1:19;
a(99,99)=0;
b=0;
for i=x
   for j=x
      for k=x
         c = a(i:i+j,k:k+j);
         c = c(:);
         b = max(b,sum(c)*~std(c));
      end
   end
end

Expanded for clarity:

% size of input matrix
[m,n] = size(a);
% largest possible square fitting in a
o = min(m,n);
% fill with zeros, so we do not need to check for bounds
a(2*n,2*m) = 0;
% b will contain the sum of the heaviest box so far
b=0;

% for every possible left column
for i=1:n
    % for every possible square size
    for j=1:o
        % for every possible bottom row
        for k=1:m
            % extract the square to test
            c = a(i:i+j,k:k+j);
            % convert it into a vector
            c = c(:);
            % if all the values are the same in c its std will be 0,
            % only then sum(c) is considered to substitute the old b
            b = max(b,sum(c)*~std(c));
      end
   end
end

b

b =

    20

plot_solution('heaviest',a_original,b,[1 3 2 4])

Heaviest Box: Examples

clear
a = [1 1 1 2 5 5 5 5 5 5 6 6 7 7 8 8 9 9 9;
     1 1 1 2 5 5 5 5 5 5 6 6 7 7 8 8 9 9 9];
a_original = a;

submission13790
plot_solution('heaviest',a_original,b,[16 18 0 2])

clear
a = gallery('moler',10)+flipud(gallery('moler',10));
a_original = a;

submission13790
plot_solution('heaviest',a_original,b,[7 10 3 6])

Pathfinder: Per Rutquist's elegant variation of the Dijkstra algorithm.

clear
a = zeros(36);
a([ ...
1;2;5;6;37;38;39;41;42;43;74;75;76;78;79;80;111;112;115;116;145;146;149;
150;158;181;182;183;185;186;187;218;219;220;222;223;224;255;256;259;260;
278;297;298;333;334;335;370;371;372;407;408;409;444;445;461;473;482;483;
518;519;526;556;557;562;592;593;605;630;631;666;667;670;704;705;706;740;
741;743;771;772;775;776;778;813;815;816;851;852;853;888;889;892;908;926;
927;962;963;964;997;999;1000;1021;1025;1037;1038;1073;1074;1078;1111;1112;
1147;1148;1149;1184;1185;1186;1218;1221;1222;1223;1258;1259;1260;1295;
1296]) = 1;
a = a|a' + eye(36);

b = [ ...
1 11;1 10;1 9;1 8;2 11;2 10;2 9;2 8;9 12;10 12;11 12;12 12;13 12;3 11;
4 10;6 10;7 11;3 7;4 8;6 8;7 7;5 9;5 5;6 5;7 5;5 4;6 4;7 4;13 9;16 10;
12 5;13 5;14 5;15 5;20 2;20 1];

"PPath III" by Per Rutquist

type submission14049.m

d = b*[1;i];
p = d==d;
f = abs(p*d.'-d*p');
h = p'/0;
h(1) = 0;
for j=p'
    q=h'*p'+f./a
    [h,r] = min(q+~f)
    [h] = min(q)
end
[x,c]=max(h);
while(c(1)>1)
  c=[r(c(1)) c];
end

Expanded for clarity:

% number of points on the plane
n = size(b,1);

% create a complex number so 'abs' can be used to compute distances
d = b * [1;1i];

% compute all pairwise Euclidean distances
[x,y] = meshgrid(d);
f = abs(x-y);

% cancel non-connected edges (Per computed this inside the loop)
f(a==0) = Inf;

% h keeps the known minimum distances to node 1
h = repmat(Inf,1,n);
% we start from the first point in the list
h(1) = 0;

% flooding
for j = 1:n
    % adding the new segment, (non valid edges will add Inf)
    q = repmat(h',1,n) + f;
    % r stores the route for every node to node 1, taken after finding
    % the min, but invalidating the self-segment
    [h,r] = min(q+eye(n));
    % update the distances vector
    [h] = min(q);
end
% find the farthest node to node 1
[x,c]=max(h);
while(c(1)>1)
    % trace back the trajectory, start at the farthest point until the
    % node 1 is found
  c=[r(c(1)) c];
end

plot_solution('pathfinder',a,b,c)

Pathfinder: Examples

p = [9 2:8 1 10:36];
a = a(p,p);
b = b(p,:);

pathfinder_solver
plot_solution('pathfinder',a,b,c)

clear
a = [1 0 1 0 0 0;0 1 1 1 0 0;1 1 1 1 0 0;0 1 1 1 1 1;0 0 0 1 1 0; ...
0 0 0 1 0 1];
b = [0 0;0 4;1 1;2 2;3 0;3 3];

pathfinder_solver
plot_solution('pathfinder',a,b,c)

Snake: Winning entry by Nicke finds a hole in our test suite

clear
a = [ 6 6 4 6 ;
      1 2 3 6 ;
      6 3 7 7 ;
      6 4 5 7 ];

"Revolution IV" by Nicke:

type submission14560

[h w b]=size(a);
for i=1:h*w
 c=[];
 while any(i)
  i=i(1);
  c=[c; i];
  [v z]=ind2sub(h,i);
  t=i+[h*[z<w -(z>1)] v<h -(v>1)];
  i=t(a(t)==a(i)+1);
 end
 if nnz(c)>nnz(b)
  b=c;
 end
end

Expanded for clarity:

% size of input matrix
[h,w] = size(a);
% b will contain the best snake
b = [];

% for every possible start for the snake
for i = 1 : h*w
    % c will contain the current snake
    c = [];

    % until no new link is found
    while any(i)
        % take arbitrarily one of the paths. This will not work in
        % some cases!
        i=i(1);
        % concatenate the new element
        c=[c; i];
        % change linear index to subscripts
        [v,z] = ind2sub([h,w],i);
        % 4 neighbors to 'i', if it's out of bounds then return 'i
        new_v = max(min(v+[0 0 1 -1],h),1);
        new_z = max(min(z+[1 -1 0 0],w),1);
        % back to linear index
        t = sub2ind([h,w],new_v,new_z);
        % check if one of those can continue the snake
        i=t(a(t)==a(i)+1);
    end

    % if the new snake is longer than the current best
    if numel(c)>numel(b)
        % then store the new best
        b=c;
    end
end

plot_solution('snake',a,b)
title('The winning program fails on some cases !')
hold on, plot([ 2 2 2 3],[ 3 2 1 1],'b')

Snake: John Arthur proposed a "randomized" alternative

"h13" by John Arthur:

type submission14525

[h w b]=size(a);
p=h*w;
for k=';;;;;;;;;;;'
  for i=1:p
    c=i;   
    while i
      t = i+[1&mod(i,h) -(1&mod(i-1,h)) h -h];
      t(t<1|t>p)=i;
      i = t(a(t)==a(i)+1);
      j=nnz(i);
      if j
          i=i(ceil(j*rand));
      end
      c =[c; i];
   end

   if nnz(c)>nnz(b)
      b=c;
   end
end  
end

Expanded for clarity:

clear
a = [6 6 4 6;
     1 2 3 6;
     6 3 7 7;
     6 4 5 7];

% size of input matrix
[h,w] = size(a);
% number of element in input matrix
p=numel(a);
% b will contain the best snake
b = [];

% try several times in case of bifurcation
for k=1:11

    for i=1:p
        c=i;

        while i
            % change linear index to subscripts
            [v,z] = ind2sub([h,w],i);
            % 4 neighbors to 'i', if it's % out of bounds then return 'i'
            new_v = max(min(v+[0 0 1 -1],h),1);
            new_z = max(min(z+[1 -1 0 0],w),1);
            % back to linear index
            t = sub2ind([h,w],new_v,new_z);

            % checking if one of those can continue the snake
            i = t(a(t)==a(i)+1);
            % number of possible paths to continue
            j=numel(i);

            % in case there are several paths
            if j
                % select one randomly
                i=i(ceil(j*rand));
            end

            % concatenate the new element to the current snake
            c =[c; i];
        end

        % if the new snake is longer than the current best
        if numel(c)>numel(b)
            % then store the new best
            b=c;
        end
    end
end

b

plot_solution('snake',a,b)
title('The second place ''by luck'' does the job')

Snake: Examples

clear
a = ceil(hilb(10)*100);
a(2:6,1:5) = spiral(5)+17;

submission14525
plot_solution('snake',a,b)

clear
a = zeros(10,14);
b = [128:-10:88 87:-1:83 73 74 64 65 55 56]';
for ii=1:length(b)
    a(b(ii))=ii+4;
end
ind = find(a==0);
a(ind)=mod(1:length(ind),max(a(b)))+3;

submission14525
plot_solution('snake',a,b)

clear
a = full(gallery('tridiag',32:41,1:2:22,2:2:21))+20;
a(:,7:end) = flipud(a(:,7:end));
a(a==0) = 15;
a = flipud(a);

submission14525
plot_solution('snake',a,b)

Appendix: Plotting Code

type plot_solution

function plot_solution(s,varargin)
%PLOT_SOLUTION Visualizes the solution to some MATLAB Golf holes.

feval(s,varargin{:})

%=====================================================================
function pathfinder(a,b,c)
clf
gplot(a,b);
hold on;
plot(b(c,1),b(c,2),'r--','Linewidth',3)
n = 1;
text(b(n,1),b(n,2),[' ' num2str(n) ' '],'Background',[1 1 0.8],...
    'HorizontalAlignment','center','EdgeColor','red','fontsize',9,...
    'color','red')
for n = 2:length(b)
    text(b(n,1),b(n,2),[' ' num2str(n) ' '],'Background',[1 1 0.8],...
        'HorizontalAlignment','center','EdgeColor','black','fontsize',7)
end
axis([min(b(:,1))-.5 max(b(:,1))+.5 min(b(:,2))-.5 max(b(:,2))+.5])
set(gcf,'Color','white');axis off;axis equal;

%======================================================================
function snake(a,b)
clf
[r,c] = size(a);
[x,y] = meshgrid(1:c,r:-1:1);
plot(x(b),y(b),'r','Linewidth',3)
for i = 1:r*c
    text(x(i),y(i),[' ' num2str(a(i)) ' '],'Background',[1 .92 1],...
        'HorizontalAlignment','center','EdgeColor','black','fontsize',7)
end
axis off;axis equal;axis([.5 c+.5 .5 r+.5])
set(gcf,'Color','white');

%=======================================================================
function heaviest(a,b,d)
clf
subplot(1,1.3,1)
[r,c] = size(a);
[x,y] = meshgrid(.5:c,r-.5:-1:0);
for i = 1:r*c
    text(x(i),y(i),[' ' num2str(a(i)) ' '],'Background',[1 1 1],...
        'HorizontalAlignment','center','EdgeColor','w','fontsize',10)
end
hold on
u = plot(repmat([0:1:c],2,1),repmat([0 r]',1,c+1));
set(u,'color',[.7 .7 .3])
u = plot(repmat([0 c]',1,r+1),repmat([0:1:r],2,1));
set(u,'color',[.7 .7 .3])
axis off;axis equal;axis([0-.1 c+.1 0-.1 r+.1])
set(gcf,'Color','white');
plot(d([1 1 2 2 1]),d([3 4 4 3 3]),'r','linewidth',2)
subplot(1,3,3)
text(.5,.5,[' = ' num2str(b) ' '],'Background',[1 1 1],'color','red',...
    'HorizontalAlignment','center','EdgeColor','w','fontsize',25)
axis off;

%========================================================================
function infection(a,b,c,Q,x,y)
clf
n = numel(a);
hold on
for i = 1:n
    for j = 1:n
        if ((i~=j) & (Q(i,j)>0))
            plot(x([i j]),y([i j]),'g')
        end
    end
end
for i = 1:n
    t(i) = text(x(i),y(i),[' '  num2str(i) '-' num2str(a{i}) ' '], ...
        'Background',[.95 .95 1],...
        'HorizontalAlignment','center','EdgeColor','b','fontsize',10);
end
QQ = Q^3;
for i = 1:n
    if QQ(b,i)>0
        set(t(i),'Background',[ 1 .95 .95],'linewidth',1,'EdgeColor','r');
    end
end
QQ = Q*Q;
for i = 1:n
    if QQ(b,i)>0
        set(t(i),'Background',[ 1 .95 .95],'linewidth',2,'EdgeColor','r');
    end
end
for i = 1:n
    if Q(b,i)>0
        set(t(i),'Background',[ 1 .95 .95],'linewidth',3,'EdgeColor','r');
    end;
end
for i = 1:n
    if i==b
        set(t(i),'Background',[ 1 .8 .8],'linewidth',4,'EdgeColor','r');
    end
end
axis off
axis([min(x)-.5 max(x)+.5 min(y)-.5 max(y)+.5]);

golf_1

		Home Rules Winners Evolution Analysis Hall of fame Newsgroup thread Send us feedback

<#assign current_year = request.date?string("#")?date("yyyyMMdd")?string("yyyy")>

Related Topics

Programs to Remember

Contents

Infection: Claus Still shows his mastery of cell-matrix-cell conversions

Infection: A clever approach by A. Skvortsov using matrix multiplication

Infection: Other examples:

Heaviest Box: A skillful use of statistics by François Glineur

Heaviest Box: Examples

Pathfinder: Per Rutquist's elegant variation of the Dijkstra algorithm.

Pathfinder: Examples

Snake: Winning entry by Nicke finds a hole in our test suite

Snake: John Arthur proposed a "randomized" alternative

Snake: Examples

Appendix: Plotting Code