Hoje no IX Encontro do Python User Group de Pernambuco apresentei
uma palestra relâmpago no I Toró de palestras do PUG-PE. Nessa
palestra apresentei uma forma de resolução para o problema abaixo
utilizando uma abordagem funcional. Esse problema foi uma proposta
de Dojo enviada por Marcel Caraciolo a nossa lista de discussão.
Depois encontrei na internet que essa ele fazia parte da etapa
de inscrição para o Google Developer Day 2010.
Abaixo segue a descrição: 

Na pacata vila campestre de Arquivonaoencontradoville, todos os
telefones têm 6 dígitos. A companhia telefônica estabelece as
seguintes regras sobre os números:
  • Não pode haver dois dígitos consecutivos idênticos, porque isso é chato;
  • A soma dos dígitos tem que ser par, porque isso é legal;
  • O último dígito não pode ser igual ao primeiro, porque isso dá azar.
Então, dadas essas regras perfeitamente razoáveis, bem projetadas
e maduras, quantos números de telefone na lista abaixo são válidos?

215228, 218415, 221632, 224722, 229644, 230847, 233798,
237903, 239224, 241832, 242112, 243248, 246147, 247652,
250688, 252940, 255721, 256882, 259134, 262578, 263327,
266656, 268796, 270350, 272863, 275245, 278601, 278606,
281963, 283751, 288259, 291562, 296545, 298528, 302103,
303431, 307561, 311979, 315548, 320440, 322278, 324469,
324740, 327417, 330263, 331179, 334147, 334932, 336085,
338096, 338106, 342991, 347187, 347590, 348863, 350187,
353246, 354032, 358616, 363056, 363251, 366141, 369906,
371046, 372684, 377077, 381177, 382086, 385627, 385694,
386105, 388179, 390251, 392624, 394225, 395328, 398698,
400102, 404224, 408064, 410386, 411711, 413621, 415653,
417168, 419269, 424197, 427202, 430639, 432570, 437462,
442412, 444990, 447613, 452039, 456750, 459927, 462532,
465756, 467051, 468297, 469089, 471562, 474900, 475534,
476833, 478910, 480437, 482085, 485647, 487736, 489897,
493033, 495182, 498463, 502539, 502785, 505926, 508246,
511720, 515395, 515595, 516362, 520927, 525025, 529957,
530139, 531015, 533760, 534588, 538184, 541403, 542913,
546141, 548038, 549095, 552509, 556808, 560382, 563503,
565304, 567165, 567675, 572218, 573856, 576408, 578085,
578997, 579553, 584487, 589220, 590967, 593234, 597867,
599823, 603666, 607878, 611482, 611854, 612811, 614119,
615956, 617547, 621070, 621309, 626105, 626885, 631080,
635911, 639606, 640175, 641607, 645158, 647958, 652199,
656507, 658615, 662663, 662947, 664704, 666668, 667544,
669440, 673512, 675931, 676963, 677113, 678606, 682716,
682998, 684883, 686140, 688963, 689054, 692042, 695458,
697031, 697457, 697623, 698026

Apresentação.


Script Python.
http://ideone.com/3SPKF

Os Telefones

Na pacata vila campestre de Arquivonaoencontradoville, todos os telefones têm 6 dígitos. A companhia telefônica estabelece as seguintes regras sobre os números:

  • Não pode haver dois dígitos consecutivos idênticos, porque isso é chato;
  • A soma dos dígitos tem que ser par, porque isso é legal;
  • O último dígito não pode ser igual ao primeiro, porque isso dá azar.

Então, dadas essas regras perfeitamente razoáveis, bem projetadas e maduras, quantos números de telefone na lista abaixo são válidos?

215228, 218415, 221632, 224722, 229644, 230847, 233798, 237903, 239224, 241832, 242112, 243248, 246147, 247652, 250688, 252940, 255721, 256882, 259134, 262578, 263327, 266656, 268796, 270350, 272863, 275245, 278601, 278606, 281963, 283751, 288259, 291562, 296545, 298528, 302103, 303431, 307561, 311979, 315548, 320440, 322278, 324469, 324740, 327417, 330263, 331179, 334147, 334932, 336085, 338096, 338106, 342991, 347187, 347590, 348863, 350187, 353246, 354032, 358616, 363056, 363251, 366141, 369906, 371046, 372684, 377077, 381177, 382086, 385627, 385694, 386105, 388179, 390251, 392624, 394225, 395328, 398698, 400102, 404224, 408064, 410386, 411711, 413621, 415653, 417168, 419269, 424197, 427202, 430639, 432570, 437462, 442412, 444990, 447613, 452039, 456750, 459927, 462532, 465756, 467051, 468297, 469089, 471562, 474900, 475534, 476833, 478910, 480437, 482085, 485647, 487736, 489897, 493033, 495182, 498463, 502539, 502785, 505926, 508246, 511720, 515395, 515595, 516362, 520927, 525025, 529957, 530139, 531015, 533760, 534588, 538184, 541403, 542913, 546141, 548038, 549095, 552509, 556808, 560382, 563503, 565304, 567165, 567675, 572218, 573856, 576408, 578085, 578997, 579553, 584487, 589220, 590967, 593234, 597867, 599823, 603666, 607878, 611482, 611854, 612811, 614119, 615956, 617547, 621070, 621309, 626105, 626885, 631080, 635911, 639606, 640175, 641607, 645158, 647958, 652199, 656507, 658615, 662663, 662947, 664704, 666668, 667544, 669440, 673512, 675931, 676963, 677113, 678606, 682716, 682998, 684883, 686140, 688963, 689054, 692042, 695458, 697031, 697457, 697623, 698026,

Demorou mas estou postando aqui a minha apresentação no último encontro do PUG-PE.

Palestra + exemplos

Foi um dos melhores encontros já realizados pelo grupo, todos  realmente estão de parabéns. Quem perdeu pode ler o resumo do nosso encontro e em breve ver as palestras no Blip.tv.

Álbum de foto do VI Encontro do PUG-PE

No começo desse mês (03/08) falei um pouco sobre Python e o Python Poli aos calouros do curso de Engenharia de Computação da UPE . A “Semana dos calouros” é um  evento realizado pelo Centro Acadêmico de Engenharia de Computação (CAEC)  a cada inicio de período e tem como intuito principal dá as boas vindas  e tirar as possíveis dúvidas sobre o curso. Minha palestra aconteceu no momento reservado aos  grupos de estudos. Por sinal, a POLI-UPE possui vários entre eles o Java Poli, Jogos, .Net, Desenvolvimento Web, Software Livre, Python Poli. Talvez a maioria não funcione da forma ideal mas  o fato de existirem já é uma grande incentivo ao estudo dessas tecnologias.

Próximo sábado, mas precisamente dia 14/08 haverá a reunião do mês de agosto do Grupo de usuários de Python de Pernambuco nas  dependências da UFRPE. Estarei por lá falando um pouco  sobre Python e as suas ferramentas de programação funcional.

Dando continuidade a Um pouco de Funcional, hoje o post é sobre a função filter.

Filter

Imagem do livro Python para Desenvolvedores (Creative Commons)

A função filter deve ser utilizada quando é necessário filtrar uma sequência. Sua utilização segue o seguinte modelo

filter(func,seq) #func
filter(None,seq) #None

Em alguns casos também pode ser reproduzido com list comprehension dessa maneira

[item for item in seq if func(seq)] #func
[item for item in seq if item]      #None

A função filter retorna uma sequência formada por todos os itens em que func(item) é True. Quando é usada com None, retorna os itens que são True.

>>> def func(item):
 return item%15==0 and not item%10==0

>>> filter(func,range(100))
[15, 45, 75]
>>> [item for item in range(100) if func(item)]
[15, 45, 75]

>>> filter(None,[1,0,None,False,True,"Filter",""])
[1, True, 'Filter']
>>> [item for item in [1,0,None,False,True,"Filter",""] if item]
[1, True, 'Filter']

Em Python 2.x o retorno de filter sempre é uma lista, exceto quando a sequência é uma String ou Tupla, nesse caso o retorno é do tipo da sequência.

>>> filter(lambda x: not x%2,range(5))
[0, 2, 4]
>>> filter(lambda x: not x%2,tuple(range(5))) # tupla retorna tupla
(0, 2, 4)

Em Python 3 o retorno de filter é um iterator.

>>> filter(lambda x: len(x)>5,["Django","Web2py","CherryPy","GAE"])
<filter object at 0xb7b8a70c>
>>> from itertools import ifilterfalse
>>> list(ifilterfalse(None,[1,0,None,False,True,"Filter",""]))
[0, None, False, '']

ifilterfalse é uma função do módulo itertools que assemelha-se a filter porém retorna um iterator com todos os itens em que  func(item) é False.

Abaixo segue algumas utilizações de filter

Filtrar as pastas do diretório

>>> filter(os.path.isdir,os.listdir(r'/home/rodrigoclira/'))

Filtrar os palíndromos de uma lista de strings

>>> filter(lambda x: x[::-1]==x,["casa","ovo","palavra","radar"])
['ovo', 'radar']

O número 3.025 possui a seguinte característica: 30 + 25 = 55 e 55^2 = 3025. Escreva um  programa que mostre todos os números com quatro algarismos que possuem a  citada característica

>>> filter(lambda x : (x/100 + x%100)**2==x,range(1000,10000))
[2025, 3025, 9801]

Encontrar a soma de todos números amigos menores que 10000.

>>> divisores = lambda num: sum(filter(lambda y: num%y==0,range(1,(num/2)+1,[1,2][num%2])))
>>> sum(map(lambda (div,num): num ,filter(lambda (div,num): div!=num and divisores(div)==num ,map(lambda x: (divisores(x),x),range(1,10000)))))
31626

Explicando os passos usados para resolver o problema

1. Cria-se função que retornará a soma dos divisores de um número.

>>> num = 10
>>> filter(lambda y: num%y==0,range(1,(num/2)+1,[1,2][num%2]))
[1, 2, 5]
>>> sum(filter(lambda y: num%y==0,range(1,(num/2)+1,[1,2][num%2])))
8
>>> divisores = lambda num: sum(filter(lambda y: num%y==0,range(1,(num/2)+1,[1,2][num%2])))

2. Aplicar um mapeamento para criar uma lista de tuplas no seguinte formato

(soma_divisores,num)

>>> map(lambda x: (divisores(x),x),range(1,10000))
[(0, 1), (1, 2), (1, 3), (3, 4),...

Se você está testando cada passo desses, nessa etapa será criada uma lista com 9999 tuplas . 😉

3. As seguintes condições tem que ser verdadeiras para X ser considerado um número amigo de Y

Y = divisores(X)
X != Y e divisores(Y) == X

Então vamos filtrar a lista para obter apenas os amigos usando a ideia anterior

>>> filter(lambda (div,num): div!=num and divisores(div)==num ,map(lambda x: (divisores(x),x),range(1,10000)))
[(284, 220), (220, 284), (1210, 1184), (1184, 1210), (2924, 2620), (2620, 2924), (5564, 5020), (5020, 5564), (6368, 6232), (6232, 6368)]

4. Para finalizar é necessário somar os números amigos, que nessa abordagem é representado pela segunda posição da tupla.

>>> map(lambda (div,num): num ,filter(lambda (div,num): div!=num and divisores(div)==num ,map(lambda x: (divisores(x),x),range(1,10000))))
[220, 284, 1184, 1210, 2620, 2924, 5020, 5564, 6232, 6368]

>>> sum(map(lambda (div,num): num ,filter(lambda (div,num): div!=num and divisores(div)==num ,map(lambda x: (divisores(x),x),range(1,10000)))))
31626

Esse problema foi retirado do Project Euler, mas especificamente o problema 21. O resultado está certo, porém espero que alguém possa aconselhar uma solução mais eficiente.

Links

http://docs.python.org/library/functions.html#filter
http://aprenda-python.blogspot.com/2009/10/filter-ou-list-comprehension.html
http://www.faqs.org/docs/diveintopython/regression_filter.html
http://www.python.org.br/wiki/PythonFuncional#Filter

Continuando a série “Um pouco de Funcional“, chegou a hora de falar sobre map. Apesar de ser uma função originalmente de programação funcional, map hoje já está presente em várias linguagens (ver tabela).

A função map é utilizada para fazer mapeamentos em sequência.

Entenda sequência como qualquer objeto iterável.
ex.: listas, tuplas, strings, etc.

mapeamento

Imagem retirada do livro "Python para Desenvolvedores"

Mapeamento consiste em aplicar uma determinada função para cada elemento da sequência. A sua utilização em Python segue o seguinte modelo

map(funcao,seq1,seq2,seqn)

Para fins didáticos entenda que quanto as sequências são de tamanhos diferentes serão ‘preenchidas’ com None.

É possível simular o funcionamento de map com laço for da seguinte maneira

lista=list()
for x,y,z in zip(seq1,seq2,seqn):
	lista.append(funcao(x,y,z))

A função map independente do tipo de sequência, retorna uma lista com os resultados do seu mapeamento, porém, em Python 3k a função map retorna um iterator.

! map em Python 3k comporta-se como o itertools.imap()

>>> map(lambda x:x+1,range(3))
<map object at 0xb7c2b50c>

Mas se você realmente necessite que map retorne uma lista pode seguir três caminhos para consertar essa incompatibilidade.

1. Utilizar o construtor de lista na função map

#python3
>>> list(list(map(lambda x: x+1,range(4))))
[1,2,3,4]

2. Utilizar List Comprehension (melhor solução)

#python3
>>> [(lambda x:x+1)(x) for x in range(4)]
[1,2,3,4]

3. Reescrever o código para não precisar de uma lista. 🙂

>>> print ("FUUUUUUU",end="n")

Caso você esteja no Python 2.7 e queira testar esse novo comportamento do map

>>> from future_builtins import map

Como foi visto a utilização de map é bastante simples, e junto com lambda, reduce e filter torna-se uma ferramente bastante poderosa na resolução de vários problemas.

Abaixo segue algumas utilizações de map

>>> import re
>>> teste = ["2a","a3","c10",'1a2aaaaas']
>>> teste = map(lambda item: re.sub(r"[a-z]", "", item), teste)
['2', '3', '10', '12']
"".join(map(chr,[112, 121, 116, 104, 111, 110]))
'python'

Nos exemplos anteriores utilizei funções anônimas (lambda) com map, apenas por comodidade mas não há nenhuma restrição em utilizar funções definida por def

>>> def myPow(x,y):
	return x**y
>>> map(myPow,range(4),[2,3,4,5])
[0, 1, 16, 243]

Abaixo segue um exemplo de código utilizando as duas ferramentas já explicadas até aqui (lambda e map) .

#Gráfico de barras horizontal
#python 2.6.2
>>> from sys import stdout
>>> barras = lambda char,valores : map(lambda (valor,barra): stdout.write( "%2d"%valor+"  |"+ barra +"n"),map(lambda valor: (valor,valor*char),valores))
>>> barras("=",[2,3,10,3,1,0,7])
 2  |==
 3  |===
10  |==========
 3  |===
 1  |=
 0  |
 7  |=======
[None, None, None, None, None, None, None]

DICA: Na criação de códigos aninhados usando map, filter, reduce, lambda, etc sempre use a tática “dividir para conquistar”.

Agora vamos tentar explicar a função histograma, utilizando a dica anterior.

1. Cria-se uma lista de tuplas onde a primeira posição representa o valor e a segunda, a barra.

>>> valores = [2,3,10,3,1,0,7]
>>> char = "="
>>> map(lambda valor: (valor,valor*char),valores)
[(2, '=='), (3, '==='), (10, '=========='), (3, '==='), (1, '='), (0, ''), (7, '=======')]</p>

2. Aplica-se novamente o mapeamente com uma função que imprime na tela no formato  Valor  |  Barra

>>> from sys import stdout
>>> map(lambda (valor,barra): stdout.write( "%2d"%valor + "  |" + barra + "n"),[(2, '=='), (3, '==='),
(10, '=========='), (3, '==='), (1, '='), (0, ''), (7, '=======')])

3. Está quase tudo pronto mas ainda falta transformar tudo isso numa função

>>> from sys import stdout
>>> barras= lambda char,valores : map(lambda (valor,barra): stdout.write( "%2d"%valor+"  |"+ barra
+"n"),map(lambda valor: (valor,valor*char),valores))
>>> barras("=",[2,3,10,3,1,0,7])
 2  |==
 3  |===
10  |==========
 3  |===
 1  |=
 0  |
 7  |=======
[None, None, None, None, None, None, None]

Voilá !

Agora é necessário explicar duas coisas que talvéz tenham passado sem ser notado.

Por que além de imprimir na tela apareceu uma lista de None?

Bem, como tinha dito, sempre um mapeamento retorna uma lista com os valores da função aplicada em cada elemento, porém o sys.stdout.write é um método que não possou retorno. Logo, a lista de None é o retorno da função map.

! Funções sem retorno em Python, retornam None. 🙂

Por que usar sys.stdout.write ao invés de print?

Para responder isso teria que voltar a o último post e ver umas das regras na criação
de funções lambda.

  • O corpo da função deve ser uma expressão, não uma instrução.

Usar sys.stdout.write é uma forma de burlar essa restrição, o próprio print é definida usando o sys.stdout.write.

Até em Python 2.x print é uma instrução porém em Python 3k já é uma função. Isso fez-me fazer alguns testes:

#python2.6.2
>>> map(print,range(3))
SyntaxError: invalid syntax
>>> map(lambda x: print x,range(3))
SyntaxError: invalid syntax
#python3.0.1
>>> list(map(print,range(3)))
0
1
2
[None, None, None]
>>> list(map(lambda x: print(x),range(3)))
0
1
2
[None, None, None]

Como já era de esperar, com Python 3k não seria necessário usar o sys.stdout.write.

Ainda sobre o código do gráfico de barras, há a opção de juntar os dois lambdas em apenas um e assim aplicar o mapeamento apenas uma vez, vai ficar mas complicado que já está mas é uma opção.

Até o próximo post.

Links

http://docs.python.org/library/future_builtins.html#future_builtins.ascii
http://en.wikipedia.org/wiki/Map_(higher-order_function)
http://docs.python.org/library/functions.html#map
http://docs.python.org/tutorial/datastructures.html#functional-programming-tools
http://docs.python.org/release/3.0.1/whatsnew/3.0.html#views-and-iterators-instead-of-lists
http://ark4n.wordpress.com/python/
Rodrigo Lira

2  |==
3  |===
10  |==========
3  |===
1  |=
0  |
7  |=======

Hoje, vou começar uma série de posts que tem como finalidade mostrar um pouco das ferramentas de programação funcional que Python propicia aos programadores. O post de hoje é sobre lambda mas pretendo no futuro falar um pouco sobre filter, map, reduce, any, all, list comprehension, etc.

Python permite a criação de funções anônimas através do construtor lambda. Funções definidas por lambda possuem apenas uma linha e seu corpo deve conter apenas expressões. Quem já teve contato com alguma linguagem funcional talvez já tenha se deparado com elas

(a-> a+1) 5 -- Haskell
(lambda (arg) (+ arg 1) 5)  ;Lisp

Ambas funções incrementam em um o valor recebido como argumento, logo o retorno seria 6.

O mesmo exemplo com Python

>>> (lambda x: x+1) (5)
6

Funções lambdas são criadas da seguinte forma

lambda arg1,arg2,arg3,argn: expressão

Utilizando def a função correspondente seria

def func(arg1,arg2,arg3,argn):
 return expressão

Também é possível nomea-las

>>> quadrado = (lambda x = x**2)
>>> quadrado(3)
4

e atribuir argumentos opcionais

>>> (lambda x,y=1: x**y) (2)
2
>>> (lambda x,y=1: x**y) (2,2)
4

Funções lambdas são frequentemente utilizadas em callback

#http://effbot.org/zone/tkinter-callbacks.htm
def callback(numero):
 print "botão",numero

Button(text="um";,command=lambda: callback(1)).pack()
Button(text="dois",command=lambda: callback(2)).pack()
Button(text="tres",command=lambda: callback(3)).pack()

e como argumento nas funções map,filter e reduce

>>> map(lambda x : (x**2)+x,[2,4,6])
[6,20,42]

É importante frisar que a sua utilização é inteiramente opcional (sempre poder usar a instrução def). Porém o uso de funções lambdas  se torna útil na criação de funções simples e de uso exclusivo.

Necessário lembrar que

  • O corpo da função deve ser uma expressão, não uma instrução;.
  • Nas funções lambdas não existe uma instrução return. O valor retornado pela função é o valor da expressão no corpo da função.
  • Possui apenas uma linha.

Links

http://docs.python.org/reference/expressions.html#lambda
http://diveintopython.org/power_of_introspection/lambda_functions.html
http://www.secnetix.de/olli/Python/lambda_functions.hawk

Rodrigo Lira