MROC3 (Шамаева Лена)

Большинство использовало exec.

   1 res = ""
   2 s = input().rstrip()
   3 while s:
   4     if s.startswith("class") and ":" in s:
   5         res += f"{s.split(':')[0]}: pass\n"
   6     s = input().rstrip()
   7 try:
   8     exec(res)
   9 except Exception as E:
  10     print("No")
  11 else:
  12     print("Yes")

Это читерство )). И в этом примере лучше было бы сделать exec() в изолированном пространстве.

Теперь решение на основе алгоритма.

Алгоритм хорошо расписан здесь [https://www.python.org/download/releases/2.3/mro/ https://www.python.org/download/releases/2.3/mro/]

Берем класс и его родителей, делаем линеаризацию.

linear.png

Надо разобраться с merge. На картинке на вход merge приходит список линеаризаций родительских классов и сами родительские классы.

Например, [[A,B,C], [D,C], [A,E], …] 

Вкратце: на входе у нас список каких-то списков.

В комментариях приведены значения переменных при входных данных:

class A: pass
class B(A): pass
class C(A,B): pass

Программа:

   1 Cls, L = {}, {}
   2 # Cls – словарь, ключ – название класса, значение – список родительских классов
   3 # пример: {'A': [], 'B': [], 'C': ['A', 'B']}
   4 # L — словарь, ключ — название класса, значение — линеаризация этого класса
   5 # пример: L {'A': ['A'], 'B': ['B', 'A']}
   6 
   7 def merge(parents): # например, для строки ‘class C(A,B):’ parents = ['A', 'B']
   8     if not parents: # если parents пустой, то линеаризовать нечего
   9         return
  10     S = [L.setdefault(b, [b, *merge(Cls[b])]).copy() for b in parents] + [parents]      # [L(B1), L(B2),...L(Bn), B1,…, Bn], см. Зам. 1
  11     while S:
  12         for s in S:
  13             if not s: continue #на пустые не обращаем внимание, они могут быть даны изначально
  14             e = s[0]
  15             if all(e==ss[0] or e not in ss for ss in S): # см. Зам. 2
  16                 yield e
  17                 for ss in S:
  18                     if ss and ss[0] == e: # удаляем уже рассмотренный элемент
  19                         del ss[0]
  20                 S = list(filter(len, S)) #удаляем пустые
  21                 break
  22         else:
  23             raise TypeError # см. Зам. 3
  24 
  25 reClass = re.compile(r"class\s+(\w+)\s*(?:\((.*)\))?\s*:")
  26 #class{пробелы}{имя_класса}{пробелы_или_пусто}'''('''родительские_классы_или_пробелы''')''':
  27 s = input().rstrip() # rstrip — могут быть пустые строчки, какие-то пробельчики справа
  28 while s:
  29     res = reClass.match(s)
  30     if res:
  31         Nam, Par = res.groups()
  32         Cls[Nam] = [c.strip() for c in Par.split(",")] if Par else []
  33         try:
  34             L[Nam] = [Nam, *merge(Cls[Nam])]
  35         except TypeError:
  36             print("No")
  37             break
  38     s = input().rstrip()
  39 else:
  40     print("Yes")

Зам.1

  1. В классическом алгоритме merge применяется к L(B1), L(B2),…,L(Bn), [B1, B2,…,Bn]: L[C(B1 … BN)] = C + merge(L[B1] … L[BN], [B1 … BN])

    • В решении на вход функции merge дается только B1, …, Bn - родительские классы для C.

    • Мы сами строим [L(B1), L(B2),…,L(Bn), [B1, B2,…,Bn]], используя [B1, … Bn].

  2. [b, *merge(Cls[b])] – линеаризация L(Bi).

    • Здесь используем то, что в python3 можно
         1 >>> a = [1,2,*range(8)]
         2 >>> a
         3 [1, 2, 0, 1, 2, 3, 4, 5, 6, 7]
         4 
      
    • Тогда
         1 S = [[b, *merge(Cls[b])] for b in parents] + [parents]
         2 # [L(B1),…,L(Bn),[B1,…,Bn]]
      
  3. Но так каждый раз линеаризация пересчитывается заново. Хотим использовать ранее вычисленную линеаризацию, которая хранится в L.
       1 L_B = L[b] if b in L else [b, *merge(Cls[b])] – L(Bi)
    
  4. В словарях питона есть setdefault, который возвращает значение по ключу, инициализируя элемент словаря, если необходимо, указанным значением.
       1 >>> d = {}
       2 >>> d.setdefault('a', 15)
       3 15
       4 >>> d
       5 {'a': 15}
       6 
    
    • Перепишем с setdefault:
         1 L_B = L.setdefault(b, [b, *merge(Cls[b])]) – L(Bi).
         2 S = [L.setdefault(b, [b, *merge(Cls[b])]) for b in parents] + [parents]
         3 # [L(B1),…,L(Bn),B1,…,Bn]
      
  5. <!> Если оставить так, то при удалении элемента из списка линеаризации (del ss[0]), мы удаляем его из Cls{} (потому что мы модифицируем списки, которые хранятся, как значения в ss[0]). Это серьезный изъян!

    • Сделаем копию. Стало правильно, но в 5 раз медленнее:
         1 S = [L.setdefault(b, [b, *merge(Cls[b])]).copy() for b in parents] + [parents]
      
    • Общая идея: если вы получаете список и собираетесь его модифицировать, есть шанс, что вы модифицируете это по-живому (и модифицируете то, что где-то еще используется).

Зам. 2

Класс не должен зависеть сам от себя и в списке зависимостей два раза один и тот же класс не должен повторяться. Поэтому, если элемент содержится в голове, то он точно не содержится в хвосте.

Для элемента - кандидата на линеаризацию и проверяемого списка могут быть две взаимоисключающие ситуации:

Если это не так, то линеаризация невозможна.

По смыслу надо проверять, что элемента нет в хвосте, то есть

Зам. 3

Профилирование на 7 тесте