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 :

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

Cinc problemes de programació

Una de les conseqüències de l’ERO a Indra (on encara treballo) és que a …curt? …mig? termini m’incorporaré al mercat laboral, o el que és el mateix, que hauré de buscar feina. I és bastant probable (i em sembla el més sensat) que la feina que busqui estigui relacionada amb el que sé fer, que és, bàsicament, de programador.

Programador? Alguns diran Analista, o en anglès, Software Engineer, o Software Architect, o títols encara més originals… En essència, però, jo crec que el que és distintiu de la meva feina és que sóc capaç de programar ordinadors i fer-los funcionar junts. Per tant, fem-ho fàcil i digues-me programador. Ras i curt.

El cas és que buscant sobre el que em puc esperar a les entrevistes de feina vaig trobar el següent article: “Five programming problems every Software Engineer should be able to solve in less than 1 hour“. Sí,ho heu entès: cinc problemes de programació que tot enginyer de software hauria de ser capaç de resoldre en menys d’una hora. Em va semblar força interessant.

L’autor d’aquest article diu que quan publica una oferta demanant programadors es troba amb candidats que no saben què vol dir “programar”. Aleshores proposa el que, al seu entendre, són cinc problemes bàsics que tot programador “de veritat” hauria de ser capaç de resoldre en menys d’una hora.

Cinc problemes en una hora. Cal fer algunes consideracions. Què ha de fer un programador per superar un repte d’aquest estil? primer de tot, cal comprendre (analitzar) el problema i les seves implicacions, i dissenyar una solució. Encara que sigui en forma de notes mentals. Hi ha alguna forma de validar el disseny de la solució trobada? Un cop analitzat i dissenyat el problema, cal pensar en la implementació de la solució. Probablement serà més eficient un llenguatge específic del domini del problema que un llenguatge de propòsit general. Si es pot triar, en general és més ràpid desenvolupar una resposta amb un intèrpret que amb un compilador (ni que només sigui perquè s’estalvia el temps de compilat); per descomptat, és més eficient disposar d’un bon entorn de desenvolupament, que proporcioni coses com compleció del codi, acoloriment de sintaxi, snippets de codi, generació automàtica de codi, depurador… que fer servir un editor de texts pelat, per molt que per Internet es trobin acudits tan graciosos com aquell que diu que el millor IDE és vi + gcc.

Per descomptat, més enllà de si interpretat o compilat, és clau per a desenvolupar de forma eficient, el conèixer a fons el llenguatge triat per al desenvolupament. Finalment, l’experiència és un grau. És més probable que algú que ha fet moltes hores de programació s’hagi trobat amb problemes similars en algun moment de la seva trajectòria i que els hagi solucionat. En resum: per a millorar l’eficiència cal experiència i coneixement en el llenguatge i les eines a utilitzar.

A més de tot l’anterior, un programador de veritat sap que l’objecte del seu treball, el codi, ha de tenir unes determinades característiques, com per exemple la legibilitat i l’organització. per no parlar de la gestió de recursos, erros i la generació i gestió de casos de proves.

Per si fos poc, el codi, com producte, s’ha d’administrar i segueix uns fluxos dins de les organitzacions. Al menys com usuari, un programador hauria d’estar al cas dels sistemes de Control de Versions, o dels sistemes d’Integració Continua.

Tot això son coneixements tècnics que ha de tenir el programador. Però no només. El programador hauria de tenir unes competències generals que inclourien la capacitat d’auto-organització (tècniques com GTD), l’autonomia, l’auto-didactisme, la bona capacitat de comunicació, oral i escrita (afegiria també audiovisual), la capacitat de treball en equip, i també capacitat didàctica i de lideratge. I segur que em deixo coses.

Bé. De totes aquestes característiques no no en parla l’autor de l’article. Jo trobo que a l’hora de contractar un programador caldria tenir-les en compte. Però el fet és aquest: el que de debò és imprescindible per a un programador és que sàpiga programar.

Tornant al prinicipi: Quins són aquests cinc problemes que tot programador hauria de poder resoldre en menys d’una hora?

Problem 1
Write three functions that compute the sum of the numbers in a given list using

  • a for-loop
  • a while-loop
  • recursion

Problem 2
Write a function that combines two lists by alternatingly taking elements. For example: given the two lists [a, b, c] and [1, 2, 3], the function should return [a, 1, b, 2, c, 3].

Problem 3
Write a function that computes the list of the first 100 Fibonacci numbers. By definition, the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two. As an example, here are the first 10 Fibonnaci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, and 34.

Problem 4
Write a function that given a list of non negative integers, arranges them such that they form the largest
possible number. For example, given [50, 2, 1, 9], the largest formed number is 95021.

Problem 5
Write a program that outputs all possibilities to put + or – or nothing between the numbers 1, 2, …, 9 (in this order) such that the result is always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.

Déu n’hi do! Els problemes 1,2 i 3 són senzills. Ara bé, el 4 i el 5 poden fer-te rumiar una bona estona.

En una actualització de post, el mateix autor de l’article reconeixia que els problemes 4 i 5 havien generat una important controvèrsia.

Bé, jo també trobo que en una hora els cinc problemes és, més aviat, justet.

En el meu cas, em vaig decidir a fer els problemes. Ara bé, no pretenia resoldre’ls en una hora. De fet, el que pretenia és que em servissin per practicar un llenguatge que em fa molta gràcia i que he “descobert”, per dir-ho d’alguna manera, fa poc: amb l’Elisp de l’Emacs.

Sí, he fet servir lisp per resoldre els problemes, què passa? xD (de fet, el problema 5 l’he fet primer amb Python, però ja en parlaré després)

Allà van les meves solucions:

Solució al problema 1 (amb for-loop –> dotimes)

;; The 5 problems
;;
;; Problem 1
;; Write three functions that compute the sum of the numbers in a given list using 
;;  - a for-loop
;;  - a while-loop
;;  - recursion
;;
;; 1.1 - for-loop (dotimes)
(progn 
  (setq nums (list 1 2 3 4 5 6 7 8 9 10))
  (setq N (length nums))
  (setq suma 0)

  (dotimes (i N) 
    (setq suma (+ suma (elt nums i)))
  )

  (insert (format "\nFor loop (with dotimes) sum: %d" suma))
)
For loop (with dotimes) sum: 55

Solució al problema 1 (amb while-loop)

;; 1.2 - while
(progn 
  (setq nums (list 1 2 3 4 5 6 7 8 9 10))
  (setq N (length nums))
  (setq suma 0)
  (setq i 0)
  (while (< i N) 
    (setq suma (+ suma (elt nums i)))
    (setq i (1+ i))
  )

  (insert (format "\nWhile loop sum: %d" suma))
)
While loop sum: 55

Solució al problema 1 (recursiva)

;; 1.3 - recursion
(defun recursiveSum(numsList)
  (setq N (length numsList))
  
  (if (> N 0)
    (+ (car numsList) (recursiveSum (cdr numsList)))  ;; if part
    0                                                 ;; else part
  )
)

(progn 
  (setq nums (list 1 2 3 4 5 6 7 8 9 10))
  (setq suma 0)

  (setq suma (+ (car nums) (recursiveSum (cdr nums)))) 
  
  (insert (format "\nRecursive sum: %d" suma))
)
Recursive sum: 55

Fàcils, no? Anem pel problema 2:

;; Problem 2
;; Write a function that combines two lists by alternatingly taking elements. 
;; For example: given the two lists [a, b, c] and [1, 2, 3], 
;; the function should return [a, 1, b, 2, c, 3].
;;
(defun merger (listData indexListData listUnion) 
  (push (nth indexListData listData) listUnion)
  listUnion   ;; not strictly necessary
)

(progn 
  ;; test data
  (setq list1 (list "a" "b" "c"))
  (setq list2 (list 1 2 3 4 5 6))
  (setq listUnion (list))

  ;; get length of lists
  (setq lengthList1 (length list1))
  (setq lengthList2 (length list2))
  
  ;; length of union list
  (setq lengthUnion (+ lengthList1 lengthList2))

  (setq indexList1 0)
  (setq indexList2 0)

  (dotimes (i lengthUnion)
    ;; list 1
    (if (< indexList1 lengthList1)
      (setq listUnion (merger list1 indexList1 listUnion)) 
    )
    (setq indexList1 (1+ indexList1))
    
    ;; list 2
    (if (< indexList2 lengthList2)
      (setq listUnion (merger list2 indexList2 listUnion)) 
    )
    (setq indexList2 (1+ indexList2))
  )
 
  ;; reverse
  (setq listReversed (reverse listUnion))

  ;; show results
  (print "List merger")
  (print listReversed)
)

Una mica embolicat, no? No és el millor codi que he escrit, la veritat. El codi s’hauria simplificat si en comptes de fer servir list hagués fet servir vectors.

La funció merger no fa mes que posar al principi de la llista unificada l’element enèsim de la llista passada com argument. Com que els elements de les dues llistes es van posar alternativament al començament (push) de la llista unificada, per això cal fer un reverse de la llista unificada al final.

Bé, amb Python o amb Basic m’hauria sortit millor. Seguim.

Solució del problema 3

;; Problem 3
;; Write a function that computes the list of the first 50 Fibonacci numbers. 
;; By definition, the first two numbers in the Fibonacci sequence are 0 and 1, 
;; and each subsequent number is the sum of the previous two. 
;; As an example, here are the first 10 Fibonnaci numbers: 
;; 0, 1, 1, 2, 3, 5, 8, 13, 21, and 34.
;; 
(progn 
  (setq n0 0.0)
  (setq n1 1.0)
  (insert "\n - 50 first Fibonacci numbers -\n")
  (insert "0\n1\n")
  (dotimes (i 50)
    (setq n (+ n1 n0))
    (insert (format "%d\n" n))
    (setq n0 n1)
    (setq n1 n)
  )
)
 - 50 first Fibonacci numbers -
0
1
1
2
3
5
8
13
21
34
...
701408733
1134903170
1836311903
2971215073
4807526976
7778742049
12586269025
20365011074

Un clàssic. La successió de Fibonacci. Aquest problema també és molt senzill.

Solució (errònia) al problema 4

;; Problem 4
;; Write a function that given a list of non negative integers, arranges them such that they form the largest possible number. 
;; For example, given [50, 2, 1, 9], the largest formed number is 95021.
;; 
(defun greater (lower upper)
  (and (not (string< lower upper)) (not (string= lower upper)))
)

(defun swap (row i)
   (setq aux (aref row i))
   (aset row i (aref row (1+ i)))
   (aset row (1+ i) aux)
)

(defun bubble-sort (strNums)
  (setq N (length strNums))
 
   ;; sort array of strings 
  (dotimes (j (- N 1))
    (dotimes (i (- N 1)) 
      (setq lower (aref strNums i))
      (setq upper (aref strNums (1+ i)))
   
      (if (greater lower upper)
        (swap strNums i)
      )
      ;;(show-row strNums)
    )
  )
)

(defun show-row (strNums)
  (setq N (length strNums))
  (dotimes (i N)
    (insert (format "%s " (aref strNums i )))
  )
  (insert "\n") 
)

(defun reverseVector (row)
  (setq N (length row))
  (dotimes (j (/ N 2))
    (setq val1 (elt row j))
    (setq val2 (elt row (- (- N 1) j)))
      
    (aset row (- (- N 1) j) val1)
    (aset row j val2)
  ) 
)

(defun concatVector (row)
  (setq N (length row))
  (setq retvalue "")
  (dotimes (i N)
    (setq retvalue (concat retvalue (elt row i)))
  )
  retvalue  ;; not strictly necessary 
)

(progn
  ;; data: list of non negative integers
  (setq nums (list 9 8 7 6 5 4 3 2 1 0))
 
  ;; convert to array of strings
  (setq N (length nums))
  (setq strNums (make-vector N nil))
  (dotimes (i N) 
    (aset strNums i (number-to-string (elt nums i)))
  )

  (insert "\nGreatest integer\n")
  (insert "\nunsorted array:\n")  
  (show-row strNums)

  (insert "\nsorted array:\n") 
  (bubble-sort strNums)
  (show-row strNums)

  (insert "\nreversed sorted array:\n") 
  (reverseVector strNums)
  (show-row strNums)
 
  ;; string to number
  (setq greatestNumber (string-to-number (concatVector strNums)))
  (insert (format "Greatest integer: %d\n" greatestNumber)) 
)
Greatest integer

unsorted array:
9 8 7 6 5 4 3 2 1 0 

sorted array:
0 1 2 3 4 5 6 7 8 9 

reversed sorted array:
9 8 7 6 5 4 3 2 1 0 
Greatest integer: 9876543210

Doncs bé, resulta que la solució no és correcta! He suposat que n’hi havia prou amb ordenar (funció bubble-sort, com no!) alfabèticament els números, però resulta que aquesta suposició és falsa, com indiquen en aquest altre post:

“A lot of folks have rightly pointed out that this problem can be solved using a lexical comparison of strings. However, that’s not all you need.

Consider the following example: [5, 50, 56]. A lexical comparison returns 56, 50, and 5, but that doesn’t make the larger number (56, 5, 50 does)”

O sigui que: meeec! cal rumiar un altre cop la solució del problema 4. Queda pendent la solució per a un futur post.

UPDATE: Solució Brute Force:

Ahir no estava d’humor per a posar-me a investigar un algorisme pera solucionar el problema 4… i avui tampoc! L’opció és fer força bruta, que,de fet, als ordinadors se’ls dona molt bé.

Amb força bruta i generadors de Python (itertools) la cosa queda tan simple com això:

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

import itertools as itt

print "\nBiggest number\n"

nums = ['500', '5', '51', '52', '504', '506', '54', '56', '514', '515', '516', '575']

max_str = ''
num_iters = 0

for perm in itt.permutations(nums, len(nums)):
    num_iters = num_iters + 1
    num = ''.join(perm)
    if  num > max_str:
        max_str = num

print "max: %s; iters: %d\n" % (max_str, num_iters)        

'''
>>> import biggest

Biggest number

max: 575565545251651551514506504500; iters: 479001600
''' 

Aquesta solució és qualsevol cosa menys elegant, però és molt ràpida de programar i soluciona el problema en un temps finit. Cal dir que he tirat, de nou, de la màgia de Pyhton que m’ha permès resoldre amb el simple import de les itertools la generació de les permutacions dels números. Després la concatenació amb el join i actualitzar el màxim a mida que es va trobant.

Queda pendent, per a quan tingui temps i ganes d’investigar-ho, el trobar un algorisme més intel·ligent que la solució per força bruta. Això sí, en tot cas, la força bruta sempre és una opció a considerar (i els bons programadors ho saben).

Finalment, la solució al problema 5

Primer la solució amb Python. I ara veureu perquè Python és el Llenguatge dels Déus:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
'''
Problem 5
Write a program that outputs all possibilities to put + or - or nothing 
between the numbers 1, 2, ..., 9 (in this order) 
such that the result is always 100. 
For example: 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100.
'''
def get_base3_indexes(num):
    ix = [0,0,0,0,0,0,0,0]
    done = False
    i = 0
    while not done:
        quot, mod = num / 3, num % 3

        if quot >= 3:
            num = quot
            ix[i] = mod
        else:
            done = True
            ix[i] = mod
            ix[i + 1] = quot

        i = i + 1

    ix.reverse()
    return ix

if __name__ == "__main__":
    symbols = ["+","-"," "]
    formula = "1%c2%c3%c4%c5%c6%c7%c8%c9"
    ix = [0,0,0,0,0,0,0,0]
     
    # és a dir: Variacions amb Repetició de 3 elements agafats de 8 en 8
    # RV n m = n ** m
 
    top =  3**8
    
    for i in range(0, top - 1):
        ix = get_base3_indexes(i)
        
        calc = formula % (symbols[ix[0]],
                          symbols[ix[1]],
                          symbols[ix[2]],
                          symbols[ix[3]],
                          symbols[ix[4]],
                          symbols[ix[5]],
                          symbols[ix[6]],
                          symbols[ix[7]])

        calc2 = [c for c in calc if c != " "]
        calc2_compact = "".join(calc2)
        result = eval(calc2_compact)
        if result == 100:
            print "%s = %d" % (calc2_compact, result)
            
    print "%d lines analyzed" % top
    print "done!"

O sigui, calcula les “variacions amb repetició de tres elements agafats de 8 en 8″ Els tres elements són les tres “operacions” possibles entre dígits: sumar (“1” + “2” = 3), restar (“1” – “2” = -1) i concatenar (“1” concat “2” = “12”) i els agafo de 8 en 8 perquè són 8 posicions per a operadors entre els 9 operands numèrics. la iteració per tots els casos possibles i la conversió a base 3 de l’index actual permet posar els operadors adequats on els toca en cada iteració.

Però la màgia de Python ve en aquestes tres línies:

        calc2 = [c for c in calc if c != " "]
        calc2_compact = "".join(calc2)
        result = eval(calc2_compact)

La primera línia fa una llista d’elements (calc2) a partir de la llista original (calc) on els operadors “concat” apareixen com blancs entre els números. Agafa cada element c de calc excepte els elements iguals a ” “. És dir, “compacta” la llista calc eliminant-li els blancs. Es tracta d’un bonic exemple de Python Comprehensions.

La següent línea genera un string a partir de la llista compactada.

la tercera línia avalua la suma.

La dada és que fa tot això en tres línies. Eficiència i productivitat en un llenguatge és exactament això.

I ara l’equivalent amb elisp:

;; Problem 5
;; Write a program that outputs all possibilities to put + or - or nothing 
;; between the numbers 1, 2, ..., 9 (in this order) 
;; such that the result is always 100. 
;; For example: 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100.
;; 
;; variations with repetition of 3 elements (the +,- and "concat" operators) 
;; taken 8 (8 operands within the 1,2,3,4,5,6,7,8 and 9 operands) at a time
;;
;; VR n r = n ** r
;;  
(defun main ()
  ;; return vector with coeficients of the conversion of num to base 3.
  (defun get_base3 (num)
    (let
      ( 
        (base3 (make-vector 8 0))
        (n 8)
        (done nil)
        (i 0)
        (quot 0)
        (mod 0)
      )
      
      (while (not done)
        (setq quot (/ num 3))
        (setq mod (% num 3))

        (if (>= quot 3)
          (progn
            (setq num quot)
            (aset base3 i mod)
        
          )
          (progn
            (setq done t)
            (aset base3 i mod)
            (aset base3 (1+ i) quot)
          ) 
        )
        (setq i (1+ i))
      )

      ;; return
      base3
    )
  )

  ;; clean white spaces
  (defun clean_white_spc (str)
    (let
      ( 
        (c "")
        (j 0)
        (str_out "")
        (len (length str))
      )
      (dotimes (j len)
        (setq c (substring str j (+ j 1)))
        (if (not (string= c " "))
          (setq str_out (concat str_out c))
        )
      )

      ;; return
      str_out
    )
  )

  ;; formula parser
  (defun perform_calculation (formula)
    (let 
      (
        (n (length formula))
        (stackoperands (make-vector 9 0))
        (stackoperators (make-vector 8 "+"))
        (i 0)
        (j 0)
        (k 0)
        (accum 0)
      )
 
      ;; lexical parser
      (dotimes (i n)
        (setq c (substring formula i (1+ i)))
        (if (and (not (string= c "+")) (not (string= c "-")))
          (progn ;; true. c is a number
            (setq accum (+ (* accum 10) (string-to-number c)))
          ) 
          (progn ;; false. c is an operator  
            (aset stackoperands j accum)
            (aset stackoperators k c)
            (setq k (1+ k))
            (setq j (1+ j))
            (setq accum 0)
          )
        )
        (if (> accum  0)
          (aset stackoperands j accum)
        )
      )

      ;; performs the sum
      (setq i 0)
      (setq j 0)
      (setq operator "")
      (setq operand 0)
      (setq accum 0)

      (dotimes (i (length stackoperands))
        (setq operand (aref stackoperands i))
        (if (= i 0)
          (progn ;; i = 0
            (setq accum operand) 
          )
          (progn ;; i > 0
            (setq j (1- i))
            (setq operator (aref stackoperators j))
            (if (string= operator "+")
              (setq accum (+ accum operand))
              (setq accum (- accum operand))
            )
          )
        )
      )

      ;; return
      accum
    )
  )

  ;; main
  (let
    (
      (symbols ["+" "-" " "])
      (formula "1%s2%s3%s4%s5%s6%s7%s8%s9")
      (ix (make-vector 8 0)) 
      (top (- (expt 3 8) 1))
      (i 0)
      (count 0)
    )
  
    (insert "\nSum 100\n")
 
    (dotimes(i top) 
      (setq ix (get_base3 i))
      (setq calc (format formula (aref symbols (aref ix 0))
                                 (aref symbols (aref ix 1))
                                 (aref symbols (aref ix 2))
                                 (aref symbols (aref ix 3))
                                 (aref symbols (aref ix 4))
                                 (aref symbols (aref ix 5))
                                 (aref symbols (aref ix 6))
                                 (aref symbols (aref ix 7))  
                 )
      )
     
      (setq calc2 (clean_white_spc calc))
      (setq sum (perform_calculation calc2))

      (if (= sum 100)
        (progn 
          (setq count (1+ count))
          (insert (format "%d: %s = %d\n" count calc2 sum))
        )
      )
    )
    (insert (format "\n%d lines analyzed\ndone!"  top))
  )
)

És equivalent a la solució amb Pyhton, només que ha calgut fer funcions per a fer la compactació i eliminació dels espais en blanc, i també per avaluar la fórmula amb un senzill parser.

……

Una hora diu. En fi.

Una aplicació de qüestionaris amb Python, GTK (Glade) i SQLite (Star Wars Quizz!)

Motivació

Sempre pot ser útil una aplicació per a fer qüestionaris, o tests. Avui presento el que podria ser l’esquema inicial, la maqueta, d’una aplicació de qüestionaris.

En realitat, la cosa és més divertida: No cal que us recordi que avui, divendres 18 de desembre de 2015, és l’estrena mundial de “Star Wars: The Force Awakens”. Aquesta és una data esperada per molts fans i, en particular, pel meu fill. Fa uns dies el meu fill va preparar un qüestionari, amb Scratch 1.4, sobre l’univers Star Wars. El qüestionari amb Scratch li va quedar força bé i, inesperadament per ell, jo vaig obtenir la màxima puntuació en fer-lo. Va ser el moment per tenir una conversa, de pare a fill, sobre com es poden fer aquests programes de preguntes i respostes. El resultat és que jo li vaig preparar a ell un qüestionari sobre Star Wars, en mode text, amb Pyhton.

A partir d’aquí vaig pensar en sofisticar-ho una mica, desant les preguntes a una base de dades i fent servir una GUI, en comptes del mode text. El resultat és aquesta maqueta d’aplicació de qüestionaris, que originalment era un qüestionari sobre Star Wars i que, per això, és diu Star Wars Quizz! Quines coses, oi? fet aquest aclariment, només ens resta començar i… que la Força ens acompanyi!

 

Programari utilitzat

He triat per a desenvolupar l’aplicació el llenguatge Python, amb Emacs fent de IDE. He fet servir el constructor d’interfícies gràfiques Glade per a fer el disseny de les finestres de l’aplicació. La combinació de Python i Glade (GTK) és, a la pràctica, un entorn ràpid de desenvolupament.

La base de dades de l’aplicació és SQLite3.

El sistema operatiu és Lubuntu 15.10

 

Descripció funcional

Finestra principal i menú de l’aplicació

L’aplicació és molt senzilla: Es presenta com una finestra amb una barra de menús que conté  dos menús desplegables: “Arxiu” i “Ajuda”.

A “Arxiu” hi ha l’entrada “Nou”, que posa en marxa el qüestionari; i l’entrada “Surt”, que tanca l’aplicació.

A “Ajuda” hi ha l’entrada “Quant a” que presenta una finestra amb el logo de l’aplicació, crèdits i llicència.

 

Diàleg de nom i curs

Quan es fa click a “Nou” s’obre una finestra de diàleg en la que se’ns demana el nom de l’usuari i quin curs fa. Hi han dos botons, “Acceptar” i “Tancar”.

Amb “Acceptar” es prenen les dades introduïdes als camps de text, es tanca la finestra que demana el nom i el curs i es mostra el diàleg amb la primera pregunta.

Amb “Tancar” es tanca el diàleg de nom i curs i es descarta la informació que s’hagués introduït.

 

Diàleg de preguntes

La finestra de diàleg que mostra les preguntes s’encapçala amb el nom de l’usuari i el curs que fa. S’indica quin és el número de pregunta que s’està fent.  En cursiva es mostra la pregunta i, a continuació, quatre possibles respostes. L’usuari marca la resposta, o respostes, correctes activant els checkboxes corresponents.

Fent click en “Següent”, es carrega la següent pregunta si n’hi ha. Si s’ha completat el qüestionari es tanca el diàleg de preguntes i s’obre el diàleg que mostra els resultats del qüestionari.

Fent click a “Tancar” es tanca el diàleg de preguntes i respostes, i es descarta nom, curs i el resultat que s’hagués obtingut fins el moment.

 

Diàleg de resultats

Finalment, la pantalla que mostra els resultats indica el nom i curs de l’usuari i mostra quantes preguntes s’han encertat del total.

La pantalla de resultats té un botó de “Tancar” amb el que  es tanca el diàleg de resultat, es descarta nom, curs i el resultat que s’hagués obtingut fins el moment.

Taules

El primer pas ha estat desenvolupar les taules que suporten la funcionalitat  descrita. Són les taules següents:

CREATE TABLE "topics_questions" (
    "id" INTEGER PRIMARY KEY AUTOINCREMENT NOT NULL,
    "id_topic" INTEGER NOT NULL
);

CREATE TABLE "topics" (
    "id" INTEGER PRIMARY KEY AUTOINCREMENT NOT NULL
);

CREATE TABLE "questions_answers" (
    "id" INTEGER PRIMARY KEY AUTOINCREMENT NOT NULL,
    "id_question" INTEGER NOT NULL,
    "id_answer" INTEGER NOT NULL
);

CREATE TABLE "questions" (
    "id" INTEGER PRIMARY KEY AUTOINCREMENT NOT NULL,
    "question" TEXT
);

CREATE TABLE "question_right_answer" (
    "id" INTEGER PRIMARY KEY AUTOINCREMENT NOT NULL,
    "id_question" INTEGER NOT NULL,
    "id_right_answer" INTEGER NOT NULL
);

CREATE TABLE "answers" (
    "id" INTEGER PRIMARY KEY AUTOINCREMENT NOT NULL,
    "answer" TEXT
);

No faig servir totes les taules. Algunes estan pensant en futures ampliacions de funcionalitat. Les taules importants són QUESTIONS, que manté les preguntes; ANSWERS, les respostes; QUESTIONS_ANSWERS, taula de relació m-n entre preguntes i respostes; QUESTION_RIGHT_ANSWER, taula m-n entre preguntes i respostes correctes.

Ara mateix només hi ha preguntes sobre Star Wars i llavors es pot simplificar encara més: no he fet servir TOPICS, taula que manté els temes dels qüestionaris; ni TOPICS_QUESTIONS, m-n que relaciona temes i preguntes. Però les taules hi són.

db_loader

Val a dir que la versió original del programa feia servir un questionari mantingut en un parell de llistes de Python. Aleshores, el que he fet és partir d’aquestes llistes per a fer la càrrega inicial de les taules. L’script de càrrega de les taules de l’SQLite ha estat el següent:

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

import sqlite3

questions = (
    u"Com es diu el wookie que acompanya a Han Solo?",
    u"De quina especie són els ossets peluts de la lluna santuari d'Endor?",
    u"A quina batalla va ser destruida la primera Estrella de la Mort?",
    u"Quantes temporades té la serie de The Clone Wars?",
    u"Com es diu la padawan d'Anakin Skywalker?",
    u"Quin és el nom Sith del Comte Dooku?",
    u"De quin planeta és Luke Skywalker?",
    u"A quin planeta és el duel entre Anakin Skywalker i Obi-Wan Kenobi?",
    u"De quin color és l'espasa laser de Mace Windu?",
    u"De quin color és l'espasa laser dels lords Sith?"
)

answers = (
    (2, "Peret", "Chewbacca", "Sr. Spock", "Leia Organa"),
    (1, "Ewoks", "Wookies", "Mandalorians", "Corellians"),
    (4, "Waterloo", "Normandia", "Toth", "Yavin-4"),
    (3, "1000", "5", "6", "7"),
    (3, "Artiom", "Assaj Ventress", "Ahsoka Tano", "Kanan Jarrus"),
    (4, "Darth Sidious", "Darth Turo", "Darth Tenebre", "Darth Tyranus"),
    (2, "Naboo", "Tatooine", "Mandalore", "Alderaan"),
    (1, "Mustafar", "Kamino", "Vulcano", "Warsoom"),
    (4, "Blau", "Verd", "Vermell", "Violeta"),
    (2, "Blanc", "Vermell", "Blau", "Violeta")
)

CONNECTION_STRING = "/home/albert/workspace/python/quizz/db/quizz.db"
INSERT_QUESTION = "insert into questions(question) values (?)"
INSERT_ANSWER = "insert into answers(answer) values (?)"
INSERT_QUESTION_ANSWER = "insert into questions_answers(id_question, id_answer) values (?, ?)"
INSERT_RIGHT_ANSWER = "insert into question_right_answer(id_question, id_right_answer) values (?,?)"

if __name__ == '__main__':
    print "begin"
    conn = sqlite3.connect(CONNECTION_STRING)

    cur = conn.cursor()
    num_question = 0
    
    for question in questions:
        cur.execute(INSERT_QUESTION, (question,))
        id_question = cur.lastrowid

        right_answer = answers[num_question][0]

        for num_answer in range(1,5):
            cur.execute(INSERT_ANSWER, (answers[num_question][num_answer],))
            id_answer = cur.lastrowid

            cur.execute(INSERT_QUESTION_ANSWER, (id_question, id_answer))
            if num_answer == right_answer:
                cur.execute(INSERT_RIGHT_ANSWER, (id_question, id_answer))

        num_question = num_question + 1
        
    conn.commit()
    conn.close()

    print "done!"

El que és interessant de l’script anterior és la llista answers. Es tracta d’una “llista de llistes” (un array multidimensional, en definitiva). En aquesta llista de llistes l’element answers[numPregunta][0] ens diu quin és l’índex de la resposta correcta de la pregunta numPregunta. No he fet una traducció directa de l’estructura de les llistes questions i answers a taules si no que he plantejat unes entitats totalment normalitzades. En la pràctica és el dona més flexibilitat per evolucionar l’aplicació.

Arquitectura de l’aplicació

L’aplicació és molt senzilla i s’hauria pogut resoldre amb un únic mòdul. Però crec que és una bona idea mantenir els bons costums sempre i, per això, he tractat de seguir algunes “bones pràctiques” pel que fa a arquitectura. Essencialment, he procurat seguir el patró MVC i he separat la funcionalitat en quatre mòduls.

quizz.py

Aquest mòdul no fa res més que instanciar el controlador i iniciar l’aplicació.

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

from controller import Controller

if __name__ == "__main__":
    controller = Controller()
    controller.initApp()

controller.py

El controlador s’implementa amb la classe Controller, molt senzilla, que veu tant la classe GUI com la classe Loader. Realment aquest controlador fa poc més que de pont entre la GUI i les dades carregades amb el Loader. Això és perquè el pas de pantalles està codificat directament als mètodes dels events de la GUI. Seria una bona idea, des del punt de vista d’arquitectura, portar aquesta navegació entre pantalles al controlador.

El codi és el següent:

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

from gui import GUI
from db import Loader


class Controller():
    gui = None
    db = None
    
    def __init__(self):
        self.db = Loader()
        self.gui = GUI()
        self.gui.setController(self)

    def initApp(self):
        self.db.loadData()
        self.gui.initApp()

    def getQuestion(self, numQuestion):
        return self.db.getQuestion(numQuestion)

    def getNumQuestions(self):
        return self.db.getNumQuestions()

dp.py

Al mòdul db.py implemento la classe Loader. Aquesta classe fa el procés invers de l’script db_loader.py: construeix les llistes questions i answers a partir de les taules de l’aplicació. A més, també afegeix uns mètodes per obtenir el nombre total de preguntes carregades, i per obtenir una pregunta, les seves respostes i la resposta correcta.

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

import sqlite3

class Loader:
    CONNECTION_STRING = "/home/albert/workspace/python/quizz2/db/quizz.db"
    SELECT_QUESTIONS = "select id, question from questions"
    SELECT_ANSWERS = "select a.id, a.answer " + \
                     " from answers a, questions_answers qa " + \
                     " where qa.id_question = ? " + \
                     " and qa.id_answer = a.id"
    SELECT_RIGHT_ANSWER = "select id_right_answer " + \
                          " from question_right_answer " + \
                          " where id_question = ? "

    questions = []
    answer = []
    answers = []
    numQuestions = 0
    
    def loadData(self):
        conn = sqlite3.connect(self.CONNECTION_STRING)
        cur_questions = conn.cursor()
        cur_answers = conn.cursor()
        cur_right_answer = conn.cursor()
    
        cur_questions.execute(self.SELECT_QUESTIONS)
        self.numQuestions = 0
        for row_question in cur_questions:
            # load question
            self.questions.append(row_question[1])
            # load right answer
            cur_right_answer.execute(self.SELECT_RIGHT_ANSWER, (row_question[0],))
            id_right_answer = cur_right_answer.fetchone()[0]
            self.answer = []
            self.answer.append(id_right_answer)
            # load answers for this question
            cur_answers.execute(self.SELECT_ANSWERS, (row_question[0],))
            num_right_answer = 1
            for r_answer in cur_answers:
                self.answer.append(r_answer[1])
                if id_right_answer == r_answer[0]:
                    self.answer[0] = num_right_answer
                num_right_answer = num_right_answer + 1
            self.answers.append(self.answer)
            self.numQuestions = self.numQuestions + 1
        conn.close()
    
    def getQuestion(self, numQuestion):
        return [self.questions[numQuestion-1],
                self.answers[numQuestion-1],
                self.answers[numQuestion-1][0]] 

    def getNumQuestions(self):
        return self.numQuestions
        

Remarcar la utilització de les classes de connexió i de cursor. La paraula Cursor em fa pensar immediatament en els cursors de bases de dades, però a Python la classe Cursors cumpleix més missions que les d’un cursor de base de dades.

GUI.py

Finalment, implemento la classe GUI al mòdul gui.py. Aquesta classe implementa els mètodes de resposta a events de la interfícia gràfica. Tota la interfície gràfica està codificada en un fitxer xml (amb extensió .glade) ies construeix amb Gtk.builder().

L’accés als diferents objectes de la interfícies es fa per nom amb invocacions al mètode get_object(). Amb la referència a l’objecte, es poden fer servir tots els seus mètodes. El procés és molt senzill. Vet aquí el codi:

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

from gi.repository import Gtk

class GUI():
    builder = None
    formMain = None
    formNew =None
    formQuestion = None
    formScoring =None
    formAbout = None
    name = ""
    course = ""
    numQuestion = 1
    numQuestions = 0
    rightAnswer = 0
    rightAnswersCounter = 0
    controller = None
    FORMS = "/home/albert/workspace/python/quizz2/forms.glade"

    def setController(self, controller):
        self.controller = controller

    def initApp(self):
        self.builder = Gtk.Builder()
        self.builder.add_from_file(self.FORMS)
        self.builder.connect_signals(self)
        
        self.formMain = self.builder.get_object("applicationwindow1")
        self.formMain.show()
        Gtk.main()
        
    def onClose(self, *args):
        print "onClose"
        Gtk.main_quit(*args)
        exit()
    
    def onMenuitemNou(self, widget):
        self.formNew = self.builder.get_object("dialog1")
        self.formNew.set_transient_for(self.formMain)
        self.numQuestions = self.controller.getNumQuestions()
        self.builder.get_object("entry3").set_text("")
        self.builder.get_object("entry2").set_text("")        
        self.formNew.show()
        print "onMenuitemNouClick"
        
    def onMenuitemSurt(self, widget):
        print "onMenuitemSurtClick"
        Gtk.main_quit()
        exit()
        
    def onMenuitemAbout(self, widget):
        self.formAbout = self.builder.get_object("aboutdialog1")
        self.formAbout.set_transient_for(self.formMain)
        self.formAbout.run()
        self.formAbout.hide()
            
        print "onMenuitemAbout"
        
    def onButton1AcceptarClick(self, widget):
        self.name = self.builder.get_object("entry3").get_text()
        self.course = self.builder.get_object("entry2").get_text()
        self.formNew.hide()

        self.formQuestion = self.builder.get_object("dialog2")
        self.formQuestion.set_transient_for(self.formMain)
        self.setFormQuestion(self.numQuestion)
        self.formQuestion.show()        
        
        print "Nom: %s; Curs: %s" % (self.name, self.course)
        print "onButton1AcceptarClick"

    def setFormQuestion(self, numQuestion):
        [question, answers, self.rightAnswer] = self.controller.getQuestion(numQuestion)
        self.builder.get_object("label8").set_text("%s de %s curs" % (self.name, self.course))
        self.builder.get_object("label3").set_text("Pregunta %d" % numQuestion)
        self.builder.get_object("label4").set_text(question)
        self.builder.get_object("checkbutton1").set_label(answers[1])
        self.builder.get_object("checkbutton2").set_label(answers[2])
        self.builder.get_object("checkbutton3").set_label(answers[3])
        self.builder.get_object("checkbutton4").set_label(answers[4])
        self.builder.get_object("checkbutton1").set_active(False)
        self.builder.get_object("checkbutton2").set_active(False)
        self.builder.get_object("checkbutton3").set_active(False)
        self.builder.get_object("checkbutton4").set_active(False)

    def onButton2CancelarClick(self, widget):
        self.formNew.hide()
        print "onButton2CancelarClick"

    def onButtonSeguir(self, widget):
        # validate right answer. increment question counter,
        myAnswer = (1 * self.builder.get_object("checkbutton1").get_active()) + \
                   (2 * self.builder.get_object("checkbutton2").get_active()) + \
                   (4 * self.builder.get_object("checkbutton3").get_active()) + \
                   (8 * self.builder.get_object("checkbutton4").get_active())
        rightAnswer = pow(2, self.rightAnswer - 1)

        if myAnswer == rightAnswer:
            self.rightAnswersCounter = self.rightAnswersCounter + 1

        self.numQuestion = self.numQuestion + 1

        if self.numQuestion <= self.numQuestions:
            self.setFormQuestion(self.numQuestion)
            self.formQuestion.show()
        else:
            self.formQuestion.hide()
            self.formScoring = self.builder.get_object("dialog3")
            self.formScoring.set_transient_for(self.formMain)
            self.builder.get_object("labelNom").set_text("%s de %s curs" % (self.name, self.course))
            self.builder.get_object("label6").set_text("%d preguntes" % self.rightAnswersCounter)
            self.builder.get_object("label7").set_text("d'un total de %d preguntes" % self.numQuestions)
            self.formScoring.show()        

        print "onButtonSeguir"
        
    def onCancelarQuizz(self, widget):
        self.reset()
        self.formQuestion.hide()
        print "onCancelarClick"

    def onTancarClick(self, widget):
        self.reset()
        self.formScoring.hide()
        print "onTancarClick"

    def reset(self):
        self.name = ""
        self.course = ""
        self.numQuestion = 1
        self.rightAnswer = 0
        self.rightAnswersCounter = 0

Millores
El programa és una maqueta i es pot ampliar de moltes formes. Se m’acuden les següents millores:
– desar nom, curs i resultat obtingut a la BD.
– incorporar un cronòmetre per qüestionari: temps màxim de resolució del qüestionari.
– incorporar un cronòmetre per pregunta: temps màxim per pregunta.
– possibilitat de navegació endavant i endarrere pel qüestionari (ara només deixa avançar)
– possibilitat de nombre variable de possibles respostes
– possibilitat de vàries (o cap) respostes correctes possibles
– possibilitat de repetir el qüestionari un nombre màxim de cops.

Més millores:
– Afegir pantalles per a poder entrar nous qüestionaris
– perfils d’usuari (administrador, pot crear qüestionaris; usuari, pot resoldre qüestionaris)
– tenir en compte el curs i que l qüestionari s’adapti als nivell de l’usuari
– selecció de qüestionaris per tòpic, o per codi…
– descarregar d’Internet nous qüestionaris i desar-los en local per a execució off-line
– publicació a un servidor dels resultats obtinguts
– …

En fi. Un munt de possibilitats. De fet, si fem servir programari educatiu veurem un munt d’opcions que es podrien implementar a l’aplicació.

Repositori Github
Tot el codi el podeu trobar al github, a https://github.com/abaranguer/quiz

Introducció pràctica a Python per a principiants, amb Jessica McKellar

Al youTube he trobat aquest tutorial sobre Pyhton. Es tracta d’un tutorial, en anglès, orientat als principiants. És de la PyCon 2014 celebrada l’any passat a Montreal. Podeu trobar més vídeos de la conferència de l’any passat al seu canal youTube.

La PyCon és l’organització que aplega la comunitat internacional de desenvolupadors en Python. Enguany la PyCon 2015 es va tornar a celebrar a Montreal, el passat mes d’abril (canal youTube) La conferència EuroPython es celebrarà a Bilbao del 20 al 26 de juliol.

El tutorial està presentat per Jessica McKellar, que tot i la seva joventut ja s’ha fet un nom reconegut dins el món pythonista.

Avui, doncs, un entretingut tutorial de presa de contacte amb el llenguatge Python.

També podeu trobar la conferència homònima de l’any anterior, més curta, impartida a la PyCon US2013 a Santa Clara, Califòrnia.

Python. Progressbar amb tkinter.

Aquest estiu he aprofitat per practicar una mica amb Python. La idea, no gaire original, ho reconec, ha estat desenvolupar una aplicació de biblioteca per gestionar el contingut de les dotzenes i dotzenes de DVDs acumulats durant els anys.

Evidentment que hi ha programari fet que serveix per això mateix -com ja he dit, no he estat gaire original- però l’interès principal era practicar amb Python.

L’aplicació llegeix els continguts d’un DVD, o d’un pendrive o targeta SD, i emmagatzema la informació sobre contingut del media a una base de dades SQLite. Després, es pot consultar, modificar, esborrar la informació. L’aplicació fa servir el mòdul tkinter per a fer la interfície gràfica d’usuari.

Coses que he posat en pràctica? tkinter, per la GUI, el mòdul os per llegir el contingut del media (os.walk), el mòdul sqlite per a tractar amb la BD.

potser en un post posterior presentaré l’aplicació completa. Avui només vull comentar un dels aspectes del desenvolupament.

Un indicador de progrés

Potser és una mica sorprenent, però la part que m’ha portat més feina ha estat aquesta:

La lectura del media és un procés que, potencialment, pot ser llarg. Tinc alguns DVDs amb milers de pàgines html de javadoc. O amb milers de fotografies i vídeos familiars acumulats. La lectura d’aquest DVDs és llarga. Quan passa això: processos pesats que consumeixen temps, la solució professional és oferir a l’usuari alguna mena de feedback indicant-li que hi ha un procés en marxa i que esperi. Una forma habitual de fer-ho és amb finestres popup que mostrin alguna mena d’indicador de progrés.

Dit i fet, he estat buscant com es podia fer això amb Tkinter (una progressbar és un widget de interfície gràfica i això vol dir que la implementació concreta depèn de la llibreria de GUI triada.)

Ha calgut fer algunes proves, però al final he arribat al següent esquema per a fer un popup d’indicació de progrés.

main_thread.py

Em calen dues classes, una que representa el fil principal d’execució, amb la GUI, i que rep el nom de MainThread, que deso al fitxer main_thread.py:

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

from secondary_thread import BackgroundJob
from tkinter import *
import queue

class MainThread():
    root = None
    queue = None
    strVar = None
    value = 0
    popup = None
    
    def onButtonClick(self):
        self.queue = queue.Queue()
        self.popupWindow()
        
        backgroundJob = BackgroundJob(self.queue)
        backgroundJob.start()

    def __init__(self):
        print("Inici")
        print("Aquest és el fil principal")

        self.root = Tk()
        self.root.title("Main window")
        self.root.geometry("320x240")

        label = Label(self.root, text="Prem el botó per executar el fil")
        label.pack(expand = True)

        button = Button(text="Execute", command=self.onButtonClick)
        button.pack()
        # self.root.wait_window()
        self.root.mainloop()
        
    def popupWindow(self):
        self.popup = Toplevel(self.root)
        self.popup.title("Progress window")
        self.popup.geometry("200x50")  
        self.popup.focus()
        self.strVar = StringVar()
        self.strVar.set("Valor inicial")
        label = Label(self.popup, textvariable = self.strVar)
        label.pack(expand=True)
        
        self.root.after(100, self.read_queue)
        
    def setValue(self, newValue):
        self.strVar.set("Valor actual (%d)" % newValue)
    
    def read_queue(self):
        try:
            self.value = self.queue.get_nowait()
            print("read from queue: %d" % (self.value))
            self.setValue(self.value)
        except Queue.Empty:
            pass
  
        if self.value < 1000000:
            self.root.after(100, self.read_queue)
        else:
            print("job done")
            self.popup.destroy()

# main
if __name__ == "__main__":
    app = MainThread()

secondary_thread.py

I una segona classe BackgroundJob que hereta de threading.Thread i que executa el job en background. Al fitxer de nom secondary_thread.py

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

import threading
import queue

class BackgroundJob(threading.Thread):
    queue = None

    def __init__(self, queue):
        threading.Thread.__init__(self)
        self.queue = queue

    def run(self):
        value = 0
        while value < 1000000:
            value = value + 1
            if value % 100000 == 0:
                self.queue.put(value)
                print("value %d" % (value))
             

Remarques al codi
He fet servir Python3. La recomanació per a nou codi és fer servir aquesta versió del llenguatge. la primera línia de tots dos fitxers és la que estableix l’execució amb la versió Python3. En el neu cas, que tinc fins a tres versions de Python a algun ordinador, aquesta discriminació inicial és important.

Com que algun text que apareix fa servir caràcters accentuats, he especificat l’encoding amb la segona línia dels comentaqris.

No he fet servir el widget Progressbar de ttk perquè he preferit presentar primer una solució general. És molt senzill modificar el codi per a fer servir aquest widget, com mostraré després.

El fil principal és el que mou la GUI. Aquest és un requeriment de Tkinter. El job pesat, en el cas de l’exemple, un comptador de 0 fins 1.000.000 ha d’executar-se en el fil secundari.

La classe principal, per tant, és la que obre la finestra principal, amb el botó que llença l’execució del job, per una banda, i obre la finestra popup amb un label que mostra l’evolució del job.

El job pesat s’executa dins de la classe derivada de threading.Thread, al mètode run. El mètode run és el que s’invoca en un fil apart quan des del fil principal es fa backgroundJob.start()

Quan s’instancia la classe BackgroundJob, se li passa una cua (en aquest cas senzill, també s’hauria pogut fer servir una pipe). El fil secundari posa (put) a la cua, cada 100.000 iteracions, el nombre actual d’iteració.

El fil principal, per la seva banda executa cada 100 milisegons (fent servir el mètode after del toplevel widget) el mètode read_queue. Aquest mètode llegeix (get) la cua i actualitza el popup de progressbar.

Quan read_queue del fil principal llegeix a la cua que el procés pesat del fil secundari ha acabat, destrueix el popup.

Es tracta d’un parell de classes nomès però és un exemple molt bonic ja que amaga una considerable riquesa de conceptes: GUI amb tkinter, programació multifil amb threadind.Thread, comunicació entre processos mitjançant cues. Déu n’hi do.

Amb el widget ttk.Progressbar
Finalment, l’adaptació del codi per a fer servir el widget ttk.Progressbar. Hi han un parell d’opcions per a la progressbar: quan se sap exactament en quin estat es troba el procés i es pot expressar numèricament, aleshores es pot fer servir una Progressbar en mode “determinate”, i passar-li un grau de progrés. Aleshores la representació gràfica de la barra de progrés mostra el mateix tant per cent de barra de progrés completat com de procés. Si, en canvi, es desconeix la durada del procés, aleshores es pot fer servir el mode “indeterminate” en que la barra de progrés mostra un indicador oscil·lant.

Tenint en compte l’anterior, l’adaptació per a mostrar una barra de progrés en mode “indeterminate” és directa. Només cal afegir l’import i substituir el widget label pel widget progressbar. És el que he de fer servir a l’aplicació que llegeix els DVD i els pendrive ja que, en principi, no se quin és el volum de contingut de cada DVD i no faig una passada prèvia per a determinar-lo.

Afegeixo l’import del widget progressbar

from secondary_thread import BackgroundJob
from tkinter import *
from tkinter.ttk import Progressbar
import queue

i substitueixo el label. Tan aviat com es mostra el popup amb la progressbar, inicia l’oscil·lació amb pb.start()

    def popupWindow(self):
        self.popup = Toplevel(self.root)
        self.popup.title("Progress window")
        self.popup.geometry("200x50")  
        self.popup.focus()
        self.strVar = StringVar()
        self.strVar.set("Valor inicial")
        #label = Label(self.popup, textvariable = self.strVar)
        #label.pack(expand=True)
        pb = Progressbar(self.popup, mode="indeterminate", orient="horizontal")
        pb.start()    # inicia l'oscil·lació
        pb.pack(expand=True)

Però en el cas del comptador de 0 a 1.000.000 sí que soc capaç de dir en quin punt es troba el procés, per tant, sí que té sentit fer servir el mode “determinate”. El seguent és el codi del fil principal modificat per a fer servir una Progressbar en mode ‘determinate’.

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

from secondary_thread import BackgroundJob
from tkinter import *
from tkinter.ttk import Progressbar
import queue

class MainThread():
    root = None
    queue = None
    counter = None
    value = 0
    popup = None
    
    def onButtonClick(self):
        self.queue = queue.Queue()
        self.popupWindow()
        
        backgroundJob = BackgroundJob(self.queue)
        backgroundJob.start()

    def __init__(self):
        print("Inici")
        print("Aquest és el fil principal")

        self.root = Tk()
        self.root.title("Main window")
        self.root.geometry("320x240")

        label = Label(self.root, text="Prem el botó per executar el fil")
        label.pack(expand = True)

        button = Button(text="Execute", command=self.onButtonClick)
        button.pack()
        # self.root.wait_window()
        self.root.mainloop()
        
    def popupWindow(self):
        self.popup = Toplevel(self.root)
        self.popup.title("Progress window")
        self.popup.geometry("200x50")  
        self.popup.focus()
        self.counter = IntVar()
        self.counter.set(0)
        #label = Label(self.popup, textvariable = self.strVar)
        #label.pack(expand=True)
        pb = Progressbar(self.popup, mode="determinate", orient="horizontal", variable=self.counter, maximum=1000000)
        pb.start()
        pb.pack(expand=True)
        
        self.root.after(100, self.read_queue)
        
    def setValue(self, newValue):
        self.counter.set(newValue)
    
    def read_queue(self):
        try:
            self.value = self.queue.get_nowait()
            print("read from queue: %d" % (self.value))
            self.setValue(self.value)
        except Queue.Empty:
            pass
  
        if self.value < 1000000:
            self.root.after(100, self.read_queue)
        else:
            print("job done")
            self.popup.destroy()

# main
if __name__ == "__main__":
    app = MainThread()

En negreta he ressaltat el més interessant.

Remarcar com en el progressbar he indicat el valor màxim, i com el “progrés” ve donat per la “variable” counter de tipus IntVar.

Per anar acabant: el video amb l’execució del programa:

i l’enllaç al repositori GitHub

https://github.com/abaranguer/progressbar-tkinter

Una variant del problema de Monty Hall (divertiment courserià)

Els cursos de Coursera estan resultant ser una de les coses més divertides que he fet últimament. Estic apuntat al MOOC Financial Engineering and Risk Management II i fa un parell de setmanes un dels exercicis era una adaptació de “El problema de Monty Hall“. Que ningú s’esveri: és un problema de probabilitats que es pot resoldre amb coneixements de batxillerat.

De la Viquipèdia:
“El problema de Monty Hall és un trencaclosques de probabilitat basat en el programa de televisió americà Let’s Make a Deal (“Fem un tracte”). El nom ve del presentador del programa, Monty Hall. El problema també s’anomena la paradoxa de Monty Hall.

hall_lmad

Una explicació coneguda del problema va ser publicada a la revista Parade:

«Suposa que ets al programa “Fem un tracte” i et deixen triar una de tres portes. Darrere una, hi ha un cotxe; darrere de les altres, cabres. Tries una porta, per exemple, la número 1, i Monty Hall que sap què hi ha darrere les portes obre una altra porta, per exemple la 3, que té una cabra. Després et diu: “Vols canviar a la 2?”

Hi surts guanyant si canvies el que havies triat? (Whitaker 1990)»

Com que no hi ha manera de saber quina de les dues portes no obertes és la guanyadora, la majoria de la gent creu que cada porta té les mateixes probabilitats i conclou que canviar de porta no importa. Però aquesta conclusió és incorrecta: de fet si el jugador canvia la probabilitat de guanyar passa d’1/3 a 2/3. Canviar no dóna cap avantatge si el jugador tria inicialment la porta guanyadora, el que té una probabilitat d’1/3. Triar inicialment la porta incorrecta té una probabilitat de 2/3; quan es revela l’altra porta incorrecta, canviar suposa guanyar. Així, la probabilitat de guanyar quan es canvia de porta és de 2/3.

Quan la solució del problema va aparèixer a la revista Parade, aproximadament 10.000 lectors, incloent uns 1.000 amb doctorat, van escriure a la revista dient que la resposta era incorrecta. Molta part de la controvèrsia fou perquè la versió de la revista del problema és tècnicament ambigua ja que hi ha aspectes que el presentador no explica, com que ha d’obrir una porta i ha d’oferir al concursant si vol canviar de porta.”

Doncs bé, al MOOC de Financial Engineering and Risk Managemnent II de Coursera, actualment en curs, han plantejat en un exercici una variació del problema de Monty Hall:

«Suposa que ets al programa “Fem un tracte” i et deixen triar una de quatre portes: dues amaguen cotxes i darrere les altres dues, hi han cabres. Tries una porta, per exemple, la número 1, i Monty Hall que sap què hi ha darrere les portes obre una altra porta, per exemple la 3, que té una cabra. Després et diu: “Vols canviar de porta?”

La probabilitat que el concursant triï una porta amb cotxe el primer cop és 1/2.

Què canvia quan el presentador obre una de les altres tres i mostra una cabra?

La tria del jugador afecta a la porta que obre el presentador. Que el presentador obri una porta no es un esdeveniment totalment aleatori ni inconnex.

Si el concursant tria en la seva primera opció una porta amb cotxe (probabilitat 1/2), aleshores el presentador pot obrir dues de les tres portes que resten tancades. El jugador té probabilitats de guanyar el cotxe si canvia en la segona tria a una de les altres dues portes tancades, que amaguen un cotxe (probabilitat d’aquesta segona tria, doncs, 1/2)

Si el concursant ha triat una porta amb cabra en la seva primera opció (probabilitat 1/2), el presentador només pot obrir una de les altres tres portes, l’única que amagarà una cabra. Les altres dues portes amaguen un cotxe. Si el concursant canvia de porta, guanya segur (probabilitat d’aquesta segona tria igual a 1).

Resumint: si manté la tria original guanya només si la primera porta amagava un cotxe (amb probabilitat de 1/2).

Si canvia:
Guanya segur si en la primera opció ha triat una porta que amaga una cabra, perquè les altres portes tancades amaguen dos cotxes. (probabilitat = 1)
Si la porta de la tria inicial amagava un cotxe, la probabilitat de triar l’altre cotxe al canviar és de 1/2, perquè pot triar entre entre les altres dues portes, que amaguen un cotxe i una cabra.

Matemàticament, doncs:

Siguin els següents esdeveniments aleatoris:

W: guanyar, és dir, triar porta amb cotxe en la segona tria
G1: triar porta amb cabra en la primera tria
C1: triar porta amb cotxe en la primera tria

G1 i C1 són esdeveniments complementaris.

Probabilitat de G1 union C1 = P(G1 union C1) = 1 newline
Probabilitat de G1 intersection C1 = P(G1 intersection C1) = 0

Siguin les probabilitats
P(W) = Probabilitat de guanyar si canvia en segona opció
P(G1) = Probabilitat d’haver triat cabra en la primera opció (1/2)
P(Win | G1) = Probabilitat de guanyar si canvia en segona opció condicionat a haver triat cabra en la primera (1)
P(C1) = Probabilitat d’haver triat cotxe en la primera opció (1/2)
P(Win | C1) = Probabilitat de guanyar si canvia en segona opció condicionat a haver triat cotxe en la primera (1/2)

Aleshores:

Selecció_002

I Substituint:

(1/2) * (1/2) + 1 * (1/2) = 1/4 + 1/2 = 3/4 = 0.75

Per tant, l’estratègia correcta és canviar en la segona opció, ja que la probabilitat d’haver triat cotxe en la primera opció P(C1) és només de 1/2.

Aquest resultat xoca amb la intuïció. La majoria de la gent no veu que obrir la porta amb la cabra sigui motiu per canviar la porta triada. És un biaix psicològic relacionat amb l’efecte de dotació, o l’aversió a la pèrdua. Un cop el concursant “ha comprat” la primera porta, li atribueix més valor que el que realment pot tenir

Un llibre molt interessant (i llarg) que parla, d’entre moltes altres coses, d’aquest efecte és “Thinking, fast and slow” del premi Nobel, psicòleg i economista Daniel Kahneman, que amb Amos Tversky, va desenvolupar la denominada teoria de les perspectives (prospect theory), segons la qual els individus prenen decisions, en entorns d’incertesa, que s’aparten dels principis bàsics de la probabilitat.

El cas és que quan vaig llegir el problema per primer cop vaig caure de quatre potes al biaix cognitiu i la resposta ràpida que em va sortir era equivocada.

Ferit en l’orgull i com que els apunts de matemàtica em quedaven lluny vaig optar per solucionar el problema amb força bruta: Vaig escriure un programa en Python per repetir la versió modificada de l’experiment de Monty Hall tants cops com volgués, de forma que estimaria la probabilitat a partir de la freqüència dels resultats.

No cal dir que l’experiment confirma la teoria.

Es poden trobar molt bones explicacions teòriques del problema de Monty Hall a Internet i aquí n’he reproduït una adaptant-la al problema plantejat al MOOC.

Vet aquí el codi del simulador. Els casos de prova es poden ajustar amb la variable num_experiments (per defecte a 100.000)

No té truc: he definit una classe MontyHall que simula l’experiment al constructor que a mida que va progressant ajusta propietats. La classe té mètodes per consultar els valors de les propietats.

El bloc principal no és més que la repetició de l’experiment tants cops com digui num_experiments. A cada iteració acumula els valors. Finalment, calcula les probabilitats i mostra els resultats.

from random import *

class MontyHall():
    rand = None
    door = []
    first_selection = 0
    door_goat = 0
    new_user_selection = 0
    has_changed = 0
    has_won = 0
    
    def __init__(self):
        self.door = ["Car", "Car", "Car", "Car"]
    
        self.rand = Random()
        D1 = self.rand.randint(1,4)
        D2 = self.rand.randint(1,4)
		
        while( D1 == D2):
            D2 = self.rand.randint(1,4)
			
        self.door[D1-1] = "Goat"
        self.door[D2-1] = "Goat"

        #print "---------------------------"
        #print self.door

        # first user selection
        self.first_selection = self.rand.randint(1,4)
        #print "User selects door %d" % self.first_selection 

        # monty halls shows a goat
        for i in range(1,5):
            if (self.door[i-1] == "Goat") and (i != self.first_selection):
                self.door_goat = i
                break;

        #print "Monty Hall shows goat on door %d" % self.door_goat

                
        # user selects new door
        self.new_user_selection = self.rand.randint(1,4)
        while(self.new_user_selection == self.door_goat):
            self.new_user_selection = self.rand.randint(1,4)

        # has changed?
        if (self.new_user_selection != self.first_selection):
            self.has_changed = 1
            #print "User has changed from door %d to door %d" % (self.first_selection, self.new_user_selection)
        #else:
            #print "User has not changed and remains on door %d" % self.first_selection


        # User wins?
        #print "In door %d got a %s " % (self.new_user_selection, self.door[self.new_user_selection-1]) 
        if (self.door[self.new_user_selection-1] == "Car"):
            self.has_won = 1
            #print "User wins!"
        #else:
            #print "User loses!"

    def get_has_won(self):
        return self.has_won

    def get_has_changed(self):
        return self.has_changed;

    def show_new_user_selection(self):
        print self.new_user_selection

    def show_goat_door(self):
        print self.door_goat

    def show_first_selection(self):
        print self.first_selection
		
    def show(self):
        print self.door
		
# ---- main ----
num_experiments = 100000

for j in range(0, 10):

    count_changes = 0.0
    count_no_change_won = 0.0
    count_change_won = 0.0

    for i in range(1,num_experiments + 1):
        montyHall = MontyHall()
        count_changes = count_changes + montyHall.get_has_changed()
        if montyHall.get_has_changed() == 1:
            count_change_won = count_change_won + montyHall.get_has_won()
        else:
            count_no_change_won = count_no_change_won + montyHall.get_has_won()

    print "---------------------------"
    print "Totals:"
    print "Num. experiments: %d" % num_experiments
    print "Num changes: %d" % count_changes
    print "Num no changes: %d" % (num_experiments - count_changes)
    print "Num changes won: %d" % count_change_won
    print "Num no changes won: %d" % count_no_change_won
    print "Num changes won/Num changes = %f" % (count_change_won / count_changes)
    print "Num no changes won/Num no changes = %f" % (count_no_change_won / (num_experiments - count_changes))

Un bon experiment per a noies i nois de batxillerat.

El codi es pot descarregar del meu github: https://github.com/abaranguer/montyhall.