Archivi tag: python

BlueVinyl Pi

Come usare il Raspberry per rendere bluetooth-compatibile il tuo vecchio giradischi!

Da un pò di tempo ho rispolverato il vecchio giradischi di mio padre, sarà anche per colpa della moda che ha riportato popolare  i vinili.

Poichè il vecchio amplificatore è un bel pò ingombrante, ho pensato di sfruttare il mio vecchio RaspberryPi 2 come pre-amplificatore e ci ho collegato anche una cuffia Bluetooth, così da rendere il mio giradischi il più moderno e fruibile possibile.
Continua a leggere

Machine Learning – Alberi di decisione

Google Developers sul suo profilo Youtube sta pubblicando delle  video-tutorial sul machine learning. I primi due video parlano degli alberi di decisione (linko wikipedia inglese perchè è più completa).
Vedendo i video mi è tornata in mente la mia tesi, in cui ho analizzato le firme grafometriche e dove ho usato un albero di decisione “fatto a mano” per classificare. Così mi son messo a scrivere un pò di codice python per far pratica con i metodi automatici. Continua a leggere

Algoritmi Randomizzati e Paralleli per risolvere il Sudoku

Durante l’ultima sessione di corsi, ho seguito Agoritmi 2, in cui il prof per spiegarci il BackTrack c’ha fatto implementare in python un sudoku solver, basandosi sugli appunti di Norving, che usa backtrack con constraint propagation.

Base

Io ho scritto il programma con una euristica diversa dalla sua: non uso la propagazione dei vincoli (e che lo facevo uguale :P) e non risolvo solo per sottogriglie, ma vado a vedere la colonna o la riga o la sottogriglia che ha il maggior numero di numeri già inseriti e lì vado a tentare l’inserimento di un nuovo numero, ovviamente il tutto ottimizzato usando le hash table (usando la funzione set in python) in modo da non contare ogni volta il numero di elementi presenti.

Con questi meccanismi rapportato all’algoritmo di Norving “mi difendo”, non ho performance  così elevate, però riesco a risolvere i suoi hardest sudoku anche in 0.03 secondi, ma a volte anche di più (parlo di secondi e molti a volte):

Solution computed
 .  .  .  9  2  .  .  .  .      3  8  7  9  2  6  4  1  5 
 .  .  6  8  .  3  .  .  .      5  4  6  8  1  3  9  7  2 
 1  9  .  .  7  .  .  .  6      1  9  2  4  7  5  8  3  6 
 2  3  .  .  4  .  1  .  .      2  3  5  7  4  9  1  6  8 
 .  .  1  .  .  .  7  .  .      9  6  1  2  5  8  7  4  3 
 .  .  8  .  3  .  .  2  9      4  7  8  6  3  1  5  2  9 
 7  .  .  .  8  .  .  9  1      7  5  4  3  8  2  6  9  1 
 .  .  .  5  .  7  2  .  .      6  1  3  5  9  7  2  8  4 
 .  .  .  .  6  4  .  .  .      8  2  9  1  6  4  3  5  7 

Number of recursive calls: 735
In  0.0366179943085 seconds

..

Solution computed
 7  .  .  .  .  .  4  .  .      7  9  8  6  3  5  4  2  1 
 .  2  .  .  7  .  .  8  .      1  2  6  9  7  4  5  8  3 
 .  .  3  .  .  8  .  7  9      4  5  3  2  1  8  6  7  9 
 9  .  .  5  .  .  3  .  .      9  7  2  5  8  6  3  1  4 
 .  6  .  .  2  .  .  9  .      5  6  4  1  2  3  8  9  7 
 .  .  1  .  9  7  .  .  6      3  8  1  4  9  7  2  5  6 
 .  .  .  3  .  .  9  .  .      6  1  7  3  5  2  9  4  8 
 .  3  .  .  4  .  .  6  .      8  3  5  7  4  9  1  6  2 
 .  .  9  .  .  1  .  3  5      2  4  9  8  6  1  7  3  5 

Number of recursive calls: 3595
In  0.172569036484 seconds

Continua a leggere