La scorsa settimana l'ho dedicata prevalentemente a correggere il paper e ripassare C.
Alla fine non e' cosi' male come linguaggio, non mi ricordavo piu' la potenza dei puntatori, ed un bel ripassone e' servito. Ne ho approfittato cosi' per creare un programma che mi risolvesse un giochino che sul cellulare, che mi sta facendo dannare dato che non riesco a trovarne la soluzione.
Il giochino si chiama Stone Bricks, ed e' presente sotto forma di gioco java sui Moto Razr V3. Il gioco e' abbastanza semplice: data una scacchiera a forma di croce, vengono disposte n pedine sulla scacchiera. Se una pedina e' adiacente ad un altra su un lato (verticale o orizzontale), mentre sull'altro lato e' presente una casella vuota, la pedina puo' essere mangiata da quella adiacente, che si posizionera' sulla casella vuota. Il gioco termina quando c'e' solo una pedina sulla scacchiera. Ci sono 5 configurazioni iniziali, la cui difficolta' varia in base al numero di pedine iniziali presenti. La scacchiera e' composta da 45 caselle, con blocchi di 3x3 messi a croce.
Io ho risolto le prime quattro, mentre non riesco a finire la quinta (rimango sempre con almeno 3 pedine sulla scacchiera, disposte in modo tale che non possono annullarsi a vicenda). Allora ho pensato di fare un programma per risolverlo.
Il programma C e' strutturato come segue: data una matrice 9x9, valorizzo le caselle della croce a "1" se e' presente una pedina, "0" altrimenti. Le caselle non facenti parte della croce hanno valore "-9". Una struttura dati ad albero tiene traccia delle mosse effettuate e da effettuare, utilizzando un algoritmo DFS ricorsivo per scoprire ed analizzare i nuovi nodi. Una struttura ad albero binario parallela poi e' usata per memorizzare le configurazioni della matrice gia' visitate, in modo tale da non ri-applicare la DFS su configurazioni gia' visitate (capita spesso che una stessa configurazione possa essere raggiunta partendo da passi diversi).
I problemi principali di questo programma sono due: l'esplosione di stati della DFS e la lentezza nel controllo di una configurazione gia' osservata. In particolare osservo gravi rallentamenti sull'ultimo livello, che riempie 44 delle 45 caselle disponibili.
Il primo problema non e' poi cosi' grave: la DFS non ha bisogno di memorizzare troppi nodi contemporaneamente, in quanto ogni volta sono allocati solo tutti i nodi padri, i relativi fratelli e il nodo stesso. Contando che avendo 44 pedine al massimo risolvero' il problema in 43 mosse (ma che generalmente ci si ferma a 5 pedine sulla scacchiera), e che mediamente ad ogni mossa ne ho a disposizione altre 5, i nodi allocati contemporaneamente sono 38*5.
Il secondo problema invece e' piu' noioso. Le configurazioni possibili sulla scacchiera sono 2^45: non posso andare in accesso diretto alla memoria con 2^45 combinazioni cosi' son stato costretto a costruire un albero binario, che per ogni casella della matrice avesse un puntatore a un nodo "1" o "0". Ogni volta che cosi' ho un nuovo passo mi trovo a scorrere tutto l'albero per vedere se e' gia' stato visitato o meno.
Miglioramenti
E nel frattempo non ho ancora la soluzione...
Alla fine non e' cosi' male come linguaggio, non mi ricordavo piu' la potenza dei puntatori, ed un bel ripassone e' servito. Ne ho approfittato cosi' per creare un programma che mi risolvesse un giochino che sul cellulare, che mi sta facendo dannare dato che non riesco a trovarne la soluzione.
Il giochino si chiama Stone Bricks, ed e' presente sotto forma di gioco java sui Moto Razr V3. Il gioco e' abbastanza semplice: data una scacchiera a forma di croce, vengono disposte n pedine sulla scacchiera. Se una pedina e' adiacente ad un altra su un lato (verticale o orizzontale), mentre sull'altro lato e' presente una casella vuota, la pedina puo' essere mangiata da quella adiacente, che si posizionera' sulla casella vuota. Il gioco termina quando c'e' solo una pedina sulla scacchiera. Ci sono 5 configurazioni iniziali, la cui difficolta' varia in base al numero di pedine iniziali presenti. La scacchiera e' composta da 45 caselle, con blocchi di 3x3 messi a croce.
Io ho risolto le prime quattro, mentre non riesco a finire la quinta (rimango sempre con almeno 3 pedine sulla scacchiera, disposte in modo tale che non possono annullarsi a vicenda). Allora ho pensato di fare un programma per risolverlo.
Il programma C e' strutturato come segue: data una matrice 9x9, valorizzo le caselle della croce a "1" se e' presente una pedina, "0" altrimenti. Le caselle non facenti parte della croce hanno valore "-9". Una struttura dati ad albero tiene traccia delle mosse effettuate e da effettuare, utilizzando un algoritmo DFS ricorsivo per scoprire ed analizzare i nuovi nodi. Una struttura ad albero binario parallela poi e' usata per memorizzare le configurazioni della matrice gia' visitate, in modo tale da non ri-applicare la DFS su configurazioni gia' visitate (capita spesso che una stessa configurazione possa essere raggiunta partendo da passi diversi).
I problemi principali di questo programma sono due: l'esplosione di stati della DFS e la lentezza nel controllo di una configurazione gia' osservata. In particolare osservo gravi rallentamenti sull'ultimo livello, che riempie 44 delle 45 caselle disponibili.
Il primo problema non e' poi cosi' grave: la DFS non ha bisogno di memorizzare troppi nodi contemporaneamente, in quanto ogni volta sono allocati solo tutti i nodi padri, i relativi fratelli e il nodo stesso. Contando che avendo 44 pedine al massimo risolvero' il problema in 43 mosse (ma che generalmente ci si ferma a 5 pedine sulla scacchiera), e che mediamente ad ogni mossa ne ho a disposizione altre 5, i nodi allocati contemporaneamente sono 38*5.
Il secondo problema invece e' piu' noioso. Le configurazioni possibili sulla scacchiera sono 2^45: non posso andare in accesso diretto alla memoria con 2^45 combinazioni cosi' son stato costretto a costruire un albero binario, che per ogni casella della matrice avesse un puntatore a un nodo "1" o "0". Ogni volta che cosi' ho un nuovo passo mi trovo a scorrere tutto l'albero per vedere se e' gia' stato visitato o meno.
Miglioramenti
- Ogni matrice che visito la registro 4 volte nell'albero, ovvero registro anche quella speculare da ogni lato. In questo modo aumento la probabilita' di trovare un nodo gia' visitato (e che non porta a soluzione).
- Valutavo l'idea del backtracking, al posto della ricorsione. Dovrei implementare un sistema per salvare gli iteratori delle matrici ad ogni singolo step, nulla di complicato, ma non so quanto migliori il programma, in quando reputo che non sia li' il problema principale.
- Dimezzare l'albero binario. Potrei portare l'albero binario a "soli" 13 nodi al posto di 45, ed allocare per gli ultimi 32 un array lungo 2^32.
E nel frattempo non ho ancora la soluzione...
1 commento:
Oi, achei teu blog pelo google tá bem interessante gostei desse post. Quando der dá uma passada pelo meu blog, é sobre camisetas personalizadas, mostra passo a passo como criar uma camiseta personalizada bem maneira. Até mais.
Posta un commento