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