python e automi cellulari – life

Volendo farmi un’idea del python, dopo aver letto il tutorial ho pensato di provare a fare un piccolo programma e, avendo recentemente letto un articolo sugli automi cellulari la scelta è caduta su un’implementazione del famoso gioco life.

Per chi non lo conoscesse, life è un automa cellulare, ovvero un sistema che evolve sulla base di regole di interazione tra gli elementi del sistema. Nel caso specifico di life il sistema è costituito da una tabella in cui ogni elemento è costituito da una casella che può essere in due stati: morto o vivo. Ogni casella ha 8 vicini:

  1. Se una casella è morta ed ha esattamente 3 vicini vivi, diventa viva. Altrimenti rimane morta
  2. Se una casella è viva ed ha 2 o 3 vicini vivi rimane viva altrimenti muore

nell’implementazione che ho realizzato il sistema è a topologia toroidale:

  1. l’elemento a destra di quello a più a destra è l’elemento più a sinistra della stessa riga,
  2. l’elemento a sinistra di quello più a sinistra è l’elemento più a destra della stessa riga
  3. l’analogo per le colonne

Riporto ora il programma da copiare in un file ed eseguire con python 3.
In questa implementazione ho trovato comodo dare valore 0 alle cellule more ed 1 a quelle vive.

import random

def evolve( array ):
### esegue lo step di evoluzione del gioco life su una tabella sferica
   rows = len(array)
   columns = len(array[0])
   array2 = [[0 for j in range(rows)] for i in range(columns)]

# i=0, j=0 
   totale = array[rows-1][columns-1]+array[rows-1][0]+array[rows-1][1]+array[0][columns-1]+array[0][0]+array[0][1]+array[1][columns-1]+array[1][0]+array[1][1]
   if    array[0][0] == 0:
      if totale == 3:
         array2[0][0]=1
      else:
         array2[0][0]=0
   if array[0][0] == 1:
      if totale <= 2:
         array2[0][0]=0
      elif totale <= 4:
         array2[0][0]=1
      else:
         array2[0][0]=0
# i=rows-1, j=0 
   totale = array[rows-2][columns-1]+array[rows-2][0]+array[rows-2][1]+array[rows-1][columns-1]+array[rows-1][0]+array[rows-1][1]+array[0][columns-1]+array[0][0]+array[0][1]
   if    array[rows-1][0] == 0:
      if totale == 3:
         array2[rows-1][0]=1
      else:
         array2[rows-1][0]=0
   if array[rows-1][0] == 1:
      if totale <= 2:
         array2[rows-1][0]=0
      elif totale <= 4:
         array2[rows-1][0]=1
      else:
         array2[rows-1][0]=0

# i=0, j=columns-1
   totale = array[rows-1][columns-2]+array[rows-1][columns-1]+array[rows-1][0]+array[0][columns-2]+array[0][columns-1]+array[0][0]+array[1][columns-2]+array[1][columns-1]+array[1][0]
   if    array[0][columns-1] == 0:
      if totale == 3:
         array2[0][columns-1]=1
      else:
         array2[0][columns-1]=0
   if array[0][columns-1] == 1:
      if totale <= 2:
         array2[0][columns-1]=0
      elif totale <= 4:
         array2[0][columns-1]=1
      else:
         array2[0][columns-1]=0

# i=rows-1, j=columns-1 
   totale = array[rows-2][columns-2]+array[rows-2][columns-1]+array[rows-2][0]+array[rows-1][columns-2]+array[rows-1][columns-1]+array[rows-1][0]+array[0][columns-2]+array[0][columns-1]+array[0][0]
   if    array[rows-1][columns-1] == 0:
      if totale == 3:
         array2[rows-1][columns-1]=1
      else:
         array2[rows-1][columns-1]=0
   if array[rows-1][columns-1] == 1:
      if totale <= 2:
         array2[rows-1][columns-1]=0
      elif totale <= 4:
         array2[rows-1][columns-1]=1
      else:
         array2[rows-1][columns-1]=0

# i=0
   for j in range( 1, columns-2 ):
      totale = array[rows-1][j-1]+array[rows-1][j]+array[rows-1][j+1]+array[0][j-1]+array[0][j]+array[0][j+1]+array[1][j-1]+array[1][j]+array[1][j+1]
      #print( totale )
      if    array[0][j] == 0:
         if totale == 3:
            array2[0][j]=1
         else:
            array2[0][j]=0
      if array[0][j] == 1:
         if totale <= 2:
            array2[0][j]=0
         elif totale <= 4:
            array2[0][j]=1
         else:
            array2[0][j]=0

# i=rows-1
   for j in range( 1, columns-2 ):
      totale = array[rows-2][j-1]+array[rows-2][j]+array[rows-2][j+1]+array[rows-1][j-1]+array[rows-1][j]+array[rows-1][j+1]+array[0][j-1]+array[0][j]+array[0][j+1]
      #print( totale )
      if    array[rows-1][j] == 0:
         if totale == 3:
            array2[rows-1][j]=1
         else:
            array2[rows-1][j]=0
      if array[rows-1][j] == 1:
         if totale <= 2:
            array2[rows-1][j]=0
         elif totale <= 4:
            array2[rows-1][j]=1
         else:
            array2[rows-1][j]=0

# j=0
   for i in range( 1, rows-2 ):
      totale = array[i-1][columns-1]+array[i-1][0]+array[i-1][1]+array[i][columns-1]+array[i][0]+array[i][1]+array[i+1][columns-1]+array[i+1][0]+array[i+1][1]
      #print( totale )
      if    array[i][0] == 0:
         if totale == 3:
            array2[i][0]=1
         else:
            array2[i][0]=0
      if array[i][0] == 1:
         if totale <= 2:
            array2[i][0]=0
         elif totale <= 4:
            array2[i][0]=1
         else:
            array2[i][0]=0

# j=columns-1
   for i in range( 1, rows-2 ):
      totale = array[i-1][columns-2]+array[i-1][columns-1]+array[i-1][0]+array[i][columns-2]+array[i][columns-1]+array[i][0]+array[i+1][columns-2]+array[i+1][columns-1]+array[i+1][0]
      #print( totale )
      if    array[i][columns-2] == 0:
         if totale == 3:
            array2[i][columns-2]=1
         else:
            array2[i][columns-2]=0
      if array[i][columns-2] == 1:
         if totale <= 2:
            array2[i][columns-2]=0
         elif totale <= 4:
            array2[i][columns-2]=1
         else:
            array2[i][columns-2]=0

# other cases
   for i in range( 1, rows-2 ):
      for j in range( 1, columns-2 ):
         totale = array[i-1][j-1]+array[i-1][j]+array[i-1][j+1]+array[i][j-1]+array[i][j]+array[i][j+1]+array[i+1][j-1]+array[i+1][j]+array[i+1][j+1]
         #print( totale )
         if    array[i][j] == 0:
            if totale == 3:
               array2[i][j]=1
            else:
               array2[i][j]=0
         if array[i][j] == 1:
            if totale <= 2:
               array2[i][j]=0
            elif totale <= 4:
               array2[i][j]=1
            else:
               array2[i][j]=0

   return array2

# j=0
   for i in range( 1, rows-2 ):
      totale = array[i-1][columns-1]+array[i-1][0]+array[i-1][1]+array[i][columns-1]+array[i][0]+array[i][1]+array[i+1][columns-1]+array[i+1][0]+array[i+1][1]
      #print( totale )
      if    array[i][0] == 0:
         if totale == 3:
            array2[i][0]=1
         else:
            array2[i][0]=0
      if array[i][0] == 1:
         if totale <= 2:
            array2[i][0]=0
         elif totale <= 4:
            array2[i][0]=1
         else:
            array2[i][0]=0

# j=columns-1
   for i in range( 1, rows-2 ):
      totale = array[i-1][columns-2]+array[i-1][columns-1]+array[i-1][0]+array[i][columns-2]+array[i][columns-1]+array[i][0]+array[i+1][columns-2]+array[i+1][columns-1]+array[i+1][0]
      #print( totale )
      if    array[i][columns-2] == 0:
         if totale == 3:
            array2[i][columns-2]=1
         else:
            array2[i][columns-2]=0
      if array[i][columns-2] == 1:
         if totale <= 2:
            array2[i][columns-2]=0
         elif totale <= 4:
            array2[i][columns-2]=1
         else:
            array2[i][columns-2]=0

# other cases
   for i in range( 1, rows-2 ):
      for j in range( 1, columns-2 ):
         totale = array[i-1][j-1]+array[i-1][j]+array[i-1][j+1]+array[i][j-1]+array[i][j]+array[i][j+1]+array[i+1][j-1]+array[i+1][j]+array[i+1][j+1]
         #print( totale )
         if    array[i][j] == 0:
            if totale == 3:
               array2[i][j]=1
            else:
               array2[i][j]=0
         if array[i][j] == 1:
            if totale <= 2:
               array2[i][j]=0
            elif totale <= 4:                
               array2[i][j]=1
            else:
               array2[i][j]=0
    return array2 

def start_configuration( lenght = 6 ): 
### genera la tabella iniziale quadrata e di dimensione iniziale lenght
    board = [[]]
    line = []
    random.seed()

    for a in range( lenght ):
       line = []
       for b in range( lenght ):
           tmp = random.randint( -1, 1 )
           if tmp > 0:
             line.append( 1 )
          else:
             line.append( 0 )
      board.append( line )

   board.remove([])
   return board

board = [[]]
board = start_configuration( 20 )

for i,v in enumerate(board):
   print(board[i])

print("\n")

while True:
   ok = input()
   board = evolve( board )
   for i,v in enumerate(board):
      print(board[i])

Dopo aver importato il modulo random che utilizzerò per generare la configurazione iniziale, il programma definisce due funzioni: la prima per calcolare uno step di evoluzione, la seconda per generare una configurazione iniziale. Segue poi il corpo principale.

Iniziamo ad esaminare il programma a partire dal corpo principale che è piuttosto semplice:

board = [[]]
board = start_configuration( 20 )

inizio dichiarando la tabella come lista di liste e gli assegno una configurazione con una funzione che esamineremo in seguito. Alla funzione start_configuration() passo come parametro il numero di righe e colonne: ho presupposto che fosse quadrata.

for i,v in enumerate(board):
   print(board[i])

stampo a video la configurazione iniziale con un semplice loop sugli elementi della lista. enumerate restituisce come primo valore l’indice numerico dell’elemento di una lista, indice che poi uso per stampare l’elemento.

while True:
   ok = input()
   board = evolve( board )
   for i,v in enumerate(board):
      print(board[i])

entro infine in un loop infinito per il calcolo degli stati successivi del sistema. Per avere controllo sul processo ad ogni ciclo attendo un invio da parte dell’utente e poi calcolo e stampo a video lo stato successivo.

Esaminiamo ora la prima funzione.

import random

start_configuration() genera casualmente la configurazione iniziale e per farlo ho importato il modulo random

def start_configuration( length = 6 ):
### genera la tabella iniziale quadrata e di dimensione iniziale length

segue poi la definizione della funzione nella quale ho impostato un valore di default per la variabile passata e una riga di commento.
Questa riga di commento ad inizio funzione e preceduta da tre # è in qualche modo speciale e serve a documentare il codice. Appositi tool possono essere utilizzati per esaminare il codice in python alla loro ricerca e generare automaticamente della documentazione.

   board = [[]]
   line = []

definisco le liste che mi serviranno

   random.seed()

inizializzo il generatore di numeri casuali.

   for a in range( length ):
      line = []
      for b in range( length ):
          tmp = random.randint( -1, 1 )
          if tmp > 0:
             line.append( 1 )
          else:
             line.append( 0 )
      board.append( line )

entro nel loop che genera la tabella casuale. Dato che la tabella è in realtà una lista di liste la cosa che mi è sembrata funzionare meglio è stata genereare una riga alla volta per poi aggiungerla alla tabella utilizzando la funzione append delle liste.

   board.remove([])

per come l’ho generata, la tabella conteneva una riga vuota che quindi rimuovo.

   return board

Restituisco infine la tabella generata.

La funzione evolve() sebbene molto lunga non è particolarmente complicata. La sua lunghezza deriva dalla casistica articolata necessaria per gestire cosa accade sui bordi della tabella.

def evolve( array ):
### esegue lo step di evoluzione del gioco life su una tabella sferica
   rows = len(array)
   columns = len(array[0])
   array2 = [[0 for j in range(rows)] for i in range(columns)]

[...]
# other cases
   for i in range( 1, rows-2 ):
      for j in range( 1, columns-2 ):
         totale = array[i-1][j-1]+array[i-1][j]+array[i-1][j+1]+array[i][j-1]+array[i][j]+array[i][j+1]+array[i+1][j-1]+array[i+1][j]+array[i+1][j+1]
         #print( totale )
         if    array[i][j] == 0:
            if totale == 3:
               array2[i][j]=1
            else:
               array2[i][j]=0
         if array[i][j] == 1:
            if totale <= 2:
               array2[i][j]=0
            elif totale <= 4:
               array2[i][j]=1
            else:
               array2[i][j]=0

   return array2

ho riportato quindi solo il caso generico.

Dato che lo stato nel tempo successivo dipende dal numero di vicini e dato che si è scelto di assegnare 1 per il caso cella viva e 0 per quello cella morta, tutto quello che serve è sommare i valori delle caselle coinvolte e confrontare il risultato con le regole che definiscono il gioco.

Il programma andrebbe migliorato sotto diversi aspetti. In particolare:

  • trovare un modo più elegante per gestire la variegata casistica dell’evoluzione per le caselle lungo il bordo.
  • stampare lo stato in modo più visibile
  • dare al  programma un aspetto più unix like, permettendo di eseguirlo passando dei parametri, come le dimensioni delle tabelle, un fiel con una configurazione iniziale, se si vuole che il programma aspetti l’ok dell’esecutore per passare allo stato successivo o eseguire un numero predeterminato di step, altro.
  • capire se il python ha strutture dati più adatte
  • molto altro probabilmente.

PS 1

Si può usare l’operatore modulo per scrivere in modo più compatta la funzione evolve() che diverrà

def evolve( array ):
### esegue lo step di evoluzione del gioco life su una tabella sferica
   rows = len(array)
   columns = len(array[0])
   array2 = [[0 for j in range(rows)] for i in range(columns)]

   for i in range( 0, rows ):
      for j in range( 0, columns ):
         totale = array[(i-1)%(rows)][(j-1)%(columns)]+array[(i-1)%(rows)][j%(columns)]+array[(i-1)%(rows)][(j+1)%(columns)]+array[i%(rows)][(j-1)%(columns)]+array[i%(rows)][j%(columns)]+array[i%(rows)][(j+1)%(columns)]+array[(i+1)%(rows)][(j-1)%(columns)]+array[(i+1)%(rows)][j%(columns)]+array[(i+1)%(rows)][(j+1)%(columns)]
         #print( totale )
         if array[i][j] == 0:
            if totale == 3:
               array2[i][j]=1
            else:
               array2[i][j]=0
         if array[i][j] == 1:
            if totale <= 2:
               array2[i][j]=0
            elif totale <= 4:
               array2[i][j]=1
            else:
               array2[i][j]=0

   return array2

command line perl e analisi dei log

Tempo fa abbiamo visto come utilizzare il perl come tool di linea di comando. Vediamo oggi come utilizzarlo in un caso un poco più complesso: per contare le occorrenze di un dato vhost in un access.log di apache e magari al tempo stesso avere le statistiche di quante volte apache da una risposta corretta (return code 200) o qualche altro errore.

Osserviamo per prima cosa una riga di log del nostro sito preferito

xx.xx.xx.xx linuxandcompany.it - [06/Apr/2014:23:54:13 +0200] "GET /2014/01/squid-come-reverse-proxy/ HTTP/1.1" 200 10177 "-" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_8_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/27.0.1453.110 Safari/537.36"

Questo tipo di analisi si riesce a fare direttamente in linea con il perl. Iniziamo prima da una cosa cosa semplice: contiamo il numero di occorrenze dei vari return code per un dato sito:

cat linuxandcompany.it-08-04-2014.log|grep "linuxandcompany.it" |perl -ne '{@fields = split(/ /); $stat{$fields[8]}++;}END{while( ($key1, $value1) = each(%stat) ){print $key1. "\t" .$value1. "\n"}}'

che darà un risultato della forma:

304	16
200	397
302	4
301	2
404	2

Il comando inizia con un cat che passa ogni riga del file di log in stdout. Lo stdout viene intercettato da un grep che seleziona le righe del mio sito.
Le righe selezionate vengono poi passate al comando per che, come visto, con le opzioni ne applica il comando che segue ad ogni riga.
Il comando per è costituito da due blocchi: quello ordinario nella prima coppia di parentesi graffe e un secondo blocco identificato da END{…} che viene eseguito solo a conclusione del ciclo.

Il primo blocco inizia con uno split che separa la stringa in stdin in un array con le varie parole per elementi

@fields = split(/ /);

Tra gli slash è riportato il carattere scelto per spezzare la stringa.
Lo split avrebbe potuto anche essere scritto come

@fields = split(/ /, $_);

Utilizzo poi i campi per incrementare un hash di contatori che ha per chiavi i return code.

$stat{$fields[8]}++;

Il blocco finale si occuperà poi di visualizzare il risultato:

while( ($key1, $value1) = each(%stat) )
   {
   print $key1. "\t" .$value1. "\n"
   }

ed è costituito da un ciclo sulle coppie chiave, valore dell’hash.

In una situazione reale questo comando funziona però fino ad un certo punto perché le stringhe possono contenere spazi anche se non è frequentissimo. Un risultato molto migliore si ottiene combinando due split: un primo basato sulle virgolette, che racchiudono le stringe significative, ed un secondo basato sugli spazi da applicare alle sottostringhe:

cat linuxandcompany.it-08-04-2014.log|grep "linuxandcompany.it" |perl -ne '{@fields = split(/"/); @sub_fields = split(/ /, $fields[2]); $stat{$sub_fields[1]}++;}END{while( ($key1, $value1) = each(%stat) ){print $key1. "\t" .$value1. "\n"}}'

Si può poi complicare a piacere andando a fare la stessa statistica per ogni sito presente nel log. Sotto faccio un doppio report (per sito e complessivo).

cat linuxandcompany.it-08-04-2014.log |perl -ne '{@fields = split(/"/); @sub_fields1 = split(/ /, $fields[0]); @sub_fields2 = split(/ /, $fields[2]); $stat1{$sub_fields1[1]}{$sub_fields2[1]}++; $stat2{$sub_fields2[1]}++}END{while(($key1, $value1) = each(%stat1)){ while( ($key2,$value2) = each(%$value1) ){print $key1. "\t" . $key2."\t".$value2. "\n"}}; print "\n\n"; while( ($key1, $value1) = each(%stat2) ){print $key1. "\t" .$value1. "\n"}}'

Rimane evidente che questo è al limite di quello che ha senso fare con una linea di comando e non scrivendo un piccolo script.

Comandi analoghi si possono utilizzare ad esempio per contare le occorrenze delle pagine nel log.