Archivio

Posts Tagged ‘Conway’

Gioco della vita di Conway: da Python a C

7 novembre 2009
1 commento

Vi ricordate il post sul gioco della vita di Conway (life)? Avevo scritto un algoritmo che oltre a implementare questo giochino (vedi Gioco della vita di Conway), ricercasse, con un bruteforce, tutte le figure che si ripetevano. Ora l’ho riscritto in C, supportando come parametri anche shift e step (sono un metodo grezzo per permettere un balance tra cpu/pc lanciando processi con parametri diversi) e un metodo economico (ma stupido) per il calcolo delle figure successive (vedere la variabile dirty e la nota n. 1). Quest’ultima caratteristica rende l’algoritmo intrinsecamente più veloce rispetto a quello che avevo scritto in Python, per cui le prestazioni sono sfasate (penso che questo trucco possa rendere il codice cinque volte più veloce mediamente, ma devo ancora studiare meglio gli effetti).

Tenendo conto di questo, il rapporto tra il programma in C, il programma Python convertito in C++ con Shedskin, la versione che usa Psyco, e la versione “classica”, è: (approssimativamente) 1:10:70:300. Ripeto: devo ancora applicare l’algoritmo nuovo in Python, e pare che gli ultimi tre dati si possano dividere per cinque circa, portando la versione Shedskin nello stesso ordine di grandezza della versione in C (questo sottolinea la validità del progetto), mentre la versione Pythonica sarebbe meno di due ordini di grandezza più lenta.

Il codice è questo :) Non lo commenterò passo passo, in quanto mi pare molto leggibile e simile a quello della versione in Python. Oltretutto, è già lungo di suo, quindi eviterei di riprendere inutilmente pezzi di codice per commentare la loro funzione :D Ho tolto la licenza… Tenete conto che, ovviamente, è sotto GPLv3:

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

#include <stdio.h>
#include <stdlib.h>
 
void clean(int *p, int dim) {
    int c; for (c=0; c<=dim; c++, p++) *p = 0;
}
 
void clone(int *from, int *to, int dim) {
    int c; for (c=0; c<=dim; c++) to[c] = from[c];
}
 
int compare(int *from, int *to, int dim) {
    int c;
    for (c=0; c<=dim; c++) { if (*to != *from) return 0; from++; to++; }
    return 1;
}
 
int main(int argc, char *argv[]) {
    if ((argc != 3) && (argc != 5)) {
        printf("Usage: %s [rows] [columns] [shift] [step]\n", argv[0]);
        return 1;
    }
    const int rows = atoi(argv[1]);
    const int columns = atoi(argv[2]);
    const int dim = rows*columns;
 
    int shift = 0;
    int step = 1;
    if (argc == 5) {
        shift = atoi(argv[3]);
        step = atoi(argv[4]);
    }
    if (shift >= step) {
        printf("shift/step are invalid.\n");
        return 2;
    }
 
    int clean_stage[dim];  int *clean_p = &clean_stage[0];
    clean(clean_p, dim);
 
    int alpha_stage[dim];  int *alpha_p = &alpha_stage[0];
    clean(alpha_p, dim);
    int beta_stage[dim];   int *beta_p = &beta_stage[0]; 
    clean(beta_p, dim);
    int first_stage[dim];  int *first_p = &first_stage[0];
    clean(first_p, dim);
 
    int i;
 
    int dirty;
 
    int p = dim-1;
    int r, sum, row, column, row_p, row_n;
    r = 0;
    while (1) {
        p = dim-1;
        while (first_stage[p] == 1) p--;
        first_stage[p] = 1;
        for (p++; p<dim; p++) first_stage[p] = 0;
        if (r%step != shift) {
            r++;
            continue;
        } else r = 0;
        clone(first_p, alpha_p, dim);
        dirty = 0;
        while (dirty != 18) { /* [1] Nota a fine programma... */
            for (i=0; i<dim; i++) {
                row = i/columns;
                column = i%columns;
                if (row == 0) {
                    row_n = i+columns;
                    if (column == 0) sum =\
                        alpha_stage[i+1] +\
                        alpha_stage[row_n] +\
                        alpha_stage[row_n+1];
                    else if (column < columns-1) sum =\
                        alpha_stage[i-1] +\
                        alpha_stage[i+1] +\
                        alpha_stage[row_n-1] +\
                        alpha_stage[row_n] +\
                        alpha_stage[row_n+1];
                    else sum = \
                        alpha_stage[i-1] +\
                        alpha_stage[row_n-1] +\
                        alpha_stage[row_n];
                } else if (row < rows-1) {
                    row_p = i-columns;
                    row_n = i+columns;
                    if (column == 0) sum =\
                        alpha_stage[row_p] +\
                        alpha_stage[row_p+1] +\
                        alpha_stage[i+1] +\
                        alpha_stage[row_n] +\
                        alpha_stage[row_n+1];
                    else if (column < columns-1) sum =\
                        alpha_stage[row_p-1] +\
                        alpha_stage[row_p] +\
                        alpha_stage[row_p+1] +\
                        alpha_stage[i-1] +\
                        alpha_stage[i+1] +\
                        alpha_stage[row_n-1] +\
                        alpha_stage[row_n] +\
                        alpha_stage[row_n+1];
                    else sum =\
                        alpha_stage[row_p-1] +\
                        alpha_stage[row_p] +\
                        alpha_stage[i-1] +\
                        alpha_stage[row_n-1] +\
                        alpha_stage[row_n];
                } else {
                    row_p = i-columns;
                    if (column == 0) sum =\
                        alpha_stage[row_p] +\
                        alpha_stage[row_p+1] +\
                        alpha_stage[i+1];
                    else if (column < columns-1) sum =\
                        alpha_stage[row_p-1] +\
                        alpha_stage[row_p] +\
                        alpha_stage[row_p+1] +\
                        alpha_stage[i-1] +\
                        alpha_stage[i+1];
                    else sum =\
                        alpha_stage[row_p-1] +\
                        alpha_stage[row_p] +\
                        alpha_stage[i-1];
                }
 
                beta_stage[i] = 0;
                switch (sum) {
                    case 2: beta_stage[i] = alpha_stage[i]; break;
                    case 3: beta_stage[i] = 1;
                }
            }
            if (compare(beta_p, first_p, dim)) {
                for (i=0; i<dim-1; i++) printf("%d ", first_stage[i]);
                printf("%d\n", first_stage[dim-1]);
                break;
            }
            if (compare(alpha_p, beta_p, dim)) break;
            clone(beta_p, alpha_p, dim);
 
            dirty++;
        }
    if (compare(first_p, clean_p, dim)) break;
    }
    return 0;
}
 
/* Nota [1]:
  Per non comparare sempre lo stage corrente con quelli precedenti,
  ho creato una modalità "stupida" di computazione. Il valore 18
  indica che non è necessario calcolare ulteriori stages se non si è
  ancora usciti dal ciclo, in quanto pare che non ci siano figure nel
  primo stadio, che si ripetano dopo il 18esimo stadio. */

P.S. Ho trovato una implementazione di questo giochino, molto carina, (senza bruteforce ovviamente) nella directory di Python 3.1.1 (ma penso si trovi anche in versioni precedenti) che usa curses, sotto Python-3.1.1/Demo/curses/life.py :)

frafra C/C++, Python , ,

Gioco della vita di Conway

23 marzo 2009
Nessun 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 , ,