How can a python program output a random result on the same data?
There is a task on pythontutor called "Pedigree: ancestors and descendants".
Condition:
Two elements in the tree are given. 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 problem, followed by the number of queries K. Each of the following K lines contains the names of two tree elements.
For each such query, output 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 is the ancestor of the other.
The introductory notes are given to it (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, there is an attempt to solve it):
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 everything would be fine, if not for the 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
Actually figured it out.
The block that I noted as problematic is a curve in itself, and the randomness of the result depends on the fact that the set that is involved in this block does not have sorting by definition and the elements are located differently each time, respectively, the cycle does not reach all the values, as I understood, and the output depends on where the element is in the set.
After all, I finished it off (I didn't peek 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, you need to use recursion in this task. I myself have been trying to solve this problem for quite a long time, also using pythontutor, and I made a very long and terrible solution(without any recursion, of course)) ) and it worked on all variants of pythontutor, then I understood the solution that pythontutor provided me with) A difficult task for me.