Нужна помощь в построении цепочки из пар чисел ⇐ Python

[Anonymous]

Я работаю над задачей AdventOfCode, день 5 (таблица лидеров уже заполнена, поэтому задавать вопросы по ней разрешено).
Настройка:
Вы получаете пары числа в формате X|Y, где X и Y представляют номера страниц. Одна из этих пар называется правилом. Это означает, что X должен быть напечатан перед Y (т. е. появиться в окончательном списке страниц именно в этом порядке). Отсюда вы также получаете списки номеров страниц, которые необходимо правильно упорядочить.
Теперь, чтобы решить проблему, мне нужно создать полный список всех номеров, содержащихся в правилах, называемый набором правил (например, [12, 10, 88, 57...]), который подчиняется всем правилам.
Для этого я перебираю все правила и затем различаю 3 случая.
1. Ни одно из чисел еще не содержится в полном наборе правил:

В этом случае я просто добавляю пару (X, Y) в конец набора правил.2. Одно из чисел уже содержится в наборе правил:

В этом случае я просто добавляю оставшееся число перед или после числа, уже существующего в наборе правил.
3. Оба числа уже содержатся, но в неправильном порядке:

Моя идея в этом случае заключалась в том, чтобы просто поменять местами два числа, что не работает для этого примера, предоставленного в комментарии. и это должно быть проблемой, мешающей работе моего кода:

rules: [1,2], [3,4], [4,1]

Использование приведенного выше алгоритма приводит к неправильному результату, когда первые два правила больше не соблюдаются:

[] -> [1,2] -> [1,2,3,4] -> [4,2,3,1]

Теперь я не знаю, что делать в случае 3, чтобы убедиться, что все остальные правила по-прежнему выполняются. Часть меня чувствует, что здесь может быть подходящий алгоритм теории графов, но я не могу его придумать.
Минимально воспроизводимый пример:
rule_chain = []
rules = [[1,2], [3,4], [4,1]]
for rule in rules:
if rule[0] not in rule_chain and rule[1] not in rule_chain: # None contained
rule_chain.append(rule[0])
rule_chain.append(rule[1])

elif rule[0] in rule_chain and rule[1] not in rule_chain: # One contained
rule_chain.insert(rule_chain.index(rule[0]) + 1, rule[1])

elif rule[0] not in rule_chain and rule[1] in rule_chain: # One contained
rule_chain.insert(rule_chain.index(rule[1]), rule[0])

else:
i_0 = rule_chain.index(rule[0])
i_1 = rule_chain.index(rule[1])
if i_0 > i_1: # Both contained
rule_chain[i_1], rule_chain[i_0] = rule_chain[i_0], rule_chain[i_1]
print(rule_chain)


Подробнее здесь: https://stackoverflow.com/questions/792 ... rs-numbers