Archivio

Archivio per marzo 2009

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 , ,

Rilasciato Wesnoth 1.6

23 marzo 2009
1 commento

Ebbene si… Anche i programmatori ogni tanto amano svagarsi con qualche buon gioco di strategia :)
Proprio oggi è stata rilasciata la nuova stabile di Wesnoth, il famoso gioco di strategia a turni libero e multipiattaforma.

Link: www.wesnoth.org/start/1.6/
Changelog completo: svn.gna.org/viewcvs/*checkout*/wesnoth/tags/1.6/changelog

frafra News

Controllo dei valori – prima revisione

22 marzo 2009
3 commenti

E’ possibile migliorare il codice scritto precedentemente in Controllo dei valori, riducendo il numero di linee e rendendo più dettagliato l’errore. Nel vecchio sorgente, noi possiamo sapere su quale variabile fallisce il controllo, ma non quale controllo fallisce. Inoltre, vorremmo veder visualizzato un errore personalizzato. Questo è possibile con questa nuova versione, che, tra l’altro, non fa più uso di un dizionario (come poteva essere locals()) per richiamare le variabili, permettendo così di inserire, nella nostra tabella di regole, direttamente un valore, senza dover sapere come si chiama la variabile.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#!/usr/bin/env python
# -*- coding: utf-8 -*-
 
check = lambda rules: rule[0](*rule[1:]) for rule in rules
 
if __name__ == "__main__":
    def integer(x): assert isinstance(x, int), "%s non è intero" % x
    def positive(x): assert 0 <= x, "%i non è positivo" % x
    def between(f, x, t): assert f <= x < t, "%x non è tra %f e %t" % (f, x, t)
    height = 3; width = 2; row = 1; column = 2
    check((
        (integer, height), (positive, height),
        (integer, width), (positive, width),
        (integer, row), (between, 0, row, height),
        (integer, column), (between, 0, column, width),
        ))

Andiamo ad analizzarlo meglio:

7
8
9

    def integer(x): assert isinstance(x, int), "%s non è intero" % x
    def positive(x): assert 0 <= x, "%i non è positivo" % x
    def between(f, x, t): assert f <= x < t, "%x non è tra %f e %t" % (f, x, t)

In questo passaggio definiamo tre regole: a livello di funzionamento, solo l’ultima varia dalla versione precedente (è più generica, in quanto permette di stabilire un minimo che, nell’altra versione, era impostato su zero). La sintassi però è diversa:

  1. Si usa “assert” (ed è qui il vero cambiamento del controllo del valore): non dobbiamo creare una classe a parte per il nostro errore, e…
  2. Possiamo specificare, dopo la condizione, un nostro messaggio di errore, che ci renda immediata l’individuazione del punto dove il controllo fallisce 
11
12
13
14
15
16

    check((
        (integer, height), (positive, height),
        (integer, width), (positive, width),
        (integer, row), (between, 0, row, height),
        (integer, column), (between, 0, column, width),
        ))

Abbiamo cambiato anche il modo di definire le regole: ogni regola è separata dalle altre, mentre precedentemente più regole erano associate a una variabile da controllare. Inoltre i parametri della funzione, li mettiamo come elementi della nostra regola, e non come argomenti della funzione stessa.
Riepilogando, ogni regola è formata da:

  1. Una funzione, che risulta essere il primo elemento
  2. Una o più variabili, che risultano trovarsi dal secondo elemento in avanti

Infine, abbiamo definito una nuova funzione per la verifica:

4

check = lambda rules: rule[0](*rule[1:]) for rule in rules

…in una sola linea, di facile comprensione :)

frafra Python

Controllo dei valori

21 marzo 2009
Nessun commento

Accade che ci si ritrovi a dover verificare un valore (spesso inserito dall’utente), per evitare spiacevoli sorprese (ad esempio, dobbiamo controllare che l’utente abbia inserito un numero intero maggiore di zero, altrimenti il programma crasha). Ora, vi propongo una soluzione… ;)


Primo problema… Come specificare le regole? Attraverso delle parole chiave (per esempio, associare al valore una lista di parole chiave, come “intero”, “maggiore_di_zero”)? Il problema principale di questo approccio consiste nel fatto che per permettere una validazione utilizzabile in vari ambiti, dovremo scrivere tante regole, con tonnellate di “if”, e svariate decine (o centinaia) di righe.
Come fare? Semplice, la lista delle regole che andremo a creare, non è altro che una lista di una o più funzioni, che restituiscono vero (nel caso la condizione sia soddisfatta) o falso (nel caso non lo sia).
Prima vi mostro il codice sorgente completo del programmino-libreria, che poi andremo ad analizzare pezzo per pezzo:

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

#!/usr/bin/env python
# -*- coding: utf-8 -*-
 
class ValidationError(Exception):
    def __init__(self, value):
        self.value = value
    def __str__(self):
        return "validation error at '%s'" % self.value
 
def check(rules, values):
    for name, rule in rules.iteritems():
        if not all(f(values[name]) for f in rule):
            raise ValidationError, name
 
if __name__ == "__main__":
    integer = lambda var: type(var) == int
    positive = lambda var: 0 <= var
    from_zero_to_num = lambda num: lambda var: 0 <= var <= num-1
    height = 3; width = 2; row = 1; column = 2
    check({
        "height":(integer, positive),
        "width":(integer, positive),
        "row":(integer, from_zero_to_num(height)),
        "column":(integer, from_zero_to_num(width)),
        }, locals())

Analizziamo ora il primo blocco di istruzioni eseguito all’avvio del programma:

16
17
18

    integer = lambda var: type(var) == int
    positive = lambda var: 0 <= var
    from_zero_to_num = lambda num: lambda var: 0 <= var <= num-1

Qui sopra definiamo tre regole d’esempio, che poi verranno utilizzate nella lista delle regole da verificare associate alla variabile:

  1. La prima funzione restituisce True se il var è un numero intero
  2. La seconda se var è maggiore/uguale a zero
  3. La terza se var è maggiore/uguale a zero e minore/uguale di num-1

Semplice, no? Adesso diamo dei valori a qualche variabile e definiamo la nostra lista delle regole:

20
21
22
23
24
25
26

    height = 3; width = 2; row = 1; column = 2
    check({
        "height":(integer, positive),
        "width":(integer, positive),
        "row":(integer, from_zero_to_num(height)),
        "column":(integer, from_zero_to_num(width)),
        }, locals())

La funzione di controllo si chiama check, e ha per argomenti:

  1. Un dizionario, dove il nome di una variabile è associato a delle regole
  2. Un dizionario, dove sono presenti queste variabili (vedi locals())

ndr.: è consigliabile porre le regole in ordine: dalla meno restrittiva alla più restrittiva.
Questa è la funzione di controllo:

10
11
12
13

def check(rules, values):
    for name, rule in rules.iteritems():
        if not all(f(values[name]) for f in rule):
            raise ValidationError, name

Con all(…) verifichiamo che tutte le funzioni restituiscano True. Ricordiamo che all() è una funzione short-circuit.
E, infine, ecco la nostra eccezione “ValidationError”:

4
5
6
7
8

class ValidationError(Exception):
    def __init__(self, value):
        self.value = value
    def __str__(self):
        return "validation error at '%s'" % self.value

Spero possa esservi utile ;)

frafra Python

Rieccomi

21 marzo 2009
5 commenti

Dopo un lungo periodo di pausa, Frafra torna col suo nuovo blog, per scrivere di software libero, programmazione in Python e news.
Ogni suggerimento è ben accetto ;) Inoltre, sulla pagina Proposte, puoi segnalarmi news che hanno a che fare con gli argomenti trattati in questo blog, o chiedere che vengano trattati alcuni problemi (ad esempio, “qual è il modo migliore per scrivere su un file in python?”).


Buona navigazione ;)

frafra Frafra