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
guadagno=(valNodoCorrente-board(nodoCorrente-1));
if guadagno>=0
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
%guadagno spostamento DOWN
%verifichiamo se è possibile spostarsi SOTTO: indice mod numRighe != 0
if mod(nodoCorrente,numRighe)~=0
guadagno=(valNodoCorrente-board(nodoCorrente+1));
if guadagno>=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
%guadagno spostamento LEFT
%verifichiamo se è possibile spostarsi a SX: indice > numRighe
if (nodoCorrente > numRighe)
guadagno=(valNodoCorrente-board(nodoCorrente-numRighe));
if guadagno>=0
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
%guadagno spostamento RIGHT
%verifichiamo se è possibile spostarsi a DX: indice + numRighe < numeroNodi
if (nodoCorrente + numRighe < numeroNodi)
guadagno=(valNodoCorrente-board(nodoCorrente+numRighe));
if guadagno>=0
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
|
