събота, 17 януари 2009 г.

Примерна задачка на Python


„ Програмиране с Python“, ФМИ

Стефан Кънев & Николай Бачийски

02.04.2007г.

Какво ще правим?

  • Ще си припомним условието
  • Ще ви предложим примерно решение
  • Ще видим дали може да се направи по-хубаво

Условие—начало

Основната ви цел е да напишете функция със следните име и аргументи: module_game(m1, m2).

Входни данни: m1 и m2 са модули.

Резултат: n-торка с 2 елемента, с броя на точките събрали първия и втория модул при играта, която е описана по-долу в условието.

Предварително известни факти:

  • всички речници в модулите са или празни или само от цели числа. Ключовете им са винаги низове. Примери: {} {'baba': 5} {'a': 42, 'b': -69, 'x': 4360000634}
  • всички списъци в модулите са или празни или са списъци от n-торки от числа. n-торките също могат да бъдат празни. Примери: [] [()] [(1023, 4095, 8191), (), (), (0, 17), (3,)]
  • всички функции в модулите приемат два аргумента цели числа и връщат цяло число
  • може да разчитате, че тези условия ще бъдат изпълнени и няма нужда да ги проверявате

Правила на играта:

За атрибути по-надолу ще смятаме само тези реални атрибути на модулите, които не започват с _ (долна черта, подчертавка)

Условие—правило 0

Всеки модул получава 1 точка за всяка функция в него, чието име започва с последните 3 символа на друга функция в същия модул. Ето пример за част от модул, която ни гарантира две точки по този параграф:

s = "baba"
def destroy(x, y):
print "Destroyed."
return 0
def roy_keen(x, y):
print "Babyboy."
return 0
def roy_boss(x, y):
print "Holy-shmolly, that is tea!"
return 0

Условие—правило 1

Всеки модул получава 1 точка, за всеки списък в него, за който средното-аритметично на сумите от квадратите на n-орките в него е по-голямо от средно-аритметичното на всички цели числа в другия модул. Ако някоя n-торка е празна, нейната сума може да се смята за 0. Ако един списък е празен, неговото аритметично също може да се смята за 0.


Пример: имаме списъка [(1, 2), (), (8, -2), (-1, 5, -1)]. Сумите на квадратите на n-торките са съответно: 5, 0, 68, 27. Средното им аритметично е точно 25.

Условие—правило 2

По 1 точка получава модул, за всяка функция в него, която удовлетворява следните условия:

  • извикана с аргументи 0 и 0 връща 0
  • комутативна e за всички двойки числа от 0 до 99 включително

Пример за такава функция: def f(x, y): return x*y

Условие—правило 2

3 точки носи на модул всеки речник, за който:

  1. нека сортираме стойностите му по брой на цифрите в низходящ ред
  2. ако две стойности имат равен брой цифри, приемаме, че те са ъгли в градуси и сравняваме техните тангенси (отново низходящо)
  3. взимаме ключовете на първите 6 елемента. Ако елементите на речника са по-малко от 6, спираме дотук
  4. ако тези 6 ключа са ‘Chapman’, ‘Cleese’, ‘Gilliam’, ‘Idle’, ‘Jones’, ‘Palin’ независимо в какъв ред или с малки или големи букви, модулът получва трите точки

Пример за такъв речник: {'Chapman': 11, 'Charlie': 99, 'GILLIAM': 102, 'Idle': 666, 'Jones': 883, 'Palin': 55, 'Cleese': 1101}

Код—начало

def module_game(m1, m2):
return (assess(m1, m2), assess(m2, m1))

def assess(mod, mod_other):
return sum((
end3_funcs(mod),
avg_lists(mod, mod_other),
commutatives(mod),
3*monty_python_dicts(mod),
))

def valid_attributes(mod):s
return (attr for attr in dir(mod) if not attr.startswith('_'))
  • sum приема последователност и му даваме n-торка: sum((
  • valid_attributes няма нужда да връща списък, може да ползваме generator expression

Код—правило 0

def end3_funcs(mod):
func_names = [attr for attr in valid_attributes(mod) if callable(getattr(mod, attr))]
count = 0
for func in func_names:
if len(func) < 3: continue
start = func[:3]
if any((otherfunc.endswith(start) for otherfunc in func_names if func != otherfunc)):
count += 1
return count
  • Защо func_names е списък (или „за влагането на генератори“)?
  • Какво е any?

Влагане на генератори

g = (x*x for x in xrange(4))
for a in g:
for b in g:
print (a, b)
(0, 1)
(0, 4)
(0, 9)
  • Ред на извикване:
    1. g.next() във външния цикъл, a, става 0
    2. g.next() във вътрешния циъкл, b, става 1
    3. g.next() във вътрешния циъкл, b, става 4
    4. g.next() във вътрешния циъкл, b, става 9
  • генераторът не се копира
  • … и за съжаление не може лесно да се копира
  • генераторът може да се ползва само веднъж

Ами тогава?

  1. Списъци: g = [x for x in xrange(4)]
  2. Създаване на 2:
    g = (x*x for x in xrange(4))
    g_inner = (x*x for x in xrange(4))
  3. Създаване направо вътре:
    for a in (x*x for x in xrange(4)):
    for b in (x*x for x in xrange(4)):
    print (a, b)
  4. Функция генератор:
    def gen_sq(n):
    for x in xrange(n):
    yield x*x
  5. Още една функция:
    def gen_sq2(n):
    return (x*x for x in xrange(n))

Код—правило 1

def avg_lists(mod, other):
other_ints = [getattr(other, attr) for attr in valid_attributes(other)
if isinstance(getattr(other, attr), (int, long))]
other_sum, other_len = sum(other_ints), len(other_ints)
mod_lists = (getattr(mod, attr) for attr in valid_attributes(mod)
if isinstance(getattr(mod, attr), list))
count = 0
square = lambda x: x*x
for l in mod_lists:
jingled_items = [sum(imap(square, tup)) for tup in l]
jingled_sum, jingled_len = sum(jingled_items), len(jingled_items)
# don't use floats
# we know that always both the sum and the len are non-negative
# except that other_sum could be negative
if jingled_sum > 0 and 0 == other_len:
count += 1
elif jingled_len == 0 and other_sum < 0:
count += 1
elif jingled_sum*other_len > jingled_len*other_sum:
count += 1
return count

Код—правило 2

def commutatives(mod):
# този път ф-ии--не имена
funcs = [getattr(mod, attr) for attr in valid_attributes(mod)
if callable(getattr(mod, attr))]
count = 0
for func in funcs:
if func(0,0) == 0 and\
all((func(i, j) == func(j, i)
for i in xrange(0, 99) for j in xrange(i+1, 100))):
count += 1
return count

Код—правило 2

def commutatives(mod):
# този път ф-ии--не имена
funcs = [getattr(mod, attr) for attr in valid_attributes(mod)
if callable(getattr(mod, attr))]
count = 0
for func in funcs:
point_commutative = ( func(i, j) == func(j, i)
for i in xrange(0, 99) for j in xrange(i+1, 100))
if func(0,0) == 0 and\
all(point_commutative):
count += 1
return count

any и all

  • any(iterable) — връща истина, ако поне един от елементите на iterable е истина.
  • all(iterable) — връща истина, ако всички елементи на iterable са истина.
>>>people = ('God', 'Monty', 'Pinkie', 'Mityo')
>>>wannaplay = lambda name: 'x' in name
>>>friends = lambda x,y: x[0] == y[0] and x != y
>>>capitalised = lambda x: x[0].isupper()
>>>print any(map(wannaplay, people))
False # Nobody wants to play
>>>print any([friends(name, 'Mityo') for name in people])
True # Monty
>>>print all(imap(capitalised, people))
True
>>>print all((friends(name, 'Mityo') for name in people))
False

Код—правило 3

def monty_python_dicts(mod):
WANTED = set(['chapman', 'cleese', 'gilliam', 'idle', 'jones', 'palin'])
dicts = [getattr(mod, attr) for attr in valid_attributes(mod) if isinstance(getattr(mod, attr), dict)]
count = 0

def make_strange_cmp(dict_):
def strange_cmp(x, y):
x, y = dict_[x], dict_[y]
sx, sy = str(sx).lstrip('-'), str(sx).lstrip('-')
if (len(sx) != len(sy)):
return cmp(len(sx), len(sy))
return cmp(math.tan(math.radians(x)), math.tan(math.radians(y)))

for d in dicts:
ordered = sorted(d, cmp=make_strange_cmp(d), reverse=True)
if set(imap(string.lower, ordered[:6])) == WANTED:
count += 1
return count

Код—правило 3

def monty_python_dicts(mod):
WANTED = set(['chapman', 'cleese', 'gilliam', 'idle', 'jones', 'palin'])
dicts = [getattr(mod, attr) for attr in valid_attributes(mod)
if isinstance(getattr(mod, attr), dict)]
count = 0
# DSU, DSU
def make_decorate(dict_):
def decorate(key):
value = dict_[key]
svalue = str(value).lstrip('-')
return (len(svalue), math.tan(math.radians(value)))
return decorate

for d in dicts:
ordered = sorted(d, key=make_decorate(d), reverse=True)
if set(imap(string.lower, ordered[:6])) == WANTED:
count += 1
return count

DSU

  • DSU = Decorate, Sort, Undecorate
  • Трансформацията на Шварц (Schwartzian transform)
  • Искаме да сортираме списък от имена първо по второто име, после по пъврото
  • names = ['Monty Python', 'Bilbo Baggins', 'Mityo Python']
    # 2 пъти split
    # цялото се вика n*log(n) пъти
    def names_cmp(n1, n2):
    first1, last1 = n1.split()
    first2, last2 = n2.split()
    if last1 != last2:
    return cmp(last1, last2)
    else:
    return cmp(first1, first2)

    names.sort(names_cmp)

DSU (2)


# (('Python', 'Monty'), 'Monty Python')
decorated = zip([tuple(reversed(name.split())) for name in names], names)
decorated.sort()
undecorated = [value for (decor, value) in decorated]
print undecorated
['Bilbo Baggins', 'Mityo Python', 'Monty Python']
  • списъци и n-орки се сравняват първо по първи елемент, ако са равни—по-втори и т.н.
  • zip взима няколко списъка и връща списък от n-орки с поредните елементи на списъците
  • обработката на един елемент се вика веднъж и се пише веднъж

DSU (3)

ready = sorted(names, key = lambda name: tuple(reversed(name.split())))

или:


def decorate(name):
first, last = name.split()
return last, first
ready = sorted(names, key = decorate)
  • В Python 2.4 има доста нововъведения: sorted, key параметъра на sort и sorted
  • Параметърът key очаква функция с един аргумент и сортира по нейната стойност, а не по стойността на елементите на поредицата
  • Стойностите на поредицата не се променят от викането на функцията, дадена на key
  • DSU се прилага вече много по-лесно и кратко :)

Няма коментари:

Публикуване на коментар