Составление словаря неопределённой длинны по двум условиям

Question

Простая математическая задача!

В классе каждый ученик дружит ровно c шестью другими,
и у любых двух учеников есть ровно два общих друга.
Сколько учеников в этом классе?

Техническое ЗАДАНИЕ:

Скрипт должен составляет словарь friends в соответствии с условиями задачи.

Ключ - имя ученика, а значение - последовательность имён друзей ученика.
В классе нет учеников с одинаковыми именами.

Составление словаря прекращается, как только условия задачи будут соблюдены.

Алгоритм не должен опираться на заранее определённое кол-во учеников в классе.

input:

from datetime import datetime

names = {'Лёша', 'Влад', 'Миша', 'Вова', 'Саня', 'Коля',
         'Дима', 'Толя', 'Ваня', 'Петя', 'Олег', 'Сеня',
         'Лёня', 'Егор', 'Витя', 'Стас', 'Глеб', 'Илья',
         'Женя', 'Вика', 'Нина', 'Анна', 'Соня', 'Рита',
         'Лика', 'Маша', 'Лиля', 'Роза', 'Таня', 'Надя',
         'Алла', 'Даша', 'Кира', 'Лена', 'Тоня', 'Люда',
         }

friends = {}

output:

Каждый ученик дружит ровно c шестью другими,
и у любых двух учеников есть ровно два общих друга?

Результат проверки: True .

Словарь составлен за 0:00:00.004601 ms.

В классе 16 учеников.

^^^^^^^
У меня словарь составляется за 4601 ms, на таком маленьком объёме данных это медленно.
Это связанно с большим количеством проверок на соответствие условиям задачи.
Своё решение я опубликую ответом вечером 09.08.2024г.

test:

from functools import reduce


def checking(friends) -> bool:
    """Функция проверяет словарь на соответствие условиям задачи.
    Тёски среди учеников приведут к неверной оценке.
    """

    return (
        (
            set(friends.keys())
            ==
            reduce(lambda x, y: set(x) | set(y), friends.values())
        )
        and
        (
            all((len(v) == 6 for v in friends.values()))
        )
        and
        (
            all((all((2 == len(set(val) & set(v))
                      for v in friends.values()
                          if v != val)
                     )
                 for val in friends.values()
                 )
                )
        )
    )


print(f'Каждый ученик дружит ровно c шестью другими,\n'
      f'и у любых двух учеников есть ровно два общих друга?\n\n'
      f'Результат проверки: {checking(friends)} .')

print(f'Словарь составлен за {end - start} ms.\n')

print(f'В классе {len(friends)} учеников.\n\n')

Критерии оценки решений

по убыванию веса:

время выполнения (т.к. проверки условий самая затратная часть)
алгоритм не должен опираться на заранее известное кол-во учеников;
зависимости (использование сторонних библиотек должно давать эффект в п. 1)

Цель:

получить альтернативные решения, найти оптимальные приёмы.

Если кто-нибудь хочет выступить спонсором,
можете объявить конкурс, это приветствуется.

Answer 1

'''список `quartet` представляет собой четверку общих друзей, на основании которых
составляются первые 4 значения
первая тройка: друзья студента из quartet.
вторая тройка: подбираются уникальные имена из names для каждого

составление друзей оставшихся студентов производится следующим алгоритмом:
ключ: студент, присутствующий в друзьях студента, но не являющийся ключом.

первая тройка: всё соответствующие индексы в значениях первых
4 элементов в списке(кроме того,что уже является ключом).

вторая тройка: все значения из второй тройки, в котором находился
взятый ключ(кроме самого ключа) + тот студент, у которого в друзьях
был тот самый ключ, который мы взяли.

алгоритм закончится тогда, когда все участники словаря friends в значениях
станут ключами без возможности добрать новых.'''
from functools import reduce
from datetime import datetime

names = {'Лёша', 'Влад', 'Миша', 'Вова', 'Саня', 'Коля',
         'Дима', 'Толя', 'Ваня', 'Петя', 'Олег', 'Сеня',
         'Лёня', 'Егор', 'Витя', 'Стас', 'Глеб', 'Илья',
         'Женя', 'Вика', 'Нина', 'Анна', 'Соня', 'Рита',
         'Лика', 'Маша', 'Лиля', 'Роза', 'Таня', 'Надя',
         'Алла', 'Даша', 'Кира', 'Лена', 'Тоня', 'Люда',
         }

friends = {}
quartet, names = list(names)[-4:], list(names)[:-4]
test_list = [0,1,2,3]
test_list1 = [3,4,5]


start = datetime.now()
for i in range(4):
  friends[quartet[i]] = [*quartet[:i],*quartet[i+1:] , names.pop(),
                              names.pop(), names.pop()]


values = [*friends.values()]
for i in values:
  for j in i:
      if j not in list(friends.keys()):
        y = list(values).index(i)# № элемента, в котором было найдено
                                  # значение, еще не являющееся ключом словаря
        x = i.index(j)# № элемента в списке
        remained = [i for i in test_list if i not in [y]]#↓↓↓↓
        remained1 = [i for i in test_list1 if i not in [x]]#удаление ключа из
                                                  #списка студентов, из 
                                                  #которого
                                                  #составляются друзья

        friends[values[y][x]] = [*[values[f][x] for f in remained],
                                       *[values[y][f] for f in remained1],
                                       [*friends.keys()][y]]
end = datetime.now()


def checking(friends) -> bool:
    """Функция проверяет словарь на соответствие условиям задачи.
    Тёски среди учеников приведут к неверной оценке.
    """

    return (
        (
            set(friends.keys())
            ==
            reduce(lambda x, y: set(x) | set(y), friends.values())
        )
        and
        (
            all((len(v) == 6 for v in friends.values()))
        )
        and
        (
            all((all((2 == len(set(val) & set(v))
                      for v in friends.values()
                          if v != val)
                     )
                 for val in friends.values()
                 )
                )
        )
    )


print(f'Каждый ученик дружит ровно c шестью другими,\n',
      f'и у любых двух учеников есть ровно два общих друга?\n\n',
      f'Результат проверки: {checking(friends)}.')

print(f'Словарь составлен за {end - start} s.\n')

print(f'В классе {len(friends)} учеников.\n\n'

БЛОГ НА HUSL