Python решение задачи

Question

Дано дерево задач с одним корнем. Узлами дерева являются группы задач, листьми - сами задачи. Внутри группы могут содержаться либо другие группы, либо задачи, но не то и другое одновременно. Каждый элемент дерева имеет уникальный идентификатор id (неотрицательное целое число) и название name (строка). Дополнительно задачи имеют приоритет priority (неотрицательное целое число), а группы задач приоритета не имеют. Необходимо реализовать функцию findTaskHavingMaxPriorityInGroup, в которую передается дерево задач и идентификатор группы. Она должна найти задачу с наибольшим приоритетом среди всех из этой группы (включая те из них, которые находятся во вложенных группах). Если не удалось найти группу с указанным идентификатором, функция должна генерировать исключение. Если в группе нет ни одной задачи, должно возвращаться неопределенное значение (undefined в JavaScript, None в Python, nullptr в C++ и null в Kotlin).

Пример:

Допустим, имеется дерево задач

id = 0, name = "Все задачи"
- id = 1, name = "Разработка"
  - id = 2, name = "Планирование разработок", priority = 1
  - id = 3, name = "Подготовка релиза", priority = 4
- id = 4, name = "Аналитика"

Отступами обозначается вложенность групп задач. Это дерево содержит три группы ("Все задачи", "Разработка" и "Аналитика"), а также две задачи ("Планирование разработок" и "Подготовка релиза"). Для этого дерева вызов функции findTaskHavingMaxPriorityInGroup c номером группы

0 - должен вернуть задачу "Подготовка релиза" (имеет максимальный приоритет 4)
3 - сгенерировать исключение (не является группой)
5 - сгенерировать исключение (группа не существует)

4 - вернуть неопределенное значение (в группе нет ни одной задачи)

Дерево

tasks = {
    'id': 0,
    'name': 'Все задачи',
    'children': [
        {
            'id': 1,
            'name': 'Разработка',
            'children': [
                {'id': 2, 'name': 'Планирование разработок', 'priority': 1},
                {'id': 3, 'name': 'Подготовка релиза', 'priority': 4},
                {'id': 4, 'name': 'Оптимизация', 'priority': 2},
            ],
        },
        {
            'id': 5,
            'name': 'Тестирование',
            'children': [
                {
                    'id': 6,
                    'name': 'Ручное тестирование',
                    'children': [
                        {'id': 7, 'name': 'Составление тест-планов', 'priority': 3},
                        {'id': 8, 'name': 'Выполнение тестов', 'priority': 6},
                    ],
                },
                {
                    'id': 9,
                    'name': 'Автоматическое тестирование',
                    'children': [
                        {'id': 10, 'name': 'Составление тест-планов', 'priority': 3},
                        {'id': 11, 'name': 'Написание тестов', 'priority': 3},
                    ],
                },
            ],
        },
        {'id': 12, 'name': 'Аналитика', 'children': []},
    ],
}

Подскажите решение, а лучше в какую сторону копать и где искать информацию по этому поводу. Я понимаю что нужно обойти дерево и найти соответствующий элемент. Но вот как сделать этот обход не знаю

Answer 1

Мне стало интересно и я написал не большой код с использованием рекурсии. Можешь его переделать. обрабатывать результаты можешь отдельно от функции. 100% гарантию того что код выполняет то что нужно дать не могу. Просто показываю пример того как это можно реализовать. Я сам не особо хороший кодер, так что не суди строго.

tree_list = []
name_list = []
def getting_data_from_tree(arr, id):
    if isinstance(arr, dict):
        if 'children' in list(arr.items())[2]:
            if id == arr.get('id'):
                name_list.append(arr.get('name'))
                return name_list
            tree_list.append([arr.get('id'), arr.get('name'), None])
            getting_data_from_tree(arr.get('children'), id)
    elif isinstance(arr, list):
        for i in arr:
            if isinstance(i, dict):
                if 'children' in list(i.items())[2]:
                    if id == i.get('id'):
                        try:
                            newlist = sorted(i.get('children'), key=lambda k: k['priority'])
                            name_list.append(newlist[-1].get('name'))
                        except:
                            if len(i.get('children')) == 0:
                                name_list.append('в группе нет ни одной задачи')
                                return name_list
                            else:
                                name_list.append(i.get('name'))
                                return name_list
                getting_data_from_tree(i.get('children'), id)
    return name_list

if __name__ == '__main__':
    print(getting_data_from_tree(tasks, 6))

Answer 2

def findTaskHavingMaxPriorityInGroup(tasks, groupId):
# ------------------------------------------------------------------------------------------------
# Решение задачи 2
# ------------------------------------------------------------------------------------------------
    def search_group(id, tasks):
        """Функция проверяет id родителя"""
        if tasks['id'] == id:
            search_max(tasks)
            return 1
        search_group2(id, tasks)

    def search_group2(id, tasks):
        """Если id родителя не подходит по условию, функция ищет группу соответствующую переданому id"""
        if 'children' in tasks:
            _ = tasks['children']
            for pot in _:
                if pot['id'] == id:
                    search_max(pot)
                    return 0
                if 'children' in pot:
                    search_group2(id, pot)

    def search_max(tasks):
        """Проверяет относится ли данный id к группе"""
        global flag
        if 'priority' in tasks:
            raise Exception("not a group")
        if tasks['children'] == []:
            flag = None
            return 0
        search_max2(tasks)

    def search_max2(tasks):
        """Ищет задачу с максимальным приоритетом"""
        if 'children' in tasks:
            _ = tasks['children']
            for pot in _:
                if 'priority' in pot:
                    if pot['priority'] > max['priority']:
                        max['priority'] = pot['priority']
                        max['name'] = pot['name']
                        max['id'] = pot['id']
                if 'children' in pot:
                    search_max2(pot)

    max = {'id': 0, 'name':'', 'priority':0,}# Задаем начальное значение
    global flag
    flag = 1
    search_group(groupId, tasks)
    if flag == None:
        return None
    if max['name'] == '':
        # если id не найден вырабатывается исключение
        raise Exception("not a group")
    return max

БЛОГ НА HUSL

Python решение задачи

Ответы (2 шт):