In che cosa consiste il nostro lavoro? Alcuni progetti sono molto articolati e non sono semplici siti web. Ve li racconteremo in modo più dettagliato attraverso qualche post.
Partiamo con l’Algoritmo Round Robin in PHP. Che cos’è e per cosa l’abbiamo usato?
Algoritmo Round Robin in PHP
Abbiamo di recente sviluppato un progetto per gestire la i gironi sportivi. Per creare le giornate con i giusti abbinamenti tra le squadre in modo che non ci siano ripetizioni il concetto a cui fare riferimento è quello del round-robin.
Dato che abbiamo fatto un po’ di prove prima di trovare la formula giusta per sviluppare l’algoritmo round robin in PHP ve la postiamo, ma prima qualche curiosità.
Che cos’è il Round Robin?
La locuzione round-robin indica un’attività in cui i partecipanti si alternano, in modo regolare, nel suo svolgimento.
L’espressione deriva dal termine «ruban rond» («nastro rotondo» in lingua francese). Nel XVII secolo, indicava l’usanza di disporre in cerchio le firme di una petizione inviata a un’autorità, così da rendere impossibile individuare un capo o risalire a una gerarchia tra i firmatari.
Nel nostro caso una competizione sportiva, con il formato del round-robin, prevede che ogni squadra affronti tutte le altre. Questa formula è conosciuta anche con il nome di Girone all’italiana.
Che cos’è il Girone all’italiana?
Il girone all’italiana (o torneo all’italiana) prevede lo svolgimento di incontri diretti tra tutti i partecipanti in tutti gli abbinamenti possibili. Il numero di squadre sufficienti è almeno 3, in quanto un confronto tra 2 causerebbe l’eliminazione di una di esse.
Il calendario della competizione è stilato dall’algoritmo di Berger, che determina le “giornate” o “turni” accoppiando le squadre; in caso di girone con partite di andata e ritorno, ovvero con l’ordine dei campi invertito, ogni formazione usufruisce del fattore casalingo lo stesso numero di volte.
Algoritmo di Berger
Prende il nome dal suo inventore, lo svizzero Johann Berger. Lo riportiamo di seguito.
<?php
function AlgoritmoDiBerger($arrSquadre)
{
$numero_squadre = count($arrSquadre);
if ($numero_squadre % 2 == 1) {
$arrSquadre[]="BYE"; // numero giocatori dispari? aggiungere un riposo (BYE)!
$numero_squadre++;
}
$giornate = $numero_squadre - 1;
/* crea gli array per le due liste in casa e fuori */
for ($i = 0; $i < $numero_squadre /2; $i++)
{
$casa[$i] = $arrSquadre[$i];
$trasferta[$i] = $arrSquadre[$numero_squadre - 1 - $i];
}
for ($i = 0; $i < $giornate; $i++)
{
/* stampa le partite di questa giornata */
echo '<br />'.($i+1).'a Giornata<br />';
/* alterna le partite in casa e fuori */
if (($i % 2) == 0)
{
for ($j = 0; $j < $numero_squadre /2 ; $j++)
{
echo ' '.$trasferta[$j].' - '.$casa[$j].'<br />';
}
}
else
{
for ($j = 0; $j < $numero_squadre /2 ; $j++)
{
echo ' '.$casa[$j].' - '.$trasferta[$j].'<br />';
}
}
// Ruota in gli elementi delle liste, tenendo fisso il primo elemento
// Salva l'elemento fisso
$pivot = $casa[0];
/* sposta in avanti gli elementi di "trasferta" inserendo
all'inizio l'elemento casa[1] e salva l'elemento uscente in "riporto" */
array_unshift($trasferta, $casa[1]);
$riporto = array_pop($trasferta);
/* sposta a sinistra gli elementi di "casa" inserendo all'ultimo
posto l'elemento "riporto" */
array_shift($casa);
array_push($casa, $riporto);
// ripristina l'elemento fisso
$casa[0] = $pivot ;
}
} La nostra versione
In rete si trovato vari algoritmi round-robin, ma il problema riscontrato in tutti era che in ogni abbinamento la prima squadra fornita avrebbe sempre giocato in casa.
Seguendo, quindi, il ragionamento previsto dal round-robin e cercandone la definizione abbiamo trovato l’algoritmo di Berger su Wikipedia (era proprio lì sotto al nostro naso!) e l’abbiamo modificato. In questo modo dato l’array delle squadre e il tipo di girone (andata o ritorno) vengono restituiti gli abbinamenti per ogni giornata.
<?php
function AlgoritmoDiBerger( $arrSquadre, $andata_ritorno ) {
$numero_squadre = count( $arrSquadre );
if ( $numero_squadre % 2 == 1 ) {
$arrSquadre[] = "BYE"; // numero giocatori dispari? aggiungere un riposo (BYE)!
$numero_squadre ++;
}
$giornate = $numero_squadre - 1;
/* crea gli array per le due liste in casa e fuori */
for ( $i = 0; $i < $numero_squadre / 2; $i ++ ) {
$casa[ $i ] = $arrSquadre[ $i ];
$trasferta[ $i ] = $arrSquadre[ $numero_squadre - 1 - $i ];
}
for ( $i = 0; $i < $giornate; $i ++ ) {
/* alterna le partite in casa e fuori */
if ($andata_ritorno == 'a') {
if ( ( $i % 2 ) == 0 ) {
for ( $j = 0; $j < $numero_squadre / 2; $j ++ ) {
$c = $trasferta[ $j ];
$o = $casa[ $j ];
$abbinamenti[ $i ][] = array( $c, $o );
}
} else {
for ( $j = 0; $j < $numero_squadre / 2; $j ++ ) {
$o = $trasferta[ $j ];
$c = $casa[ $j ];
$abbinamenti[ $i ][] = array( $c, $o );
}
}
} else {
if ( ( $i % 2 ) == 0 ) {
for ( $j = 0; $j < $numero_squadre / 2; $j ++ ) {
$o = $trasferta[ $j ];
$c = $casa[ $j ];
$abbinamenti[ $i ][] = array( $c, $o );
}
} else {
for ( $j = 0; $j < $numero_squadre / 2; $j ++ ) {
$c = $trasferta[ $j ];
$o = $casa[ $j ];
$abbinamenti[ $i ][] = array( $c, $o );
}
}
}
// Ruota in gli elementi delle liste, tenendo fisso il primo elemento
// Salva l'elemento fisso
$pivot = $casa[0];
/* sposta in avanti gli elementi di "trasferta" inserendo
all'inizio l'elemento casa[1] e salva l'elemento uscente in "riporto" */
array_unshift( $trasferta, $casa[1] );
$riporto = array_pop( $trasferta );
/* sposta a sinistra gli elementi di "casa" inserendo all'ultimo
posto l'elemento "riporto" */
array_shift( $casa );
array_push( $casa, $riporto );
// ripristina l'elemento fisso
$casa[0] = $pivot;
}
return $abbinamenti;
}Come abbiamo già sperimentato più volte, il riutilizzo del codice, anche di altri è fondamentale per sbrogliare parti di programmazione. Ecco perchè abbiamo creato questa rubrica: speriamo di essere di aiuto ad altri programmatori e di far capire ancora meglio ai clienti cosa c’è dietro ai loro prodotti.
Quando sviluppate e vi serve un aiuto a quali siti fate riferimento solitamente?
Foto di Monica Sauro da Unsplash