Home > Python > Gioco della vita di Conway

Gioco della vita di Conway

23 marzo 2009
Vai ai commenti Lascia un commento

Ho implementato il gioco della vita di Conway in Python. Avete in mente il simbolo hacker (il glider, quella griglia 3×3 con dei pallini neri)? Beh, sono strettramente legati :)
Questa implementazione permette svariate cose, tra cui:

  1. Una volta impostata una griglia, vedere l’evolversi della situazione.
  2. Definite le dimensioni della griglia, trovare (con un bruteforce) tutte le figure che si ripetono dopo N stadi.

Ecco il codice (commentato parzialmente in inglese):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

#!/usr/bin/env python
# -*- coding: utf-8 -*-
 
try:
    import psyco
    from psyco.classes import __metaclass__
    psyco.full()
except:
    pass
 
class Life:
    """ Implementation of the Conway's game of life """
    def __init__(self, rows, columns):
        """ Inizializes 2d table """
        self.rows, self.columns = rows, columns
        self.board = [[0,]*self.columns for row in xrange(self.rows)]
    def get(self, row, column):
        """ Gets value or return 0 """
        check = 0 <= row < self.rows and 0 <= column < self.columns
        return (check and self.board[row][column] or 0)
    def add(self, row, column):
        """ Adds eight cells near current cell """
        return self.get(row - 1, column - 1) + \
            self.get(row - 1, column) + \
            self.get(row - 1, column + 1) + \
            self.get(row, column - 1) + \
            self.get(row, column + 1) + \
            self.get(row + 1, column - 1) + \
            self.get(row + 1, column) + \
            self.get(row + 1, column + 1)
    def next(self):
        """ Calculates the next stage """
        current = [row[:] for row in self.board] # It clones the table
        for r, row in enumerate(current): # For every row...
            for c, item in enumerate(row): # ...and for every column...
                near = self.add(r, c) # ...it calculates near cells
                if near not in (2, 3) and item: # Condition to death
                    current[r][c] = 0 # Let's kill it :(
                elif near == 3 and not item: # Condition to became alive
                    current[r][c] = 1 # Let's live! :D
        self.board = current # It overwrites the old stage
    def show(self, target = False):
        """ Shows the table """
        for row in (target or self.board):
            print("".join([column and "@" or "x" for column in row]))
 
def bruteforce(rows, columns):
    life = Life(rows, columns)
    possibilities = [list(i) for i in product((0, 1), repeat=columns)]
    for select in product(xrange(len(possibilities)), repeat=rows):
        life.board = [possibilities[i] for i in select]
        history = [life.board]
        while 1:
            life.next()
            if life.board in history:
                if life.board == history[0]:
                    life.show(history[0])
                    print("")
                break
            history.append(life.board)
 
if __name__ == "__main__":
    from itertools import product
    from sys import argv
    try:
        rows, columns = int(argv[1]), int(argv[2])
    except IndexError:
        print("Usage: %s [rows] [columns]" % argv[0])
    except ValueError:
        print("Usage: %s [rows] [columns]" % argv[0])
    else:
        bruteforce(rows, columns)
 
"""
# Example code: glider (spaceship, hacker symbol)
if __name__ == "__main__": # If you're executing this program...
    life = Life(6, 6) # It inizializes a 2d 6x6 table
    life.board[2][0] = 1 # 2, 0 set alive
    life.board[2][1] = 1 # 2, 1 set alive
    life.board[2][2] = 1 # 2, 2 set alive
    life.board[1][2] = 1 # 1, 2 set alive
    life.board[0][1] = 1 # 0, 1 set alive
    for time in range(12): # For n times...
        life.next() # ...it makes the next stage...
        life.show() # ...and it shows it :)
"""

La prima porzione di codice è la seguente:

4
5
6
7
8
9

try:
    import psyco
    from psyco.classes import __metaclass__
    psyco.full()
except:
    pass

In questa maniera, importiamo, se disponibile, la libreria psyco, che, su macchine x86, permette di eseguire operazioni molto onerose per la cpu, in maniera molto più veloce :)
Successivamente troviamo questa classe:

11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class Life:
    """ Implementation of the Conway's game of life """
    def __init__(self, rows, columns):
        """ Inizializes 2d table """
        self.rows, self.columns = rows, columns
        self.board = [[0,]*self.columns for row in xrange(self.rows)]
    def get(self, row, column):
        """ Gets value or return 0 """
        check = 0 <= row < self.rows and 0 <= column < self.columns
        return (check and self.board[row][column] or 0)
    def add(self, row, column):
        """ Adds eight cells near current cell """
        return self.get(row - 1, column - 1) + \
            self.get(row - 1, column) + \
            self.get(row - 1, column + 1) + \
            self.get(row, column - 1) + \
            self.get(row, column + 1) + \
            self.get(row + 1, column - 1) + \
            self.get(row + 1, column) + \
            self.get(row + 1, column + 1)
    def next(self):
        """ Calculates the next stage """
        current = [row[:] for row in self.board] # It clones the table
        for r, row in enumerate(current): # For every row...
            for c, item in enumerate(row): # ...and for every column...
                near = self.add(r, c) # ...it calculates near cells
                if near not in (2, 3) and item: # Condition to death
                    current[r][c] = 0 # Let's kill it :(
                elif near == 3 and not item: # Condition to became alive
                    current[r][c] = 1 # Let's live! :D
        self.board = current # It overwrites the old stage
    def show(self, target = False):
        """ Shows the table """
        for row in (target or self.board):
            print("".join([column and "@" or "x" for column in row]))

Questo codice è stato scritto con una particolare attenzione alle prestazioni. Cerchiamo di comprendere meglio le varie funzioni:

  1. __init__(self, rows, columns): dati due numeri interi, “disegna” una tabella delle dimensioni specificate
  2. get(self, row, column): è una funzione che viene usata per vedere se una cella è viva o morta. In caso questa cella non esista, ritorna semplicemente zero, come se fosse morta. Ho trovato questo metodo sensibilmente più veloce rispetto al fare un try/except (senza quindi controllare l’esistenza della cella in base alle coordinate), e molto più chiaro rispetto al creare una tabella con un bordo di una cella.
  3. add(self, row, column): date le coordinate di una cella, somma le otto celle accanto, utilizzando get().
  4. next(self): calcola lo stadio successivo.
  5. show(self, target=False): visualizza in maniera abbastanza “grezza” la nostra griglia sul terminale.

Qui finisce il “grosso” del codice. Successivamente abbiamo la funzione per il bruteforce:

47
48
49
50
51
52
53
54
55
56
57
58
59
60

def bruteforce(rows, columns):
    life = Life(rows, columns)
    possibilities = [list(i) for i in product((0, 1), repeat=columns)]
    for select in product(xrange(len(possibilities)), repeat=rows):
        life.board = [possibilities[i] for i in select]
        history = [life.board]
        while 1:
            life.next()
            if life.board in history:
                if life.board == history[0]:
                    life.show(history[0])
                    print("")
                break
            history.append(life.board)

Questa funzione fa uso di itertools per calcolare le combinazioni possibili. Bisogna prestare particolarmente attenzione a piccoli accorgimenti, come il calcolare volta per volta ogni possibile combinazione, semplicemente “scegliendo” tra le “righe” generate. Ho trovato questo metodo particolarmente efficente e veloce.
Per sapere se una figura è già apparsa, crea una lista degli stadi, finché qualcosa non si ripete. Questo deve sempre avvenire, in quanto anche se non capitassimo di fronte a una figura “particolare”, dopo qualche passaggio tutte le celle morirebbero, e le ritroveremmo nuovamente morte nello stadio successivo, provocando una ripetizione (che, in questo caso, non verrà però visualizzata).
Il blocco successivo serve a rendere operativo il bruteforce:

62
63
64
65
66
67
68
69
70
71
72

if __name__ == "__main__":
    from itertools import product
    from sys import argv
    try:
        rows, columns = int(argv[1]), int(argv[2])
    except IndexError:
        print("Usage: %s [rows] [columns]" % argv[0])
    except ValueError:
        print("Usage: %s [rows] [columns]" % argv[0])
    else:
        bruteforce(rows, columns)

Come già accennato precedentemente, importiamo itertools.product (assieme a sys.argv), e prendiamo gli argomenti passati da linea di comando, che diamo in pasto a bruteforce().
L’ultima parte è commentata, e mostra un utilizzo alternativo della classe Life:

74
75
76
77
78
79
80
81
82
83
84
85
86

"""
# Example code: glider (spaceship, hacker symbol)
if __name__ == "__main__": # If you're executing this program...
    life = Life(6, 6) # It inizializes a 2d 6x6 table
    life.board[2][0] = 1 # 2, 0 set alive
    life.board[2][1] = 1 # 2, 1 set alive
    life.board[2][2] = 1 # 2, 2 set alive
    life.board[1][2] = 1 # 1, 2 set alive
    life.board[0][1] = 1 # 0, 1 set alive
    for time in range(12): # For n times...
        life.next() # ...it makes the next stage...
        life.show() # ...and it shows it :)
"""

Si inizializza una griglia col famoso simbolo hacker, e si mostrano gli stadi successivi :)

Simpatico, no? :)

P.S. Ho omesso la licenza per problemi di spazio… Ovviamente è GPLv3 :)

frafra Python , ,