Tree Walker Tree Walker
Simple+
EN Russian

Этим летом прошла 4-я ежегодная конференция PyBay , посвящённая (та-дааам) разработке на языке Python. Одним из спикеров был Рэймонд Хеттингер , член Python Software Foundation (PFS) с 2003 года, в период 2008-2012гг входил в состав совета директоров этой организации. Заслуги Рэймонда в PFS весьма обширны: он работал над созданием множеств (тип данных), генераторов, модулей “collections” и “itertools”, а также упорядоченного словаря (ordered dict). Кроме того, он внёс существенный вклад в Python Cookbook.

Доклад Рэймонда назывался “Питон – интеллектуальная игра” (“The Mental Game of Python“). Целиком запись выступления можно посмотреть здесь . В докладе на примерах рассматривалось использование различных стратегий, упрощающих процесс разработки, делающих код проще, а значит – лучше. Эта миссия представляет собой задачу на обход дерева данных, использованную Рэймондом для демонстрации применения итерационного (инкрементального) подхода к разработке.

В программировании дерево - абстрактный тип представления информации в иерархической структруре. Все элементы дерева называются узлами (или нодами). Линии, соединяющие узлы дерева, называют ветвями , а узлы без потомков называют листьями или конечными узлами. Узел, не имеющий родителя, называют корнем или корневым узлом. Максимальная глубина вложенности дерева - расстояние от корня до наиболее удалённого конечного узла. Кроме того, любой узел в дереве является корневым узлом поддерева .

example

В этой миссии в качестве входных данных даются конечное дерево данных произвольной структуры и определённое целевое значение. Требуется подсчитать количество листьев или поддеревьев данного дерева, которые соответствуют целевому значению. Узлы могут быть представлены любым из типом данных из этого списка: int, str, list, dict.
Чтобы лучше понимать, о чём идёт речь, посмотри на иллюстрации примеров ниже (визуальный порядок элементов списков важен). Если при решении задачи возникнут проблемы, задумайся над применением итеративного подхода разработки и посмотри это видео , демонстрирующее, как этот подход может применяться при решение задачи.

Входные данные: Два аргумента:

  • первый - произвольная структура данных (tree)
  • второй - целевое значение (target) , может иметь любой тип из списка int, str, list, dict

Выходные... Количество листьев дерева (или поддеревьев), соответствующих целевому значению (целое число).

tree_walker(tree=[1, "2", 3, [[3], 1, {1: "one"}]], target=1) == 2                                        #example #1
tree_walker(tree={"one": 1, "two": [{1: "one", 2: "two"}, 1, "1", "one"]}, target=1) == 2                 #example #2
tree_walker(tree={"one": [1, 2], "two": [{1: "one", 2: "two"}, [1, 2], "1", "one"]}, target=[1, 2]) == 2  #example #3
tree_walker(tree=5, target=5) == 1                                                                        #example #4

samples


You should be an authorized user in order to see the full description and start solving this mission.