2011-11-09 12:00:00 UTC

# 1_Biforc

Status: Passed
Results: 77864587 (cyc: 35, node: 1780)
CPU Time: 67.562
Score: 778929.0
Submitted at: 2011-11-08 20:27:07 UTC
Scored at: 2011-11-08 20:29:16 UTC

Current Rank: 1279th (Highest: 963rd )
Based on: 1_Biforc (diff)
Basis for: 1_BiforcGNS (diff)

Code
```function [moves, vine] = solver(board, limit)
% SOLVER Sample solver for the MATLAB Vines Contest

% The MATLAB Contest Team
% Copyright 2011 The MathWorks, Inc.
%FLM
%Nome submission: 3_Biforc

moves = [];
%[ignore,vine] = max(board(:));

numeroNodi=size(board,1)*size(board,2);
if numeroNodi==1
vine(1)=1;
else
%innanzitutto calcoliamo il vine migliore senza nessun spostamento
numRighe=size(board,1);
%----------------------------------------------------------
%stabiliamo il valore massimo
[valMaxColonna riga]=max(board);
[valMax col]=max(valMaxColonna);
%assignin('base', 'valMax', valMax);
%----------------------------------------------------------
%stabiliamo il valore minimo
[valMinColonna rigamin]=min(board);
[valMin colmin]=max(valMinColonna);
%assignin('base', 'valMax', valMax);
%----------------------------------------------------------
%calcoliamo il valore medio delle caselle:
totBoard=0;
for riga=1:size(board,1)
for col=1:size(board,2)
totBoard=totBoard+board(riga, col);
end
end
valMedio=totBoard/numeroNodi;
%----------------------------------------------------------
%calcoliamo la dev standard delle caselle:
%devstdcol=std(board);
%     devstd=0;
%     for riga=1:size(board,1)
%         for col=1:size(board,2)
%             devstd=devstd+(board(riga, col)-valMedio)^2;
%         end
%     end
%     devstd=devstd/(numeroNodi-1);
%     devstd=devstd^0.5;
%----------------------------------------------------------
%     if (devstd/valMedio)<0.1
%         threshold=valMedio-5*devstd; %+(valMax-valMedio)/10;
%     elseif (devstd/valMedio)<0.5
%         threshold=valMedio-0.25*devstd;
%     else
%         threshold=valMedio+0.5*devstd;
%     end

threshold=valMax;
%     x = valMin:1:valMax;
%     y = reshape(board,1,size(board,1)*size(board,2));
%     figure(1), hist(y,x)

%----------------------------------------------------------
maxValVine=0; %
%vine(1)=1;
%----------------------------------------------------------
numNodiStartProcessati=0;
%----------------------------------------------------------
%Ottimizziamo il Board
%[moves board]=ottimizzaBoard(board,limit)
%----------------------------------------------------------
%
for riga=1:size(board,1)
for col=1:size(board,2)
if board(riga, col)>=threshold
numNodiStartProcessati=numNodiStartProcessati+1;
%calcoliamo il Path, solo se il Nodo di partenza ha un valore
%superiore a quello di Soglia
nodoStart=sub2ind(size(board), riga, col);

%CALCOLIAMO IL MIGLIOR PATH per questo nodoStart
valBestPathCurrent=0;
[valBestPathCurrent bestPathCurrent]=calcolaBestPath(nodoStart,board);

%ora bestPathCurrent contiene il Path a maggior valore per
%questo Nodo di Partenza
if valBestPathCurrent> maxValVine
maxValVine=valBestPathCurrent;
vinelen=size(bestPathCurrent,2);
vine=zeros(1,vinelen);
%il vine è inverso risp. al bestPathCurrent
for k=1:vinelen
vine(k)=bestPathCurrent(1,vinelen-k+1);
end
end
end
end %next Nodo Partenza
end %next Nodo Partenza

%assignin('base', 'valMax', tempvineValMax);

%OTTIMIZZAZIONE----------------------------------------------
numnodo=1;
len=size(vine,2);
if len>3
if limit>0
%moves=zeros(limit,2);
numOttimizzazioni=0;
Ottimizza=1;

while Ottimizza>0
indNodo=vine(len-numnodo+1);
indNododaOpt=vine(len-numnodo);
opt=zeros(1,4);
%esiste Elemento per ottimizzare il Path?

%esiste elemento SOPRA? indice mod numRighe != 1
if mod(indNododaOpt,numRighe)~=1
%esiste, migliora il Path?
opt(1)=(board(indNododaOpt-1)-board(indNododaOpt));
if opt(1)>0
%ottimizza: controlliamo che non sia > del nodo di partenza
if board(indNododaOpt-1)-board(indNodo)>0
%è > del nodo di partenza: NON possibile
opt(1)=0;
end
%controlliamo se già appartiene al vine
if appartienevine(vine,indNododaOpt-1)==1
%appartiene
opt(1)=0;
end
else
%Non Ottimizza
opt(1)=0;
end
else
%NON Esiste
opt(1)=0;
end
%--------------------------------------------------------
%esiste elemento SOTTO? indice mod numRighe != 0
if mod(indNododaOpt,numRighe)~=0
%esiste, migliora il Path?
opt(2)=(board(indNododaOpt+1)-board(indNododaOpt));
if opt(2)>0
%ottimizza: controlliamo che non sia > del nodo di partenza
if board(indNododaOpt+1)-board(indNodo)>0
%è > del nodo di partenza: NON possibile
opt(2)=0;
end
%controlliamo se già appartiene al vine
if appartienevine(vine,indNododaOpt+1)==1
%appartiene
opt(2)=0;
end
else
%Non Ottimizza
opt(2)=0;
end
else
%NON Esiste
opt(2)=0;
end
%--------------------------------------------------------
%esiste elemento a SX?
if indNododaOpt>numRighe
%esiste, migliora il Path?
opt(3)=(board(indNododaOpt-numRighe)-board(indNododaOpt));
if opt(3)>0
%ottimizza: controlliamo che non sia > del nodo di partenza
if board(indNododaOpt-numRighe)-board(indNodo)>0
%è > del nodo di partenza: NON possibile
opt(3)=0;
end
%controlliamo se già appartiene al vine
if appartienevine(vine,indNododaOpt-numRighe)==1
%appartiene
opt(3)=0;
end
else
%Non Ottimizza
opt(3)=0;
end

else
%NON Esiste
opt(3)=0;
end
%--------------------------------------------------------
%esiste elemento a DX?
if indNododaOpt+numRighe < numeroNodi
%esiste, migliora il Path?
opt(4)=(board(indNododaOpt+numRighe)-board(indNododaOpt));
if opt(4)>0
%ottimizza: controlliamo che non sia > del nodo di partenza
if board(indNododaOpt+numRighe)-board(indNodo)>0
%è > del nodo di partenza: NON possibile
opt(4)=0;
end
%ottimizza: controlliamo se già appartiene a lvine
if appartienevine(vine,indNododaOpt+numRighe)==1
%appartiene
opt(4)=0;
end
else
%Non Ottimizza
opt(4)=0;
end
else
%NON Esiste
opt(4)=0;
end
%--------------------------------------------------------
%SCELTA NODO che ottimizza: il 4°
[opt,arrayIndiciNodiOpt] = sort(opt);
if opt(4)>0
%tutti i check OK: Ottimizziamo
numOttimizzazioni=numOttimizzazioni+1;
switch arrayIndiciNodiOpt(4)
case 1 %SOPRA
moves(numOttimizzazioni,1)=indNododaOpt-1;
board(indNododaOpt)=board(indNododaOpt-1);
board(indNododaOpt-1)=0;
case 2 %SOTTO
moves(numOttimizzazioni,1)=indNododaOpt+1;
board(indNododaOpt)=board(indNododaOpt+1);
board(indNododaOpt+1)=0;
case 3 % a SX
moves(numOttimizzazioni,1)=indNododaOpt-numRighe;
board(indNododaOpt)=board(indNododaOpt-numRighe);
board(indNododaOpt-numRighe)=0;
case 4 % a DX
moves(numOttimizzazioni,1)=indNododaOpt+numRighe;
board(indNododaOpt)=board(indNododaOpt+numRighe);
board(indNododaOpt+numRighe)=0;
end
moves(numOttimizzazioni,2)=indNododaOpt;
limit=limit-1;
%incrementi
numnodo=numnodo+2;
else
numnodo=numnodo+1;
end

%check fine ottimizzazione
if (limit==0)
Ottimizza=0;
elseif (numnodo>=len-2)
Ottimizza=0;
%             elseif board(indNodo)<=valMedio
%                 Ottimizza=0;
end
end
end
end

end

end %END FUNCTION solver

function [valBestPathCurrent bestPathCurrent]=calcolaBestPath(nodoStart,board)

%miglior Path calcolato finora
bestPathCurrent=zeros(1,1);
valBestPathCurrent=0;

%matrice dei Path
matricePathIniz=zeros(1,1);
matricePathIniz(1,1)=nodoStart;

%matrice che continene i possibili Path, per questo nodoStart
numPathTot=1;
numPathTotNuovo=1;

%valPathIniz=zeros(numPathTot,1);
%valPathIniz(1,1)=board(nodoStart);

%matrice dei Path terminati nel ciclo While
matricePathTerminati=zeros(numPathTot,1);
%valPathTerminati=zeros(numPathTot,1);

numPathInseriti=0;
numPathTerminatiTot=0;

lenMaxPath=1;
%-------------------------------------------------------------
FineWhile=1;
while FineWhile>0

FineWhile=0; %se dopo non viene aggiornato termina

%--------Calcolo Nodo Successivo per ogni Path-----------------------
%per ogni Path calcoliamo il/i Nodo/i successivo/i
numPathTotNuovo=0;
numPathTerminati=0;
valoriNext=zeros(numPathTot,4);
indiciNext=zeros(numPathTot,4);
allungaPath=1;
for numpath=1:numPathTot
nodoCorrente=matricePathIniz(numpath,lenMaxPath);

%         [valoriNext(numpath,:) indiciNext(numpath,:)]=...
%             calcolaNext(board,nodoCorrente,matricePathIniz(numpath,:),numPathTot);
indiciNext(numpath,:)=...
calcolaNext(board,nodoCorrente,matricePathIniz(numpath,:),numPathTot);

temp=find(indiciNext(numpath,:));
nonnull=size(temp,2);
if nonnull==0
%numPathTotNuovo=numPathTotNuovo+1;
%questo Path è terminato
numPathTerminati=numPathTerminati+1;
numPathTerminatiTot=numPathTerminatiTot+1;
else
numPathTotNuovo=numPathTotNuovo+nonnull;
end

if numPathTerminati>0
matricePathTerminati=zeros(numPathTerminati,lenMaxPath);
indiciPathTerminatiIniz=zeros(1,numPathTerminati);
indiciPathTerminati=zeros(1,numPathTerminati);
end

end
if numPathTerminati==numPathTot
allungaPath=0;
end

%--------Aggiornamento Matrice Path-----------------------------------
%matricePath=zeros(numPathTotNuovo,numeroNodi+1);
if allungaPath==1
lenMaxPath=lenMaxPath+1;
matricePath=zeros(numPathTotNuovo,lenMaxPath);
%valPath=zeros(1,numPathTotNuovo);

%aggiorniamo la matrice path
numPathInseriti=0;
countPathTerminati=0;
%per ogni Path della Vcchia MatricePath, inseriamo gli eventuali nuovi Path
for numPathVecchio=1:numPathTot

%elementi diversi da 0
biforc=0;
for countbif=1:4
if indiciNext(numPathVecchio,countbif)>0
biforc=biforc+1;
end
end
%             temp=find(indiciNext(numPathVecchio,:)) ;
%             biforc=size(temp,2);
switch biforc

case 0
%questo Path è finito:
%copiamo tutto il vecchio path nella matricePathTerminati
%numPathInseriti=numPathInseriti+1;
countPathTerminati=countPathTerminati+1;
%matricePath(numPathInseriti,:)=[matricePathIniz(numPathVecchio,:) 0];
matricePathTerminati(countPathTerminati,:)=matricePathIniz(numPathVecchio,:);

indiciPathTerminatiIniz(countPathTerminati)=numPathVecchio;
indiciPathTerminati(countPathTerminati)=numPathInseriti;
case 1
%questo Path continua, ma non si biforca
FineWhile=1;
numPathInseriti=numPathInseriti+1;
matricePath(numPathInseriti,:)=...
[matricePathIniz(numPathVecchio,:) indiciNext(numPathVecchio,1)];

otherwise
%questo Path si biforca
FineWhile=1;
for numbiforc=1:biforc
numPathInseriti=numPathInseriti+1;
matricePath(numPathInseriti,:)=...
[matricePathIniz(numPathVecchio,:) indiciNext(numPathVecchio,numbiforc)];

end
end %Switch

end % Next Path vecchio

%per il prossimo ciclo
matricePathIniz=zeros(numPathTotNuovo,lenMaxPath);
matricePathIniz=matricePath;
numPathTot=numPathTotNuovo;

else % Tutti i Path presenti nella matricePathIniz sono terminati
for numPathVecchio=1:numPathTot
indiciPathTerminatiIniz(numPathVecchio)=numPathVecchio;
indiciPathTerminati(numPathVecchio)=numPathVecchio;
matricePathTerminati(numPathVecchio,:)=matricePathIniz(numPathVecchio,:);
end
FineWhile=0;
end
%--------Fine Aggiornamento Matrice Path------------------------------

if numPathTerminati>0
%1 o più Path sono terminati durante questo ciclo
%  questi Path sono nella matricePathTerminati
for countPathTerminati=1:numPathTerminati
%stabiliamo quallo che ha val Max
valpathtemp=0;
for k=1:size(matricePathTerminati,2)
valpathtemp=valpathtemp+board(matricePathTerminati(countPathTerminati,k));
end
if (valpathtemp> valBestPathCurrent)
valBestPathCurrent = valpathtemp;
bestPathCurrent=zeros(1,size(matricePathTerminati,2));
bestPathCurrent=matricePathTerminati(countPathTerminati,:);
end
end
% matricePathTerminatiIniz=zeros(numPathTerminatiTot,lenMaxPath-1);
%  matricePathTerminatiIniz=matricePathTerminati;

else %nessun Path è terminato
%ricopiamo la matrice
%         matricePathIniz=zeros(numPathTotNuovo,lenMaxPath);
%         matricePathIniz=matricePath;

%numPathTot=numPathTotNuovo;
end %end IF numPathTerminati

%per il prossimo ciclo
%     matricePathIniz=zeros(numPathTotNuovo,lenMaxPath);
%     matricePathIniz=matricePath;
%     numPathTot=numPathTotNuovo;

end %end WHILE

end %END Function

function [indiciNext]=calcolaNext(board,nodoCorrente,tempPath,numPathContemporanei)
%function [valoriNext indiciNext]=calcolaNext(board,nodoCorrente,tempPath,numPathContemporanei)
%dato un nodo di Input, calcola Valori e Indici dei nodi UP-DOWN-LEFT-RIGHT
% maxSizeMatricePath=1000;
% lenPath=size(tempPath,2);
% numMaxPathContemporanei=maxSizeMatricePath/lenPath;
numMaxPathContemporanei=1;

numeroNodi=size(board,1)*size(board,2);
numRighe=size(board,1);
lenpath=size(tempPath,2);

valoriNext=zeros(1,4);
indiciNext=zeros(1,4);

if nodoCorrente>0
if numeroNodi>1

%----------------------------------------------------------

valNodoCorrente=board(nodoCorrente);

if numRighe==1
%gli spostamento UP e DOWN  NON sono possibili
valoriNext(1)=0;
valoriNext(2)=0;
indiciNext(1)=0;
indiciNext(2)=0;
else
%costo spostamento UP
%verifichiamo se è possibile spostarsi SOPRA: indice mod numRighe != 1
if mod(nodoCorrente,numRighe)~=1
valoriNext(1)=board(nodoCorrente-1);
indiciNext(1)=nodoCorrente-1;
else
valoriNext(1)=0;
indiciNext(1)=0;
end
else
%lo spostamento UP NON è possibile
valoriNext(1)=0;
indiciNext(1)=0;
end
%verifichiamo se è possibile spostarsi SOTTO: indice mod numRighe != 0
if mod(nodoCorrente,numRighe)~=0
valoriNext(2)=board(nodoCorrente+1);
indiciNext(2)=nodoCorrente+1;
else
valoriNext(2)=0;
indiciNext(2)=0;
end
else
%lo spostamento DOWN NON è possibile
valoriNext(2)=0;
indiciNext(2)=0;
end
end

%verifichiamo se è possibile spostarsi a SX: indice > numRighe
if (nodoCorrente > numRighe)
valoriNext(3)=board(nodoCorrente-numRighe);
indiciNext(3)=nodoCorrente-numRighe;
else
valoriNext(3)=0;
indiciNext(3)=0;
end
else
%lo spostamento NON è possibile
valoriNext(3)=0;
indiciNext(3)=0;
end
%verifichiamo se è possibile spostarsi a DX: indice + numRighe < numeroNodi
if (nodoCorrente + numRighe < numeroNodi)
valoriNext(4)=board(nodoCorrente+numRighe);
indiciNext(4)=nodoCorrente+numRighe;
else
valoriNext(4)=0;
indiciNext(4)=0;
end
else
%lo spostamento NON è possibile
valoriNext(4)=0;
indiciNext(4)=0;
end

%verifichiamo che tali valori Non appartengono già al Path
for k=1:4
if indiciNext(k)>0
for  h=1:lenpath
if tempPath(h)==indiciNext(k)
valoriNext(k)=0;
indiciNext(k)=0;
break
end
end
end
end

%stabiliamo per ora che le biforcazioni si hanno solo a parità di
%valore (dobbiamo scegliere i valori minori)
[valoriNext , ind]=  sort(valoriNext,'descend');
tempindiciNext=zeros(1,4);
for k=1:4
tempindiciNext(k)=indiciNext(k);
end
for k=1:4
indiciNext(k)=tempindiciNext(ind(k));
end

for k=2:4
if (valoriNext(k)<valoriNext(1))
valoriNext(k)=0;
indiciNext(k)=0;
end
end

%----------SOGLIA sul numero di Path contemporanei
if numPathContemporanei>numMaxPathContemporanei
for k=2:4
valoriNext(k)=0;
indiciNext(k)=0;
end
end
%----------------------------------------------
end
end
end

function appartiene=appartienevine(vine,indice)
%appartiene=1 se indice appartiene al vine
%appartiene=0 se indice non appartiene al vine
appartiene=0;
for k=1:size(vine,2)
if indice==vine(k)
appartiene=1;
break
end
end
end```