Info:

twitter

Ultimi commenti: Comment feed

Tags:

Sponsor:

Archivio 2018:

Lug Giu Mag Feb Gen

Archivio 2017:

Dic Nov Ott Mag Apr Mar Feb Gen

Archivio 2016:

Dic Nov Ott Ago Mag Mar Feb Gen

Archivio 2015:

Nov Ott Set Mar Gen

Archivio 2014:

Dic Nov Ott Set Lug Giu Mag Apr Gen

Archivio 2013:

Dic Nov Set Ago Lug Giu Mag Apr Feb Gen

Archivio 2012:

Dic Nov Ott Set Ago Giu Mag Apr Mar Feb Gen

Archivio 2011:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2010:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2009:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2008:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2007:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2006:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Lunedì quiz - 7

Scrivere un algoritmo super performante in grado di analizzare il risultato di partite tic-tac-toe e dichiarare se c’è il vincitore per ogni partita. Si assume che le partite abbiano risultati validi quindi la risposta è limitata ad 1, X o 2.

image

-quack

Commenti (18):
1. Blackstorm
lunedì 22 novembre 2010 alle 1:41 PM - firefox 3.6.12 Windows 7
   

Aspetta, non ho capito... vuoi che il vincitore venga dichiarato prima dell'ultima mossa o non è necessario?

   
2. Giuseppe
lunedì 22 novembre 2010 alle 4:28 PM - IE 9.0 Windows 7
   

la frase "super performante" mi fa paura...

   
3. Paperino
lunedì 22 novembre 2010 alle 5:12 PM - chrome 8.0.552.200 Windows 7
   

@blackstorm: ottima domanda. Escludiamo i casi in cui un giocatore vince prima dell'ultima mossa.

   
4. Edward
lunedì 22 novembre 2010 alle 5:14 PM - firefox 4.0 Windows 7
   

Non capisco: bisogna analizzare una partita gia' giocata (quindi vittoria = 3 simboli uguali allineati) oppure enumerare tutte le possibili mosse e distinguere fra quelle concludenti con vittoria e pareggio dal resto? Nel secondo caso ci sono 3^n! possibili stati, con n = numero di caselle: la classica matrice 3x3 basta per mettere alla prova la pazienza di chiunque tranne Joshua

 

Edward

   
5. Paperino
lunedì 22 novembre 2010 alle 6:34 PM - chrome 7.0.517.44 Windows 7
   

Bisogna analizzare una serie di partite (tantissime!) già giocate e assegnare vittoria (1,2) o pareggio (X) o al massimo "invalida" (Y).

Si possono fare altre assunzioni volte a semplificare il problema.

   
6. Paperino
lunedì 22 novembre 2010 alle 6:42 PM - chrome 7.0.517.44 Windows 7
   

OT: Questo video è spettacolare.... non sapevo c'era un finale alternativo al film: http://www.youtube.com/watch?...

   
7. Blackstorm
lunedì 22 novembre 2010 alle 7:21 PM - firefox 3.6.12 Windows 7
   

Uhm... a intuito direi un confronto fra bit.

   
8. wac
mercoledì 24 novembre 2010 alle 11:26 PM - firefox 3.6.12 Windows 7
   

si possono pregenerare i possibili risultati di vittoria(1 o 2) e confrontarle con la matrice in input, in caso non si trovi una combinazione che indichi una vittoria si bolla la partita come pareggio. Che ne dite, è na *azzata

   
9. Paperino
mercoledì 24 novembre 2010 alle 11:39 PM - chrome 7.0.517.44 Windows 7
   

@wac: non è una *azzata. Elabora meglio, strada giusta imboccata.

   
10. wac
giovedì 25 novembre 2010 alle 4:59 PM - firefox 3.6.12 Windows 7
   


indicando con 0 (O) e con 1 (X), in una matrice 3x3 avremo 2^9 possibili configurazioni(considerando l'ipotesi semplificativa del Papero al commento 3),ovviamente non tutte legali. Ai fini di determinare un esito vincente, bisogna controllare solo le 3 righe, le 3 colonne e le 2 diagonali, per ogni giocatore. A questo punto, bisogna valutare se è più conveniente pregenerare tutte le configurazioni valide e procedere ad un confronto "bit a bit"(AND), oppure, considerando l'ipotesi di ricevere in input solamente configurazioni legali, controllare le 3 righe, le 3 colonne e le due diagonali. Questo è quanto ho elaborato finora

   
11. Blackstorm
giovedì 25 novembre 2010 alle 5:40 PM - firefox 3.6.12 Windows 7
   

Beh, però teoricamente potresti scorrere solo una volta le diagonali. Per esempio, diciamo che la scacchiera è fatta così:

123

456

789

 

Tu ti posizioni in 1 e vedi che simbolo c'è. Supponiamo X (è solo un esempio, vale con entrambi, chiaramente). A quel punto tu controlli le coppie 23, 59, 47. Se in una di queste due coppie c'è il simbolo X, allora X vince. Altrimenti ti sposti in 5. In 5 controlli 28, 46, 37, 19. In 9 controlli 36, 78, 15. Penso che partendo da questo schema si possano eliminare alcune coppie da controllare. Ad esempio, se fai un doppio controllo, nel senso che per ogni posizione controlli entrambi i valori, saprai già ad esempio se escludere la diagonale 159. cose del genere.

   
12. Daniele
venerdì 26 novembre 2010 alle 11:21 AM - firefox 4.0 Windows 7
   

Occhio che bisogna anche controllare che ci siano 5+4 simboli, per altro assumendo un'ipotesi sul primo simbolo (che stabilisce quali sono 5 e quali 4).

   
13. il nonno
venerdì 26 novembre 2010 alle 11:45 AM - chrome 8.0.552.200 Windows 7
   

Vi do' un suggerimento: le combinazioni vincenti sono in numero molto ridotto... basta verificare che nella matrice appaia una combinazione vincente, non serve fare molto di piu'... ottimizzare ottimizzare

   
14. wac
venerdì 26 novembre 2010 alle 3:22 PM - firefox 3.6.12 Windows 7
   

si nonno, infatti era quello che intendevo io. Si precalcolano le sole combinazioni vincenti e poi si confronta. Stasera che ho più tempo appronto un prototipo

   
15. Paperino
sabato 27 novembre 2010 alle 4:53 AM - chrome 7.0.517.44 Windows 7
   

Non occorre, la soluzione è buona descritta così.

   
16. wac
sabato 27 novembre 2010 alle 2:23 PM - firefox 3.6.12 Windows 7
   

Papero lo so che ormai sei terrorizzato quando passo da queste parti XD...stavolta sarò magnanimo, non posterò il codice. Cmq il prototipo era strutturato all'incirca così:

le soluzioni precalcolate memorizzate in due array di UInt16

la matrice in input trasformata in un UInt16(o direttamente UInt16 in input)

XOR tra le soluzioni precalcolate e la matrice in input, se il risultato è zero = vittoria, se != da zero pareggio

 

 

 

 

   
17. LowLevelCoder
sabato 27 novembre 2010 alle 5:58 PM - chrome 7.0.517.44 Windows 7
   

Paperino: volevo innanzitutto ringraziarti per questi interessanti "quiz" di programmazione

Poi, volevo sapere: se uno volesse tentare di lavorare su Windows in Microsoft, è necessario saper svolgere esercizi programmatorii di questo tipo? O di altro tipo?

C'è molta competizione per cercare di lavorare su Windows, in particolare su aspetti a basso o medio livello del sistema (es. kernel, device driver, grafica)? Ci sono posti disponibili?

E' sufficiente conoscere la programmazione nativa (C/C++), o è bene sapere anche di programmazione managed (C#, .NET) ?

Grazie per eventuali lumi!

E auguri per il tuo lavoro (è bello sapere che c'è un po' di codice "made in Italy" dentro il software di Microsoft, che milioni di persone usano nel mondo!).

   
18. Paperino
lunedì 29 novembre 2010 alle 8:07 PM - chrome 7.0.517.44 Windows 7
   

@LLC:

Prego!

Di solito le assunzioni dall'esterno vengono fatte in base alle capacità piuttosto che alle conoscenze, per questo il linguaggio di programmazione è piuttosto rilevante per le posizionio "junior": c'è così tanto da imparare al di là della programmazione che il linguaggio di programmazione di "base" diventa irrilevante. Ho fatto da mentor a tre ragazzi, tutti diventati dei mostri, che venivano dal C++, il 'peggiore' dei quali mi ha fatto quasi venire un collasso quando ha scritto le prime righe di codice in C#. 

Per quanto riguarda i quiz: anche qui vale che un algoritmo in C++ è equivalente ad uno in C#, ma quelli in C# sono avvantaggiati perché li so leggere meglio e per via del fatto che c'è un framework di base da cui pescare classi pronte per l'uso.

   
Lascia un commento:
Commento: (clicca su questo link per gli smiley supportati; regole di ingaggio per i commenti)
(opzionale, per il Gravatar)