Algoritmo e funzione JavaScript per il gioco Dobble

Avete mai sentito parlare di Dobble? Se avete bambini, scommetto di si! Ad ogni buon conto, si tratta di un gioco da tavolo per grandi e piccini basato sul pattern recognition, ovvero sulla capacità di riconoscere segni e modelli (in questo caso forme e colori) il più velocemente possibile.

Il gioco presenta 55 carte, ciascuna delle quali presenta 8 diversi disegni disposti in ordine sparso. Il gioco è fatto in modo che ogni coppia di carte abbia un solo simbolo in comune, che i giocatori devono trovare nel più breve tempo possibile. Il gioco è uscito nel 2009 con il nome di Spot It!, mentre Dobble è un nome alternativo con cui è stato commercializzato in molti paesi europei (tra cui l'Italia, pubblicato dalla casa editrice Asmodee). Per maggiori informazioni, consigliamo di consultare la pagina del gioco su BoardGameGeek.com.

Se vi siete imbattuti in questo articolo, è probabile che abbiate interesse ad approfondire come hanno fatto i creatori del gioco a realizzare le carte di Dobble in modo tale che ciascuna di esse abbia sempre un (e un solo) simbolo in comune con tutte le altre. In questo articolo proveremo a illustrare questa tecnica, spiegando sinteticamente i principi su cui si basa, in modo da consentire a chiunque di poter creare una sua versione personalizzata di Dobble.

Un problema "geometrico"

Come è facile intuire, si tratta di un risultato che è possibile ottenere mediante l'applicazione di un determinato algoritmo. Nello specifico, si tratta di una funzione per la generazione di serie geometriche combinatorie aventi seguenti caratteristiche:

ciascuna serie deve essere composta da un determinato numero (N) di elementi diversi tra loro;
ciascuna serie deve avere un (e un solo) elemento in comune con ciascuna altra serie;

Nel caso di Dobble, ciascuna serie (la carta) è composta da 8 elementi (i simboli): N è dunque pari a 8. Sappiamo inoltre che il mazzo è composto da 55 carte. La nostra funzione dovrà quindi essere in grado di produrre almeno 55 serie, ciascuna delle quali composta da 8 elementi diversi tra loro e aventi 1 (e un solo) elemento in comune con ciascun'altra serie.

Il codice sorgente

La funzione dobble() presente nel codice JavaScript che proponiamo in questo articolo è pensata per generare il massimo numero possibile di serie (e quindi di carte) dato un numero N di elementi presenti su ciascuna carta. Affinché l'algoritmo utilizzato funzioni, N deve avere un valore pari a quello di un qualsiasi numero primo +1: potrà dunque avere un valore pari a 8 (come nel caso di Dobble) ma anche 3, 4, 6, 12, 14, 18, 20 e così via. Nel caso in cui a N sia assegnato un valore non valido, la funzione mostrerà un warning e, con tutta probabilità, una serie di errori prodotti dalla funzione outputTests().

Ovviamente, le serie generate conterranno dei numeri, ciascuno dei quali ha il compito di rappresentare un elemento, o per meglio dire un simbolo, tra quelli presenti sulle nostre carte: il numero 1 corrisponderà al cuore, il numero 2 all'albero, e così via.

// -----------------------------------------------------------------------------------
// Funzione che genera serie geometriche combinatorie per Dobble / Spot it!
// 
// Ciascuna serie generata presenta le seguenti caratteristiche:
//
// - E' composta da N elementi diversi tra loro, dove N è un qualsiasi numero primo +1
// - Contiene sempre un elemento (e uno solo) in comune con le altre.
//
// Rilasciato su licenza GNU - General Public Licence v3.0
// https://www.gnu.org/liceNes/gpl-3.0.en.html
// 
// Darkseal, 2018-2019
// https://www.ryadel.com/algoritmo-funzione-javascript-dobble-spot-it/
// ----------------------------------------------------------------------------------- 
// 
function dobble() {
  var N = 12;     // number of symbols on each card
  var nC = 0;    // progressive number of cards
  var sTot = []; // array of series (cards)
  
  // check if N is valid (it must be a prime number +1)
  if (!isPrime(N-1)) {
    document.write("<pre>ERROR: N value ("+N+") is not a prime number +1:"); 
    document.write(" some tests will fail.</pre>");
  }
  
  // Generate series from #01 to #N
  for (i=0; i <= N-1; i++)  {
    var s = [];
    nC++;
    s.push(1);
    for (i2=1; i2 <= N-1; i2++) {
        s.push((N-1) + (N-1) * (i-1) + (i2+1));
    }
    sTot.push(s);
  }
  
  // Generate series from #N+1 to #N+(N-1)*(N-1)
  for (i= 1; i<= N-1; i++) {
    for (i2=1; i2 <= N-1; i2++) {
      var s = [];
      nC++;
      s.push(i+1);
      for (i3=1; i3<= N-1; i3++) {
        s.push((N+1) + (N-1) * (i3-1) + ( ((i-1) * (i3-1) + (i2-1)) ) % (N-1));
      }
      sTot.push(s);
    }
  }
  
  // Print the series to screen
  outputSeries(sTot);

  // perform 1000 test and print the results to screen
  outputTest(sTot, 1000);
}
  
function isPrime(num) {
  for(var i = 2; i < num; i++) {
    if(num % i === 0) return false;
  }
  return num > 1;
}

function pad(n, width, z) {
  z = z || '0';
  n = n + '';
  return n.length >= width ? n : new Array(width - n.length + 1).join(z) + n;
}

function outputSeries(sTot) {
  var nPad = sTot.length.toString().length;
  var cnt = 0;
  document.write("<div>Printing "+ sTot.length +" series of "+ sTot[0].length +" elements each.</div>");
  document.write("<pre>");
  for (var i in sTot) {
    cnt++;
    var sLog = "#" + pad(cnt,nPad) + ":";
    for (var i2 in sTot[i]) {
      sLog += " " + pad(sTot[i][i2], nPad);
    } 
    document.write(sLog + "\n");
  }
  document.write("</pre>");
}

// test function
// compares n pairs of different series randomly taken from sTot 
// and outputs the results.
function outputTest(sTot, n) {
  var nSucc = 0;
  var nFail = 0;
  var err = "";
  for (i = 0; i < n; i++) {
    var i1 = Math.floor(Math.random() * (sTot.length - 1));
    var i2 = 0;
    do {
      i2 = Math.floor(Math.random() * (sTot.length - 1));
    }
    while (i1 == i2);
    var s1 = sTot[i1];
    var s2 = sTot[i2];
    var nEquals = 0;
    for (var p1 in s1) {
      for (var p2 in s2) {
        if (s1[p1] == s2[p2]) {
          nEquals++;
        }
      }
    }
    if (nEquals == 1) {
      nSucc++;
    }
    else {
      nFail++;
      err += "FAILURES #"+nFail+": Series #"+ s1 +" and series #"+ s2 + " do have "+ nEquals +" numbers in common. +\n";
    }
  }
  document.write("<pre>");
  document.write("Test result (after "+n+" tests):\n");
  document.write("- SUCCESS #: "+nSucc+"\n");
  document.write("- FAILURE #: "+nFail+"\n");
  if (nFail > 0) {
    document.write("<pre>"+ err +"</pre>");
  }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

// -----------------------------------------------------------------------------------

// Funzione che genera serie geometriche combinatorie per Dobble / Spot it!

// Ciascuna serie generata presenta le seguenti caratteristiche:

// - E' composta da N elementi diversi tra loro, dove N è un qualsiasi numero primo +1

// - Contiene sempre un elemento (e uno solo) in comune con le altre.

// Rilasciato su licenza GNU - General Public Licence v3.0

// https://www.gnu.org/liceNes/gpl-3.0.en.html

// Darkseal, 2018-2019

// https://www.ryadel.com/algoritmo-funzione-javascript-dobble-spot-it/

// -----------------------------------------------------------------------------------

function dobble() {

var N = 12; // number of symbols on each card

var nC = 0; // progressive number of cards

var sTot = []; // array of series (cards)

// check if N is valid (it must be a prime number +1)

if (!isPrime(N-1)) {

document.write("<pre>ERROR: N value ("+N+") is not a prime number +1:");

document.write(" some tests will fail.</pre>");

}

// Generate series from #01 to #N

for (i=0; i <= N-1; i++) {

var s = [];

nC++;

s.push(1);

for (i2=1; i2 <= N-1; i2++) {

s.push((N-1) + (N-1) * (i-1) + (i2+1));

}

sTot.push(s);

}

// Generate series from #N+1 to #N+(N-1)*(N-1)

for (i= 1; i<= N-1; i++) {

for (i2=1; i2 <= N-1; i2++) {

var s = [];

nC++;

s.push(i+1);

for (i3=1; i3<= N-1; i3++) {

s.push((N+1) + (N-1) * (i3-1) + ( ((i-1) * (i3-1) + (i2-1)) ) % (N-1));

}

sTot.push(s);

}

// Print the series to screen

outputSeries(sTot);

// perform 1000 test and print the results to screen

outputTest(sTot, 1000);

}

function isPrime(num) {

for(var i = 2; i < num; i++) {

if(num % i === 0) return false;

}

return num > 1;

}

function pad(n, width, z) {

z = z || '0';

n = n + '';

return n.length >= width ? n : new Array(width - n.length + 1).join(z) + n;

}

function outputSeries(sTot) {

var nPad = sTot.length.toString().length;

var cnt = 0;

document.write("<div>Printing "+ sTot.length +" series of "+ sTot[0].length +" elements each.</div>");

document.write("<pre>");

for (var i in sTot) {

cnt++;

var sLog = "#" + pad(cnt,nPad) + ":";

for (var i2 in sTot[i]) {

sLog += " " + pad(sTot[i][i2], nPad);

}

document.write(sLog + "\n");

}

document.write("</pre>");

}

// test function

// compares n pairs of different series randomly taken from sTot

// and outputs the results.

function outputTest(sTot, n) {

var nSucc = 0;

var nFail = 0;

var err = "";

for (i = 0; i < n; i++) {

var i1 = Math.floor(Math.random() * (sTot.length - 1));

var i2 = 0;

do {

i2 = Math.floor(Math.random() * (sTot.length - 1));

}

while (i1 == i2);

var s1 = sTot[i1];

var s2 = sTot[i2];

var nEquals = 0;

for (var p1 in s1) {

for (var p2 in s2) {

if (s1[p1] == s2[p2]) {

nEquals++;

}

if (nEquals == 1) {

nSucc++;

}

else {

nFail++;

err += "FAILURES #"+nFail+": Series #"+ s1 +" and series #"+ s2 + " do have "+ nEquals +" numbers in common. +\n";

}

document.write("<pre>");

document.write("Test result (after "+n+" tests):\n");

document.write("- SUCCESS #: "+nSucc+"\n");

document.write("- FAILURE #: "+nFail+"\n");

if (nFail > 0) {

document.write("<pre>"+ err +"</pre>");

}

La versione presente all'interno di questo articolo potrebbe essere obsoleta: la versione più aggiornata è disponibile su GitHub.

E' possibile provare o modificare questa funzione su qualsiasi browser web utilizzando questo JSFiddle.

Come si può vedere, la funzione effettua due cicli: il primo costruisce un numero di serie pari al numero degli elementi (N) mettendo in prima posizione l'elemento numero 1 e poi riempiendole con elementi in ordine crescente seguendo un percorso "orizzontale". In questo modo, si assicura che tutte le serie prodotte finora avranno l'elemento numero 1 (e soltanto quello) in comune. Questa operazione, come si può vedere dall'immagine, costruisce una matrice che contiene tutti gli elementi.

Il secondo ciclo costruisce tutte le serie rimanenti mettendo in prima posizione gli elementi numero 2, 3, 4, 5 e così via (fino a N) e poi riempiendole con elementi in ordine crescente: stavolta, però, il percorso è sviluppato in "verticale", così da "incrociare" ciascuna serie generata durante il ciclo precedente una (e una sola) volta.

Inoltre, ogni volta in cui il numero in prima posizione cambia, la funzione effettua uno shift incrementale del percorso verticale della serie verso la parte destra della matrice, così da "incrociare" ogni numero di ciascuna colonna verticale una (e una sola) volta.

Da questo si evince anche che il numero di serie diverse tra loro che questo algoritmo è in grado di produrre è pari a N + (N-1) * (N-1). Nel caso di Dobble, in cui N è pari a 8, significa che possiamo avere fino a un massimo di 8 + (8-1)*(8-1) = 57 carte diverse, quindi ben 2 in più del numero di carte contenute nell'edizione italiana. Se i simboli su ogni carta fossero 10, potremmo quindi avere fino a 91 carte diverse; se fossero 12, potremmo averne fino a 133: e così via. Ricordatevi però di assegnare a N un valore pari a un qualsiasi numero primo +1, altrimenti vi ritroverete con un certo numero di serie non valide (che saranno mostrate a schermo dalla funzione di test).

Conclusioni

Per il momento è tutto: mi auguro che questo articolo possa soddisfare la curiosità di quanti si sono interrogati sul funzionamento "matematico" di questo bellissimo gioco.