Earth optimized

%% HISTORIQUE
% v1
%   move randomly

% v2
%   initialisation au point le plus haut
%   chemine vers des voisins valides, cad:
%       - libres (non deja utilises)
%       - de valeur plus petite

% v3
%   avoid culs de sac

% v4
%   ajoute un dernier coup sans eviter les cul de sac (derniere chance)
%   initialisation en tenant compte des voisins de rang 1

% v5
%   introduction of direction choice (aim = to loop)

% v6
%   introduction of moves
%   now forbid null cells

% v7 Mercury
%   re-introduction of direction choice

% v7.1
%   for equal values, winner is the one with the highest nb of same
%   neighbours

% v8 Venus
% introduction of weight to choose next inner cell

% v9 Earth
% change direction given history

% NEXT JOB TO weight differently given map

%% CONVENTIONS

% CARTE
% representation en vecteur (comme resultat attendu)
%   - board = carte initiale
%   - carte = carte tranformee
%   - dim = [hauteur largeur]

% INDICES
% Sur carte initiale
%   - X : largeur selon horizontale (vers la droite)
%   - Y : hauteur selon verticale (vers le bas)

% VINE
% usedCellses : true si deja utilise

% MOUVEMENTS
% as the result

% DIRECTIONS
% 1: top
% 2: right
% 3: bottom
% 4: left

% VARIABLES GLOBALES (pour l'instant)
% HEIGHTH           hauteur de la carte
% WIDTH             largeur de la carte
% DIM               dimensions de la carte
% NB_ELEMENTS       nombre de cases de la carte
% carte             carte courante (apres mouvements precedents)
% usedCells         vecteur des indices deja utilises
% vine              vecteur de vine, dans l'ordre coissant
% lastDir           derniere direction utilisee
% moves             liste des moves
% cw_acw            0 = ACW, 1 = CW

% CONVENTIONS
% k, j              indice d'un vecteur
% ind, indice       numero d'indice dans la carte


%% FONCTION PRINCIPALE
function [finalMoves, finalVine] = solver(board, limit)

    global HEIGHTH WIDTH DIM NB_ELEMENTS LIMIT
    global carte
    global usedCells vine lastDir
    global moves nbMoves
    global aNB aCOST aVALUE aDIR
    global cw_acw
    
% CONSTANTES
    HEIGHTH = size(board, 1);
    WIDTH = size(board, 2);
    DIM = [HEIGHTH, WIDTH];
    NB_ELEMENTS = numel(board);
    LIMIT = limit;
    
% INITIALISATIONS
    % carte remodelee
    carte = reshape(board, NB_ELEMENTS, 1);
    usedCells = zeros(NB_ELEMENTS, 1);
    
    % pas de deplacement initial...
    moves = [];
    nbMoves = 0;
    
    % vine initial = valeur maximale
    vine = positionInitiale();
    usedCells(vine) = 1;
    
    % derniere direction peu importe
    lastDir = 1;
    
    % clockwise
    cw_acw = 0;
    
    % sets weights
    setWeights();
    
% RESOLUTION
    while addCellToVine(nextCell(vine(1)));
    end
    addCellToVine(voisinsValides(vine(1)));
    
% MISE EN FORME
    finalVine = vine;
    finalMoves = moves;
end


%% ANNEXES

function [] = setWeights()
% set weights given board
    global aNB aCOST aVALUE aDIR
    global carte
    
        %aNB = 3;
        %aCOST = 20;
        %aVALUE = 30;
        %aDIR = 1;

        %aNB = 3;
        %aCOST = 6;
        %aVALUE = 20;
        %aDIR = 1;

end

function ind = nextCell(currentIndex)
% gives next cell
% eventually modify board

% for each possibility
% move = move to achieve
% cost = cost of the move(s)

    global carte nbMoves LIMIT lastDir cw_acw
    
    % takes neighbours
%disp('=================================================')
%disp(['Val courante: ' num2str(carte(currentIndex))])
    [index dir] = voisinsValidesSansQ2Sac(currentIndex);
    cost = zeros(length(index), 1);
    move = zeros(length(index), 2);

    if nbMoves<LIMIT
        % for moves, looks in all neighbours
        [indexAllNeighbours dirAllNeighbours] = voisins(currentIndex);
        for k=1:length(indexAllNeighbours)
            indNext = voisinsValides(indexAllNeighbours(k), currentIndex);
            if ~isempty(indNext)
                index = [index ; indNext];
                vectorOne = ones(length(indNext), 1);
                % cost is null if replaced cell cannot be used
                % (value higher than current)
                costNext = carte(currentIndex)*vectorOne .* (carte(indNext) <= carte(currentIndex));
                cost = [cost ; costNext];
                move = [move; [indNext indexAllNeighbours(k)*vectorOne]];
                dir = [dir; dirAllNeighbours(k)*vectorOne];
            end
        end
    end

    if ~isempty(index)
        
        nbSameVal = zeros(length(index), 1);
        for k=1:length(index)
            % if rank 1...
            if move(k, 1) == 0
                nbSameVal(k) = nbOfSameValueInNeighbours(index(k));
            % ... if rank 2, check if one is deleted
            else
                nbSameVal(k) = nbOfSameValueInNeighbours(move(k, 2)) ...
                    - (carte(index(k)) == carte(move(k, 2)));
            end
        end
        nbSameVal = min(nbSameVal, 4);

        kWinner = weights(nbSameVal, cost, index, dir, move);
        
        % does the move if necessary
        if move(kWinner, 1) > 0 && doMove(move(kWinner,1), move(kWinner,2));
            ind = move(kWinner, 2);
        else
            ind = index(kWinner);
        end
        
        % update direction
        % if this move is CW then try to turn CW for next moves
        if mod(4 + dir(kWinner) - lastDir, 4) == 1
            cw_acw = 1;
        end
        % if this move is ACW then try to turn ACW for next moves
        if mod(4 + dir(kWinner) - lastDir, 4) == 3
            cw_acw = 0;
        end
        % if no turn keep the same CW/ACW
        lastDir = dir(kWinner);
    else
        ind = [];
    end
end

function kWinner = weights(nbSameVal, cost, index, dir, move)
% finds the best index
    global carte
    global aNB aCOST aVALUE aDIR
    
        weight = [nbSameVal cost carte(index) directionPrivilegiee(dir)] ...
                    * [-aNB ; aCOST ; -aVALUE ; -aDIR];
        %disp('==========================================');
        [nbSameVal cost carte(index) dir directionPrivilegiee(dir) weight move];
        
        [v k] = sort(weight);
        kWinner = k(1);
end

function nbVal = nbOfSameValueInNeighbours(curIndex)
% retunrs the nb of neighbours and neighbours of neighbours
% having same value as ind
    global carte
    
    indexAllNeighbours = voisins(curIndex);
    N = length(indexAllNeighbours);
    for k=1:N
        indNext = voisinsValides(indexAllNeighbours(k), curIndex);
        if ~isempty(indNext)
            indexAllNeighbours = [indexAllNeighbours ; indNext];
        end
    end

    nbVal = sum(carte(indexAllNeighbours) == carte(curIndex));
end

function [indice direction] = voisins(ind)
% returns neighbours
% eliminates used cells
    global HEIGHTH WIDTH usedCells
    
    % init
    indice = [];
    direction = [];
    
    % takes care of borders
    if mod(ind, HEIGHTH) ~= 1 && HEIGHTH > 1
        indice = [indice ; ind - 1];
        direction = [direction ; 1];
    end
    if ind <= HEIGHTH*(WIDTH-1)
        indice = [indice ;  ind + HEIGHTH];
        direction = [direction ; 2];
    end
    if mod(ind, HEIGHTH) ~= 0
        indice = [indice ; ind + 1];
        direction = [direction ; 3];
    end
    if ind > HEIGHTH
        indice = [indice ; ind - HEIGHTH];
        direction = [direction ; 4];
    end
    
    % takes care of already used cells
    index = ~usedCells(indice);
    
    if any(index)
        indice = indice(index);
        direction = direction(index);
    else
        indice = [];
        direction = [];
    end
end

function [indice direction] = voisinsValides(ind, ind2compare)
% retourne les indices voisins
% seulement ceux dont la valeur est inferieure a la courante
% et seulement les non nuls

% les ordonne selon leur direction
    
    global carte
    
    % initializations
    [indice direction] = voisins(ind);
    
    % ejecte les cases avec des valeurs > ind2compare
    if nargin == 2
        index = carte(indice) <= carte(ind2compare);
    else
        index = carte(indice) <= carte(ind);
    end
        
    % ejecte les cases nulles
    index = index & (carte(indice) ~= 0);
    
    if any(index)
        indice = indice(index);
        direction = direction(index);
    else
        indice = [];
        direction = [];
    end
end

function [indice direction] = voisinsValidesSansQ2Sac(ind)
% retourne les indices voisins
% seulement ceux dont la valeur est inferieure a la courante
% et seulement ceux qui ne sontpas encore utilises
% et seulement ceux qui ne sont pas des culs de sac

    [indice direction] = voisinsValides(ind);
    index = ~culDeSac(indice);
    if any(index)
        indice = indice(index);
        direction = direction(index);
    else
        indice = [];
        direction = [];
    end
end

function weight = directionPrivilegiee(dir)
% returns the weights of the directions in vector dir
% we want it to turn clockwise
% highest = better
    global lastDir cw_acw
    
    % for direction 1
    if cw_acw == 1
        dirFor1 = [2; 3; 0; 1];
    else
        dirFor1 = [2; 1; 0; 3];
    end
    weight = dirFor1(1+mod(8 + (dir-lastDir), 4));
end

function bol = culDeSac(inds)
% retourns true if cell is in a cul de sac
% i.e. there are no valid neighbours
% ok for vector
    
    % initializations
    bol = ones(1, length(inds));
    
    % work
    for k=1:length(inds)
        indice = voisinsValides(inds(k));
        if any(indice)
            bol(k) = 0;
        end 
    end
end

function indice = positionInitiale()
% retourne le point initial
    global carte NB_ELEMENTS
    % prend le max (rapide)
    [valeur indice] = max(carte);
    
    % compare la somme des valeurs voisins (lent)
    %somme = zeros(NB_ELEMENTS, 1);
    %for ind = 1:NB_ELEMENTS
    %    [indiceVoisins valeurVoisin] = voisinsValidesSansQ2Sac(ind);
    %    somme(ind) = carte(ind) + sum(valeurVoisin);
    %end
    %[valeur indice] = max(somme);
end

function ok = addCellToVine(ind)
% add a cell to vine
% inf ind has several values, takes the first one
    global vine usedCells
    ok = ~isempty(ind);
    if ok
        vine = [ind(1) ; vine];
        usedCells(ind(1)) = 1;
    end
end

function ok = doMove(indOrig, indDest)
% move a cell from indOrig to indDest
    global carte usedCells
    global moves nbMoves LIMIT
    ok = (~( usedCells(indOrig) || usedCells(indDest) )) && nbMoves<LIMIT;
    if ok
        carte(indDest) = carte(indOrig);
        carte(indOrig) = 0;
        moves = [moves; [indOrig indDest]];
        nbMoves = nbMoves + 1;
    end
end