I'm working on the AdventOfCode Problem Day 5 (Leaderboard is already full, so asking questions about it is allowed). The setup: You get pairs of numbers in the format X|Y where X and Y represent page numbers. One of these pairs is called a rule. That means that X should be printed before Y (i.e. appear in the final list of pages in that order). From there you also receive lists of page numbers to be ordered correctly. Now, to solve the problem I have to build a full list of all numbers contained in rules, called a ruleset (e.g. [12, 10, 88, 57...]) that obeys all the rules. To do this, I loop through all the rules and then differentiate 3 cases. 1. None of the numbers are already contained in the full ruleset: In this case, I just add the pair (X, Y) to the end of the ruleset. 2. One of the numbers is already contained in the ruleset: In this case, I just add the remaining number in front of, or behind the one already existing in the ruleset. 3. Both of the numbers are already contained, but in the wrong order: My idea in this case was to just swap the two numbers, which does not work for this example provided by a comment and should be the issue preventing my code to work: rules: [1,2], [3,4], [4,1] Using the algorithm above, this leads to a wrong result where the first two rules are not adhered to anymore: [] -> [1,2] -> [1,2,3,4] -> [4,2,3,1] Now, I am not sure what to do in case 3 to ensure that all other rules are still met. A part of me feels like there would be a fitting graph theory algorithm here, but I cannot come up with one. Minimum reproducible example: 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) Continue reading...
