% Monte-Carlo Search Algoritm on low-autocorrelation program
% BSDLicence
% Rick van der Zwet - 0433373 - <hvdzwet@liacs.nl>

% 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;
        endif
    endfor
    fitness = best_fitness;
    value = best_value;
endfunction

% Basic variables
iterations = [1:10:200];
repetitions = 20;
length = 20;


% Plot the stuff
fitnesses = [];
for iteration = iterations
    fitness = [];
    for rep = 1:repetitions
        printf('Iter:%i, Rep:%i\n',iteration,rep);
        [new_fitness, value] =  mcs(length,iteration);
        fitness = [fitness, new_fitness];

        % Little hack to display output nicely
        % disp(rot90(value,-1));
    endfor
    
    fitnesses = [fitnesses,mean(fitness)];
endfor

plot(iterations,fitnesses);
title(sprintf('Monte-Carlo Search on Low-Corretation set - repetitions %i',repetitions));
ylabel('fitness');
xlabel('iterations');
grid on;
legend(sprintf('Length %i',length));
print("mcs-fitness.eps","-depsc2");