Salve a tutti. Sono agli sgoccioli per una consegna di laboratorio. L'obiettivo è programmare in C il gioco del Bingo. Il problema più grosso lo sto riscontrando nella generazione delle cartelle. In particolare, nel rispettare il vincolo secondo cui "Per ogni colonna deve essere presente almeno un valore". Provando a generare i numeri singolarmente, (con la rand()) da 1 a 90, non sono riuscito a venire a capo del problema. Per chi non avesse familiarità con il Bingo, le regole di generazione di una cartella sono le seguenti:
-Ogni cartella è composta da 3 righe e 9 colonne (e fin qui...)
-Ogni riga della cartella contiene esattamente 5 valori (e va bene...)
-I numeri vanno disposti nella cartella ordinati per decine:
(1° colonna: numeri da 1 a 9; 2° colonna: numeri 10-19; 3° colonna: 20-29;...; 9°colonna: 80-90) (Anche questo banale)
-Ogni cartella non può contenere numeri duplicati (Banalissimo..)
e poi arriviamo ai due vincoli che riescono a complicare tutto ciò che finora sembrava una sciocchezza:
-Ogni colonna deve avere almeno un valore (non possono esserci colonne vuote)
-Le cartelle vanno generate a gruppi di 6, e le 6 cartelle devono contenere tutti i numeri da 1 a 90, senza ripetizioni
Come ho detto non sono riuscito a trovare un algoritmo che mi permettesse di generare correttamente le cartelle estraendo un numero alla volta. Tuttavia non sono affatto qui per cercare qualcuno che magicamente mi risolva il problema. Anzi, io stesso ho elaborato un algoritmo che mi permette di generare serenamente una cartella del bingo, anche se "casuale" solo in linea di principio. Mi spiego:
-Per prima cosa genero una matrice di 5x18 elementi contenente tutti i 90 numeri in ordine crescente, disposti per riga.
-Estraggo un valore a caso tra 0 e 8, che identificherà una delle prime 9 colonne della suddetta matrice. Successivamente estrarrò un altro valore pseudocasuale tra 7 e 17, che identificherà una delle ultime 11 colonne della matrice. A questo punto ho la certezza che la prima colonna conterrà un numero compreso tra 1 e 9, e la seconda uno tra 80 e 90.
-Estraggo una terza colonna in tutto l'intervallo 0-17, tale che la "distanza" (calcolata via valore assoluto) tra l'indice di colonna più piccolo e quello più grande vi sia una distanza minima di 8 colonne (questo serve a garantire che i valori intermedi coprano tutte le decine della cartella, senza lasciare quindi colonne vuote). Ovviamente ogni estrazione è seguita da un controllo sui valori precedentemente estratti. Se uno stesso valore di colonna è stato estratto in precedenza, viene reiterata la rand().
-Una volta evidenziati in base a questi criteri i 3 indici di colonna della matrice principale (che chiamerò "sorgente"), la cartella viene compilata copiando ognuna delle colonne evidenziate sulla corrispondente riga della cartella. Successivamente provvedo a riempire con degli zeri gli spazi che non contengono valori (le celle bianche della cartella).
A questo punto UNA cartella è fatta. Tenendo traccia (in un array, magari) degli indici di colonna già estratti per questa cartella, se ne può creare un'altra con gli stessi principi che non contenga nessuna delle colonne già estratte. Così si avranno due cartelle LEGALI senz ripetizioni. Per estensione, questo funziona egregiamente anche sui gruppi di 6 cartelle, che esauriranno quindi i 90 numeri della matrice sorgente senza ripetizioni. Il problema però è il seguente:
Capita (non spessissimo, ma purtroppo capita) che le ultime 3 colonne non ancora estratte NON SODDISFINO i requisiti esposti sopra (sulla distanza tra le colonne, sull'appartenenza a determinati range ecc.). In questo caso il programma continua a estrarre numeri casuali finché non ne trova 3 che non siano già stati estratti, e verifica se questa nuova terna verifica le condizioni. Il problema è che è l'UNICA terna rimasta, quindi la estrarrà all'infinito e ogni volta si accorgerà di non poterci costruire una cartella. Quindi il programma non va in crash, non stampa cartelle sbagliate: rimane in un loop infinito quando si trova a calcolare l'ultima cartella di un dato gruppo (che può essere il primo come il sesto), ogni qual volta dovesse capitare una situazione di questo tipo. Faccio un esempio pratico (anceh se questo post sta diventando enorme)
Matrice Sorgente:
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18
19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
TERNE ESTRATTE:
cartella1: 2-12-11
cartella2: 6-17-4
cartella3: 8-16-15
cartella4: 5-14-9
cartella5: 0-10-13
Provando a compilare le cartelle utilizzando le colonne estratte (N.B. la numerazione è da 0 a 17, non da 1 a 18) si ottengono tutte cartelle lecite. Il problema però è che per la sesta cartella, le uniche colonne della "sorgente" non ancora estratte sono: 1-3-7. Che non verificano il vincolo sulla "distanza" tra le colonne più esterne (|1-7|=6<8). Provando a compilarci una cartella infatti otterremmo questo:
+----------------------------+
|02| |20|38| |56| |74| |
|04| |22| |40|58| |76| |
|08| |26| |44| |62| |80|
+----------------------------+
Come è evidente manca tutta la colonna dei numeri compresi tra 10-19.
Ho provato a fare in modo di inserire un contatore all'interno del ciclo di calcolo dell'ultima colonna: ogni volta che i valori trovati non sono validi incrementa una variabile di controllo. Quando avrà iterato TOT volte senza successo, esce dal ciclo e RIPETE l'estrazione dei tutto il gruppo di cartelle.
La mia domanda è: qualcuno saprebbe darmi qualche dritta su come migliorare questo algoritmo OPPURE un altro algoritmo anche radicalmente diverso purché faccia ciò che miserve? il professore infatti ha chiaramente detto che a suo parere sarebbe stato possibile trovare in internet gli algoritmi già belli e pronti, per generare le cartelle (non ho avuto fortuna in questo purtroppo), e che a lui interessa solo che il CODICE sia scritto da noi, non che anche l'algoritmo sia farina del nostro sacco (come in questo caso). Arrivato a questo punto, con la consegna tra meno di due giorni, sinceramente non so più dove sbattere la testa per farlo funzionare. Chiedo scusa per il post LUUUUUUUUUUNGO ma sono alla disperazione ormai T.T