There is a task for the pythontutor called "Pedigree: Ancestors and Descendants."

Condition:
Given two items in the tree. Determine whether one of them is a descendant of the other.
The input data contains a tree in the same format as in the previous task. Next comes the number of queries K. Each of the following K lines contains the names of two tree elements.
For each such query print one of three numbers: 1, if the first element is the ancestor of the second, 2, if the second is the ancestor of the first, or 0, if neither of them is the ancestor of the other.

To her given introductory (src_data.txt):

9 Alexei Peter_I Anna Peter_I Elizabeth Peter_I Peter_II Alexei Peter_III Anna Paul_I Peter_III Alexander_I Paul_I Nicholaus_I Paul_I 3 Anna Nicholaus_I Peter_II Peter_I Alexei Paul_I

There is a code (well, that is, an attempt to solve):

 def input(): return rows.pop(0) rows = [] file = open('src_data.txt', 'r') for line in file: rows.append(line[:-1]) # ======== Досюда это имитация ввода на PythonTutor === names = set() tree = [] for _ in range(int(input()), 1, -1): child, parrent = input().split() tree.append([child, parrent]) names.update([child, parrent]) for name in names: for item in tree: if name == item[0]: for i in range(len(tree)): if name == tree[i][-1]: tree[i].append(item[1]) # === Собственно проблема вот этом блоке (который выше) == # === Он то формирует списки как нужно, то недовставляет элементы == res_row = [] for _ in range(int(input())): pers_1, pers_2 = input().split() res = '0' for branch in tree: if pers_1 in branch and pers_2 in branch: if branch.index(pers_1) > branch.index(pers_2): res = '1' else: res = '2' res_row.append(res) print(' '.join(res_row))

And all would be nothing if it were not for random values ​​in the output:

 for i in {1..40}; do python3 first.py; sleep 1; done 0 2 0 0 2 0 0 2 0 1 2 0 0 2 0 1 2 0 1 2 0 0 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 0 2 0

Please explain how this can be and what is the error?

    2 answers 2

    Actually figured out. The block I noted as problematic in itself is a curve, and the randomness of the result is that the set that is involved in this block has no sorting by definition and the elements are arranged differently each time, so the cycle does not reach all values, as I understand it, and on what place in the set is the element depends on the output.

    So I finished it (I did not look at the developers myself) :-)).

     def family(p: list, main_dict: dict): if p[-1] not in main_dict: return p return family(p + main_dict[p[-1]], main_dict) ancestors = {x: [y] for x, y in [input().split() for _ in range(int(input()) - 1)]} for child, parent in ancestors.items(): ancestors[child] = family(ancestors[child], ancestors) for child, parent in ancestors.copy().items(): if parent[0] not in ancestors: ancestors[parent[0]] = ancestors.get(parent[0], list()) relatives = [] for _ in range(int(input())): kinsman_1, kinsman_2 = input().split() if kinsman_1 in ancestors[kinsman_2]: relatives.append(1) elif kinsman_2 in ancestors[kinsman_1]: relatives.append(2) else: relatives.append(0) print(*relatives)

      Don't forget to make file.close () after file = open (***) and, by the way, recursion should be used in this task. I myself tried for a long time to solve this problem also on the pythontutor, made a very long and terrible solution (without any recursion naturally))) and it worked on all pythontutor variants, then I understood the solution that the pythontutor provided me) The difficult task for me.

      • one
        I honestly brain swollen from this task. - Andrey
      • Here now, I also sat with a swollen head, after a heap of attempts to solve) The task is not an easy one - fedotsoldier