PDA

Visualizza la versione completa : [C] Generazione cartelle del Bingo


KevinMoore
25-05-2012, 19:29
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

Scara95
25-05-2012, 21:26
per ogni cartella generi i numeri in colonna con rand():
le colonne saranno:
1-10 -> rand()%9+1
11-20 -> rand()%9+11
21-30 -> rand()%9+21
e così via...
quando generi il numero controlli che non sia già presente nella colonna, se è presente ne generi un'altro, altrimenti lo inserisci...
Alla fine della generazione i numeri saranno disposti in decine per colonne e saranno unici, non saranno ordinati quindi dovrai applicare un algoritmo di sorting, almeno che tu non usi un inserimento ordinato durante la generazione...

L'algoritmo è piuttosto semplice e facilmente modificabile, io lo appoggerei su una struttura ausiliaria e solo poi lo trasferirei nella cartella, ma sarebbe veloce anche una generazione sulla matrice....

KevinMoore
25-05-2012, 21:44
Ciao Scara95, intanto grazie per la risposta.
L'algoritmo di sorting non credo sia indispensabile. Non mi risulta che ci sia un vincolo che impone che le colonne siano ordinate dall'alto verso il basso.

Per il resto: se ho capito bene tu intendi generare le colonne di una cartella una alla volta con le rand, verificando che il numero estratto non sia già stato utilizzato, e disponendoli per colonne in base alle decine.

Tuttavia così TUTTE le colonne della cartella saranno complete, e quindi avremmo 9 numeri per riga, 3 numeri per colonna. Un totale di 27 numeri. Invece i numeri in una cartella devono essere 15 (5 per riga, per 3 righe). Riempire l'intera cartella con numeri senza ripetizioni e disponendoli correttamente è in effetti un problema molto banale, e di soluzione immediata. Il problema qui è che devono esserci SOLO ed ESATTAMENTE 5 numeri per ogni riga, ma disposti in modo tale che non ci siano colonne vuote (quindi, ad esempio, non possono essere sempre le prime 5 colonne a contenere valori, perché rimarrebbero 4 colonne vuote a cartella). IN PIU', le cartelle vanno generate a gruppi di SEI. E i numeri contenuti da tutte e 6 le cartelle devono essere necessariamente tutti i numeri del tabellone, da 1 a 90, senza ripetizioni. Insomma il problema più grosso è come fare ad essere sicuro di avere almeno un numero (ma non per forza SOLO uno) per ogni colonna di OGNI cartella del gruppo >.<

Scara95
25-05-2012, 22:30
Generi un numero casuale di numeri da 1 a 3 per ogni colonna, quando raggiungi i ((15 -numero_numeri_generati) == numero_colonne_rimanenti) ti fermi e distribuisci 1 numero per ogni colonna rimanente, se alla fine della generazione non raggiungi i 15 ricominci dalla prima colonna e aggiungi un numero in ogni colonna in cui puoi aggiungerlo fino al raggiungimento dei 15...

Questa può essere una soluzione per creare una cartella casuale e che sia ben formata...

KevinMoore
25-05-2012, 23:01
Aspetta temo di non aver capito bene il procedimento

Perché devo generare un numero casuale da 1 a 3? Che uso ne faccio?

Scara95
25-05-2012, 23:04
Un numero di numeri casuali...

KevinMoore
25-05-2012, 23:09
ah ho capito ora. Quindi quel valore indica, per ogni colonna, quanti valori inserirci dentro. Se poi non bastano, ne aggiungo per coprire i "Buchi". Però così pur risolvendo il problema sulla singola cartelle, non lo risolvo sul gruppo di 6 cartelle.

Supponiamo infatti che nella prima cartella, alla terza colonna (che può contenere solo numeri da 20 a 29) vengano assegnati 2 valori (20-21, ad esempio)

Nella seconda cartella vengono assegnati, alla stessa colonna, altri 2 valori (22-23)

Nella terza altri 3: 24-25-26

Nella quarta altri 2: 27-28

Nella quinta uno: 29

Non ci sono più valori leciti per riempire la terza colonna della sesta cartella, che rimarrebbe vuota (ma non mi poteva capitare come traccia la battaglia navale? XD)

Scara95
25-05-2012, 23:24
Aggiungi una condizione nel riempimento... Che il numero dei numero già inseriti - quello di quelli disponibili sia minore o uguale al numero di cartelle mancanti...

Certo che sta diventando complicato O.o, io l'avevo pensato più semplice...

Scara95
25-05-2012, 23:26
Scusa: sparato una cavolata: che il numero dei numeri disponibili (una decina) - il numero dei numeri inseriti sia >= al numero di cartelle rimanenti...

KevinMoore
25-05-2012, 23:27
ti confesso che anche a me all'inizio sembrava una scemenza XD proverò qualcosa in questo senso e ti farò sapere se ho risolto qualcosa. In realtà queste condizioni le avevo già provate sul mio algoritmo, ma dava risultati imprevisti (Loop infiniti di calcolo e stampa di cartelle corrette ad esempio). Magari cambiando la logica di base è più facile non imputtanarlo :) grazie dell'aiuto, in ogni caso

Loading