Примерна задачка на 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 се прилага вече много по-лесно и кратко :)