Un servidor SSH a la tauleta Android

Tota tauleta Android té un Linux amagat al seu interior.

Per arribar fins aquest Linux hi han diverses opcions. La que he trobat més senzilla és mitjançant l’app Termux.

Termux

Termux és una app que es pot instal·lar des del Google Play.

Segons ens diu la seva pàgina:

“Termux combina una potent emulació de terminal amb una extensa col·lecció de packages de Linux :

• Gaudeix de les shells bash i zsh.
• Edita fitxers amb nano i vim (o emacs, però en aquest cas és imprescindible un teclat!)
• Accedeix a servidors remots mitjançant ssh (o, afegeixo, aixeca un servidor ssh i accedeix remotament a la teva tauleta/telèfon!)
• Desenvolupa en C/C++ amb les eines clang, make i gdb.
• Fes servir la consola Python com una calculadora de butxaca (o escriu scripts de propòsit general amb Python).
• Fes check out o clona projectes de repositoris remots amb git o amb subversion.
• Juga amb aventures conversacionals basades en text (us sona la saga Zork?) amb l’interpret frotz.”

Tot això -punt important- sense necessitat de rootejar la tauleta.

Instal·lar Termux no té cap secret. A més de Termux,  convé instal·lar l’app Termux:API que complementa a Termux :

“Termux:API proporciona accés per la línia de comandes a les API’s del disposotiu :

* lectura i enviament de sms des del terminal.
* Accés al GPS des dels scripts.
* Aplicació del dispositiu text-to-speech als resultats de les comandes.
* Vibració del dispositiu.
* Accés al clipboard per als scripts.
* Accés a la llista de contactes per als scripts.”

Per un petit preu, també s’ofereixen altres apps que encara fan més útil Termux.

– Termux:Boot : permet executar scripts quan el dispositiu arrenca.
– Termux:Float : Permetr executar Termuxa una finestra flotant.
– Termux:Styling _ squemes de color i customització de l’aparença delterminal.
– Termux:Task : permet invocar executables de Termux des de Tasker i apps compatibles
– Termux:Widget : permet arrencar scripts de Termux des de la pantalla inicial de la tauleta

La Wiki de Termux és força completa i entenedora. Dins la Wiki de Termux també trobem una completa secció de FAQs.

El que m’ha interessat més ha estat la possibilitat de disposar d’un repositori git a la tauleta, i que aquest repositori fos accessible des d’un altre ordinador mitjançant protocol ssh. És dir, el problema principal que m’he proposat resoldre amb Termux ha estat : com posar en marxa el servidor ssh a la tauleta? idealment, amb el servidor ssh actiu a la tauleta, jo podria connectar-m’hi un client git des del portàtil, per exemple.

Instal·lació del programari

Primer de tot, cal instal·lar el programari necessari a la tauleta. La instal·lació de Termux des de Google Play no té cap dificultat. Un cop instal·lat, engego Termux…

Welcome to Termux!

Wiki: https://wiki.termux.com
Community forum: https://termux.com/community
IRC channel: #termux on freenode
Gitter chat: https://gitter.im/termux/termux
Mailing list: termux+subscribe@groups.io

Search packages: pkg search 
Install a package: pkg install 
Upgrade packages: pkg upgrade
Learn more: pkg help
bash-4.4$ 

Observo que només hi ha un sistema base i cal afegir tot el programari que emcalgui.

Executo les següents instruccions (un teclat extern USB o Bluetooth pot ser de molta ajuda!)

Afegir paquets és molt semblant al procediment que se segueix amb distribucions Linux com Debian.

Vull una shell bash, com al Linux del sobretaula:

bash-4.4$ pkg install bash
Hit:1 http://termux.net stable InRelease
Reading package lists... Done
Building dependency tree       
Reading state information... Done
36 packages can be upgraded. Run 'apt list --upgradable' to see them.
Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following packages will be upgraded:
  bash
1 upgraded, 0 newly installed, 0 to remove and 35 not upgraded.
Need to get 360 kB of archives.
After this operation, 0 B of additional disk space will be used.
Get:1 http://termux.net stable/main arm bash arm 4.4.23-2 [360 kB]
Fetched 360 kB in 0s (1291 kB/s)
(Reading database ... 7367 files and directories currently installed.)
Preparing to unpack .../archives/bash_4.4.23-2_arm.deb ...
Unpacking bash (4.4.23-2) over (4.4.19) ...
Setting up bash (4.4.23-2) ...
bash-4.4$ 

Vull C/C++ i Python per a poder programar

– instal·lació de clang

bash-4.4$ pkg install clang
Hit:1 http://termux.net stable InRelease
Reading package lists... Done
Building dependency tree
Reading state information... Done
38 packages can be upgraded. Run 'apt list --upgradable' to see them.
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages will be upgraded:
clang
1 upgraded, 0 newly installed, 0 to remove and 37 not upgraded.
Need to get 11.1 MB of archives.
After this operation, 13.4 MB of additional disk space will be used.
Get:1 http://termux.net stable/main arm clang arm 6.0.1 [11.1 MB]
Fetched 11.1 MB in 6s (1664 kB/s)
(Reading database ... 7379 files and directories currently installed.)
Preparing to unpack .../archives/clang_6.0.1_arm.deb ...
Unpacking clang (6.0.1) over (5.0.1-1) ...
Setting up clang (6.0.1) ...
bash-4.4$

– instal·lació de python :

bash-4.4$ pkg install python
Hit:1 http://termux.net stable InRelease
Reading package lists... Done
Building dependency tree       
Reading state information... Done
37 packages can be upgraded. Run 'apt list --upgradable' to see them.
Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following packages will be upgraded:
  python
1 upgraded, 0 newly installed, 0 to remove and 36 not upgraded.
Need to get 5564 kB of archives.
After this operation, 393 kB disk space will be freed.
Get:1 http://termux.net stable/main arm python arm 3.6.6 [5564 kB]
Fetched 5564 kB in 3s (1849 kB/s) 
(Reading database ... 7397 files and directories currently installed.)
Preparing to unpack .../archives/python_3.6.6_arm.deb ...
Unpacking python (3.6.6) over (3.6.4-1) ...
dpkg: warning: unable to delete old directory '/data/data/com.termux/files/usr/lib/python3.6/lib2to3/tests': Directory not empty
Setting up python (3.6.6) ...
Setting up pip...
Looking in links: /data/data/com.termux/files/usr/tmp/tmp599bopw8
Collecting setuptools
Collecting pip
Installing collected packages: setuptools, pip
  Found existing installation: setuptools 28.8.0
    Uninstalling setuptools-28.8.0:
      Successfully uninstalled setuptools-28.8.0
  Found existing installation: pip 9.0.1
    Uninstalling pip-9.0.1:
      Successfully uninstalled pip-9.0.1
Successfully installed pip-10.0.1 setuptools-39.0.1
bash-4.4$ 

Haureu notat que els missatges que estic mostrant no corresponen a una instal·lació inicial si no a un upgrade. És que, de fet, per a escriure aquest post estic tornant a passar l’instal·lador.

En resum : el procediment és el mateix que amb els gestor de paquets d’altres distribucions.

Vull el git per mantenir el meu codi ben versionat

– git

pkg install git

Vull un editor que em permeti fer de tot, i que a més sigui programable amb Lisp!

– emacs

pkg install emacs

Necessito relaxar-me i distreure’m amb jocs de ficció interactiva.

– frotz

pkg install frotz

Criptografia i ssh.

– openssl :

pkg install openssl

– openssh :

pkg install openssh

Altres paquets que poden ser interessants : el gpg, netcat, curl…

Si feu

pkg list-all

Obtindreu una llista dels paquets disponibles. En general, instal·lar un paquet és tan senzill com

pkg install nom_paquet

Configuració del servidor SSH

El client SSH ens queda instal·lat sense més que instal·lar el paquet openssh El que resta és configurar el servidor ssh per a fer accessible la tauleta des de l’exterior.

Em baso en el que hi ha a :

https://glow.li/technology/2015/11/06/run-an-ssh-server-on-your-android-with-termux/

i també a https://wiki.termux.com/wiki/Remote_Access

El primer que cal tenir en compte és que el Termux només es per a un usuari. Això vol dir que qualsevol accés des de l’exterior ha de fer-se amb l’usuari que termux ens ha proporcionat. Però com us adonareu, termux no ens dona el password d’aquest usuari. És dir: no podem fer un login amb usuari – password.

Necessàriament, doncs, hem de fer el login d’una altre forma. La solució és crear una parell clau privada – clau pública d’accés amb ssh-keygen.

Simplement, executo ssh-keygen amb les opcions per defecte.

En el meu cas, com que ja disposava d’un parell clau privada/clau pública i ja l’he distribuït, el que he fet és generar el parell de claus a una carpeta alternativa.

bash-4.4$ ssh-keygen
Generating public/private rsa key pair.
Enter file in which to save the key (/data/data/com.termux/files/home/.ssh/id_rsa): /data/data/com.termux/files/home/alternative1_rsa
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
Your identification has been saved in /data/data/com.termux/files/home/alternative1_rsa.
Your public key has been saved in /data/data/com.termux/files/home/alternative1_rsa.pub.
The key fingerprint is:
SHA256:xMACExf/9or00y35to2/vw/ft3HBWKZypXOoWFJpAFk u0_a89@localhost
The key's randomart image is:
+---[RSA 2048]----+
|  +ooo..+E       |
|   o...+  . .    |
|     .. o  +   + |
|       o  o   X  |
|        S. o B + |
|       . .+ + o .|
|      .  o.+  ...|
|     . o..+ oo o=|
|      . o. ++o+=X|
+----[SHA256]-----+
bash-4.4$ 

Ara puc observar que han aparegut els fitxers id_rsa i id_rsa.pub a la carpeta ~/.ssh. Respectivament la clau privada i la clau pública que he generat.

bash-4.4$ ls -al ~/.ssh
total 32
drwx------    2 u0_a89   u0_a89        4096 Sep  1 22:33 .
drwx------    7 u0_a89   u0_a89        4096 Sep  2 17:20 ..
-rw-------    1 u0_a89   u0_a89           0 Sep  1 22:34 authorized_keys
-rw-------    1 u0_a89   u0_a89        3381 Sep  1 21:15 id_rsa
-rw-------    1 u0_a89   u0_a89         742 Sep  1 21:15 id_rsa.pub
-rw-r--r--    1 u0_a89   u0_a89         532 Sep  1 21:32 known_hosts
bash-4.4$ 

Ara vaig a provar que el servidor ssh funciona. Per a fer-ho, primer de tot l’engego (amb termux en mode bàsic, no tinc una altre opció que engegar manualment)

sshd

Vull provar connectant-me amb ssh des del mateix termux, per a fer-ho cal que la clau pública que acabo de generar estigui a la llista de claus autoritzades

Per això, simplement la concateno a authorized_keys que es troba a ~/.ssh

bash-4.4$ cat id_rsa.pub >> authorized_keys
bash-4.4$ chmod 600 authorized_keys
bash-4.4$ ls -al
total 36
drwx------    2 u0_a89   u0_a89        4096 Sep  2 18:42 .
drwx------    7 u0_a89   u0_a89        4096 Sep  2 17:20 ..
-rw-------    1 u0_a89   u0_a89         742 Sep  2 18:42 authorized_keys
-rw-------    1 u0_a89   u0_a89        3381 Sep  1 21:15 id_rsa
-rw-------    1 u0_a89   u0_a89         742 Sep  1 21:15 id_rsa.pub
-rw-r--r--    1 u0_a89   u0_a89         532 Sep  1 21:32 known_hosts
bash-4.4$ 

Arribats a aquest punt, ja puc provar el meu servidor ssh

bash-4.4$ ssh ip_tauleta -p 8022
Welcome to Termux!

Wiki:            https://wiki.termux.com
Community forum: https://termux.com/community
IRC channel:     #termux on freenode
Gitter chat:     https://gitter.im/termux/termux
Mailing list:    termux+subscribe@groups.io

Search packages:   pkg search 
Install a package: pkg install 
Upgrade packages:  pkg upgrade
Learn more:        pkg help
$ 

Accés des de l’exterior

A la vista de com ha funcionat aquest primer accés, ja puc veure quin és el procediment per accedir remotament al servidor ssh de la tauleta: cal que a les authorized_keys de la tauleta hi hagi la clau pública de l’usauri de l’ordinador remot amb el que penso accedir.

Això vol dir que si vull accedir a la tauleta des del meu sobretaula, el procediment és el següent:

1 – he de generar una parella clau privada-clau pública amb ssh-keygen al sobretaula
2 – aleshores, he de concatenar la clau pública generada a l’authorized_keys de la la tauleta.
3 – reinicio sshd.
Per engegar el servidor :

sshd

Per controlar-ne el funcionament :

logcat -s 'syslog:*'

Per aturar el servidor :

pkill sshd

He de copiar la clau pública del sobretaula a la tauleta. La solució més primitiva és fer servir un pendrive usb, passant físicament la clau des del sobretaula a la tauleta. Però, certament, aquest mètode no és gaire elegant.

Hi ha una opció millor : Des de la tauleta puc connectar-me amb scp o sftp al sobretaula (evidentment, sempre que el sobretaula també tingui un servidor ssh! en funcionament)

$ sftp albert@ip_sobretaula
Connected to albert@ip_sobretaula.
sftp> ls
Baixades                               Escriptori                             ...      
sftp> cd .ssh
sftp> ls
authorized_keys   authorized_keys~  id_rsa            id_rsa.pub        known_hosts       
sftp> get id_rsa.pub id_rsa_sobretaula.pub
Fetching /home/albert/.ssh/id_rsa.pub to id_rsa_sobretaula.pub
...
sftp> exit
$ ls -al
total 36
drwx------    2 u0_a89   u0_a89        4096 Sep  2 22:25 .
drwx------    7 u0_a89   u0_a89        4096 Sep  2 22:23 ..
-rw-------    1 u0_a89   u0_a89         742 Sep  1 22:06 authorized_keys
-rw-------    1 u0_a89   u0_a89        3381 Sep  1 21:15 id_rsa
-rw-------    1 u0_a89   u0_a89         742 Sep  1 21:15 id_rsa.pub
-rw-------    1 u0_a89   u0_a89         740 Sep  2 22:25 id_rsa_sobretaula.pub
-rw-r--r--    1 u0_a89   u0_a89         532 Sep  1 21:32 known_hosts
$ 

Cal indicar que des del sobretaula, també hi ha la possibilitat de fer servir ssh-copy-id per passar la clau pública tot just generada a un servidor remot. (consulteu https://www.ssh.com/ssh/copy-id).

ssh-copy-id

Es pot fer amb una instrucció com aquesta:

ssh-copy-id -i ~/.ssh/mykey user@host

Aquesta instrucció accedeix al host remot i afegeix la clau pública (*) de mykey al fitxer authorized_keys del host remot.

(*) La clau pública! La clau privada, com el seu nom indica, és privada i ningú més que el propietari l’ha de conèixer!

Si li cal, ssh-copy-id demanarà la forma d’autenticar-se amb el host remot. En el cas de Termux, això planteja el problema que no es coneix el password de l’usuari de Termux.

Arribats a aquest punt, ja tinc la clau pública del sobretaula a la tauleta i l’he concatenat a l’authorized_keys. Reinicio el servidor sshd i, des del sobretaula provo a accedir :

albert@artemis:~$ ssh 192.168.0.112 -p 8022
Welcome to Termux!

Wiki:            https://wiki.termux.com
Community forum: https://termux.com/community
IRC channel:     #termux on freenode
Gitter chat:     https://gitter.im/termux/termux
Mailing list:    termux+subscribe@groups.io

Search packages:   pkg search 
Install a package: pkg install 
Upgrade packages:  pkg upgrade
Learn more:        pkg help
$ 

Ja puc accedir a la tauleta des del sobretaula.

Seguint el mateix procediment puc donar accés ssh a la tauleta des de qualsevol altre equip. El truc és generar el parell clau privada/clau pública a cada ordinador des del que em vulgui connectar i concatenar la clau pública obtinguda a l’authorized_keys de la tauleta.

Accés Git al repositori de la tauleta

Finalment, una aplicació pràctica. Inicialitzo un repositori git a la tauleta. En el meu cas he creat una carpeta workspace amb diferents subcarpetes per a desar-hi projectes en diferents llenguatges. He inicialitzat un repositori git a aquesta carpeta workspace.

$ ls 
albert                alternative1_rsa      alternative1_rsa.pub  hosts                 prova.txt             storage               workspace
$ cd workspace/
$ ls -al
total 40
drwx------   10 u0_a89   u0_a89        4096 Sep  1 20:53 .
drwx------    7 u0_a89   u0_a89        4096 Sep  2 22:30 ..
drwx------    7 u0_a89   u0_a89        4096 Sep  1 20:58 .git
drwx------    2 u0_a89   u0_a89        4096 Aug 19 12:48 as
drwx------    2 u0_a89   u0_a89        4096 Aug 19 12:49 awk
drwx------    2 u0_a89   u0_a89        4096 Dec 16  2017 bash
drwx------    2 u0_a89   u0_a89        4096 Feb 20  2018 c
drwx------    2 u0_a89   u0_a89        4096 Feb 20  2018 cc
drwx------    2 u0_a89   u0_a89        4096 Dec 16  2017 elisp
drwx------    4 u0_a89   u0_a89        4096 Aug 19 12:49 python
$ 

Ara me’n vaig al sobretaula, i obro, per exemple, l’Eclipse que té el client EGit.

Simplement he de configurar ela URI del repositori al que vull accedir. He de parar atenció a:

1 – Indicar protocol ssh.
2 – Indicar la ip de la tauleta i, molt important, el port 8022.
3 – He indicat el path complet fins el repositori
3 – No cal que indiqui usuari i password.

La imatge ho aclareix :

git01

La següent pantalla em mostra la branca master del repositori git de la tauleta :

Selecció_002

A partir d’aquest punt ja podria fer el checkout dels projectes.

Molt important : per a que tot això funcioni cal que les IP dels diferents dispositius involucrats siguin fixes. Això vol dir que

1 – Al router de la vostra xarxa local cal donar IP fixes (dins del rang intranet, òbviament, és dir 192.168.x.x) als diferents ordinadors , impresores, smartphones o tauletes que pugueu tenir connectats

2 – Cal indicar a les tauletes que facin servir sempre la mateixa IP que li heu fet correspondre al router  per connectar-se a la vostra xarxa local.

Anuncis

Encoder-Decoder Codi Binari – Codi Gray

Reprenc el bloc després d’una aturada d’un any!

He dedicat bona part del temps que dedicava al bloc a estudiar. Des de fa un any i mig estic matriculat als estudis de Màster d’Enginyeria Informàtica de la UOC. He tornat a la Universitat gairebé trenta anys després de posar-hi el peu per primer cop!

Fa poc més d’un parell d’anys les circumstàncies professionals em van empènyer a canviar de feina. Una de les conseqüències d’aquell canvi va ser que em va semblar que era un bon moment per capitalitzar l’experiència professional acumulada després de… gairebé vint-i-cinc anys al sector TIC, dels quals més de setze específicament a la consultoria.

He de dir que em va molt bé, per ara, i que duri. També cal dir que m’ho estic prenent amb calma: només faig dues assignatures per semestre.

Tanmateix, la quantitat de temps que cal dedicar als treballs i pràctiques, només amb dues assignatures, és prou important. Tant que en tot un any no m’he vist amb cor de dedicar temps al bloc d’apunts de tecnologia.

idealment, a meva intenció és que bloc i estudis siguin activitats sinèrgiques. No és el cas d’avui, però alguns dels treball que ja he fet per a la UOC donen per a un post interessant, i potser els adaptaré i els acabaré publicant aquí. En aquest sentit, a diferència dels polítics del PP, el meu màster me l’estic currant…  i puc aportar proves.

Fetes aquestes explicacions, anem al gra. Avui presento un exercici senzill per reprendre el bloc : es tracta d’un decoder/encoder de codi Binari a codi Gray. El codi Gray és una d’aquelles coses que vaig aprendre a l’Enginyeria Tècnica de Telecos, quan estudiava electrònica digital allà pels finals dels vuitanta. Hi havia alguna cosa gairebé màgica en les simplificacions de circuits combinacionals fent servir mapes de Karnaugh. La màgia és que als mapes  de Karnaugh els minterms es distribueixen per la taula seguint el codi de gray, aleshores, elements adjacents difereixen només en un bit, i això vol dir que es pot simplificar la variable binària corresponent al bit que canvia en aquells termes adjacents.

Però té més usos. Notablement, es fa servir per minimitzar els errors en les modulacions digitals QAM i Gray Coded M-PSK.

De Viquipèdia (https://ca.wikipedia.org/wiki/Codi_Gray) : « El codi binari reflectit o codi Gray, nomenat així en honor de l’investigador Frank Gray, és un sistema de numeració binari en què dos valors successius difereixen només en un dels seus dígits.

El codi Gray va ser dissenyat originalment per prevenir senyals espuris dels switches electromecànics. Actualment és utilitzat per a facilitar la correcció d’errors en els sistemes de comunicacions, com ara alguns sistemes de televisió per cable i la televisió digital terrestre. »

Vet aquí un vídeo que explica perquè el codi gray és tan útil en els codificadors de posició rotatoris (elimina els valors espuris que podria introduir la codificació binària directa) :

De fet, la idea original d’aquest post era implementar un control rotatori basat en el codi Gray amb Arduino . Queda per a més endavant.

Anem per feina, el que vull fer és un codificador / decodificador de binari a gray, és dir, vull un mètode al que li passo un número enter de n bits, i vull que em torni un array amb els bits del codi gray corresponent al número rebut.

també vull el mètode que faci el camí de tornada, és dir, vull el mètode al que li passi un array de bits amb el codi gray d’un número de n bits, i vull que em torni un array amb els bits de la codificació binària directa d’aquell número.

L’algoritme per a calcular el codi gray / codi binari és, en realitat, molt senzill. Està ben explicat a la wiki. La gràcia de tot això és que abans de consultar-ho a la wiki he dedicat un temps a veure si me’n recordava com es feia aquesta codificació i descodificació. Després d’algunes proves (de les que en trobareu rastre al meu GitHub), finalment me n’he sortit. Vet aquí el resultat :

Vet aquí el codi Python

Coder

def calculate_gray(number, n):
    bits = []
    gray = []
    
    remainder = number
    for nn in range(0, n):
        [quotient, remainder] = divmod(remainder, 2 ** (n - 1 - nn))
        bits.append(quotient)
        if nn == 0:
            gray.append(bits[0])
        else:
            gray.append(bits[nn - 1] ^ bits[nn])      
            
            
    return [bits, gray]

i decoder

def calculate_binary(gray, n):  # gray is an array of bits
    bits = []

    for pos in range(0, n):
        if pos == 0:
            bits.append(gray[0])
        else:
            bits.append(bits[pos - 1] ^ gray[pos])      
            
    return bits

i una taula de prova

if __name__ == '__main__':
    print "print a Gray table for n bits"
    n = raw_input('Number of bits? ')
    n = int(n)
    print "number of bits : %d" % n   
    
    bits = []
    gray = []
    grayTable = []

    for i in range(0, 2 ** n):
        [bits, gray] = calculate_gray(i, n)
        grayTable.append(gray)
        strBits = ''.join(map(lambda (x) : chr(ord('0') + x), bits))
        strGray = ''.join(map(lambda (x) : chr(ord('0') + x), gray))
        
        print "%5d --> %s --> %s" % (i, strBits, strGray)
    
    print "-------------------------------------------"
    
    bits = []

    for i in range(0, 2 ** n):
        bits = calculate_binary(grayTable[i], n)
        strBits = ''.join(map(lambda (x) : chr(ord('0') + x), bits))
        strGray = ''.join(map(lambda (x) : chr(ord('0') + x), grayTable[i]))
        
        print "%5d --> %s --> %s" % (i, strGray, strBits)

    print "Done!"

Com a cosa molt bonica, indicaria l’us de lambdes i join per a passar l’array de bits a cadena de caràcters; i també la funció divmod, que utilitzada en cascada em permet obtenir els bits corresponents a l’enter que vull codificar.

El repositori Github és :

https://github.com/abaranguer/gray-code-py-version.git

Bé, tot plegat queda una mica curt, oi? el que he fet és escriure una segona versió del codi, però aquest cop amb llenguatge C. Així, de pas, l’he refrescat una mica.

Python és un llenguatge de molt alt nivell d’abstracció i m’ha permès implementar l’algoritme en un obrir i tancar d’ulls. La versió C, en canvi, ha estat més interessant. Vet aquí el codi :

#include 
#include 
#include 

#define BUF_SIZE 3

/* typedef */
typedef struct typeRetDivMod {
	int quotient;
	int remainder;
} RetDivMod;

typedef struct typeRetCalculateGray {
	int *bits;
	int *gray;
} RetCalculateGray;

/* prototypes */
int main(void);
RetCalculateGray calculate_gray(int number, int n);
int *calculate_binary(int *gray, int n);
RetDivMod divmod(int number, int divisor);
char *bitsToString(int *bits, int numBits);

/* functions */
int main() {
	char buf[BUF_SIZE];
	int n;
	int i;
	RetCalculateGray retValue;
	int *bitsFromGray;
	char *bits;
	char *bits2;
	char *gray;

	printf("Print a Gray table for n bits\n\n");
	printf("Number of bits? ");
	fgets(buf, BUF_SIZE, stdin);
	n = atoi(buf);
	printf("number of bits : %d\n", n);

	int range = pow(2, n);

	for (i = 0; i  %s --> %s --> %s\n", i, bits, gray, bits2);
		free(bits);
		free(gray);
		free(bits2);
		free(retValue.bits);
		free(retValue.gray);
		free(bitsFromGray);
	}

	printf("Done!\n");
	return 0;
}

RetCalculateGray calculate_gray(int number, int n) {
	int remainder;
	int nn;
	RetDivMod retDivMod;
	RetCalculateGray retValue;

	retValue.bits = (int *) malloc(n * sizeof(int));
	retValue.gray = (int *) malloc(n * sizeof(int));

	remainder = number;

	for (nn = 0; nn < n; nn++) {
		retDivMod = divmod(remainder, pow(2, n - 1 - nn));
		retValue.bits[nn] = retDivMod.quotient;
		remainder = retDivMod.remainder;
		if (nn == 0) {
			retValue.gray[nn] = retValue.bits[0];
		} else {
			retValue.gray[nn] = retValue.bits[nn - 1] ^ retValue.bits[nn];
		}
	}

	return (retValue);
}

int *calculate_binary(int *gray, int n) {
	int nn;
	int *bits;

	bits = (int *) malloc(n * sizeof(int));

	for (nn = 0; nn < n; nn++) {
		if (nn == 0) {
			bits[nn] = gray[0];
		} else {
			bits[nn] = bits[nn - 1] ^ gray[nn];
		}
	}

	return (bits);
}

RetDivMod divmod(int number, int divisor) {
	RetDivMod retDivMod;

	retDivMod.quotient = number / divisor;
	retDivMod.remainder = number % divisor;

	return retDivMod;
}

char *bitsToString(int *bits, int numBits) {
	int i;
	char *charBits;

	charBits = (char *) malloc(numBits * sizeof(char) + 1);
	for (i = 0; i < numBits; i++) {
		charBits[i] = '0' + bits[i];
	}
	charBits[numBits] = '\0';

	return charBits;
}

El repositori Github de la versió C :

https://github.com/abaranguer/gray-code-c-version.git

Per acabar, doncs, a la versió C hi han més coses a comentar. En destaco :

  • L’us de typedef i struct per a definir estructures que faig servir per moure arguments entre  main  i les funcions de coding i encoding.
  • Us de malloc i free per reservar / alliberar dinàmicament l’espai de memòria per als arrays dels bits.
  • La versió C de la funció divmod de Python.
  • L’ús de fgets per a prendre entrada per consola de forma segura aprofitant que fgets fa automàticament el control de desbordament del buffer d’entrada.

El joc Memory amb Python i Tkinter

En aquest post presento un joc de Memory, fet amb Pyhton i amb Tkinter.

El Memory és juga en un tauler de NxN cartes amb N parell. Hi han N²/2 cartes diferents, és dir, de cada carta n’hi han dues d’iguals. Les cartes estan barrejades i inicialment les N² cartes estan tapades. La mecànica del joc és anar destapant destapant parelles de cartes, si les cartes coincideixen, queden destapades, si no, es tornes a tapar i es continua amb una altre parella. Es repeteix fins que totes les parelles estan destapades.
L’objectiu del joc és haver de repetir el mínim nombre de cops. Per aconseguir-ho, doncs, cal memoritzar on són les cartes. Es tracta, doncs, d’un exercici de memorització.

El cas és que a Internet vaig trobar una imatge amb 50 súper-herois i súper-malvats dels còmics de Marvel i gairebé veient la imatge se’m va acudir fer el joc de cartes.

Vet aquí la imatge :

Abans de començar, però, vaig rumiar la mecànica del joc. El resultat va ser aquesta versió en mode text

Memory en mode text

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import random
import os
import time

instructions = '''
Memory
------

Memory és el joc clàssic de recordar les parelles.
Tenim un tauler de 4x4, 6x6 o 8x8 caselles. 
Cada casella es correspon amb un número.
Cada casella amaga el nom d'un objecte. Hi han 8, 16 o 32 objectes diferents.
Cada objecte apareix dues vegades.
En cada torn, el jugador ha de destapar dues caselles. 
Si a ambdues caselles hi ha el mateix objecte, les caselles queden destapades.
Si no, després d'un temps de 3 segons, les caselles tornen a tapar-se
El cicle es repeteix fins que el jugador ha destapat totes les caselles 
'''

class Card:
    nom = ""
    tapada = True

def initGame(n):
    cards = initCards()
    table = initTable(cards, n)
    return {"table":table, "cards":cards}
    
def initCards():
    cards = [Card() for i in range(0, 32)]
    cards[0].nom = 'Wolverine'
    cards[1].nom = 'Psylocke'    
    cards[2].nom = 'Storm'
    cards[3].nom = 'Jubilee'    
    cards[4].nom = 'X-23'
    cards[5].nom = 'Jean Grey'    
    cards[6].nom = 'Dark Fenix'
    cards[7].nom = 'Cyclops'    
    cards[8].nom = 'Gambit'
    cards[9].nom = 'Angel'    
    cards[10].nom = 'Beast'
    cards[11].nom = 'Nightcrawler'    
    cards[12].nom = 'Mystique'
    cards[13].nom = 'Professor X'    
    cards[14].nom = 'Magneto'
    cards[15].nom = 'Rogue'    
    cards[16].nom = 'Deadpool'
    cards[17].nom = 'Captain America'    
    cards[18].nom = 'Thor'
    cards[19].nom = 'Iron Man'    
    cards[20].nom = 'Spiderman'
    cards[21].nom = 'Black Widow'    
    cards[22].nom = 'Scarlet Witch'
    cards[23].nom = 'Ant Man'    
    cards[24].nom = 'Hulk'
    cards[25].nom = 'Colossus'    
    cards[26].nom = 'Venom'
    cards[27].nom = 'Doctor Strange'    
    cards[28].nom = 'Green Goblin'
    cards[29].nom = 'Ultron'    
    cards[30].nom = 'Vision'
    cards[31].nom = 'Black Panther'    
    return cards

def clrscr():
    os.system("clear")

def initTable(cards, n):
    table = [None for i in range(0, n * n)]
    for i in range(0, n * n / 2):
        while True:
            pos1 = random.randint(0, n * n - 1)
            pos2 = random.randint(0, n * n - 1)
            if (table[pos1] == None) and \
               (table[pos2] == None) and \
               (pos1 != pos2):
                table[pos1] = cards[i]
                table[pos2] = cards[i]
                break;
    return table

def showTable(table, n):
    for i in range(0, n * n):
        if not table[i].tapada:
            print "casella %d : %s" % (i + 1), table[i].nom

def getCells(table, n):
    while True:
        try:
            p1 = int(raw_input('\nguess cell 1 : '))
            p2 = int(raw_input('guess cell 2 : '))
            if not (p1 in range(1, n * n + 1)) or \
               not (p2 in range(1, n * n + 1)):
                print "Only numbers 1 to %d " % n * n
                continue
            if (not table[p1-1].tapada) or (not table[p2-1].tapada):
                print "Only closed cells"
                continue
            break
        except:
            print "Only integer values 1 to %d" % n * n
    return [p1-1, p2-1]

def analyzeCells(table, cells, n):
    endGame = True
    pos1 = cells[0]
    pos2 = cells[1]
    nom1 = table[pos1].nom 
    nom2 = table[pos2].nom 
    
    print "cell %d : %s" % (pos1 + 1, nom1)
    print "cell %d : %s" % (pos2 + 1, nom2)

    if (nom1 == nom2):
        table[pos1].tapada = False 
        table[pos2].tapada = False

    time.sleep(3)
    clrscr()
    
    for i in range(0, n * n):
        endGame = endGame and (not table[i].tapada)
          
    return not endGame

def showTable(table, n):
    for i in range(0, n * n):
        if not table[i].tapada:
            print "Posició %d : %s" % ((i + 1), table[i].nom)
        
def gameLoop(gameObjects, n):
    table = gameObjects.get("table")
    showTable(table, n)
    cells = getCells(table, n)
    continueGame = analyzeCells(table, cells, n)
    return continueGame

if __name__ == "__main__":
    clrscr()
    continueGame = True
    print(instructions)
    while True:
        n = raw_input("dimension NxN (4,6,8) ? ")
        if n in ['4','6','8']:
            break

    n = int(n)
    
    gameObjects = initGame(n)
    while continueGame:
        continueGame = gameLoop(gameObjects, n)

    print "Well done!"

El joc no té massa truc. Dins del if __name__==”__main__”: mostro les instruccions, espero a rebre un vlaor vàlid per N, i inicialitzo el joc.

L’array cells de 32 posicions manté la llista de cartes d’herois/malvats. Inicialitzo aquest array amb initCards. Noteu l’ús de la python comprehension per a inicialitzar l’array. També hagués pogut crear-lo inicialitzant amb [] i omplint-lo després amb append.

L’array table manté el tauler NxN. Aquest array es carrega amb initTable. Faig servir un algoritme molt simple de força bruta per omplir-lo de parelles : simplement trio un parell d’ubicacions a l’atzar dins del rang del tauler i comprovo si no estan repetides i si estan disponibles.

Un cop disposo de cells i table, ja només cal encetar la iteració del joc, és dir : demanar un parell de posicions, verificar que son vàlides, comprovar quina parella amaga i decidir si s’ha trobat una parella i s’ha d’acabar el joc, o si no és una parella vàlida i cal mostrar durant tres segons, abans d’esborrar la pantalla i continuar preguntant. Aquesta lògica es codifica a analyzeCells dins gameLoop.

És molt simple. L’aplicació fa servir entrada i sortida simpl per pantalla (es podria haver fet amb la llibreria ncurses). L’esborrat de pantalla es va invocant el programa clear amb os.system(“clear”), i l’espera de tres segons es fa amb time.sleep(3).

Amb aquesta versió en mode text, ja tinc les bases per a la versió amb GUI.

Memory amb GUI Tkinter

A la versió Tkinter he afegit algunes millores.

– Un tauler addicional de 10×10 i tinc, per tant, quatre possibles mides : 4×4, 6×6, 8×8 i 10×10
– Gestió per menú que permet controlar el final del joc, o començar-ne un de nou.
– una indicació del nombre de clicks utilitzats

Tinc, doncs, quatre frames :

– la finestra de l’aplicació, amb el menú que és on s’obren els frames de l’aplicació :

– el frame de nou joc, on es pot triar la mida del tauler

– el tauler NxN amb el joc pròpiament dit.

– la pantalla de final de joc on es diu quants clicks han calgut per destapar totes les cartes

Cal tenir present, a l’hora de treballar amb Tkinter que només pot haver un mainloop, l’aplicació es desenvolupa dins d’aquest mainloop. El mainloop és el fil principal de l’aplicació. Això és important perquè prefigura com ha de ser l’aplicació.

Les imatges

En un experiment inicial he fet servir Image i TkImage de PIL (Python Image Library) per a carregar directament la imatge jpg i processar-la per a retallar (crop) els de cada carta. Al final he optat per una altre alternativa : generar la imatge ppm de cada heroi/malvat per a fer-la servir amb un PhotoImage de Tkinter. Aquest objecte PhotoImage és estàndar del Tkinter, a diferència de les imatges amb PIL, llibreria que cal importar explícitament i que aporta funcionalitat de processament d’imatges. Tkinter.PhotoImage no permet gran cosa més que carregar la imatge i mostrar-la, a més només treballa amb imatges ppm, pgm i gif.

Per a crear les imatges ppm he fet servir aquest programa _

#!/usr/bin/python
# -*- coding: utf-8 -*-

import Tkinter as tk
from PIL import Image, ImageTk


# 450 293
xdim = 45
ydim = int(293.0 / 5.0)
cropDimensions= (xdim, ydim)

images = []

imageFace = Image.open("marvel-heros-villains-reduced.3.jpg")
imageHide = Image.open("diamond-shaped-texture-background.jpg")
       
for i in range(0, 50):
    y = i / 10
    x = i % 10
    x1 = x * xdim 
    x2 = x1 + xdim
    y1 = int(y * (293.0 / 5.0))
    y2 = y1 + ydim
    
    images.append(imageFace.crop((x1, y1, x2, y2)))

images.append(imageHide.crop((0, 0, xdim, ydim)))

print "working!"

for i in range(0, len(images) - 1):
    print "file %d " % i
    images[i].save("hero_%d.ppm" % i)

print "file 50"
images[50].save("hide_card.ppm")

print "done!"

El resultat de l’script anterior són les imatges amb les cares dels herois/malvats.

He utilitzat una aproximació basada en objectes. He assignat una classe a cada un dels objectes principals, i he posat cada classe en un fitxer, a més d’un fitxer memory_main.py principal des d’on es llença l’execució de l’aplicació.

Els objectes i els scripts corresponents són :

memory_main.py           --> incia el joc

memory_model.py          -->  class MemoryModel
memory_card.py           -->  class ImageButton
memory_controller.py     -->  class MemoryController

memory_app_window.py     -->  class MemoryAppWindow
memory_frame_new_game.py -->  class FrameNewGame
memory_frame_memory.py   -->  class FrameMemory
memory_frame_congrat.py  -->  class FrameCongrat

El joc s’inicia amb memory_main que executa el constructor de MemoryAppWindow

El constructor de MemoryAppWindow carrega la finestra principal i inicialitza tauler buit, llista de cartes, controlador del joc que es compartirà amb tots els frames i inicialitza els frames. A continuació mostra el frame newGame invocant-ne el constructor, al que li passa el controlador i la llista de frames

Des del frame de nou joc es pot triar la mida del tauler. EN fer click a una mida, passa o obrir-se el tauler amb la mida sol·licitada, per a fer-ho cal carregar el tauler amb cartes, que en aquest cas, són objectes de la classe ImageButton, que no és més que un embolcall del Button de Tkinter amb una PhotoImage. El cor de FrameMemory és un array de ImageButtons que es carrega al controlador. Es necessari que estigui allà perquè és al controlador on està la lògica d’anàlisi de la jugada i on es decideix si la parella queda descoberta, o es tapa, o si finalitza el joc.

Quan s’ha destapat totes les cartes, es mostra el frame de felicitacions i presentació el nombre de clicks. per iniciar un altre joc cal triar l’opció de nou joc al menú, o bé l’opció d’acabar si no es vol seguir.

Només comentar que, a diferència d’altres programes amb Tkinter que he fet, en aquest les classes Frame no deriven del Frame de Tkinter, si no que tenen el frame com un atribut. Seria una altre opció de codificació.

Com que he partit de la versió en modetext que ha seguit un paradigma de programació estructurada, el resultat és que aquest model d’objectes ja vingut donat per una redistribució del codi més que no pas per un anàlisi d’objectes pròpiament dit, a més que Tkinter imposa algunes característiques,com la necessitat d’un mainloop.

En tot cas, el joc queda força bonic, i la creació de la GUI amb Tkinter ha estat força directa.

Per si voleu fer un cop d’ull al codi, el podeu trobar al respositori GitHub : https://github.com/abaranguer/memory

Per acabar, un tauler de 10×10 amb una partida a punt d’acabar :

Caçar el Wumpus!

huntthewumpus

“Hunt the Wumpus” és un joc d’ordinador de 1972, inicialment escrit en mode text i desenvolupat en llenguatge BASIC. La seva simplicitat, a més de tenir les fonts disponibles, va motivar l’aparició de diverses i successives versions.

En aquest post escric la meva pròpia versió en català i en Python

Vet aquí les instruccions de “Caçar el Wumpus” :

Caçar el Wumpus
—————
El Wumpus és un monstre enorme i pesat amb la pell plena de ventoses
que s’alimenta de tot allò que cau a les seves urpes.
Tu ets un caçador que vol aconseguir el cap del Wumpus com a trofeu
i ets a un castell on se sap que n’hi ha un.
El castell té vint habitacions, cada habitació es connecta amb
altres tres habitacions.
Si entres a l’habitació on és el Wumpus, et menjarà.
Al castell hi ha un parell d’habitacions que tenen un fals terra.
Només entrar s’ensorra el terra i caus a un pou amb un potent àcid al fons.
Tothom que entra a una habitació amb pou, mor.
Menys el Wumpus. El Wumpus no hi cau perquè amb les seves ventoses
s’enganxa a les parets i no toca l’àcid.
Al castell també hi ha un parell de rats penats gegants.
Si entres a una habitació amb un rat penat, t’agafarà, se t’emportarà volant
i et deixarà caure a una habitació qualsevol del castell.
Els rats penats no poden endur-se al Wumpus perquè pesa massa per ells
i el Wumpus no es pot menjar als rats penats perquè són massa ràpids
per atrapar-los.
Saps que a alguna de les habitacions adjacents hi ha el Wumpus
perquè mai s’ha banyat i fa molta pudor, i el pots ensumar.
Saps que a les habitacions adjacents hi poden haver rats-penats
perquè sents el soroll del batec de les seves ales,
I, finalment, saps que a les habitacions adjacents poden haver pous
perquè sents el soroll de l’acid bullint.
Tens cinc fletxes. Has de moure’t pel castell
i quan dedueixis a quina habitació està el Wumpus, pots tirar-li
una fletxa des d’una de les habitacions adjacents.
Si l’habitació a la que has tirat la fletxa és la del Wumpus,
el mataràs i hauràs guanyat.
Però si el Wumpus no és a l’habitació, el soroll de la fletxa
potser el posarà en alerta i farà que es mogui a alguna habitació
contigua a la que ocupa.
Si esgotes totes les fletxes, aleshores ja no tens defensa
possible contra el Wumpus, que et trobarà i et menjarà.

Com he implementat les anteriors instruccions?

“El castell té vint habitacions, cada habitació es connecta amb altres tres habitacions.”

De fet, el castell del wumpus es pot modelar com un dodecaedre, on cada vèrtex representa una habitació i cada aresta ens porta a l’habitació contigua.

Vet aquí una bonica imatge d’un dodecaedre regular extreta de la Viquipèdia:

Si aplano aquesta figura obtinc una versió del mapa que em serà més útil.

Per a dibuixar el mapa del castell he fet servir el següent codi Python :

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import Tkinter as tk
import math

class Room:
    xc = 0
    yc = 0
    x0 = 0
    y0 = 0
    x1 = 0
    y1 = 0
    doors = []

if __name__ == "__main__":
    # initialize map
    rooms = [Room() for i in range(0, 20)]

    rooms[ 0].doors = [1, 4, 5]
    rooms[ 1].doors = [0, 2, 7]
    rooms[ 2].doors = [1, 3, 9]
    rooms[ 3].doors = [2, 4, 11]
    rooms[ 4].doors = [0, 3, 13]
    rooms[ 5].doors = [0, 6, 14]
    rooms[ 6].doors = [5, 7, 16]
    rooms[ 7].doors = [1, 6, 8]
    rooms[ 8].doors = [7, 9, 17]
    rooms[ 9].doors = [2, 8, 10]
    rooms[10].doors = [9, 11, 18]
    rooms[11].doors = [3, 10, 12]
    rooms[12].doors = [11, 13, 19]
    rooms[13].doors = [4, 12, 14]
    rooms[14].doors = [5, 13, 15]
    rooms[15].doors = [14, 16, 19]
    rooms[16].doors = [6, 15, 17]
    rooms[17].doors = [8, 16, 18]
    rooms[18].doors = [10, 17, 19]
    rooms[19].doors = [12, 15, 18]    
    
    root = tk.Tk()
    canvas = tk.Canvas(root, width=600, height=600, borderwidth=0, highlightthickness=0, bg="grey")
    j = 0
    R = 20
    for i in range(0, 5):
        x = 300 + int(80.0 * math.cos( (2.0 * math.pi / 5.0) * i)) 
        y = 300 + int(80.0 * math.sin( (2.0 * math.pi / 5.0) * i))

        rooms[j].xc = x
        rooms[j].yc = y
        rooms[j].x0 = x - R
        rooms[j].y0 = y - R
        rooms[j].x1 = x + R
        rooms[j].y1 = y + R
        j = j + 1

    for i in range(0, 10):
        x = 300 + int(180.0 * math.cos( (math.pi / 5.0) * i)) 
        y = 300 + int(180.0 * math.sin( (math.pi / 5.0) * i))

        rooms[j].xc = x
        rooms[j].yc = y
        rooms[j].x0 = x - R
        rooms[j].y0 = y - R
        rooms[j].x1 = x + R
        rooms[j].y1 = y + R
        j = j + 1

    for i in range(0, 5):
        x = 300 + int(280.0 * math.cos( (2.0 * math.pi / 5.0) * i - (math.pi / 5.0)))
        y = 300 + int(280.0 * math.sin( (2.0 * math.pi / 5.0) * i - (math.pi / 5.0)))

        rooms[j].xc = x
        rooms[j].yc = y
        rooms[j].x0 = x - R
        rooms[j].y0 = y - R
        rooms[j].x1 = x + R
        rooms[j].y1 = y + R
        j = j + 1

    for i in range(0, 20):
        canvas.create_line(rooms[i].xc, \
                           rooms[i].yc, \
                           rooms[rooms[i].doors[0]].xc, \
                           rooms[rooms[i].doors[0]].yc)

        canvas.create_line(rooms[i].xc, \
                           rooms[i].yc, \
                           rooms[rooms[i].doors[1]].xc, \
                           rooms[rooms[i].doors[1]].yc)
        
        canvas.create_line(rooms[i].xc, \
                           rooms[i].yc, \
                           rooms[rooms[i].doors[2]].xc, \
                           rooms[rooms[i].doors[2]].yc)

    for i in range(0, 20):
        canvas.create_oval(rooms[i].x0, rooms[i].y0, rooms[i].x1, rooms[i].y1, fill='white')
        canvas.create_text(rooms[i].xc, rooms[i].yc, text='%d' % i, fill='black')
        
    canvas.grid()
    root.wm_title("El Castell del Wumpus!")
    root.mainloop()

Destacar en el codi anterior l’us del canvas de Tkinter per a fer el dibuix, i l’us de la Python comprehension per a inicialitzar l’array rooms (just abans d’assignar les door de cada room).

Al codi anterior ja apareix l’estructura del mapa : el array rooms, de 20 posicions, on cada posició conté una instancia de la classe Room que, entre d’altres propietats, té l’array doors de tres posicions, que manté els números de les habitacions que es connecten a l’habitació.

“Al castell hi ha un parell d’habitacions que tenen un fals terra…
Al castell també hi ha un parell de rats penats gegants…
Tens cinc fletxes…·

Per tant, tenim els següents personatges o objectes del joc : un caçador, un wumpus, dos pous d’àcid, dos rats penats gegants i cinc fletxes. Les cinc fletxes les porta el caçador i no cal, doncs, ubicar-les específicament. El que cal fer en iniciar el joc és col·locar els objectes wumpus, caçador, pous i rats penats al castell, de forma que el caçador no coincideix amb el wumpus, els rats penats i els pous; els rats penats no coincideixen entre ells ; i els pous tampoc. És dir : el wumpus podria compartir habitació amb un rat-penat i un pou. Però això és possible perquè “El wumpus no hi cau [als pous] perquè amb les seves ventoses s’enganxa a les parets i en pot sortir sense perill.” i “Els rats penats no poden endur-se al wumpus perquè pesa massa per ells i el wumpus no es pot menjar als rats penats perquè són massa ràpids per ell.”.

Això es fa amb aquest codi :

Una classe molt simple GameObject, que manté la ubicació de l’objecte

class GameObject:
    roomNumber = -1

    def __init__(self, roomNumber):
        self.roomNumber = roomNumber
    # initialize characters and objects
    wumpusRoom = -1
    bat1Room = -1
    bat2Room = -1
    pit1Room = -1
    pit2Room = -1
    hunterRoom = -1
    arrows = 5

    while (hunterRoom == wumpusRoom) or \
          (hunterRoom == bat1Room) or   \
          (hunterRoom == bat2Room) or   \
          (hunterRoom == pit1Room) or   \
          (hunterRoom == pit2Room) or   \
          (pit1Room == pit2Room) or     \
          (bat1Room == bat2Room):
        
        hunterRoom = rnd.randint(0, 19)
        wumpusRoom = rnd.randint(0, 19)
        bat1Room = rnd.randint(0, 19)
        bat2Room = rnd.randint(0, 19)
        pit2Room = rnd.randint(0, 19)
        pit2Room = rnd.randint(0, 19)

    hunter = GameObject(hunterRoom)
    wumpus = GameObject(wumpusRoom)
    bat1 = GameObject(bat1Room)
    bat2 = GameObject(bat2Room)
    pit1 = GameObject(pit1Room)
    pit2 = GameObject(pit2Room)

    return {"rooms":rooms, "hunter":hunter, "wumpus":wumpus,
            "bat1":bat1, "bat2":bat2, "pit1":pit1, "pit2":pit2, "arrows":arrows}

L’estratègia utilitzada és repetir fins que es torna una combinació a l’atzar que ubica tots els objectes en habitacions diferents.

Destacar, també, l’us d’un diccionari per retornar els objectes.

“Si entres a l’habitació on és el Wumpus, et menjarà…
Tothom que hi cau [a una habitació amb pou], mor…
Si entres a una habitació amb un rat penat, t’agafarà, se t’emportarà volant
i et deixarà caure a una habitació qualsevol del castell…

A la funció enterRoom tenim la codificació de les regles anteriors

def enterRoom(gameObjects):
    continueGame = True
    rooms = gameObjects.get("rooms")
    hunterRoom = gameObjects.get("hunter").roomNumber
    wumpusRoom = gameObjects.get("wumpus").roomNumber
    bat1Room = gameObjects.get("bat1").roomNumber
    bat2Room = gameObjects.get("bat2").roomNumber
    pit1Room = gameObjects.get("pit1").roomNumber
    pit2Room = gameObjects.get("pit2").roomNumber
    
    print "\nEts a l'habitació número %d" % hunterRoom

    if wumpusRoom == hunterRoom:
        print "El wumpus és a l'habitació!"
        print "T'ha atrapat i comença a devorar-te!" 
        print "No és que sigui dolent... Et menja perquè és la seva natura de Wumpus..."    
        continueGame = False

    if continueGame and (hunterRoom in (pit1Room, pit2Room)):
        print "Hi ha un pou amb acid a l'habitació!"
        print "Has caigut dins i comences a dissoldre't de forma lenta i dolorosament agònica!"
        continueGame = False

    if continueGame and (hunterRoom in (bat1Room, bat2Room)):
        print "I un rat penat gegant a l'habitació! T'ha agafat i se t'emporta volant!"
        newHunterRoom = rnd.randint(0, 19)
        newBat1Room = rnd.randint(0, 19)
        newBat2Room = rnd.randint(0, 19)
        gameObjects.get("hunter").roomNumber = newHunterRoom
        gameObjects.get("bat1").roomNumber = newBat1Room
        gameObjects.get("bat2").roomNumber = newBat2Room
        print "El rat penat t'ha deixat caure a l'habitació número %d" % newHunterRoom
        continueGame = enterRoom(gameObjects)

    if not continueGame:
        print "Has mort de forma horrible!" 
        print "..." 
        print "Però altres vindran a intentar triomfar allà on tu has fracassat tan lamentablement "

    return continueGame


“Has de moure’t pel castell…”

Una de les possibles accions és, doncs, moure’s a una habitació adjacent.

El següent codi és la part de la funció actionHunter que recull l’acció “moure’s” del caçador :

def actionsHunter(gameObjects):
    continueGame = True
    wumpusMove = False
    hunterRoom = gameObjects.get("hunter").roomNumber
    wumpusRoom = gameObjects.get("wumpus").roomNumber
    arrows = gameObjects.get("arrows")
    rooms = gameObjects.get("rooms")
    [door0, door1, door2] = rooms[hunterRoom].doors

    while True:
        action = raw_input("Moure's 'm' o Tirar una fletxa 's' ? ")
        if action in ('m','s','M','S'):
            break

    while True:
        try:
            door = int(raw_input("A quina habitació %d, %d or %d ? " % (door0, door1, door2)))
            if door in (door0, door1, door2):
              break
        except:
            None

    if (action=='m' or action=='M'):
        gameObjects.get("hunter").roomNumber = door


“quan dedueixis a quina habitació està el Wumpus, pots tirar-li una fletxa des d’una de les habitacions adjacents.

Si l’habitació a la que has tirat la fletxa és la del wumpus, el mataràs i hauràs guanyat.

Però si el Wumpus no és a l’habitació, el soroll de la fletxa potser el posarà en alerta i farà que es mogui a alguna habitació contigua a la que ocupa…”

Això és el que es fa amb el següent fragment de actionsHunter

    if ((action=='s' or action=='S') and \
        ((wumpusRoom == door0) or \
         (wumpusRoom == door1) or \
         (wumpusRoom == door2))):
            print "La fletxa ha matat al Wumpus!"
            print "La protectora d'animals et denunciarà si et descobreixen!"
            print "Ets l'assassí del wumpus!"
            print "Un altre sàdic que mata pobres bestioletes indefenses!"
            print "Suposo que estaràs content, criminal!"
            print "En fi. Suposo que t'he de felicitar perquè has guanyat."
            continueGame = False

    if ((action=='s' or action=='S') and \
        ((wumpusRoom <> door0) and \
         (wumpusRoom <> door1) and \
         (wumpusRoom <> door2))):
            print "has fallat! No hi havia cap wumpus a l'habitació!"

            # move wumpus
            doorsWumpus = doors[wumpusRoom].doors
            randomDoor = rnd.random()
            if randomDoor < 0.75 :                 wumpusMove= True             if randomDoor >= 0 and randomDoor < 0.25:                 gameObjects.get("wumpus").roomNumber = doorsWumpus[0]             if randomDoor >= 0.25 and randomDoor < 0.50:                 gameObjects.get("wumpus").roomNumber = doorsWumpus[1]             if randomDoor >= 0.50 and randomDoor < 0.75:
                gameObjects.get("wumpus").roomNumber = doorsWumpus[2]


Si esgotes totes les fletxes, aleshores ja no tens defensa possible contra el wumpus, que et trobarà i et menjarà.

És la part final d’actionsHunter

            arrows = arrows - 1

            if arrow == 1:
                aux = "fletxa"
            else:
                aux = "fletxes"
            print "Ara tens %d %s" % (arrows, aux)

            if arrow == 0:
                print "No tens fletxes i, per tant, ja no pots matar el Wumpus."
                print "No trigarà a descobrir-te i, aleshores, et menjarà."
                print "Serà molt dolorós i horrible..."
                print "Ja se sent com ve!"
                print "Ara entra per la porta i es llença sobre teu!"
                print "La resistència és inútil.."
                print "Encara ets conscient quan se t'empassa!"
                print "Els àcids de la seva digestio fan la resta. Has mort."
                print "Però recorda que no és que el wumpus sigui dolent..." 
                print "Et menja perquè és la seva natura de Wumpus..."
            continueGame = False

            if continueGame and wumpusMove:
                print "La fletxa ha alertat el Wumpus i es mou! espero que no vingui cap aquí!"

“Saps que a alguna de les habitacions adjacents hi ha el Wumpus perquè mai s’ha banyat i fa molta pudor, i el pots ensumar.

Saps que a les habitacions adjacents hi poden haver rats-penats
perquè sents el soroll del batec de les seves ales.

I, finalment, saps que a les habitacions adjacents poden haver pous
perquè sents el soroll de l’acid bullint.”

Si el caçador pot entrar a una habitació, pot fer-se una idea de que es trobarà més endavant. És el que s’aconsegueix amb la funció examineRoom.

def examineRoom(gameObjects):
    rooms = gameObjects.get("rooms")
    hunterRoom = gameObjects.get("hunter").roomNumber
    arrows = gameObjects.get("arrows")
    wumpusRoom = gameObjects.get("wumpus").roomNumber
    bat1Room = gameObjects.get("bat1").roomNumber
    bat2Room = gameObjects.get("bat2").roomNumber
    pit1Room = gameObjects.get("pit1").roomNumber
    pit2Room = gameObjects.get("pit2").roomNumber
    [door0, door1, door2] = rooms[hunterRoom].doors
    
    print "L'habitació %d es connecta amb les habitacions %d, %d i %d" % (hunterRoom, door0, door1, door2)

    if arrows > 1:
        aux = "fletxes"
    else:
        aux = "fletxa"
    print "Encara tens %d %s" % (arrows, aux) 
    
    if wumpusRoom in rooms[hunterRoom].doors:
        print "Fa una insuportable fortor de wumpus!"
        print "Hi ha un wumpus pudent a una de les habitacions que es connecten des d'aquí!"

    if (bat1Room in rooms[hunterRoom].doors) or (bat2Room in rooms[hunterRoom].doors):
        print "Se sent soroll d'ales!"
        print "Hi ha almenys un rat penat gegant a les habitacions que es connecten des d'aquí"

    if (pit1Room in rooms[hunterRoom].doors) or (pit2Room in rooms[hunterRoom].doors):
        print "Se sent el soroll d'àcid bullint!"
        print "Hi ha almenys un pou ple d'àcid a les habitacions que es connecten des d'aquí"

En aquest moment, ja tinc tots els elements. Si ho junto tot el que obtinc és el següent codi :

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import random as rnd

class Room:
    doors = []

class GameObject:
    roomNumber = -1

    def __init__(self, roomNumber):
        self.roomNumber = roomNumber

def initializeObjects():
    # map
    rooms = [Room() for i in range(0, 20)]

    # initialize map
    rooms[ 0].doors = [1, 4, 5]
    rooms[ 1].doors = [0, 2, 7]
    rooms[ 2].doors = [1, 3, 9]
    rooms[ 3].doors = [2, 4, 11]
    rooms[ 4].doors = [0, 3, 13]
    rooms[ 5].doors = [0, 6, 14]
    rooms[ 6].doors = [5, 7, 16]
    rooms[ 7].doors = [1, 6, 8]
    rooms[ 8].doors = [7, 9, 17]
    rooms[ 9].doors = [2, 8, 10]
    rooms[10].doors = [9, 11, 18]
    rooms[11].doors = [3, 10, 12]
    rooms[12].doors = [11, 13, 19]
    rooms[13].doors = [4, 12, 14]
    rooms[14].doors = [5, 13, 15]
    rooms[15].doors = [14, 16, 19]
    rooms[16].doors = [6, 15, 17]
    rooms[17].doors = [8, 16, 18]
    rooms[18].doors = [10, 17, 19]
    rooms[19].doors = [12, 15, 18]

    # initialize characters and objects
    wumpusRoom = -1
    bat1Room = -1
    bat2Room = -1
    pit1Room = -1
    pit2Room = -1
    hunterRoom = -1
    arrows = 5

    while (hunterRoom == wumpusRoom) or \
          (hunterRoom == bat1Room) or   \
          (hunterRoom == bat2Room) or   \
          (hunterRoom == pit1Room) or   \
          (hunterRoom == pit2Room) or   \
          (pit1Room == pit2Room) or     \
          (bat1Room == bat2Room):
        
        hunterRoom = rnd.randint(0, 19)
        wumpusRoom = rnd.randint(0, 19)
        bat1Room = rnd.randint(0, 19)
        bat2Room = rnd.randint(0, 19)
        pit2Room = rnd.randint(0, 19)
        pit2Room = rnd.randint(0, 19)

    hunter = GameObject(hunterRoom)
    wumpus = GameObject(wumpusRoom)
    bat1 = GameObject(bat1Room)
    bat2 = GameObject(bat2Room)
    pit1 = GameObject(pit1Room)
    pit2 = GameObject(pit2Room)

    return {"rooms":rooms, "hunter":hunter, "wumpus":wumpus,
            "bat1":bat1, "bat2":bat2, "pit1":pit1, "pit2":pit2, "arrows":arrows}

def enterRoom(gameObjects):
    continueGame = True
    rooms = gameObjects.get("rooms")
    hunterRoom = gameObjects.get("hunter").roomNumber
    wumpusRoom = gameObjects.get("wumpus").roomNumber
    bat1Room = gameObjects.get("bat1").roomNumber
    bat2Room = gameObjects.get("bat2").roomNumber
    pit1Room = gameObjects.get("pit1").roomNumber
    pit2Room = gameObjects.get("pit2").roomNumber
    
    print "\nEts a l'habitació número %d" % hunterRoom

    if wumpusRoom == hunterRoom:
        print "El wumpus és a l'habitació!"
        print "T'ha atrapat i comença a devorar-te!" 
        print "No és que sigui dolent... Et menja perquè és la seva natura de Wumpus..."    
        continueGame = False

    if continueGame and (hunterRoom in (pit1Room, pit2Room)):
        print "Hi ha un pou amb acid a l'habitació!"
        print "Has caigut dins i comences a dissoldre't de forma lenta i dolorosament agònica!"
        continueGame = False

    if continueGame and (hunterRoom in (bat1Room, bat2Room)):
        print "I un rat penat gegant a l'habitació! T'ha agafat i se t'emporta volant!"
        newHunterRoom = rnd.randint(0, 19)
        newBat1Room = rnd.randint(0, 19)
        newBat2Room = rnd.randint(0, 19)
        gameObjects.get("hunter").roomNumber = newHunterRoom
        gameObjects.get("bat1").roomNumber = newBat1Room
        gameObjects.get("bat2").roomNumber = newBat2Room
        print "El rat penat t'ha deixat caure a l'habitació número %d" % newHunterRoom
        continueGame = enterRoom(gameObjects)

    if not continueGame:
        print "Has mort de forma horrible!" 
        print "..." 
        print "Però altres vindran a intentar triomfar allà on tu has fracassat tan lamentablement "

    return continueGame

def examineRoom(gameObjects):
    rooms = gameObjects.get("rooms")
    hunterRoom = gameObjects.get("hunter").roomNumber
    arrows = gameObjects.get("arrows")
    wumpusRoom = gameObjects.get("wumpus").roomNumber
    bat1Room = gameObjects.get("bat1").roomNumber
    bat2Room = gameObjects.get("bat2").roomNumber
    pit1Room = gameObjects.get("pit1").roomNumber
    pit2Room = gameObjects.get("pit2").roomNumber
    [door0, door1, door2] = rooms[hunterRoom].doors
    
    print "L'habitació %d es connecta amb les habitacions %d, %d i %d" % (hunterRoom, door0, door1, door2)

    if arrows > 1:
        aux = "fletxes"
    else:
        aux = "fletxa"
    print "Encara tens %d %s" % (arrows, aux) 
    
    if wumpusRoom in rooms[hunterRoom].doors:
        print "Fa una insuportable fortor de wumpus!"
        print "Hi ha un wumpus pudent a una de les habitacions que es connecten des d'aquí!"

    if (bat1Room in rooms[hunterRoom].doors) or (bat2Room in rooms[hunterRoom].doors):
        print "Se sent soroll d'ales!"
        print "Hi ha almenys un rat penat gegant a les habitacions que es connecten des d'aquí"

    if (pit1Room in rooms[hunterRoom].doors) or (pit2Room in rooms[hunterRoom].doors):
        print "Se sent el soroll d'àcid bullint!"
        print "Hi ha almenys un pou ple d'àcid a les habitacions que es connecten des d'aquí"
    
def actionsHunter(gameObjects):
    continueGame = True
    wumpusMove = False
    hunterRoom = gameObjects.get("hunter").roomNumber
    wumpusRoom = gameObjects.get("wumpus").roomNumber
    arrows = gameObjects.get("arrows")
    rooms = gameObjects.get("rooms")
    [door0, door1, door2] = rooms[hunterRoom].doors

    while True:
        action = raw_input("Moure's 'm' o Tirar una fletxa 's' ? ")
        if action in ('m','s','M','S'):
            break

    while True:
        try:
            door = int(raw_input("A quina habitació %d, %d or %d ? " % (door0, door1, door2)))
            if door in (door0, door1, door2):
              break
        except:
            None

    if (action=='m' or action=='M'):
        gameObjects.get("hunter").roomNumber = door

    if ((action=='s' or action=='S') and \
        ((wumpusRoom == door0) or \
         (wumpusRoom == door1) or \
         (wumpusRoom == door2))):
            print "La fletxa ha matat al Wumpus!"
            print "La protectora d'animals et denunciarà si et descobreixen!"
            print "Ets l'assassí del wumpus!"
            print "Un altre sàdic que mata pobres bestioletes indefenses!"
            print "Suposo que estaràs content, criminal!"
            print "En fi. Suposo que t'he de felicitar perquè has guanyat."
            continueGame = False

    if ((action=='s' or action=='S') and \
        ((wumpusRoom <> door0) and \
         (wumpusRoom <> door1) and \
         (wumpusRoom <> door2))):
            print "has fallat! No hi havia cap wumpus a l'habitació!"

            # move wumpus
            doorsWumpus = doors[wumpusRoom].doors
            randomDoor = rnd.random()
            if randomDoor < 0.75 :                 wumpusMove= True             if randomDoor >= 0 and randomDoor < 0.25:                 gameObjects.get("wumpus").roomNumber = doorsWumpus[0]             if randomDoor >= 0.25 and randomDoor < 0.50:                 gameObjects.get("wumpus").roomNumber = doorsWumpus[1]             if randomDoor >= 0.50 and randomDoor < 0.75:
                gameObjects.get("wumpus").roomNumber = doorsWumpus[2]

            arrows = arrows - 1

            if arrow == 1:
                aux = "fletxa"
            else:
                aux = "fletxes"
            print "Ara tens %d %s" % (arrows, aux)

            if arrow == 0:
                print "No tens fletxes i, per tant, ja no pots matar el Wumpus."
                print "No trigarà a descobrir-te i, aleshores, et menjarà."
                print "Serà molt dolorós i horrible..."
                print "Ja se sent com ve!"
                print "Ara entra per la porta i es llença sobre teu!"
                print "La resistència és inútil.."
                print "Encara ets conscient quan se t'empassa!"
                print "Els àcids de la seva digestio fan la resta. Has mort."
                print "Però recorda que no és que el wumpus sigui dolent..." 
                print "Et menja perquè és la seva natura de Wumpus..."
            continueGame = False

            if continueGame and wumpusMove:
                print "La fletxa ha alertat el Wumpus i es mou! espero que no vingui cap aquí!"

    return continueGame

def gameLoop(gameObjects):
    continueGame = True

    while continueGame:
        continueGame = enterRoom(gameObjects)
        if continueGame:
            examineRoom(gameObjects)
            continueGame = actionsHunter(gameObjects)

instructions = '''
Caçar el Wumpus
---------------
El Wumpus és un monstre enorme i pesat amb la pell plena de ventoses 
que s'alimenta de tot allò que cau a les seves urpes. 
Tu ets un caçador que vol aconseguir el cap del Wumpus com a trofeu 
i ets a un castell on se sap que n'hi ha un.  
El castell té vint habitacions, cada habitació es connecta amb 
altres tres habitacions.
Si entres a l'habitació on és el Wumpus, et menjarà.
Al castell hi ha un parell d'habitacions que tenen un fals terra. 
Només entrar s'ensorra el terra i caus a un pou amb un potent àcid al fons. 
Tothom que entra a una habitació amb pou, mor. 
Menys el Wumpus. El Wumpus no hi cau perquè amb les seves ventoses 
s'enganxa a les parets i no toca l'àcid.
Al castell també hi ha un parell de rats penats gegants. 
Si entres a una habitació amb un rat penat, t'agafarà, se t'emportarà volant 
i et deixarà caure a una habitació qualsevol del castell. 
Els rats penats no poden endur-se al Wumpus perquè pesa massa per ells 
i el Wumpus no es pot menjar als rats penats perquè són massa ràpids 
per atrapar-los.
Saps que a alguna de les habitacions adjacents hi ha el Wumpus
perquè mai s'ha banyat i fa molta pudor, i el pots ensumar.
Saps que a les habitacions adjacents hi poden haver rats-penats
perquè sents el soroll del batec de les seves ales,
I, finalment, saps que a les habitacions adjacents poden haver pous 
perquè sents el soroll de l'acid bullint.
Tens cinc fletxes. Has de moure't pel castell 
i quan dedueixis a quina habitació està el Wumpus, pots tirar-li 
una fletxa des d'una de les habitacions adjacents. 
Si l'habitació a la que has tirat la fletxa és la del Wumpus, 
el mataràs i hauràs guanyat. 
Però si el Wumpus no és a l'habitació, el soroll de la fletxa 
potser el posarà en alerta i farà que es mogui a alguna habitació 
contigua a la que ocupa.
Si esgotes totes les fletxes, aleshores ja no tens defensa 
possible contra el Wumpus, que et trobarà i et menjarà.
'''

if __name__ == "__main__":

    print instructions

    # gameObjects = [rooms, hunter, wumpus, bat1, bat2, pit1, pit2]
    gameObjects = initializeObjects()
    
    gameLoop(gameObjects)

Per si algú té ganes de millorar-lo -afegint una interfície gràfica, per exemple- el codi es pot descarregar del repositori GitHub.

Divisió de polinomis amb Emacs Lisp

Per passar l’estona es poden fer moltes coses: llegir un llibre, escoltar música, veure la tele o escriure programes, entre moltes d’altres.

Per circumstàncies diverses, aquests darrers temps he pogut dedicar moltes estones a escriure programes i, un cop escrits, he pensat que els puc aprofitar per fer-ne un post al bloc de tecnologia.

En aquesta ocasió, es tracta d’un programa que fa la divisió entre dos polinomis. Al programa se li entrega una llista amb els coeficients numèrics del numerador (amb zero per als coeficients nuls) i una llista amb els del denominador. Cal que el grau del polinomi del numerador sigui major o igual que el del denominador.

Amb aquestes condicions, només cal aplicar el conegut algorisme de divisió de polinomis. Un exemple il·lustra el procediment:

Donats e numerador i denominador:

 N: x^3 + -12*x^2 + -42
 D: x + -3

La resposta és:

 Q: x^2 + -9*x + -27
 R: -123

Vet aquí el procediment. Cada parell és (coeficient, grau):

    (1,3)  (-12,2)  (0,1)  (-42,0) | (1,1) (-3,0) 
   -(1,3)   -(-3,2)                  (1,2)(-9,1) (-27,0)
    -------------
       0    (-9,2)   (0,1)  
           -(-9,2) -(27,1)
    ----------------------
                0  (-27,1) (-42,0)
                  -(-27,1) -(81,0) 
    ------------------------------
                        0  (-123,0)

Un exemple numèric diferent (aquí només indico el coeficients):

 6   5   4  3   2   1     | 1  2 3
-6 -12 -18                  6 -7 0 24
----------
    -7 -14  3   2   1
     7  14 21
---------------------
           24   2   1
            0   0   0
---------------------
           24   2   1
          -24 -48 -72
---------------------
              -46 -71

Es tracta d’implementar l’algorisme anterior. A manca d’alguna altre cosa, aquest cop he fet servir Emacs Lisp, el llenguatge d’extensió que porta incorporat l’Emacs. Al tractar-se d’un algorisme essencialment recursiu resulta senzill d’implementar amb un dialecte de Lisp com l’Emacs Lisp.

Bé, doncs és això:

(progn
  (setq coefs (list))
  (setq rest (list))

  (defun show-poly (poly)
    (if (>= (length poly) 1)
	(progn
	  (setq exponent (1- (length poly)))
	  (insert (format "(%s*(x^%d))" (car poly) exponent))
	  (if (> exponent 0)
	      (progn
		(insert "+")
		(show-poly (cdr poly)))))))

  (defun get-quotient (num den)
    (setq lnum (length num))
    (setq lden (length den))
    (setq quotient (list))

    (setq high-coef-num (car num))
    (setq high-coef-denom (car den))
    (setq coef (/ high-coef-num high-coef-denom))

    (dotimes (i lden)
      (setq quotient (append quotient (list (- (nth i num) 
                                      (* coef (nth i den)))))))
    (dotimes (i (- lnum lden))
      (setq quotient (append quotient (list (nth (+ lden i) num)))))

    (newline)
    (insert "Last rest: ")
    (show-poly quotient)
    (newline)
    (cons coef quotient))

  (defun divide (numerator denominator)
    (setq lnum (length numerator))
    (setq lden (length denominator))
    
    (if (>= lnum lden)   
	(progn 
          (setq pair (get-quotient numerator denominator))
          (setq coefs (append coefs (list (car pair))))
          (divide (cdr (cdr pair)) denominator))))

  ;; main
  (newline)
  (newline)
  (insert "Polynomial division")
  (newline)
  (setq num '(1 2 1))
  (setq den '(1 1))
  (newline)
  (insert "divide")
  (newline)
  (show-poly num)
  (newline)
  (insert "by")
  (newline)
  (show-poly den)
  (newline)
  (divide num den)
  (newline)
  (insert "Quotient: ")
  (show-poly coefs)
  (newline))

Per a executar el programa copieu el codi anterior a un buffer de l’Emacs i executeu-lo amb C-x C-e (la seqüència control-x control-m).

El programa calcularà la divisió del polinomi x² + 2x + 1 per x + 1, resultat x + 1 i rest 0. Per a provar amb altres polinomis n’hi ha prou de canviar el parell de línies

  (setq num '(1 2 1))
  (setq den '(1 1))

El codi també està al meu GitHub

I, per acabar, encara que aquests dies han donat per algun altre joc amb Python que segurament també publicaré, espero que els propers posts siguin una mica més sucosos (en cartera: programació funcional amb javascript i underscore.js. A veure quan cau!).

Un puzzle 3×3 (versió amb Python i versió amb C)

Després d’una llarga aturada, reprenc el blog amb un un puzzle fet amb python (i amb C)

Segur que recordeu els puzzles en que una imatge es trosseja en NxN – 1 quadrets dins un marc de NxN (és dir, amb un espai lliure). Aleshores, movent quadrets a l’espai que queda lliure es pot aconseguir reordenar la imatge.

En el post d’avui he implementat el cas d’un puzzle de 3×3, tot molt simplificat i en mode text. Com sempre, estic desenvolupant sobre una màquina Linux. En concret, sobre el meu vell i petit eCAFÉ EC-800-H20G/S, amb Lubuntu 10.10, una maquineta minúscula amb un SO antic que, per circumstàncies personals, m’ha fet molta companyia aquests darrer mes.

  puzzle resolt    puzzle desordenat
  +---+            +---+
  |123|            | 38|
  |456|            |245|
  |78 |            |761|
  +---+            +---+

El programa ha de
1. generar un puzzle desordenat
2. mostrar el puzzle
3. demanar quin número es vol moure
4. veure si es pot moure
5.  si no es pot moure, dir-ho i tornar al punt 2
6.  si es pot moure, fer el moviment.
7.    comprovar si ha guanyat
8.      si ha guanyat acabar eljoc
9.      si no ha guanyat, tornar al punt 2.

Amb Python, l’algorisme anterior és d’implementació gairebé directa, fixeu-vos en el bloc main.

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import random
import sys

def genera_puzzle(puzzle):
  for i in range(0,9):
    repeat = True
    while repeat:
      j = random.randint(0,8)
      if puzzle[j] == 10:
        puzzle[j] = i
        repeat = False
  
  return puzzle

def mostra_puzzle(puzzle):
  print "+---+"
  print "|%d%d%d|" % (puzzle[0], puzzle[1], puzzle[2])
  print "|%d%d%d|" % (puzzle[3], puzzle[4], puzzle[5])
  print "|%d%d%d|" % (puzzle[6], puzzle[7], puzzle[8])  
  print "+---+"
  print "\n"

def demanar_numero():
  valid = False
  while not valid:
    in_value = raw_input("(1-9) or q? ")
    if len(in_value) == 1:
      if in_value in "12345678qQ":
        valid = True

  if in_value == 'q' or in_value == 'Q':
    print "\nGame interrupted\n"
    sys.exit(0)

  return int(in_value)


def obtenir_posicio(num, puzzle):
  pos = []

  for row in range(0, 3):
    for column in range(0, 3):
      if num == puzzle[row * 3 + column]:
        pos = [row, column]
        break

  return pos     


def verifica_numero(num, puzzle):
  valid = False
  pos = []
  
  pos = obtenir_posicio(num, puzzle)
  valid = verifica_posicio(pos, puzzle)

  return valid

def verifica_posicio(pos, puzzle):
  valid = False
  row = pos[0]
  column = pos[1]
  
  if (row - 1) >= 0:
    if puzzle[(row - 1) * 3 + column] == 0:
      valid = True

  if (row + 1) = 0:
    if puzzle[(row * 3) + (column - 1)] == 0:
      valid = True

  if (column + 1) = 0:
    if puzzle[(row - 1) * 3 + column] == 0:
      puzzle[(row - 1) * 3 + column] = num
      puzzle[(row * 3) + column] = 0

  if (row + 1) = 0:
    if puzzle[(row * 3) + (column - 1)] == 0:
      puzzle[(row * 3) + (column - 1)] = num
      puzzle[(row * 3) + column] = 0

  if (column + 1) <= 2:
    if puzzle[(row * 3) + (column + 1)] == 0:
      puzzle[(row * 3) + (column + 1)] = num
      puzzle[(row * 3) + column] = 0    
  
  return puzzle

def es_puzzle_completat(puzzle):
  s = ''.join(map(lambda (x): str(x), puzzle))
  if s == '123456780':
    return True
  else:
    return False


if __name__ == "__main__":
  puzzle = [10 for x in range(0, 9)]
  final = False
  puzzle = genera_puzzle(puzzle)
  while not final:
    final = False
    mostra_puzzle(puzzle)
    num = demanar_numero()
    if verifica_numero(num, puzzle):
      puzzle = moviment(num, puzzle)
      if es_puzzle_completat(puzzle):
        print "\nWell done!!\n"
        mostra_puzzle(puzzle)
        final = True

Topt i ser un programa molt curt, té algun detall bonic: per exemple, l’us d’una funció lambda a la verificació de puzzle completat. Amb una sola línia es transforma es transforma un array numèric en una cadena de text. En total, 155 línies de codi.

I això mateix, com queda amb C?Amb C són 230 línies

#ifndef PUZZLE
#define PUZZLE
#include 
#include 
#include 
#include 
#include 

#define TRUE 1
#define FALSE 0

int puzzle[] = {10,10,10,10,10,10,10,10,10};

typedef struct POS {
  int row;
  int column;
} T_POS;

int randint(int range) {
  return random() % (range + 1);  
}

void genera_puzzle(int puzzle[]) {
  int i;
  int j;
  int repeat;
  for(i = 0; i < 9; i++) {
    repeat = 1;
    while (repeat) {
      j = randint(8);
      if (puzzle[j] == 10) {
        puzzle[j] = i;
        repeat = 0;
      }
    }
  }
}

void mostra_puzzle(int puzzle[]) {
  printf("+---+\n");
  printf("|%d%d%d|\n", puzzle[0], puzzle[1], puzzle[2]);
  printf("|%d%d%d|\n", puzzle[3], puzzle[4], puzzle[5]);
  printf("|%d%d%d|\n", puzzle[6], puzzle[7], puzzle[8]);
  printf("+---+\n");
  printf("\n");
}

int demanar_numero() {
  int valid = FALSE;
  char *line;
  char c;

  while(!valid) {
    line = readline("(1-9) or q (quit)? ");
    if (strlen(line) == 1) {
      if ((strcmp(line, "q") == 0) || (strcmp(line, "Q") == 0)) {
	  valid = TRUE;
          free(line);
          printf("\nGame interrupted\n");
          exit(0);
      }
  	
      c = line[0];
      free(line);

      if ((c == '0') || (c == '1') || (c == '2') ||
          (c == '3') || (c == '4') || (c == '5') ||
          (c == '6') || (c == '7') || (c == '8')) {
        valid = TRUE;      
      }       
    }
  }
  
  return (c - '0');
}


T_POS obtenir_posicio(int num, int puzzle[]) { 
  T_POS pos;
  int row;
  int column;

  for(row = 0; row < 3; row++) {
    for(column = 0; column = 0) {
    if (puzzle[(row - 1) * 3 + column] == 0) {
      valid = TRUE;  
    }
  }

  if ((row + 1) = 0) {
    if (puzzle[(row * 3) + (column - 1)] == 0) {
      valid = TRUE;
    }
  }

  if ((column + 1) = 0) {
    if (puzzle[(row - 1) * 3 + column] == 0) {
      puzzle[(row - 1) * 3 + column] = num;
      puzzle[(row * 3) + column] = 0;
    }
  }

  if ((row + 1) = 0) {
    if (puzzle[(row * 3) + (column - 1)] == 0) {
      puzzle[(row * 3) + (column - 1)] = num;
      puzzle[(row * 3) + column] = 0;
    }
  }

  if ((column + 1) <= 2) {
    if (puzzle[(row * 3) + (column + 1)] == 0) {
      puzzle[(row * 3) + (column + 1)] = num;
      puzzle[(row * 3) + column] = 0;
    }
  }
}

int es_puzzle_completat(int puzzle[]) {
  char solved[]="123456780";
  char actual[10];
  int i;
 
  for(i = 0; i < 9; i++) {
    actual[i] = puzzle[i] + '0';
  }
  actual[9] = 0;

  if (strcmp(solved, actual) == 0) {
    return TRUE;
  } else {
    return FALSE;
  }
}

int main(int argc, char *argv[]) {
  int final = 0;
  int num;
  genera_puzzle(puzzle);
  while(!final) {
    final = 0;
    mostra_puzzle(puzzle);
    num = demanar_numero();
    if (verifica_numero(num, puzzle)) {
      moviment(num, puzzle);
      if (es_puzzle_completat(puzzle)) {
        printf("\nWell done!!\n");
        mostra_puzzle(puzzle);
        final = 1;
      }
    }
  }
}

#endif

I el makefile corresponent

all: puzzle clean

puzzle: puzzle.o
	gcc -g -lreadline -o puzzle puzzle.o

puzzle.o: puzzle.c
	gcc -g -c puzzle.c

clean:
	-rm *.o *~

Amb C també és força directe, però cal fer la gestió d’espai de memòria que amb Python ve donada.

Remarcar l’us de la llibreria readline per a fer l’entrada per teclat. Aquesta és la forma més recomanable de fer entrades per teclat a una aplicació de consola a Linux. Les aplicacions curses tenen també un sistema propi i segur per fer entrades per teclat que eviten el perill de desbordament del buffer d’entrada si es fa servir gets(), o scanf(), o qualsevol sistema que demani un buffer d’entrada de mida especificada.

Finalment, aquest puzzle bàsic es pot ampliar senzillament amb:
– incrementant a dimensions NxN amb N > 3
– afegint interfície gràfica: amb Tkinter, o Pygame, a la versió amb Python; Fent servir Glade a la versió C.

Finalment, el codi de les dues versions (C i Python) es pot descarregar del meu GitHub

Arduino Starter Kit

1 Un post sobre Arduino

Des de fa alguns anys que dins del món de programari lliure, o del moviment maker, o des d’entorns educatius i formatius de tecnologia, se sent parlar i es desenvolupa una activitat creixent al voltant d’Arduino (i de Raspberry Pi, Scratch, Processing…)

Em venia de gust provar l’Arduino i això em va dur a comprar, fa uns mesos, un Arduino Starter Kit per a fer-ne els experiments i captar-ne les “sensacions”. Finalment, he trobat temps per completar els experiments i és el moment d’explicar què m’he trobat.

L’Starter Kit deu ser, segurament, la forma més suau d’introduir-se a l’Arduino. És una caixa que inclou una placa Arduino One, una placa protoboard, components electrònics diversos, cables i ponts de connexió i un manual amb quinze experiments -cap d’ells complex, però algun de força vistós- per a realitzar amb el material inclòs.

Clarament l’Arduino Starter Kit està orientat a un públic jove. Les nenes i nens de ESO no haurien de tenir cap dificultat en la realització dels experiments i comprendre la lògica de funcionament dels circuits i els diferents components utilitzats. En cap cas es tracta d’experiments perillosos. Potser els circuits que involucren el motor de continua són els més “complexos” i els que poden presentar major dificultat de muntatge, però els resultats son espectaculars.

Però no us penseu que Arduino és tracta d’una joguina. Les noies i els nois més grans, a nivells de Batxillerat, però també universitaris, poden trobar a l’Arduino una plataforma excel·lent per a la realització de projectes. Fora dels entorns formatius, Arduino ha esdevingut una de les plaques preferides pels aficionats a l’electrònica i pel moviment Maker. Arduino es presenta en diferents versions i existeix una versió industrial per a l’us professional.

2 Però què és Arduino?

(traduccio lliure de https://www.arduino.cc/en/Guide/Introduction)

“Arduino és una plataforma de prototipatge de codi obert basada en hardware i software senzill i fàcil d’usar. Les plaques Arduino són capaces de llegir entrades: com la llum a un sensor, un dit prement un botó, o una piulada de Twitter, i transformar-les en sortides: activant un motor, encenent un LED, o publicant alguna cosa a Internet. Es pot indicar a la placa què ha de fer tot enviant-li instruccions al microcontrolador que porta muntat. Per a aconseguir-ho es fa us del llenguatge de programació de l’Arduino (basat en el llenguatge Wiring), i en l’entorn de desenvolupament integrat d’Arduino (Integrated Development Enviroment, o IDE), basat en l’entorn Processing.

Amb el pas dels anys Arduino ha estat el cervell de milers de projectes, desde objectes quotidians fins a instruments científics complexos. Una comunitat mundial de ‘makers’ -estudiants, aficionats, artistes, programadors i professionals- s’ha aplegat al voltant d’aquesta plataforma de codi obert. Les seves contribucions hab afegit una quantitat increible de coneixement accessible que pot ser de gran ajuda tant per als principiants com per als més experts.

Arduino va neixer al Ivrea Interaction Design Institute com una eina d’utilització fàcil per al prototipatge ràpid adreçada a estudiants sense fonaments en electrònica i programació. Tan aviat com va arribar a una comunitat més gran, la placa Arduino va començar a canviar per adaptar-se a noves necessitats i desafiaments, diversificant la seva oferta desde plaques simples de 8 bits, fins productes per a aplicacions de Internet of Things (IoT), wearables, impressió 3D i sistemes encastats. Totes les plaques Arduino són completament de codi obert, permetent als usuaris construir-les pels seus propis mitjans i adaptar-les als seus requeriments particulars. El programari també és de codi obert i evoluciona amb les constribucions dels usuaris d’arreu del món.

Mercès a la seva accessibilitat i simplicitat d’us, Arduino s’utilitza en milers de projectes i aplicacions diferents. El programari d’Arduino és d’us senzill per als principiants però, a l’hora, prou flexible per usuaris experimentats. Es pot executar en Mac, Windows i Linux. Els professors i els estudiants el fan servir per construir instruments científics barats, o per provar principis de física i química, o per a iniciar-se en la programació i la robòtica. Els dissenyadors i els arquitectes construeixen prototipus interactius. Músics i artistes el fan servir en instal·lacions i per experimentar amb instruments musicals nous. Els ‘Makers’, per descomptat, el fan servir per construir molts dels projectes que s’exhibeixen a les ‘Maker Faire’, per exemple. Arduino és una eina clau per a l’aprenentatge de novetats. Tothom – nens, aficionats, artistes, programadors – es pot posar mans a l’obra ja sigui seguint les instruccions pas a pas d’un kit, o compartint idees amb altres membres de la comunitat Arduino.

Hi han molts altres microcontroladors i plataformes de microcontrolador per a la construcció de sistemes físics interactius (“physical computing”). Parallax Basic Stamp, BX-24 de Netmedia, Phidgets, Handyboard del MIT, i molts altres que ofereixen funcionalitats similars. Totes aquestes eines encapsulen els detalls més farragosos de la programació de microcontroladors i el empaqueten en una interficie d’usuari més senzilla d’utilitzar. Arduino també simplifica el procés de treball amb microcontroladors i, a més, ofereix alguns avantatges per als professors, estudiants, i aficionats que no tenen els altres sistemes:

  • Barat – Les plaques Arduino són relativament barates si es comparen amb altres plataformes de microcontroladors. La versió més barata d’Arduino es pot muntar a mà, i els mòduls de version ja muntades, no arriben als 50 dòlars.
  • Multiplataforma – L’entorn de programació d’Arduino s’executa a Windows, Macintosh OSX, i distribucions Linux. La majoria de plataformes de microcontroladors estan limitades a Windows.
  • Entorn de programació senzill – L’entorn de programació és fàcil d’usar pels principiants, però prou flexible com per a que els usuaris avançats el puguin fer servir eficaçment. Per als mestres, l’entorn integrat està basat en l’entorn de programació ‘Processing’, per tant, els estudiants que estiguin aprenent a programar en aquest es trobaran que els serà familiar la forma de treballar de l’IDE d’Arduino (veure nota).
  • Codi obert i programari extensible – El programari Arduino es codi obert i es pot extendre. El llenguatge de programació es pot ampliar mitjançant llibreries C++, i la gent aque vulgui comprendre els detalls més tècnics poden fer els salt des del llenguatge de l’Arduino IDE al llenguatge de programació C per AVR en que està basat. També es pot afegir codi AVR-C directament als programes d’Arduino si es vol.
  • Codi obert i maquinari extensible – Els esquemes de les plaques Arduino es publiquen amb llicència Creative Commons, per tant els dissenyadors mes experimentats poden fer les seves pròies versions dels mòduls, extendre-les o millorar-les. Fins i tot, un principiant pot construir la seva pròpia versió dels mòduls en una placa protoboard, per a comprendre’n el funcionament i per estalviar diners.”

Nota: realment l’IDE de l’Arduino està basat en el IDE Wiring (basat en el llenguatge C), que al seu temps ho està en el IDE de Processing (basat en llenguatge Java)

3 Especificacions d’Arduino One

Les podeu trobar a la pàgina oficial. Les reprodueixo a continuació:

Technical specs
Microcontroller ATmega328P
Operating Voltage 5V
Input Voltage (recommended) 7-12V
Input Voltage (limit) 6-20V
Digital I/O Pins 14 (of which 6 provide PWM output)
PWM Digital I/O Pins 6
Analog Input Pins1 6
DC Current per I/O Pin 20 mA
DC Current for 3.3V Pin 50 mA
Flash Memory 32 KB (ATmega328P) of which 0.5 KB used by bootloader
SRAM 2 KB (ATmega328P)
EEPROM 1 KB (ATmega328P)
Clock Speed 16 MHz
Length 68.6 mm
Width 53.4 mm
Weight 25 g

I també l’esquemàtic.

4 Els circuits.

L’Starter Kit proposa la construcció de quinze circuits molt senzills. Per a cada circuit es proporciona:

  • la llista de components a utilitzar
  • l’esquema
  • la foto del circuit muntat
  • la descripció pas a pas del muntatge dels components
  • el codi C comentat que cal compilar i carregar a l’Arduino
  • com provar el circuit
  • propostes d’ampliació i variacions

4.1 Experiment 1.

S’expliquen els contactes de la protoboard; S’enuncien els rudiments dels circuits elèctrics i la llei d’Ohm, i es fan circuits mínims en serie i paral·lel. L’Arduino només es fa servir per proporcionar l’alimentació dels circuits.

4.2 Experiment 2.

És un experiment mínim que permet introduir l’Arduino IDE. Es programa una seqüència d’encesa i apagat de tres leds fent servir sortides digitals. S’aprèn a compilar i carregar els programes a la placa. Ens planteja l’estructura bàsica dels programes Arduino, amb la funció setup() que s’executa al començament de l’execució i que s’aprofita per a inicialitzar l’estat de la placa; i la funció loop() que és una funció que s’executa contínuament, i que és on es programa la funcionalitat desitjada. Les funcions setup() i loop() apareixen sempre en tots els programes d’Arduino.

S’introdueix una tècnica per reconèixer els canvis d’estat als ports d’entrada de l’Arduino.

4.3 Experiment 3.

S’introdueix el sensor de temperatura TMP36 que es capaç de proporcionar un rang de tensions de sortida que varia proporcionalment a la temperatura en graus centígrads. Es mostra l’ús de les entrades analògiques i una tècnica simple d’escalat de valors. S’introdueix el Monitor Sèrie, que permet obtenir informació i missatges provinents de la placa Arduino, i també per enviar senyals a la placa. Es fan servir les sortides digitals per simular un termòmetre fet amb leds.

4.3.1 Comunicació entre Arduino i Host pel port sèrie (USB) amb altres llenguatges

La comunicació sèrie entre l’ordinador (el host) i la placa Arduino mitjançant el port sèrie (USB) es pot fer amb varietat de llenguatges, no només amb l’Arduino IDE.

En particular, és molt senzill fer la comunicació amb aplicacions desenvolupades amb C/C++ perquè es fa servir la llibreria C estàndard. És dir, amb C/C++ n’hi ha prou amb obrir el port /dev/ttyACM0 amb fopen per a lectura/escriptura i fer servir la resta de funcions de I/O de la la llibreria estàndard: fread, fwrite, fclose…

Alternativament, també es poden fer servir les crides de baix nivell: open, write, read, close… la tria d’un o altre grup de funcions, doncs, dependrà d’altres criteris, com pot ser el grau d’abstracció que es requereixi en la comunicació entre host i Arduino. En general, però, sempre caldrà tenir en compte mantenir la consistència amb el mètode triat (Llibreria Estàndard de C, o Crides al Sistema),

Amb Python, la comunicació entre Arduino i Host es pot fer fàcilment amb la llibreria pySerial.

La llibreria s’ha de carregar. En el meu cas que faig servir una distribució Lubuntu 15.04 he de fer:

sudo apt-get install python-serial

El següent és un exemple bàsic que permet llegir els missatges que venen de la placa Arduino:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import serial
 
ser = serial.Serial('/dev/ttyACM0', 9600)
while True:
   print ser.readline()

Amb Java, es pot fer servir la llibreria RxTx. Es tracta d’un jar amb classes java i d’una so (per Linux, Mac) o dll (per Windows) que cal instal·lar. Val a dir que aquesta llibreria va inclosa amb l’entorn Processing, així que si teniu instal·lat aquest entorn ja teniu la RxTx al vostre sistema.

4.4 Experiment 4.

En aquest experiment es fan servir tres fotoresistències per a modular els senyals dels components blau, ved i vermell d’un LED RGB de càtode comú: en funció del grau d’il·luminació de cadascuna de les fotoresistències s’aconsegueix que la llum del LED variï entre el blanc (tots els sensors totalment il·luminats), tons i barreges de colors (diferents intensitats de llum sobre cada sensor), o l’apagat (amb els sensors de llum tapats).

Per a simular les sortides de diferents intensitats amb les sortides digitals s’aprofita que les sortides 3,5,6,10 i 11 de l’Arduino admeten la modulació PWM, (és dir, regular el cicle de treball del pols digital i, per tant, modular-ne el valor del component de CC). En la programació del codi es té en compte el temps necessari per a la conversió AD a les entrades connectades als sensors.

4.5 Experiment 5.

El servomotor és l’estrella de l’experiment 5. L’alimentació de 5V de l’arduino és suficient per alimentar el servomotor. Al tractar-se d’una càrrega inductiva cal protegir la placa dels corrents espúris produits pel servo: en aquest circuit s’afegeixen un parell de condensadors de desacoblament,

Al codi cal destacar

  • L’utilització de la llibreria Servo, que encapsula la utilització de sevomotors de Parallax.
  • L’us de la funció map() (veure nota) que permet fer un mapeig escalat lineal entre un rang d’entrada i un de sortida.

Per a saber més de motors i servos, se’ns recomana el llibre Making Things Move de Dustyn Roberts i l’adreça http://robives.com/mechs

nota: aquesta funcio map() no té res a veure amb la funció homònima que es pot trobar als llenguatges que segueixen el paradigma de programació funcional!

4.6 Experiment 6.

Del moviment al sò. Conceptualment és similar a l’experiment 4. Es fa servir una fotoresistència per modular el senyal que ataca un brunzidor piezoelèctric. El senyal del sensor es converteix AD a un valor que es fa correspondre amb map() (veure nota) a un valor dins el rang de control de la sortida PWM que ataca al brunzidor.

La novetat en aquest circuit és que en comptes de fer servir la funció analogWrite() es fa servir la més adequada tone(): Amb analogWrite() la freqüència que s’envia per la sortida és fixa però amb un cicle de treball (relació entre temps en estat alt i període del senyal) variable; amb tone() el cicle de treball és sempre del 50%, però canvia la freqüència del senyal.

Al codi també s’introdueix la funció millis() per controlar un temporitzador.

4.7 experiment 7.

Un altre experiment amb el brunzidor. En aquesta ocasió se substitueix el sensor de llum per una escala de resistències combinada amb uns interruptors, de forma que a la pulsació de cada interruptor li correspon un valor de tensió en l’entrada AD de l’Arduino. A cada valor d’entrada se li fa correspondre una freqüència, amb la que s’ataca al brunzidor.

la novetat al codi és la utilització d’un array de C per mantenir la taula de freqüències, i la utilització de noTone() per silenciar el brunzidor quan no hi ha cap interruptor premut.

Una taula amb les freqüències de les notes musicals es pot consultar a http://arduino.org/frequencies.

4.8 Experiment 8.

En aquest experiment es fa servir un interruptor d’inclinació per a simular un rellotge de sorra: al moure l’interruptor que està connectat a una entrada digital que s llegeix amb digitalRead(), es restaura l’estat de les sortides digitals que estan connectades a uns leds. Aleshores, a la funció loop(), en cada iteració s’observa l’hora actual que s’obté amb millis() i es compara amb l’hora en que s’ha encès el darrer LED. Si l’interval de temps supera un valor prefixat, s’encén el següent LED i s’actualitza la marca.

4.9 Experiment 9.

Es presenta el motor de continua. El motor de CC és de velocitat i sentit de gir variables. la velocitat de gir es pot controlar variant la tensió aplicada a les seves connexions (dins d’uns límits), i el sentit de gir es pot canviar invertint-ne la polaritat.

Tanmateix, fins i tot amb el petit motor inclòs a l’Starter Kit, l’Arduino no és capaç de proporcionar prou corrent per a alimentar motors directament: Arduino One no pot proporcionar més de 40mA per les sortides digitals.

El que es fa al circuit és connectar el motor a una font externa i controlar-ne l’alimentació fent servir un transistor MOSFET IRF520 com a interruptor electrònic, connectant-ne la porta a una de les sortides PWM i fent el control efectiu de l’encesa i apagada amb un interruptor connectat a una de les entrades digitals.

Al manual del kit proposen fer servir una pila de 9V per a la font externa. També es pot fer servir una font d’alimentació de les que es poden trobar a qualsevol basar xinès.

Addicionalment, es fa servir un díode rectificador N4007 connectat en oposició a l’alimentació del motor, per a proporcionar un camí de descàrrega per als corrents auto-induits quan aquest es desconnecta de l’alimentació i es va frenant fins aturar-se.

4.10 Experiment 10.

A l’experiment anterior es presentava el motor de CC i es muntava un circuit molt senzill per a engegar-lo i aturar-lo, però s’indicava que és possible regular-ne la velocitat i l sentit de gir. En aquest experiment es fa servir un circuit integrat L293D de driver per a motors per aconseguir aquest control.

L’ús de l’L293D simplifica el control dels motors: un xip substitueix el circuit del MOSFET i al díode de protecció. Però, a més, és possible realitzar el control de velocitat i la inversió de gir (un pont H) amb aquest CI.

És una bona idea revisar l’especificació de l’L293D per revisar diferents modalitats de connexió, o la connexió de fins a quatre motors amb aquest driver.

4.11 Experiment 11.

Es presenta el dispositiu LCD de visualització LCM1602C, es tracta d’un pantalla LCD de 16×2 caràcters. El muntatge connecta les sortides digitals de l’Arduino al display LCD per a mostrar missatges que canvien aleatòriament quan es mou l’interruptor d’inclinació connectat a una de les entrades digitals. És un projecte similar al de l’experiment 8, només que en comptes d’enviar els missatges aleatoris pel monitor sèrie, els mostra a l’LCD.

La lògica de comunicació entre Arduino i l’LCD s’encapsula a la llibreria LiquidCrystal. La llibreria s’explica amb detall a la url: http://arduino.org/lcd.

Pel que fa al muntatge, val a dir que hi ha alguna etiqueta de l’esquema al manual que no coincideix exactament amb l’etiqueta impresa al component LCD i potser pot produir alguna confusió. En tot cas, una revisió de les especificacions de l’LCM1602C haurien de ser suficients per esvair qualsevol dubte en el cablatge.

4.12 Experiment 12.

Un altre experiment amb el servomotor. En aquesta ocasió es fa servir el brunzidor piezoelèctric com a sensor, en lloc d’actuador. El brunzidor, a més de produir so, també el pot captar i, per tant, en aquesta ocasió es connecta a una entrada analògica de l’Arduino, enlloc de a una sortida.

El circuit de l’experiment fa un comptador de tocs (per exemple, el soroll de picar de mans).

El programa és un exemple de com implementar una senzilla màquina d’estats. El funcionament implementat va fent transicions des de l’estat de repòs (leds taronja i verd apagats, led vermell encès, servo en posició de “tancat”), a l’estat d’un toc vàlid captat (leds verd i vermell apagats, led taronja encès, servo “tancat”), dos tocs vàlids captats (mateixes condicions), i tres tocs vàlids captats (leds vermell i taronja apagats, led verd obert, i servo en posició d'”obert”), on roman fins que es rep un reset que torna a l’estat de repòs original.

4.13 Experiment 13.

l’Starter Kit ens proposa la construcció d’un “component” capacitiu amb paper d’alumini que es pugui fer servir amb la llibreria CapacitiveSensor de Paul Badger.

El component capacitiu no és més que una làmina de paper d’alumini.

El principi de funcionament d’aquest “sensor” és la càrrega i descàrrega de les capacitats paràsites que apareixen al circuit. Per a major detall, podeu consultar http://playground.arduino.cc/Main/CapacitiveSensor

També és interessant que, a diferència d’altres llibreries usades en els experiments, cal descarregar la CapacitiveSensor d’Internet i instal·lar-la correctament a l’Arduino IDE per a poder fer-la servir.

4.14 Experiment 14.

És possible “parlar” amb l’Arduino amb varietat de llenguatges, entorns i aplicacions, com podeu comprovar a http://playground.arduino.cc/Main/Interfacing.

A l’experiment 14 s’envia un senyal variable des de l’arduino pel monitor sèrie (pel port USB). El senyal és genera amb un divisor de tensió fet amb un potenciòmetre connectat a una entrada analògica, però en aquesta ocasió no es manipula cap sortida si no que el valor capturat s’envia pel port sèrie.

La novetat de l’experiment és que en comptes de capturar la dada enviada per la placa amb el Monitor Sèrie de l’Arduino IDE es fa servir una petita aplicació desenvolupada amb Processing. De la wiki: “Processing és una aplicació de codi obert amb un llenguatge per a la programació d’imatges, animació, i so. El processing és un projecte de codi lliure iniciat per Ben Fry (Institut Ample) i Casey Reas (UCLA Design / Media Arts), i és desenvolupat per artistes i dissenyadors com a alternativa a eines de programari patentades en el mateix camp, com Macromedia Flash o Director.”

Processing i Arduino IDE són molt similars. El paral·lelisme va més enllà del look-and-feel de l’entorn: els programes amb l’Arduino IDE són, bàsicament, un setup() i un loop(); amb Processing tenim també un setup() que s’executa un cop a l’inici de l’execució; i un draw(), que al igual que loop() s’executa contínuament.

Processing compta amb moltes llibreries realitzades i depurades per usuaris i compartides amb la comunitat, igual que l’Arduino IDE. En particular, compta amb una llibreria procesing.serial basada en la RxTx per a realitzar comunicacions pel port USB (serie). Internament, RxTx es basa en una llibreria nadiua al sistema operatiu hoste, que s’encapsula amb el mecanisme JNI de Java, i unes classes java que exposen la interfície de programació.

El programa proposat amb Processing escolta el port serie i, segons les dades que va rebent (entre 0 i 255, que corresponen als nivells de tensió variables amb el potenciòmetres connectat a l’entrada analògica de l’Arduino) es va canviant el color de fons d’una pantalla que mostra una imatge del logo d’Arduino.

4.14.1 Experiment 14 Amb Python, Pygame i pySerial

El cas és que m’he trobat un parell de problemes al codi del manual: el primer és que la imatge que es fa servir és referencia a través d’una URL. Aquesta URL ja no està disponible i cal canviar-la per una altre que que sí es pugui accedir. I segon: em fa l’efecte que el codi que es fa servir no està actualitzat a la darrera versió de la llibreria.

Vistes aquestes “dificultats” he optat per buscar una solució alternativa. Processing està molt bé, però com Python m’agrada molt, he assajat una solució amb Python i les llibreries Pygame i pySerial. Vet aquí el codi:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import pygame, sys, serial
from pygame.locals import *

if __name__ == "__main__":
    pygame.init()
    FPS = 25 # frames per second setting
    fpsClock = pygame.time.Clock()
    
    # set up the window
    board = pygame.display.set_mode((400, 300), 0, 32)
    pygame.display.set_caption('Arduino')

    # set up serial port
    ser = serial.Serial("/dev/ttyACM0", baudrate=9600)
    
    while True: # the main loop
        if ser.isOpen():
            A0_385 = ser.read(385) # 385 = 9600 / FPS
            A0 = ord(A0_385[0])
            FILL_COLOR = (A0, A0, A0)
        
            board.fill(FILL_COLOR)
        
        for event in pygame.event.get():
            if event.type == QUIT:
                ser.close()
                pygame.quit()
                sys.exit()

        pygame.display.update()
        fpsClock.tick(FPS)

Els programes fets amb Pygame tenen aquesta mateixa estructura setup-loop que es pot trobar als programes de Processing, o als programes de l’Arduino. És fàcil, doncs, “anar” de l’un a l’altre.

Val a dir que m’he trobat amb una dificultat que no havia previst: les diferents velocitats entre la producció de dades de la placa i la velocitat de consum, donada pel nombre d’iteracions per segon del bucle de lectura de dades i d’actualització de pantalla, que està controlat per fpsClock.tick(FPS).

La solució ha estat “descartar frames” que és el que aconsegueixo amb:

A0_385 = ser.read(385) # 385 = 9600 / FPS
A0 = ord(A0_385[0])
FILL_COLOR = (A0, A0, A0)

És dir llegeix 385 caràcters el buffer (385 = bauds / fps), però només té en compte el primer. Més que una dada precisa que permeti buidar el buffer de lectura en cada iteració, 385 (o 400) és, més aviat, un ordre de magnitud que es podria ajustar.

En tot cas, aquest valor funciona bastant bé, i movent el potenciòmetre de la placa, aconsegueixo que el color de fons de la pantalla variï gradualment en una escala de grisos entre el blanc i el negre.

4.14.2 Una “variació” de l’experiment 14 amb Scratch for Arduino

Scratch for Arduino (S4A) és un desenvolupament realitzat al Citilab de Cornellà.

De la pàgina web http://s4a.cat/index_ca.html: “Què és S4A? S4A és una modificació d’Scratch que permet programar la plataforma de hardware lliure Arduino d’una manera senzilla. Proporciona blocs nous per tractar amb sensors i actuadors connectats a una placa Arduino. També compta amb un panell de sensors similar al de la PicoBoard.

La finalitat principal del projecte és atreure gent al món de la programació. Un altre objectiu és proporcionar una interfície d’alt nivell per a programadors d’Arduino amb funcionalitats tals com la interacció amb un conjunt de plaques mitjançant esdeveniments d’usuari.”

Som-hi. Realment, aquest versió de l’experiment no segueix ben bé la mateixa lògica perquè amb S4A no puc llegir directament el monitor sèrie. El que faig es llegir el senyal de l’entrada analògica amb un sensor d’Scratch, i faig servir aquest valor per moure un sprite amb el gat d’Scratch per la pantalla.

El procés és el següent.

Descarrego i instal·lo l’S4A i el firmware de connexió (el programa d’interfície amb Scratch que realment s’executa a la placa Arduino i que és el que controla el port serie).

El circuit a la placa Arduino és el de l’experiment 14 tal com apareix al manual: un potenciòmetre fent de divisor de tensió entre Vcc i GND amb la pota de control connectada a l’entrada analògica A0.

Connecto per USB l’ordinador i l’Arduino i fent servir l’Arduino IDE carrego el firmware a la placa.

Ara engego l’S4A. No ha d’haver cap problema. L’S4A reconeix una placa Arduino connectada.

Aleshores, amb l’Scratch preparo una nova variable v_posx:

1-variable

aquest bloc per a “l’escenari”:

2-escenari

aquest per al gat:

3-gat

Li dono a la bandereta verda i, efectivament, ara tinc un gat corrent per la pantalla controlat pel potenciòmetre del circuit a la placa Arduino. Fixeu-vos en el valor de la variable de l’entrada A0 a les imatges.

4.15 Experiment 15.

I per acabar la revisió de l’Starter Kit, a l’experiment 15 se’ns anima a buscar aquelles andròmines velles que siguin susceptibles d’algun tipus de control electrònic i tractar d’imaginar com es podrien connectar a l’Arduino, i s’aprofita per presentar l’opto-acoblador 4N35.

Títols de crèdit com els d’Star Wars (efecte “rolling”) amb Python

1 Fa molt temps (però no en una galàxia molt llunyana)…

… vaig a anar al cine -i era un dels primers cops que hi anava- per veure “La guerra de las galaxias”, que era com es va traduir el nom de “Star Wars: A new hope”.
La pel·lícula em va impressionar des del primer segon, començant pels imponents títols de crèdit que introduïen la història i que s’allunyaven majestuosament per l’espai.
Per a la realització de l’efecte dels títols allunyant-se es van utilitzar tècniques “artesanals”. En aquest enllaç expliquen com, però una foto val més que mil paraules:
Star-Wars-Intro-Creation-Secret-2
Des de l’arribada de la informàtica personal s’han inventat de forma recurrent sistemes per reproduir l’efecte amb ordinadors. Una cerca a Google ens mostra un munt de resultats.
L’efecte es pot aconseguir directament amb diverses aplicacions, però segueix sent un repte interessant la seva realització per programa. En el post d’avui, doncs, presento un “prova de concepte” feta amb Python per a generar aquest efecte de rolling a uns títols de crèdit.

2 Com es fa una animació?

Es sabut que una animació no és més que la successió ràpida d’imatges (frames, o fotogrames). Per tant, per a fer una animació només cal mostrar una imatge durant un breu instant, a continuació una altre amb un petit canvi, després un altre… la integració de la successió de les imatges estàtiques al nostre cervell és el que provoca la sensació de moviment. Aleshores, per a fer una animació el que he de fer és crear els diferents fotogrames que la formen. La sensació de moviment suau depèn de quantes imatges (o frames) per segon es fan servir: amb 12 frames per segon (fps) s’arriben a notar alguns salts; a 25fps la sensació de moviment és pràcticament perfecte, i és el valor que es fa servir a les càmeres de vídeo.

2.1 Un experiment

Fem un petit experiment. Agafem aquesta imatge que és de 606×700
swtfa

En comptes de visualitzar-la sencera…

  • en visualitzaré només un quadre de 320×240;
  • aniré desplaçant el quadre un píxel per cop cap avall;
  • a una velocitat de 10 píxels per segon, és dir, a 10fps.

Faig servir la funció blit de la llibreria pygame per mostrar només una part de la imatge.

blit-image.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import pygame as pg
from pygame.locals import *

pg.init()                           # init pygame
w = 320                             # width
h = 240                             # height
size=(w,h)                          # size
screen = pg.display.set_mode(size)  # init screen
pg.display.set_caption('Star Wars TFA')  # caption
filename = "./swtfa.jpg"            # filename
img=pg.image.load(filename)         # image 606x700
x = 0
y = 0
FPS = 10                            # frames per second setting
framerate = pg.time.Clock()
repeat = True
   
while repeat:                       # iterate
    # put image
    screen.blit(img, (0,0), (x, y, 320, 240)) 
    pg.display.flip() 
          
    # scroll down image
    y = y + 1
    if (y + 240 > 800):
      y = 0

    #10fps
    framerate.tick(FPS)

    # capture events
    for event in pg.event.get():
      if event.type == QUIT:
          repeat = False

# exit          
pg.quit()    
print "done!"

Si executo el programa anterior sembla que la imatge dins el requadre es vagi movent cap avall. He aconseguit crear la sensació de moviment a partir d’una imatge estàtica. Amb els títols de crèdit he de fer el mateix: construiré una imatge amb el text i aniré obtenint-ne els diferents frames sense més que anar desplaçant-me un píxel cap avall per a cada frame. Aleshores, un cop tingui tots els frames base, aplicaré una transformació sobre cada frame per afegir l’efecte d’allunyament.

3 Esquema general

La idea és partir d’un text d’entrada inicial i obtenir, com a resultat final, un vídeo amb l’scrolling del text.
Especifico més: el vídeo serà de format mp4 de 320×240 px.

El procés es pot dividir en sub-processos més senzills. Em plantejo aquests quatre passos:

  • donar al text un format adequat per a ser processat.
  • crear els frames base del vídeo (imatges o frames de 320×240)
  • processar els frames per afegir l’efecte d’allunyament: el resultat de processar cada frame serà un nou frame, també de 320×240.
  • crear un vídeo amb els frames processats.

Som hi.

4 Donar al text un format adequat

Primer de tot, el text a mostrar:

EPISODI V
L'IMPERI CONTRAATACA
Les forces imperials avancen implacablement 
de victòria en victòria sobre els rebels. 
L'Imperi prepara el cop definitiu: 
ha descobert la principal base rebel 
al planeta gelat de Hoth 
i es llença a l'atac per destruir-la.
Però no tot està perdut per 
als rebels. 
Si aconsegueixen retenir prou temps 
a les tropes d'assalt, la flota rebel 
podrà escapar a la nova base secreta...

Ara he de preparar aquest text per a que em sigui fàcil generar els frames de la imatge i processar-los.

La idea és aquesta: vaig a convertir el text en una imatge de 320px d’ample (ample de imatge que coincideixi amb l’ample de frame) per el llarg suficient per encabir-hi el text, més 240px (un frame) addicionals en blanc al principi i 240px (un frame addicional) en blanc al final.

Amb aquestes restriccions (i després d’algunes proves) resulta que la mida 320×800 em serveix.

I quin format? La restricció és fer-m’ho fàcil i que tot sigui molt evident i clar. El format més adequat que he trobat és el pbm:

https://en.wikipedia.org/wiki/Netpbm_format

Es tracta d’un format monocrom molt senzill. Reviso l’exemple que apareix a la wiki:

P1
# This is an example bitmap of the letter "J"
6 10
0 0 0 0 1 0
0 0 0 0 1 0
0 0 0 0 1 0
0 0 0 0 1 0
0 0 0 0 1 0
0 0 0 0 1 0
1 0 0 0 1 0
0 1 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
  • ‘P1’ indica que és el format pbm, es dir monocrom amb dades en format ascii
  • ‘# This is…’ és un comentari
  • ‘6 10’ diu que és una imatge de 6×10 píxels
  • ‘0’ indica punt en blanc ‘1’ punt en negre
  • A més, els espais en blanc, i salts de línia es descarten

Tenint en compte tot l’anterior, genero amb GIMP un llenç de 320×800 de fons negre; hi afegeixo el text deixant 240px abans de l’inici i 240px després.

El resultat és aquest:

intro

5 crear el fitxer “master”

Si examino intro.pbm veig el següent:

albert@eowyn:~/workspace/python/starwars-credits$ head intro.pbm
P1
# CREATOR: GIMP PNM Filter Version 1.1
320 800
1111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111
albert@eowyn:~/workspace/python/starwars-credits$ wc intro.pbm
  3660   3668 259707 intro.pbm
albert@eowyn:~/workspace/python/starwars-credits$

La part de la imatge es divideix en línies de 70 caràcters. L’especificació dels formats pbm, pgm, ppm recomana que les línies de dades no superin els 70 caràcters, però només és una recomanació. Aprofito aquest grau de llibertat perquè em sembla que és més senzill transformar el bloc de 70×3657 (3660 línies menys les tres de capçalera) en una bloc de 320(+ 1 de retorn de carro)x800 per a poder moure’m directament als inicis de cada fila d’imatge i agafar blocs de 240 files per a generar els frames. O sigui, em preparo un “master” per a poder generar més senzillament els frames. Ho faig amb el següent codi:

w = 320                                   # width of a frame and base image
h_frame = 240                             # height of a frame
h_img_base = 800                          # height of base image
c = 0                                     # counter
frame_size=(w,h_frame)                    # size of frame
filename_read = "intro.pbm"
frames_folder = "./frames/"
filename_master = "master"
bit = ""

# create master
with open(filename_read, "r") as fr:    
    with open(frames_folder + filename_master, "w") as fm:
        # discards three first header lines
        fr.readline()
        fr.readline()
        fr.readline()

        for i in xrange(0, w * h_img_base):
            c = c + 1
            bit = fr.read(1)
            if bit == '\n':
                bit = fr.read(1)
            fm.write(bit)

            if c == w:
                fm.write('\n')
                c = 0

El resultat de l’anterior és un fitxer master de 800 files de 320 caràcters (més un caràcter de retorn de carro a cada línia).

6 creació dels frames

A partir del master és molt senzill generar els frames. Això ho faig amb el següent codi

# create frames
filename_frame = ""
filename_pattern = "frame_%0#5d.pbm"
frame_count = 0

with open(frames_folder + filename_master, "r") as fr:
    for frame_count in xrange(0, h_img_base - h_frame): 
        filename_frame = filename_pattern % frame_count
        print "[Frame %d]" % frame_count

        with open(frames_folder + filename_frame, "w") as fw:
            fw.write("P1\n")
            fw.write("# CREATOR: Albert Baranguer Codina\n")
            fw.write("%d %d\n" % frame_size)

            fr.seek(frame_count * (w + 1))

            for i in xrange(h_frame ):
                fw.write(fr.readline())

Remarcar que amb

fr.seek(frame_count * (w + 1))

Em situo a l’inici de cada frame, i amb

for i in xrange(h_frame ):
    fw.write(fr.readline())

llegeixo el bloc de 240 línies. En aquest moment, després d’executar el bloc anterior, tinc 560 fitxers pbm (560 = 800 – 240) amb noms de frame_00000.pbm a frame_00559.pbm a la carpeta frames. Cada fitxer té un bloc d’imatge de 240 línies de 320 caràcters, més un de retorn de carro, per fila.

7 EL vídeo sense processar

Puc fer servir els frames generats per visualitzar la versió del vídeo sense l’efecte d’allunyament. Faig servir el següent visualitzador:

player1.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import pygame as pg
from pygame.locals import *

pg.init()                           # init pygame
w = 320                             # width
h = 240                             # height
size=(w,h)                          # size
screen = pg.display.set_mode(size)  # init screen  
FPS = 18                            # frames per second setting
framerate = pg.time.Clock()
pg.display.set_caption('STAR WARS CAPTION FX')

filename_processed_pattern = "frame_%0#5d.pbm"
processed_frames_folder = "./frames/"  

filename_frame = ""
repeat = True
while repeat: # iterate
    for frame_count in range(0, 560):
        filename_frame = filename_processed_pattern % frame_count
 
        img=pg.image.load(processed_frames_folder + filename_frame)
        screen.blit(img, (0,0)) # put image 
        pg.display.update()
        pg.display.flip() 
        framerate.tick(FPS)

        for event in pg.event.get():
            if event.type == QUIT:
                repeat = False

        if not repeat:
            break

pg.quit()    
print "done!"

8 Filtre d’allunyament

Un cop tinc tots els frames, aplico a cadascun el filtre “d’allunyament”. La idea és mapejar  el frame rectangular a  un trapezi:

(0,0)--------------------------------------(319,0)
  |                                           |
  |                                           |
  |     (c, e)----------------------(d, e)    |
  |       |                           |       |
  |      |                             |      |
  |     |                               |     |
  |    |                                 |    |
  |   |                                   |   |
  |  |                                     |  |
  | |                                       | |
  ||                                         ||
  |                                           |
(239,0)----------------------------------(319,239)

és dir, vull una funció que transformi els punts del rectangle del frame en punts del trapezi definit per (c,e) (d,e) i els cantons inferiors del frame

  • (0,0) –> (c, e)
  • (319, 0) –> (d, e)
  • (239, 0) –> (239, 0)
  • (319, 239) –> (319, 239)

Després d’algunes proves, trio els valors e = 40, d = 199 i, per simetria, c = 319 – d = 120.

Horitzontalment, la transformació serà un escalat lineal depenent de l’alçada dins del trapezi.

A l’eix vertical la densitat del mapeig ha d’anar creixent a mida que pugem pel trapezi. És a dir, a mida que ens apropem al costat superior del trapezi han d’haver-hi cada cop “més línies”.

Combinant aquestes dues transformacions s’aconsegueix fer les lletres cada cop més petites a mida que “van pujant”.

Donat un punt del frame (x0, y0) caldrà, doncs, determinar a quina posició vertical es desplaça yt i, amb aquesta dada, determinar quin escalat horitzontal li correspon yt.

És dir, una mapeig del punt (x0, y0) al punt (xt, yt)

T:(x0, y0)——> (xt, yt)

Aquesta transformació la resolc amb la següent funció

def transform(x0, y0):
     a = 319.0
     b = 239.0
     d = 199.0
     e = 40.0
     c = a - d

     # lineal
     # y1 = e + (y0 * ((b - e) / b))
     
     # parabolic
     c0 = (b - e) / (b * b)
     c1 = e
     y1 = (c0 * y0 * y0) + c1


     x2 = (((y1 * c) - (b * c)) / (e - b))
     x3 = a - x2
     x1 = x2 + (((x3 - x2) / a) *  x0)

     return (x1, y1)

El mapeig en vertical es fa amb

# lineal
# y1 = e + (y0 * ((b - e) / b))

# parabolic
c0 = (b - e) / (b * b)
c1 = e
y1 = (c0 * y0 * y0) + c1

Al codi està comentada la línia que caldria per a fer un mapeig lineal. És dir, amb “densitat” de línies homogènia.

Si proveu el mapeig vertical lineal veureu que les lletres mantenen l’alçada durant tot el seu recorregut per la pantalla.

El que aplico és el mapeig “parabòlic”, en comptes de lineal.

La següent línia defineix una paràbola amb el vèrtex (0, c1), on c1 és 40.

y1 = (c0 * y0 * y0) + c1

El valor de c0 es determina amb la següent línia

c0 = (b - e) / (b * b)

Amb aquesta definició de c0, quan y0 és b (que té el valors de 239, és dir, última línia) y1 val b, com es pot comprovar fàcilment.

C0 és molt petit (està dividit pel quadrat de 239), de forma que amb valors “petits” de y0 tinc valors petits de y1.

El resultat és que n línies y0 es mapegen a la mateixa línia y1 (n > 1)

Però el creixement parabòlic fa que a mida que creix y0, en el mapeig d’n a 1 la n  cada cop es fa més petita.

De fet, a mida que y0 s’apropa al valor de 239 (la línia inferior) la n passa a ser fraccionària. Caldrà tenir-ho en compte mes tard.

He fet servir una funció “parabòlica” per a augmentar la densitat de línies prop de la línia superior, però és podria provar una altre funció que donés un resultat similar, a veure quin efecte té.

Un cop tinc la y1, aleshores puc calcular l’escalat horitzontal. En aquest cas es tracta d’una escalat lineal.

x2 = (((y1 * c) - (b * c)) / (e - b))
x3 = a - x2
x1 = x2 + (((x3 - x2) / a) *  x0)

A partir de y1 es calcula el punt x2 fent servir l’equació de la recta que passa per (0,239) i (c=120, e=40).

Per simetria horitzontal es calcula x3.

El punt x1 es calcula considerant el mapeig lineal entre (0, 319) i (x2, x3)

9 Optimització i línies en blanc

El mapeig és el mateix per a tots els frames. Aleshores, en comptes de recalcular el mapeig per a cada frame, es pot calcular un cop al començament i mantenir-lo en un array.
Un array, en principi, de 320×240. Però el cas és que el creixement en y1 de la funció de mapeig entre els punts d’un frame (x0,y0) i els punts del trapezi (x1, y1) fa que per a increments d’1 píxel en la variació de y0 el trapezi tingui línies buides a la seva part inferior, o sigui, y1 té “forats”. La solució és fer que els increments en y0 siguin més petits que un píxel, per a que y1 no tingui forats. Fent algunes proves, he vist que amb increments de y0 de 0.5 ja n’hi ha prou per a que la funció de transformació no deixi línies buides.

Al final, doncs, el precàlcul de la transformació es pot fer amb el següent codi:

# create frame transform master
num_steps = 2.0
frame_transform = [["1" for j in xrange(0,int(num_steps))] for i in range(0, w * h_frame)]
for y in xrange(0, h_frame):
    for x in xrange(0, w):
        for inc_y in xrange(0, int(num_steps)):
            frame_transform[x + y * w][inc_y] = transform(x, y + inc_y * (1 / num_steps) )

10 Generació dels frames processats (i afegir el color)

La generació dels frames processats és directa: per a cada frame…

for frame_count in xrange(0, h_img_base - h_frame): 
      filename_frame = filename_pattern % frame_count
      filename_processed_frame = filename_processed_pattern % frame_count

      # read and transform frame 
      with open(frames_folder + filename_frame, "r") as fr:
          # discards three first header lines 
          fr.readline()
          fr.readline()
          fr.readline()

… aplico la transformació,tenint en compte que els increments de y0 seran fraccionaris. Per simplificar, en comptes de generar directament el frame transformat faig servir un array de 320×240 com a pas intermig…

# initialize black frame
frame_bits = ["1" for i in xrange(0, w * h_frame)]

for y in xrange(0, h_frame):
    for x in xrange(0, w):
        bit = fr.read(1)
        if bit == '\n':
            bit = fr.read(1)

        # parabolic. trick for filling gaps
        for inc_y in xrange(0, int(num_steps)):
            (xt, yt) = frame_transform[x + y * w][inc_y]
            if int(xt) < w and int(yt)< h_frame:
                frame_bits[int(xt) + int(yt) * w] = bit

Finalment, escric el frame transformat. Aprofito aquest últim pas per afegir el color ja que durant tot el procés he considerat la imatge només en blanc i negre.

Simplement, genero el frame transformat amb el format PPM

10.1 Format PPM

De la viquipèdia, un exemple de PPM.

P3
# The P3 means colors are in ASCII, then 3 columns and 2 rows,
# then 255 for max color, then RGB triplets
3 2
255
255   0   0     0 255   0     0   0 255
255 255   0   255 255 255     0   0   0

Per tant,

# write transformed frame
# c = 0
rgb = ""
black = " 0 0 0"
yellow = " 255 255 0"  
print "[Processed Frame %0#5d]" % frame_count
with open(processed_frames_folder + filename_processed_frame, "w") as fw:
    fw.write("P3\n")
    fw.write("# CREATOR: Albert Baranguer Codina\n")
    fw.write("%d %d 255\n" % frame_size)
    for bit in frame_bits:
        if bit == "1":
            rgb = black
        else:
            rgb = yellow 
        fw.write(rgb)
        c = c + 1
        if (c == w):
            c = 0
            fw.write('\n')

El resultat de l’execució d’aquest codi és que tindré 560 frames processats a carpeta processed-frames

11 generació del video mp4

Arribats a aquest punt ja podem visualitzar el vídeo fent servir una petita modificació del player1.py que he mostrat abans. Però com que el resultat demanat era un mp4, amb un parell de passos addicionals fent servir convert de imagemagick i ffmpeg obtinc el resultat final.

La idea original era fer servir ffmpeg amb els pbm generats en el pas anterior per a obtenir el vídeo, pero en proves he vist que al ffmpeg no sembla agradar-li aquest format de imatge. O sigui que he transformat els pbm a png amb el següent script: pbm-to-png.sh

#!/bin/bash

for filename in $(ls -b ./processed-frames)
do
    convert ./processed-frames/"$filename" ./png/"$filename".png
done
echo "done!"

I un cop he obtingut els frame en format png a la carpeta png, finalment, he generat l’mp4 amb create-mp4.sh

#!/bin/bash
ffmpeg -i png/frame_%05d.processed.pbm.png \
       -c:v libx264 \
       -pix_fmt yuv420p png/starwars-credits-fx.v1.mp4

I vet aquí el resultat

 

12 Repositori a GitHub

Podeu trobar el codi ue he fet servir al meu repositori de GitHub

https://github.com/abaranguer/sw-rolling-fx

“Revolution OS”, the movie.

És estiu i és moment de relaxar-se.  Avui toca cine: El documental “Revolution OS”.

Vet aquí la ressenya de la pel·lícula que es pot trobar al YouTube:

“Revolution OS is a 2001 documentary which traces the history of GNU, Linux, and the open source and free software movements.

It features several interviews with prominent hackers and entrepreneurs (and hackers-cum-entrepreneurs), including Richard Stallman, Michael Tiemann, Linus Torvalds, Larry Augustin, Eric S. Raymond, Bruce Perens, Frank Hecker and Brian Behlendorf.

The film begins in medias res with an IPO, and then sets the historical stage by showing the beginnings of software development back in the day when software was shared on paper tape for the price of the paper itself.

It then segues to Bill Gates’s Open Letter to Hobbyists in which he asks Computer Hobbyists to not share, but to buy software. (This letter was written by Gates when Microsoft was still based in Arizona and spelled “Micro-Soft”.)

Richard Stallman then explains how and why he left the MIT Lab for Artificial Intelligence in order to devote his life to the development of free software, as well as how he started with the GNU project.

Linus Torvalds is interviewed on his development of the Linux kernel as well as on the GNU/Linux naming controversy and Linux’s further evolution, including its commercialization.

Richard Stallman remarks on some of the ideological aspects of open source vis-á-vis Communism and capitalism and well as on several aspects of the development of GNU/Linux.

Michael Tiemann (interviewed in a desert) tells how he met Stallman and got an early version of Stallman’s GCC and founded Cygnus Solutions.

Larry Augustin tells how he combined the resulting GNU software and a normal PC to create a UNIX-like Workstation which cost one third the price of a workstation by Sun Microsystems even though it was three times as powerful. His narrative includes his early dealings with venture capitalists, the eventual capitalization and commodification of Linux for his own company, VA Linux, and ends with its IPO.

Frank Hecker of Netscape tells how Netscape executives released the source code for Netscape’s browser, one of the signal events which made Open Source a force to be reckoned with by business executives, the mainstream media, and the public at large.

(this text is available under the terms of the GNU Free Documentation License)

I sense més dil·lació, amb tots vosaltres els gurús i hackers que són a l’origen del Linux, del Programari Lliure (el “Free Software”, amb “free as in freedom”) , del sistema GNU i del Free and Open Source Software (FOSS).

Apaguem els llums. “Revolution OS”, the movie:

60 anys de Lisp. Old rockers never die.

El programador no neix. Es fa.

La formació d’un bon programador passa per diverses etapes. En la etapa inicial hom aprèn un llenguatge. Normalment un llenguatge d’iniciació. Un llenguatge d’iniciació serveix, més que res, per comprendre conceptes de programació.  I no és tan important el seu rendiment o la seva aplicació en problemes reals.

Avui, per exemple, es fa servir, a nivell de ESO i secundària, el llenguatge Scratch (un fantàstic i versàtil entorn d’aprenentatge) com a llenguatge d’iniciació.

A nivells més avançats, hi ha més varietat. Sobretot als EUA es fa servir molt -com a llenguatge d’iniciació per a universitaris, repeteixo- el Lisp, en alguna de les seves encarnacions: Scheme, Racket, CLisp

Lisp és proper al llenguatge matemàtic, té una sintaxi mínima i no imposa gaires restriccions en quant a paradigmes de programació, tot plegat el fa molt versàtil per a presentar conceptes informàtics. Alguns dels millors i més influents manuals de programació fan servir el Lisp. Cal llegir al menys una vegada en la vida el llibre porpra: Structure and Interpretation of Computer Programs.

Potser sorprenentment, el Lisp es un llenguatge que es troba amb  facilitat a entorns productius Unix. Guile (Scheme), un altre dialecte de Lisp, és el llenguatge d’extensió oficial de les aplicacions GNU (un llenguatge d’extensió és, per entendre’ns, un llenguatge de macros). També es pot trobar Lisp sent part indestriable i indissoluble de l’Emacs, l’editor de texts més versàtil mai creat. Emacs, en ell mateix, està en molt bona part programat amb Emacs Lisp. La forma d’estendre Emacs és, evidentment, amb l’Emacs Lisp. La presència universal d’Emacs posa el Lisp allà on hi hagi un Emacs instal·lat.

Lisp (inventat per John McCarthy entre 1956 i 1958) és el segon llenguatge informàtic més antic encara en servei (el més antic, encara en servei, és Fortran. La primera especificació de Fortran va ser escrita per IBM a  1954). Aquesta timeline de la wiki us pot ajudar a situar-lo en el temps.

Estem parlant, doncs,  d’un llenguatge informàtic amb 60 anys d’història. Es diu de pressa. En termes informàtics tant de temps equival al pas  de vàries eres geològiques.

Però el millor del cas és que l’evolució del Lisp continua: és relativament senzill programar un interpret de Lisp i això fa que es puguin trobar dialectes per a multitud de plataformes. Concretament, per a la JVM en aquests moment hi ha una versió de Lisp que destaca sobre les altres: Clojure.

Clojure és un dialecte de Lisp que funciona sobre la JVM. Tot i que no imposa el paradigma, presenta una orientació envers la Programació Funcional (FP) [i Clojure FP ]. Val a dir que és possible fer FP, en general, amb dialectes comuns de Lisp.

Com a punt molt fort, es relaciona de forma senzilla amb la JVM, de forma que té accés a la infinitat de llibreries i frameworks de Java i, a l’hora, és senzill des de Java  invocar Clojure, o fer servir des de Java les classes desenvolupades amb Clojure.

Més enllà de la curiositat de portar Lisp a la JVM, sembla que Clojure està fent-se, poc a poc, això sí, amb una part de mercat en l’anàlisi de dades (on a hores d’ara dominen R i Python amb Pandas, sense comptar amb el clàssic SQL, o l’omnipresent Java).

Però, tornant al principi, en la formació d’un programador el primer pas acostuma a ser algun llenguatge d’iniciació que ràpidament es complementa amb l’aprenentatge de llenguatges més utilitzats professionalment i amb llenguatges de paradigmes diferents.

La programació amb diferents paradigmes dona una visió completa al programador. Li obre la ment. L’habilita per enfocar els problemes des de punts de vista diferents. Per això, un bon programador ho és de forma independent als llenguatges que conegui , tot i que, evidentment, el més probable i el més recomanable és que tingui alguns llenguatges preferents  que domini. I també que aquestes preferències vagin canviant amb el pas del temps. El bon programador és poliglot, i sempre té un ull posat en els nous llenguatges i paradigmes que van apareixent.

Dins la caixa d’eines del programador hom pot trobar, doncs,  diferents llenguatges per a diferents propòsits. Alguns llenguatges seran molt demandats professionalment, i altres, no tant, o gens ni mica. Però en l’arsenal mental del programador, aquesta varietat expressiva és riquesa i versatilitat.

Per acabar, l’objectiu del post d’avui era redescobrir Lisp i perquè crec que pot tenir interès dedicar un temps a aquest llenguatge. Com usuari que sóc d’Emacs (Emacs Lisp) i d’eines GNU (Guile i Scheme), Lisp té un caràcter pràctic. Com programador Java i que ha treballat més o menys amb anàlisi de dades, Clojure també em crida l’atenció.

La paraula clau és poliglotisme. Us deixo un enllaç: http://hyperpolyglot.org/. Es tracta d’un lloc web que ofereix taules de comparació entre llenguatges més o menys afins. En concret, us proposo fer un cop d’ull a aquestes taules:

Llenguatges d’Scripting : Node.js, PHP, Python i Ruby. [full 1]i [full 2].

Llenguatges d’anàlisi numèric i estadístic: MATLAB (i Octave), R, NumPy i Julia. [full 1] i [full 2].

Comparació entre dialectes de Lisp: Common Lisp, Racket (Scheme), Clojure, Emacs Lisp .