Решение AdventOfCode для дня 5 проходит пример, но не все тестовые случаи. Мне нужна помощь в решении проблемы ⇐ Python

[Anonymous]

Я работаю над задачей AdventOfCode, день 5 (таблица лидеров уже заполнена, поэтому задавать вопросы по ней разрешено).
Настройка:
Вы получаете пары числа в формате X|Y, где X и Y представляют номера страниц. Одна из этих пар называется правилом. Это означает, что X должен быть напечатан перед Y (т.е. появиться в конечном списке страниц именно в этом порядке).
Вы также получаете так называемые «обновления», которые представляют собой списки страниц, например: 63,22,13,18,25
Теперь вопросы просят нас найти все обновления, которые не соответствуют всем правилам (т. е. нарушено хотя бы одно правило). Затем эти обновления необходимо правильно упорядочить и добавить их соответствующие средние номера. Итак, если список сверху упорядочен правильно следующим образом: 22,63,25,18,13, его среднее число будет 25.
Теперь мое решение состоит из нескольких частей.Прежде всего, я создаю два списка списков: «обновления» и «правила». Все обновления и правила затем добавляются к этим двум:

Код: Выделить всё

    updates = []
rules = []
with open("input.txt", "r") as f:
lines = f.read().splitlines()
for line in lines:
if len(line) == 5: # line contains rule
rules.append(line.split("|"))
elif len(line) != 0: # line contains update
updates.append(line.split(","))

Во-вторых, для каждого обновления я создаю словарь значений и местоположений (чтобы иметь возможность доступа к ним в постоянное время для проверки правил)

Код: Выделить всё

for update in updates:
locations = {}
for n, page in enumerate(update):
locations[page] = n

В-третьих, я проверяю, применимо ли каждое правило, а если нет, добавляю ошибочное обновление в другой список, называемый error_updates, чтобы разобраться с ним позже.

Код: Выделить всё

for rule in rules:
if rule[0] in locations and rule[1] in locations:
if not int(locations[rule[0]]) < int(locations[rule[1]]):
wrong_updates.append(update)
break

После этого создается «цепочка правил». Это означает, что я объединяю все правила в один список, содержащий числа, содержащиеся в любом правиле, в правильном порядке.

Код: Выделить всё

rule_chain = []
for rule in rules:
if rule[0] not in rule_chain and rule[1] not in rule_chain:
rule_chain.append(rule[0])
rule_chain.append(rule[1])

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

elif rule[0] not in rule_chain and rule[1] in rule_chain:
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:
rule_chain[i_1], rule_chain[i_0] = rule_chain[i_0], rule_chain[i_1]

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

Код: Выделить всё

for update in wrong_updates:
new_update = []
for n in rule_chain:
if n in update:
new_update.append(n)
middle_page = int(new_update[len(new_update) // 2])
sum += middle_page
print(f"Sum of part 2: {sum}")

Этот код работает для этого конкретного примера, но не для огромного (>1000 строк), который используется для тестирования кода на веб-сайте.

Код: Выделить всё

47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13

75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47

Я перепробовал много разных вещей и обнаружил следующее:

• Количество неправильных обновлений в error_updates верен (я сравнил его с первой частью вопроса, не упомянутого здесь)
• Похоже, что алгоритм цепочки правил работает для каждой цепочки правил, которую я разработал вручную
• Суммирование в конце всегда добавляет среднее число. Нет обновлений с повторяющимися номерами или четной длиной.

Подробнее здесь: https://stackoverflow.com/questions/792 ... es-im-in-n