pdftk – a kind command line tool to manage pdf files

pdftk is a useful command line tool to manage pdf files.

It permits operations like:

  • to split a document in pages,
  • to merge several documents,
  • to extract pages,
  • to remove pages,
  • to rotate pages,
  • to apply background watermark,
  • to decrypt or encrypt a document

Some examples:

pdftk doc.pdf burst

will split the document in its pages generating several named as pg_0001.pdf, pg_0002.pdf etc…

pdftk pg_0001.pdf pg_0002.pdf cat output tets.pdf

will concatenate two documents

pdftk pg_0001.pdf cat 1east output tets.pdf

will rotate a page

shell tools – parametric commands with xargs

Sometime is necessary to execute commands several times changing only some parameters.

In most of the cases you can use a for or a while loop:

for FILE in $(ls -1); do echo ${FILE}; done 

This form isn’t particularly robust because of the unmanaged spaces in the file names but anyway it is really common because of its simplicity.

Another option is to use the -exec option of the find command.

find . -type f -exec echo '{}' \;

This form is a really powerful way of looping but can be used only on list of files

In some cases neither of the previous forms can be used. Let see an example: you have to read a file (ei: an apache access log) elaborate the row in some way and execute a command for each row. In a case like this find isn’t an option and the for loop is inconvenient at the best because you have to put much more logic in the variable definition then in the true loop. Moreover if you have a big file to manage you couldn’t have enough memory.

It would be much better to elaborate on line at time: xargs is the tool that permits us to proceed in this way.

Let’s look at an example: suppose I want to loop through a log file and search for the served pages that doesn’t contains a word. I’ll have to read the file, probably select some lines, extract the information required to execute a curl, execute the curl and examine the result.
I can do this in a single line using xargs without involving intermediate files.

cat  20150608_access.log |grep "linuxandcompany" |awk -F"GET " '{print $2}' |awk -F" HTTP/" '{print $1}' | xargs -I {} sh -c 'curl -s "http://www.linuxandcompany.it{}" | grep "pippo" > /dev/null;  [ $? -ne 0 ] && echo "{}"'

The first part is really basic: the cat command is used to read through a log file. Then I use a filter (grep) to select some lines (the ones related to this website).

To extract the searched information (URI) I use the two times the awk command.

At this point I have a pipe with a list of URI. The function of xargs is just to get these values, substitute them in a parametrized command and execute the result.

In this example I have to execute several commands at each iteration. xargs doesn’t permit this but a simply trick will help us: we choose a shell as command and execute a script inside it.

Just to complete the description of the example the curl retrieves the web page from internet, the grep command checks for the searched value, and the result is thrown in the trash. This because I’m interested only in the return value of the grep command.

The return value of the grep is checked and if the word isn’t found the URI is written in the output.

Come diventare raggiungibili da internet su rete fastweb con il protocollo IPv6

Molti di quelli che si connettono su rete Fastweb lo fanno ancora attraverso un Natting di rete; l’indirizzo IP con cui ci si presenta su internet è quindi condiviso con molti altri utenti.

Questo tipo di configurazione è perfettamente funzionale ad una normale navigazione su internet e in una certa misura migliora la sicurezza del nostro pc perché non ci espone direttamente dall’esterno.

Come contropartita però è un problema da aggirare se si vogliono implementare dei servizi di tipo server (un server web ad esempio) o per l’utilizzo di alcuni programmi (in genere giochi, sistemi peer-to-peer o altro) che, assegnando un ruolo paritario alle macchine coinvolte e richiedono ad ognuna alternativamente di assumere sia il ruolo del server sia quello del client.

Cercando su google idee su come gestire questo problema su una connessione fastweb ho trovato riferimenti sostanzialmente a tre tipi di indicazioni:

  • si ha già un IP dedicato ma bisogna configurare il portforwarding sul proprio router
  • molti dicono (ma io non ho provato e quindi mi limito a riportare quanto letto altrove) che in genere, insistendo con il supporto, si riesce a farsi assegnare un IP, non mi è chiaro se gratuitamente o meno.
  • se si è su rete nattata non c’è modo di aggirare il problema.

In realtà è comunque possibile sfruttare il protocollo IPv6 per gestire questo problema. Data la natura di questo protocollo infatti ogni IPv6 è un identificatore univoco di un apparato dulla rete.

Lo si può abilitare ad esempio come ho descritto in “primi passi in IPv6.

CORS on Amazon S3 and CloudFront

To enable the CORS (Cross-Origin Resource Sharing) on a tipical Amazon infrastructure it is necessary to configure both S3 and CloudFront. The behaviour of the various browser is not the same but on chrome the Header Access-Control-Allow-Origin is expected in the answer.

On S3 you have to add CORS properties in the properties tab. You will insert something like;

<?xml version="1.0" encoding="UTF-8"?>
<CORSConfiguration xmlns="http://s3.amazonaws.com/doc/2006-03-01/">
    <CORSRule>
        <AllowedOrigin>*</AllowedOrigin>
        <AllowedMethod>GET</AllowedMethod>
        <MaxAgeSeconds>3000</MaxAgeSeconds>
        <AllowedHeader>Athorization</AllowedHeader>
    </CORSRule>
</CORSConfiguration>

On CloudFront you have to change the behaviour of the origin to enable the forward of the request header. It is suggested to chose the whitelist mode and select the Origin header to have a better caching. This step is required to let the Origin header reach S3: without it S3 replies ignoring the CORS headers.

To test the result a curl can be used but the Origin header has to be inserted in the request using an existing (authorized) domain.

curl -H "Origin: http://www.example.com"  --verbose  http://***/fonts/arial.ttf

pattern discovery in python con Apriori Method

Parlerò in questo post di uno script python per effettuare la pattern discovery: voglio cioè estrarre i pattern più frequenti da una lista di transazioni.

Lo script utilizza l'”Apriori Method” come algoritmo per la determinazione dei Frequent Pattern e al momento non si occupa della determinazione delle “association rules”.

L'”apriori method” è uno dei più semplici algoritmi non Brute Force per la Pattern Discovery e si basa sulla considerazione che se una data sequenza ha una certa frequenza nelle transazioni, tutte le sue sottosequenza devono avere una frequenza uguale o periore. E’ quindi possibile partire dalla sequenza più corte, selezionare quelle frequenti secondo una soglia predeterminata e costruire le sequenze più lunghe a partire da quelle selezionate in precedenza.

L’algoritmo è quindi costituito da un ciclo di due step che continua fino a che è possibile generare potenziali sequenze frequenti. Gli step sono

  1. generazione della lista di potenziali sequenze a partire dalla combinazione delle sequenze prodotte dal ciclo precedente
  2. puliza (pruning) della lista basata sul calcolo dell’effettiva frequenza.

Lo script ricalca questa metologia e presenta un ciclo e due funzioni.

Iniziamo quindi ad esaminare lo script:

from pprint import pprint

debug = False;
file = 'elenco.txt';
sep= ',';
minSup = 0.07;

a = open(file, 'r')
itemList = a.readlines()
a.close()

# used sorted for simplicity, so that same 2 items but in different order
# won't be added to 2-itemsets (i.e. Beer,Diaper and Diaper,Beed)
itemList = [sorted(item.rstrip('\n').split(sep)) for item in itemList]

Lo script legge i dati da un file denominato elenco.txt in cui ogni riga rappresenta una transazione e contiene una lista separata da virgole di elementi. Ad es:

farina,uova,latte,banana,patata,biscotto,cioccolatino
farina,uova,latte,biscotto,tavolino,cioccolatino
farina,uova,latte,patata,carne,cavolfiore

I dati sono inseriti, ordinati, in una lista di liste per le successive elaborazioni.

Prima di entrare nel ciclo vero e proprio eseguo separatamente i due step per il primo run; questo è infatti anomalo perché la lista di elementi da esaminare viene generata in modo speciale: si prendono tutte le sequenze di lunghezza uno non essendoci una sequenza precedente da cui partire.

elementList = generateNextItemsetList( [], itemList );

frequencies = FrequentElements( elementList, itemList , minSup );
pprint( frequencies );

Le due due funzioni che qui compaiono corrispondono esattamente ai due step dell’algoritmo:

generateNextItemsetList()

        : genera la lista di elementi da esaminare

FrequentElements( elementList, itemList , minSup )

      : verifica la frequenza degli elementi della lista

La prima funzione restituisce una lista di liste ognuna contenente una data sequenza

[
 ['latte', 'uova'],
 ['farina', 'latte'],
 ['codetta', 'farina']
]

mentre la seconda un dizionario che ha per chiave una stringa costruita con gli elementi della sequenza e per valore una lista con le frequenze assoluta e relativa della sequenza stessa

{
 'banana,biscotto': [2, 0.08333333333333333],
 'biscotto,cioccolatino': [2, 0.08333333333333333],
 'biscotto,farina': [3, 0.125]
}

Questa parte si conclude con la stampa della frequenza degli elementi interessanti. Per la stampa ho utilizzato la funzione pprint che restituisce un output un poco più leggibile per liste e dizionari.

Inizia poi il ciclo vero e proprio che non fa nulla di realmente differente:

while ( True ):
    elementList = [];
    for a in frequencies.keys():
        elementList.append( a.split(',') );
    if debug : print ( elementList );

    elementList = generateNextItemsetList( elementList, itemList, debug );
    if debug : print ( elementList );

    frequencies = FrequentElements( elementList, itemList , minSup );
    pprint( frequencies );
 
    if len( frequencies ) == 0:
        break;

Per prima cosa costruisco la lista degli elementi a partire dalle chiavi del dizionario generato nel ciclo precedente, genero poi la nuova lista di elementi da esaminare ed esamino infine la nuova lista.

Come accennato nella premessa, se la lista generata è vuota il ciclo is interrompe.

Esaminiamo ora in maggior dettaglio le due funzioni iniziando da def generateNextItemsetList( previousList = [], transactions = [] , debug = False ).

def generateNextItemsetList( previousList = [], transactions = [] , debug = False ):
    """ This function generates (k+1)-itemset candidates starting from k-itemset
        if the previousList is empty the function generates the 1-itemset
        The function requires a sorted list as input and generate a sorted list for a new call of this function
    """
    if debug: print( previousList );
    k = len(previousList);
    elements = [];
    # if the list is empty i generate all the possible 1-itemset
    if ( k == 0 ):
        for transaction in transactions:
            for element in transaction:
               try:
                   elements.index( [element] );
                   break;
               except:
                   elements.append( [element] );
    # if the itemset is not empty join as for apriori
    # yes else is part of the for cicle
    else:
        count = 0;
        for i in range( 0, k ):
            for j in range ( 0, i ):
                if (i != j):
                    for l in range ( 0, len(previousList[i])-1 ):
                        if ( previousList[i][l] != previousList[j][l] ):
                            break;
                    else:
                        elements.append( [] );
                        if debug : print( elements[count] );
                        if debug : print( previousList[i][0] );
                        for l in range ( 0, len(previousList[i])-1 ):
                            elements[count].append( previousList[i][l] );
                        elements[count].append( previousList[i][len(previousList[i])-1] );
                        elements[count].append( previousList[j][len(previousList[j])-1] );
                        elements[count] = sorted( elements[count] ); 
                        if debug : print( elements[count] );
                        count += 1;

    if debug : print( sorted(elements) );
    return sorted(elements);

Come già detto, questa funzione si occupa di generare la lista degli elementi che è utile esaminare. Lo fa in due modi differenti: se la lista delle sequenze del ciclo precedente è vuota, esamina la lista delle transazioni ed estrae tutti gli elementi singoli. Altrimenti accoppia tutte le sequenze che differiscono per un solo elemento e genera la sequenza che contiene l’unione degli elementi di queste due sottosequenze.

Ho usato qui il costrutto for … else…: in questo modo i comandi nel blocco dell’else vengono eseguiti se il ciclo for non viene interrotto. Ovvero solo se i primi n-1 elemnti sono uguali costruisco la stringa di lunghezza n+1.

La seconda funzione è def FrequentElements( elements = [], transactions = [], minSup = 0.5, debug = False ).

def FrequentElements( elements = [], transactions = [], minSup = 0.5, debug = False ):
    """ This function get as input the list of the element to be tested, the list of transactions and the values of minimun support.
        The function returns a dictionary that has as keys the frequent elements and values a list with the count and the support
    """
    frequencies = {};
    allFrequencies = {};
    label = '';
    numTransactions = len(transactions);

    # calculate frequencies
    for element in elements:
        if isinstance( element, str ):
            for transaction in transactions:
                try:
                    allFrequencies[ element ] += transaction.count( element );
                except:
                    allFrequencies[ element ] = transaction.count( element );
        else:
            label = '';
            for a in element:
                label += ','+a;

            label=label.lstrip(',');

            for transaction in transactions:
                flag = 0;
                for field in element:
                    if ( transaction.count( field ) == 0 ):
                        flag -= 1;
                        break;

                if flag >= 0:
                    try:
                        allFrequencies[ label ] += 1;
                    except:
                        allFrequencies[ label ] = 1;

    # purging dictionary
    for element in elements:
        if isinstance( element, str ):
            if allFrequencies[ element ] / numTransactions >= minSup:
                frequencies[ element ] = [ allFrequencies[ element ], allFrequencies[ element ] / numTransactions ];
        else:
            label = '';
            for a in element:
                label += ','+a;

            label=label.lstrip(',');

            if label in allFrequencies and allFrequencies[ label ] / numTransactions >= minSup:
                frequencies[ label ] = [ allFrequencies[ label ], allFrequencies[ label ] / numTransactions ];

    return frequencies;

In questa funzione ci sono due parti: per prima cosa vengono contate le occorrenze delle sequenze in esame e come secondo step vengono selezionate le sequenze sufficientemente frequenti.

In entrambi gli step vengono considerati due casi: un primo passaggio in cui l’elemento della lista è una stringa ed i cicli successivi in cui l’elemento della lista esterna è anch’esso una lista.

E’ interessante notare che la frequenza viene determinata confrontando ogni elemento della lista di sequenze con ogni elemento della lista delle transazioni. Io ho eseguito i cicli in questo ordine: nel caso la lista delle transazioni fosse stata così grande da non poter essere mantenuta in memoria sarebbe stato conveniente invertire i due cicli in modo da dover leggere le transazioni da disco una volta sola (per una data lunghezza delle sequenze). In altre parole sarebbe convenuto prendere una transazione alla volta e incrementare dei contatori associati alle sequenze presenti.

Questa considerazione mette in evidenza uno dei limiti più importanti dell’ apriori method: richiede inevitabilmente molti “sequential scan” della lista delle transazioni: operazione che può essere molto costosa nel caso sia necessario mantenere la lista su disco.

Altro limite importante che deriva dall’effettuare la Pattern Discovery con l’Apriori Method è che la lista delle sequenze da esaminare, può essere, in determinate condizioni, estremamente lunga. Si pensi ad esempio al caso in cui esistono sequenze interessanti di centinaia o migliaia di elementi: ogni sottosequenza è potenzialmente interessante e il numero di sottosequenze non ordinate di una sequnza di lunghezza m è (2^m-1); un numero che diventa presto enorme.

Il codice di questo script può essere recuperato all’indirizzo https://github.com/grimli/pattern_discovery.

Gestione dei Log con syslog

Una necessità primaria dei sistemi di produzione è la raccolta e la gestione dei log.

Sempre di più i log vengono generati in enorme quantità e quando l’infrastruttura cresce oltre un certo livello diventa fondamentale passare ad un sistema che ne gestisca la centralizzazione.

Su Linux generalmente si usa una qualche versione del demone syslog (su ubuntu ad esempio ci sono tre opzioni dsyslog, rsyslog, syslog-ng) a questo scopo. Questi sistemi si occupano sia della gestione locale dei log sia della loro eventuale centralizzazione e mettono a disposizione strumenti per filtrare le informazioni più importanti o per integrarsi con sistemi di monitoraggio come nagios o con sistemi di reportistica come logstash. La scelta di un file come repository finale dei dati non è obbligata ma questi sistemi permettono di passare i dati a molti altri tipi di repository.

Farò riferimento per i dettagli a syslog-ng.

Conviene immaginare questi sistemi come a gestori di flussi di informazioni nei quali ci sono dei punti di entrata (un server apache ad esempio), delle regole di elaborazione più o meno complesse e dei punti di uscita (tipicamente un file, altri server syslog nei sistemi centralizzati, database etc..). La configurazione rispecchia questa prospettiva.

Una volta definiti delle opzioni generali si definisco le sorgenti dei log. Questa ad esempio raccoglie le informazioni che tipicamente finiscono sui log standard di sistema.

source s_src { unix-dgram("/dev/log"); internal();
             file("/proc/kmsg" program_override("kernel"));
};

Altre tipiche sorgenti di dati saranno delle porte in ascolto su protocolli udp o tcp

source s_udp_apache {
        udp(ip(0.0.0.0) port(8515));
};
source s_tcp_apache {
        tcp(ip(0.0.0.0) port(8515));
};

utili sia per la costruzione di sistemi gerarchici che permettano la centralizzazione dei log sia come sistema semplice per separare su molti canali i log.
Tra le possibili sorgenti ci sono anche i file

source s_apache_access {file("/var/log/apache2/access.log" log_fetch_limit(100) log_iw_size(1000)); };

utili ad esempio per raccogliere i log anche di sistemi che hanno solo questa.

Il secondo elemento chiave della configurazione sono le destinazioni dei flussi di log. Anche in questo caso è possibile inviare i log su di un file locale, su un canale tcp o udp nel caso di sistemi gerarchici per la gestione di log.

destination d_auth { file("/var/log/auth.log"); };
destination d_udp_system { udp(vip-syslog.de.prod port(8514));};
destination d_tcp_system { tcp(vip-syslog.de.prod port(8514));};

Ci sono molte possibili altre destinazioni tra cui stream unix, o mongodb.

Il terzo elemento della configurazione è filter. Come il nome lascia intuire questo elemento serve a definire delle regole per selezionare un sottoinsieme dellerighe in arrivo. L’elemento tradizionale per suddividere i log è la selezione della facility, ma filter permette di agire su svariati elementi tra cui l’host di invio, il livello del messggio (notice, warn, error…) appositi tag assegnati alla riga di log o anche regular expression sul contenuto.

filter f_err { level(err); };
filter f_mail { facility(mail) and not filter(f_debug); };

I vari elementi della configurazione devono essere poi combinati con un’ultimo elemento della configurazione:

log { source(s_src); filter(f_auth); destination(d_auth); };
log { source(s_apache_extranet); destination(d_apache_extranet); flags(flow_control); };

La combinazione di questi elementi permette una grande flessibilità nella gestione del log. Tornerò su questo tema per approfondirne il filtraggio ed altre opzioni.

Cambiare sfondo periodicamente con Ubuntu Unity

Stranamente Ubuntu Unity non prevede un meccanismo per cambiare lo sfondo periodicamente selezionando delle immagini da una cartella come invece è possibile fare su praticamente ogni altro desktop environment.

A questo è comunque possibile ovviare con facilità sfruttando il comando
gsettings
che permette di gestire da linea di comando molte delle impostazioni dell’interfaccia grafica.

Il comando per cambaire lo sfondo è molto semplice

gsettings set org.gnome.desktop.background picture-uri "file://<path to file>"

e potete testarlo con un’immagine a vostra scelta.

Il secondo obiettivo che ci eravamo posti è quello scegliere un’immagine casualmente un’immagine da una cartella. Si può fare in modo molto semplice con gli strumenti della shell unix. In primo luogo usiamo find per farci dare l’elenco dei file con i path assoluti, utilizziamo poi sort per mischiare casualmente l’eleco; sort, infatti, con l’opzione
-R restituisce un’ordinamento casuale. Usiamo infine
head
per selezionare il primo elemento della lista.

find <absolute path to image directory> |sort -R |head -1

Per combinare le due cose utiliziamo le variabili della shell

export SFONDO="$(find <absolute path to image directory>|sort -R |head -1)"; gsettings set org.gnome.desktop.background picture-uri \"file://${SFONDO}\"

L’ultimo cosa che ci rimane da fare è rendere periodica questa operazione. Per farlo useremo ovviamente
crontab
ma il comando così comè non funzionerebbe perché gsettings, per funzionare correttamente utilizza le variabili di ambiente e crontab crea un ambiente “anomalo” in cui molte di queste variabili o non sono definite o hanno valori specifici.

Per il nostro script ci serve il valore di
DBUS_SESSION_BUS_ADDRESS
. Possiamo vederne il valore con un semplice echo

echo $DBUS_SESSION_BUS_ADDRESS

Questa variabile permette a gsettings di sapere su quale ambiente grafico andare ad agire e deve essere letta “live” cambiando ad ogni sessione grafica. Per recuperarla bisogna fare un po’ di passi. In primo luogo
pgrep
ci permette di recuperare il PID del processo. Con questa operazione possiamo andare a recuperare il valore della variabile dalle informazioni in proc

export PID=$(pgrep gnome-session)
grep -z DBUS_SESSION_BUS_ADDRESS /proc/${PID}/environ

infine awk ci permette di separare il valore dal nome della variabile

grep -z DBUS_SESSION_BUS_ADDRESS /proc/${PID}/environ|awk -F= '{print $2"="$3}'

Non ci rimane che eseguire
crontab -e
ed inserire una riga con la schedulazione voluta ed i comandi

*/10 * * * *  export PID=$(pgrep gnome-session);export DBUS_SESSION_BUS_ADDRESS=$(grep -z DBUS_SESSION_BUS_ADDRESS /proc/${PID}/environ|awk -F= '{print $2"="$3}') ;export SFONDO="$(find <absolute path to image directory> |sort -R |head -1)"; gsettings set org.gnome.desktop.background picture-uri \"file://${SFONDO}\"

L’*/10 sta ad indicare che il comando deve essere eseguito ogni 10 minuti.

glusterfs – introduzione

GlusterFS è un filesystem distribuito.

Supera alcuni dei problemi storici di filesystem di rete come NFS e CIFS. In alcuni casi può essere utilizzato come alternativa ad un NAS; un NFS esportato da un NAS può infatti essere considerato affidabile ma se è un server ad esportare l’NFS, come a volte ci si trova a dover fare per ragioni economiche o perché ci si trova su cloud, difficilmente si potrà fare un grosso affidamento su questo sistema. Non è infatti possibile costruire un completamente ridondato con NFS. GlusterFS invece porta con se nativamente questa funzionalità.

GlusterFs comunque, ha tutta una serie di caratteristiche che lo rendono interessante

  1. E’ nativamente ridondabile ed possibile avere dei mount in HA: non più macchine congelate per un mount nfs che non risponde
  2. I suoi volumi possono essere fatti crescere o possono essere ristretti a caldo sfruttando la possibilità di distribuire i dati su più server o, meglio, su più brick
  3. I dati possono essere ridondati
  4. Si può aumentare la velocità di lettura replicando i dati su più server o quelle di lettura e scrittura sfruttando la funzionalità di striping
  5. Esporta anche con il protocollo NFSv3 per retrocompatibilità, ma è chiaramente meglio sfruttare il client nativo
  6. Ha una interessante funzionalità di replica geografica che permette di mantenere una copia asincrona sfruttabile per disaster recovery, backup o altro

Dopo aver definito dei pool di server affidabili, GlusterFS permette di aggiungere a dei volumi virtuali parti del filesystem dei server coinvolti denominate Brick. Non si lavora quindi con partizioni ma con directory all’interno di partizioni montate sul filesystem. Il tutto avviene in user space.

Il sito ufficiale è http://www.gluster.org/. Da qui si può scaricare l’ultima versione o in alternativa si possono utilizzare i pacchetti presenti in buona parte delle distribuzioni. Attualmente l’ultima versione stabile è la 3.5.2 e si sta lavorando al rilascio della versione 3.6.

Se si vuole una versione aggiornata sul sito ufficiale

http://download.gluster.org/pub/gluster/glusterfs/

è possibile scaricarla.
In alternativa alcune distribuzioni permettono di integrare la procedura nel proprio sistema di pacchetti. Ad esempio su ubuntu

sudo add-apt-repository ppa:semiosis/ubuntu-glusterfs-3.5
sudo aptitude update
sudo aptitude install glusterfs-server glusterfs-client

Il comando base per la gestione di glusterfs è gluster. Questo può essere eseguito direttamente con tutti i parametri come in

# gluster pool list

o, senza parametri, per accedere ad una consolle da cui gestire il cluster gluster:

# gluster
gluster> pool list

In entrambi i casi si otterrà un risultato analogo a

 
UUID					Hostname	State
dee79aaa-6042-4bc6-a17a-27e4944db3c9	localhost	Connected 

che ci informa che il solo localhost è nel pool di server che possono essere coinvolti nella formazione dei volumi.

Si consigli di l’esecuzione di

gluster help

per avere un’idea di quello che è possibile fare.

In un prossimo articolo vedremo alcuni esempi di configurazione.

python e automi cellulari – griffeath circular cellular automata

Vediamo qui un esempio diverso di automa cellulare: L’automa circolare di Griffeath.

Il sitema è analogo a quello di life trattato qui e qui. Abbiamo una tabella costituita da punti di una mappa ognuno con un suo stato, un tempo di evoluzione costituito da istanti discreti e delle regole che determinano lo stato successivo di ogni punto sulla base degli stati dei vicini.

Il sistema rimane quindi definito da:

  • una matrice di punti ad ognuno dei quali deve essere associato uno stato individuato da un intero. Utilizzaremo una lista di liste il cui valore corrisponde allo stato. 10 stati possibili  è un volore ragionevole per questo sistema e lo utilizzerò nell’esempio. Il programma sarà comunque facilmente modificabile per gestire un numero di stati differenti
  • una regola di evoluzione: un punto mangia tutti i vicini nello stato immediatamente inferiore. Se avessi 4 stati il 3 mangia il 2, il 2 mangia l’1, l’1 mangia lo 0 e lo 0 mangia il 3. Se una casella viene mangiata nell’istante successivo assumerà lo stato della casella da cui è stata mangiata.
    Ogni elemento può mangiare ed essere mangiato nello stesso step
    In questo sistema per vicini si intendono le sole 4 caselle che condividono un lato.

Questo sistema, più ricco di quello del gioco life ha un comportamento molto diverso: passa sempre attraverso tre fasi:

  • una prima fase con una distribuzione casuale di punti
  • una fase in cui si formano delle grandi macchie
  • la comparsa di spirali che crescono fino a riempire completamente il sistema.

Per realizzare questo automa cellulare ho ripreso la classe del precedente adattando i metodi al nuovo sistema. Il codice completo è disponibile a questo indirizzo.

Come per il sistema life, non ho fatto un gramde sforzo per ottimizzare il metodo che calcola l’evoluzione del sistema dato che il grosso del tempo viene speso per rappresentarlo graficamente. Vorrei comunque in futuro almeno sfruttare i thread per suddividere il calcolo tra più CPU e magari trovare un metodo migliore per rappresentare il risultato.

L’automa cellulare è basata su una classe che mostra tre metodi: il cosrtruttore, una funzione per farlo evolvere e una funzione per rappresentarlo graficamente.

Il costruttore fa proprio quello che ci si aspetterebbe da un costruttore: definisce le strutture dati che costituiscono l’oggetto e gli assegna dei valori iniziali:

class CellularAutoma:
   def __init__(self, lenght=500, scale=1, levels=10):
      """genera la tabella iniziale quadrata e di dimensione iniziale lenght""
      self.board = [[]]
      self.pantone = []
      self.scale = scale
      self.levels = levels
      self.time = 0
      line = []
      random.seed()

      for a in range( lenght ):
         line = []
         for b in range( lenght ):
             line.append( random.randint( 0, self.levels-1 ))
         self.board.append( line )

      self.board.remove([])

      #inizializzo ambiente grafico 
      self.master = Tk()
      self.master.title('Griffeath circular cellular automata')
      self.w = Canvas(self.master, width=lenght*self.scale, height=lenght*self.scale)
      self.w.pack()

      #generate pantone
      for a in range( self.levels ):
         self.pantone.append( "#"+str(random.randint( 100000,999999 )))

self.board è una lista di liste che conterrà lo stato corrente del sistema
self.pantone conterrà una tavolozza di colori necessaria per la rappresentazione grafica del sistema
scales e levels sono rispettivamente la dimensione del punto nella rappresentazione grafica e il numero di stati che può assumere un elemento del sistema.

Per scales, e per altri valori ho cambiato i valori di default rispetto all’esempio precedente per ottenere un effetto grafico più adatto a questo sistema.

self.time è un contatore che conta il numero di step di evoluzione che ha subito l’oggetto. Verrà mostrato su consolle al completamento di ogni step di evoluzione: questo rende evidente che il grosso del tempo viene speso a generare la rappresentazione grafica per inciso.

Segue un blocco di codice che assegna ad ogni elemento del sistema un valore iniziale casuale

      line = []
      random.seed()

      for a in range( lenght ):
         line = []
         for b in range( lenght ):
             line.append( random.randint( 0, self.levels-1 ))
         self.board.append( line )

      self.board.remove([])

è abbastanza semplice e non mi dilunog a spiegarlo.

Inizializzo poi l’ambiente tkinter

      self.master = Tk()
      self.master.title('Griffeath circular cellular automata')
      self.w = Canvas(self.master, width=lenght*self.scale, height=lenght*self.scale)
      self.w.pack()

come si vede creo una finestra con dentro un widget canvas su cui andrò poi a disegnare la rappresentazione grafica del sistema

Il metodo si conclude con la generazione della tavolozza di colori:

      #generate pantone
      for a in range( self.levels ):
         self.pantone.append( "#"+str(random.randint( 100000,999999 )))

Ho optato per una selezione casuale dei colori che mi ha permesso di mantenere il numero di stati un semplice parametro numerico. C’è ovviamente il rischio che due stati vengano rappresentati con lo stesso colore ma direi che è abbastanza remoto.

Il secondo metodo della classe è evolve()

   def evolve( self ):
      """esegue lo step di evoluzione del gioco life su una tabella sferica"""
      rows = len(self.board)
      columns = len(self.board[0])
      board2 = [[0 for j in range(rows)] for i in range(columns)]


      for i in range( 0, rows ):
         for j in range( 0, columns ):
            if (self.board[(i-1)%(rows)][j%(columns)]-1)%self.levels  == self.board[i][j]:
               board2[i][j] = (self.board[i][j]+1)%self.levels
            elif (self.board[i%(rows)][(j-1)%(columns)]-1)%self.levels  == self.board[i][j]:
               board2[i][j] = (self.board[i][j]+1)%self.levels
            elif (self.board[i%(rows)][(j+1)%(columns)]-1)%self.levels  == self.board[i][j]:
               board2[i][j] = (self.board[i][j]+1)%self.levels
            elif (self.board[(i+1)%(rows)][j%(columns)]-1)%self.levels  == self.board[i][j]:
               board2[i][j] = (self.board[i][j]+1)%self.levels
            else:
               board2[i][j] = self.board[i][j]

      self.board = board2
      print("time: %d" %self.time )
      self.time = self.time+1

dopo alcune definizioni iniziali di variabili che verranno sfruttate nel metodo si inizia l’esame di tutti i punti del sistema. Ogni punto viene confrontato con i vicini e se il suo stato è quello immediatamente inferiore a quello di uno dei 4 vicini viene salvato nel punto corrispondente della tabella temporanea il suo valore incrementato di uno. Altrimenti viene salvato il suo valore.
L’operatore modulo viene sfruttato qui per gestire la circolarità del sistema, sia geometrica sia sugli stati.

A esame concluso lo stato attuale viene scambiato con quello calcolato, viene stampato in consolle il numero dello step e incrementato il tempo di uno.

L’ultimo metodo su cui è stato necessario intervenire è il metodo show().

Quì era necessario un sistema più generale che permettesse di rappresentare un numero arbitrario di stati. Ne è risultata, come a volte accade, una funzione anche più semplice di quella usata negli articoli precedenti:

   def show( self ):
      """Gives a graphical representation of the data"""
      self.w.delete(ALL)
      for i,v in enumerate(self.board):
         for j,w in enumerate( self.board[i] ):
               self.w.create_rectangle(i*self.scale, j*self.scale, i*self.scale+self.scale, j*self.scale+self.scale, fill=self.pantone[self.board[i][j]], outline=self.pantone[self.board[i][j]] )

Dato che questo sistema è più gradevole alla vista se costituito da tabelle grandi e punti piccoli, ho sfruttato il parametro outline per evitare il bordino nero del rettangolo che rappresenta il punto che in questo caso era di dimensioni confrontabili con il punto stesso e, quindi, piuttosto fastidioso.

tkinter, python e automi cellulari – life

lifeRiprendiamo l’esempio del gioco life, già visto in un precedente articolo, per esaminare l’utilizzo della libreria tkinter del python. Questa libreria permette l’utilizzo della GUI in questo linguaggio.

Il codice integrale di questo esempio è disponibile a questo indirizzo; riporto qui solo gli stralci relativi alla libreria tkinter.

Il corpo principale del programma inizia ovviamente importando i moduli necessari:

import random
from tkinter import *

random per la generazione casuale della configurazione iniziale e tkinter per la GUI.

Viene poi richiesta la dimensione della tabella che si vuole gestire e, a seguire, creato un oggetto CellularAutoma.

dim = input( "Inserisci la dimensione della board: ")
board = CellularAutoma( int(dim) )

CellularAutoma è la classe su cui si basa tutto l’applicativo e, oltre a contenere una tabella (lista di liste per la precisione) con i dati dell’ultimo stato del sistema definisce i metodi per rappresentarlo graficamente (show) e calcolare lo stato successivo (evolve).

board.show()

while True:
   board.evolve( )
   board.show()
   board.master.update()

Il programma, come si vede, contiene poco più che chiamate a questi metodi; infatti, dopo lo show della configurazione iniziale, entra in un loop nel quale viene calcolato lo stato successivo, viene mostrato a video lo stato e si utilizza la funzione update della libreria per permettere al ciclo di procedere e non rimanere bloccato nei loop degli eventi dell’interfaccia grafica.

Passiamo ora ad esaminare la classe: non entreremo nel dettaglio di tutti i metodi, come detto, perché alcuni di questi non hanno differenze rilevanti dalle funzioni esaminate nel precedente articolo sul gioco life.

La struttura della classe è:

class CellularAutoma:
   def __init__(self, lenght=6):
      """genera la tabella iniziale quadrata e di dimensione iniziale lenght"""
      self.board = [[]]
 
   def evolve( self ):
      """esegue lo step di evoluzione del gioco life su una tabella sferica"""
 
   def show( self ):
      """Gives a representation of the data"""

Esaminiamo ora i metodi iniziando dal costruttore dove oltre all’inizializzazione dei dati, che qui non vediamo nel dettaglio ma che si basa sulla generazione di numeri casuali, viene anche creato un’oggetto per la GUI:

   def __init__(self, lenght=6):
      """genera la tabella iniziale quadrata e di dimensione iniziale lengoht"""
      self.board = [[]]
      
      [...]

      #inizializzo ambiente grafico 
      self.master = Tk()
      self.master.title('life game')
      self.w = Canvas(self.master, width=lenght*10, height=lenght*10)
      self.w.pack()

Viene infatti inizializzato l’ambiente grafico creando un oggetto della classe Tk, assegnato un nome alla finestra, aggiunto un oggetto immagine (Canvas) alla finestra e infine si utilizza il metodo pack() per organizzare gli oggetti nella finestra. In questo caso la chiamata a pack()  è relativamente utile essendoci solamente un oggetto canvas nella finestra.

Non entro nei dettagli del metodo evolve che non è coinvolto nella rappresentazione grafica.

Segue infine il metodo show() che rappresenta graficamente lo stato del sistema.

   def show( self ):
      self.w.delete(ALL)
      for i,v in enumerate(self.board):
         for j,w in enumerate( self.board[i] ):
            if (self.board[i][j] == 0):
               self.w.create_rectangle(i*10, j*10, i*10+10, j*10+10, fill="blue")
            else:
               self.w.create_rectangle(i*10, j*10, i*10+10, j*10+10, fill="yellow")

Anche in questo caso la libreria tkinter rende le cose piuttosto seplici; abbiamo infatti un loop su tutti gli elementi della tabella e andreamo a rappresentare sul nostro oggetto canvas un quadrato blu per le celle vuote ed un quadrato giallo per quelle piene. La funzione che utilizziamo in questo caso è

create_rectangle(x0, y0, x, y, fill="yellow")

La delete() a inizio metodo serve a rimuovere gli oggetti creati in precedenza.

La libreria tkinter mi permette quindi di definire una GUI perfettamente funzionale con pochi passi:

  • definisco un oggetto GUI
  • ne specifico gli elementi grafici
  • controllo il flusso del programma con mainloop, update e funzioni per la gestione dei vari eventi che è necessario controllare

Abbiamo visto qui un esempio di utilizzo della libreria tkinter, documentazione più completa è disponibile nella documentazione ufficiale di python.