% Monte-Carlo Search Algoritm on low-autocorrelation program
% BSDLicence
% Rick van der Zwet - 0433373 - <hvdzwet@liacs.nl>
% $Id: mcs.m 43 2009-12-17 22:18:48Z rick $

% Brute-force result of length 20
% best_20 = [-1,1,1,-1,-1,-1,1,1,-1,1,-1,-1,-1,1,-1,1,1,1,1,1];
% autocorrelation(best_20);

function [fitness,value] = mcs(length, iterations)
  best_fitness = 0;
  for i = 1:iterations
    % Generate a random column s={-1,1}^n
    n = length;
    s = rand(n,1);
    s = round(s);
    s = s - (s == 0);
  
    % Find whether we are better than everything else
    fitness = autocorrelation(s);
    if (fitness > best_fitness)
      best_value = s;
      best_fitness = fitness;
    end
  end
  fitness = best_fitness;
  value = best_value;
end