Sei gradi di separazione

E siccome non voglio parlare solo di ubuntu ma spaziare un po’, oggi vi presento un esercizio che ho fatto in python! Dovevo farlo in java, ma ho scoperto che java mi sta sul cazzo, e sì che ora è pure opensource…
Si tratta di un programma per trovare i famosi sei gradi di separazione fra due persone qualunque.

Il codice è orientato agli oggetti, ma non dev’essere proprio un bell’esempio di codice da seguire, o almeno a me piacerebbe che lo fosse, ma date le mie scarse conoscenze di programmazione(e così mi paro il culo se passa un programmatore da ‘ste parti)….
Allora, il programma va lanciato da linea di comando, e accetta come argomenti un file di testo contenente una lista di persone, ognuna affiancata dalla lista dei suoi amici, e due nomi di persona, che il programma dovrà collegare. Per poter intercettare gli argomenti della linea di comando è sufficiente usare il modulo sys, presente in tutte le distribuzioni python.

Gli argomenti vanno passati al costruttore(__init__) della classe SeiGradi; questa classe presenta diversi metodi:

• acquisisciDati si occupa di creare un dizionario, che ha come chiavi i nomi di persone che “conoscono gente”, a cui sono associate le liste di persone da queste conosciute
• vediamoCosaDiceQuesto(persona) si addentra tra le conoscenze di una data persona, cioè vede se è lui a conoscere il nostro uomo, e in caso negativo chiede ai suoi amici se loro lo conoscono. Se non raggiunge lo scopo manda una mail piena di offese a Stanley_Milgram
• chiediamoAgliAmiciDiQuesto(persona) è usato da (e a sua volta usa) vediamoCosaDiceQuesto, per esplorare tutte le conoscenze. Il meccanismo è quello della mutua ricorsione(due metodi che si richiamano a vicenda)
• trovaPercorso è un semplice metodo per avviare la ricerca
• conosceIlNostroUomo(persona) ci svela una cosa:…..no, non voglio anticiparvela, poi non c’è gusto..
• nonConosceGente(persona) ci dice se una persona ha una lista di amici o è un povero sfigato solitario, e opzionalmente dà un giudizio morale sul risultato
• stampaRisultato si occupa di valutare il risultato della ricerca e di stamparlo a video(infatti trovaPercorso riempie soltanto la lista e non ci comunica niente, questo perchè durante la ricerca uno può rompersi i coglioni di aspettare e perdere così l’interesse, o può semplicemente rendersi conto che non potrà mai arrivare a conoscere Charlize Theron e scegliere di rimanere lì col dubbio, invece di vedersi sbattere in faccia una realtà poco piacevole)
• cercaEStampaIlPercorso, per chi si ricorda di richiamare trovaPercorso ma poi si dimentica di stampare il risultato(e chi sarà mai?), è il metodo ideale per usare l’oggetto, ammesso che ci si ricordi dove mettere le maiuscole corrette

Da notare che il programma trova un solo percorso fra i vari disponibili(quando possibili), e non è manco il percorso più breve, solo che poi diventava troppo complicato…

Beh,dopo la dovuta presentazione, ecco il codice! Certo si poteva fare di meglio, ma magari in futuro lo modifico, per il gusto di arrivare a fare le cose per bene. Alla prossima 😉

#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
class SeiGradi:
    def __init__(self, argomenti):
        self.acquisisciDati(argomenti[1])
        self.nomeIniziale = argomenti[2]
        self.nomeFinale = argomenti[3]
        self.catena = []

    def acquisisciDati(self, file):
        datiGrezzi = [eleme.split(' ') for eleme in open(file).read().split('n')]
        self.rubrica = {}
        for riga in datiGrezzi:
            self.rubrica[riga[0]] = riga[1:]

    def trovaPercorso(self):
        self.vediamoCosaDiceQuesto(self.nomeIniziale)

    def nonConosceGente(self, chi):
        return  not(chi in self.rubrica.keys())

    def conosceIlNostroUomo(self, persona):
        return self.nomeFinale in self.rubrica[persona]

    def vediamoCosaDiceQuesto(self, persona):
        if persona in self.catena:
            return False
        elif self.nonConosceGente(persona):
            return False
        else:
            self.catena.append(persona)

        if self.conosceIlNostroUomo(persona):
            self.catena.append(self.nomeFinale)
            return True
        elif self.chiediamoAgliAmiciDiQuesto(persona):
            return True
        return False

    def chiediamoAgliAmiciDiQuesto(self, persona):
        amici = self.rubrica[persona]
        while len(amici):
            if self.vediamoCosaDiceQuesto(amici.pop()):
                return True
        if len(amici)==0 :
            self.catena.pop()
            return False

    def cercaEStampaIlPercorso(self):
        self.trovaPercorso()
        self.stampaRisultato()

    def stampaRisultato(self):
        if not self.catena:
            print "non c'è una catena che unisce i due tipi sfigati"
        else:
            print "la catena che collega " + self.nomeIniziale + " a " + self.nomeFinale + " è:"
            for i in range(len(self.catena)-1):
                print self.catena[i] + " conosce " + self.catena[i+1]

if __name__ == '__main__':
    prova = SeiGradi(sys.argv)
    prova.cercaEStampaIlPercorso()

Ah, già, un file di esempio con le liste:

giovanni francesco mario peter bart
marge boe lisa gerardo
luigi antonio antonino
davide marco piero antonio giovanni luigi samuel federica
antonio luca giovanni stefania elisabetta
marco luca luigi marge giovanni pietro annalisa