主页 / 问题 / 1589333
Accepted
AnnaBazueva - SPAM
Asked:2024-08-03 07:16:56 +0000 UTC2024-08-03 07:16:56 +0000 UTC

两种情况下编译不定长度字典

  • 772

一道简单的数学题！

在一个班级中，每个学生都与另外六个学生是朋友，
并且任何两个学生都有两个共同的朋友。
这个班有多少名学生？

技术规格：

该脚本应根据任务条件编译好友词典。

键是学生的姓名，值是学生好友的姓名序列。
班级里没有同名的学生。

一旦满足任务条件，字典的编译就会停止。

该算法不应依赖于班级中预定的学生数量。

输入：

from datetime import datetime

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

friends = {}

输出：

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

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

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

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

^^^^^^^
我的字典是用 编译的4601 ms，但是数据量这么小，速度很慢。
这是由于对任务条件的遵守情况进行了大量检查。
我将在 2024 年 8 月 9 日晚上发布我的决定作为答案。

测试：

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. 执行时间（因为检查条件是最昂贵的部分）
    算法不应依赖于预先已知的学生数量；
  2. 依赖项（使用第三方库应该在步骤1中生效）

目标：

获得替代解决方案，找到最佳技术。

如果有人想成为赞助商，
你可以宣布一场比赛，这是欢迎的。

python

2 个回答

  1. Best Answer
    '''список `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'
    • 4

  2. 算法。

    传奇 动画片

    形状和颜色。

    让我们根据以下标准有条件地划分朋友：

    地点 - 学生住在同一个院子（表格）。

    兴趣——学生有共同的兴趣（颜色）。

    朋友四人组。

    我们依赖的条件是：
    “两个学生恰好有两个共同的朋友”
    四个朋友满足这个条件形状/颜色
    “每个学生都与另外六个学生是朋友”
    这解释了第一阶段的名称：

    “强制拨号”

    		 在此输入图像描述

    “强制拨号”：

    1. 字典元素。

    我们招募四个朋友（圈子），
    对于每对圈子，另外两个将是共同的朋友，
    我们选择（最多 6 个）三个具有相似兴趣的朋友作为红色圈子。

    1. 字典元素。

    黄色与红色有两个共同的朋友，
    我们被迫选择（最多 6）三个具有相似兴趣的朋友作为黄色圈。

    1. 对绿色和蓝色圆圈重复相同的操作......

    我们得到以下键的 12 个名称。

    “洗牌”

    我们依次从前四个元素的值中提取新的键
    ，并将具有相似兴趣的朋友混合在一起。
    就这样，字典就编好了！

    我去年年底就解决了这个问题，我父亲
    多次带我回顾这个问题，以便我优化解决方案。

    解决方案：

    之前已上传至 Google Colab Anna_Friends.ipynb

    import random
from typing import Union
from functools import reduce
from datetime import datetime


def checking(_len: int, *, flag: str | None = None) -> Union['int', 'bool']:
    """
    Функция проверяет словарь на соответствие условиям задачи.

    Args:
        _len (int): Длина словаря для проверки.
        flag (str | None): Флаг для определения действия.
            Возможные значения: "get_i_key", "get_i_val", "get_i_rep".

            По умолчанию None.

    Returns:
        Union[int, bool]: Возвращает индекс или булевое значение
                                   в зависимости от флага.
    """


    global friends


    match flag:
        case "get_i_key":
            # Определяем индекс ключа
            return (0 if _len < 7
                    else 1 if _len < 10
                    else 2 if _len < 13
                    else 3
                    )
        case "get_i_val":
            # Определяем индекс в значении первых четырёх ключей
            return (3 if _len in (4, 7, 10, 13)
                    else 4 if _len in (5, 8, 11, 14)
                    else 5
                    )
        case "get_i_rep":
            # Определяем интекс имени в значении равное ключу
            return (_len % 3 + 2
                    if _len % 3 != 0
                    else 5
                    )
        case _:
            if _len:
                return not ((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()
                                  )
                                 )
                             )
                            )
            else:
                return True


start = datetime.now()
while checking(_len := len(friends)):
    friends.update(
        {names.pop() if not friends
         else tuple(friends.values())[0][_len-1]
         if 4 > _len
         else tuple(
             friends.values())[
                 checking(_len, flag="get_i_key")][
                     checking(_len, flag="get_i_val")]
         :
         [names.pop() for _ in range(6)]
         if not friends
         else list(map(lambda x: x
                       if x != tuple(friends.values())[0][_len-1]
                       else tuple(friends.keys())[0],
                       tuple(friends.values())[0][:3])
                   )
              + list((names.pop() for _ in range(3)))
         if 4 > _len
         else [n for n_tup in ((x[1][_len % 3 + 2 if _len % 3 != 0 else 5],)
                               if tuple(
                                   friends.values())[
                                       checking(_len, flag="get_i_key")][
                                           checking(_len, flag="get_i_val")]
                                  != x[1][checking(_len, flag="get_i_rep")]
                               else (x[0], x[1][3], x[1][4], x[1][5])
                               for x in ((k, v) for k, v in friends.items()
                                         if 4 > tuple(friends.keys()).index(k)
                                         )
                               )
               for n in n_tup
               if n != tuple(
                   friends.values())[
                       checking(_len, flag="get_i_key")][
                           checking(_len, flag="get_i_val")]
               ]
         }
    )
end = datetime.now()
    • 1

相关问题