Day 5’s input is broken up into two parts. Part 1 lists a series of “rules”. Each rule is a single line and is made up of two integers, separated by a pipe (“|”). The rule indicates that the first integer must be before the second integer in order for the series of pages to be valid. It’s important to remember that the actual value of the first and second integers doesn’t matter at all. It is perfectly ok to say that 61 comes before 29 (i.e. 61|29).
The input then has a double line break followed by a series of book pages. Each series of pages consists of two or more comma separated integers. The challenge is to find the number of lines where the pages are listed in order according to the above rules. Using the example above if in the list of pages it goes 29, 61, …. the series in invalid. However if the series goes 61, 14, 29, …. the series is valid (at least as far as that particular rule goes).
To try and make the checks work a little bit faster, I only wanted to run the checks that were necessary as opposed to cycling through all of them each time. This started when I was parsing the input. My rules variable was Default Dict which defaults to a list. As I was parsing the rules part of the input, I would split the line, and use the left integer as the key to the dictionary, and append the right value to the list under that key.
with open(path.join(path.dirname(__file__), 'input.txt'), 'r') as f:
for line in f:
line = line.strip()
if len(line) == 0:
rule = False
if rule:
line = line.split("|")
rules[line[0]].append(line[1])
As I am checking to see if the series of pages is valid, I cycle through each item in the series and pull the rules that relate to that particular page number (using that page number as the key). Then I cycle through each rule and check to see if that corresponding page number in the rule is in the series as well. If it is, I get the index for both items and compare to make sure that they are in the right order.
def validate_update(rules, update):
for page in update:
the_rules = rules[page]
cur_page = update.index(page)
for rule in the_rules:
if rule in update:
i = update.index(rule)
if not cur_page < i:
return False
return True
Part 2
The second part has us “fix” the page series that are incorrect. We of course start by checking to see if the current series we’re looking at is already valid. Assuming it isn’t then we start to correct it. To correct it, we pretty much do the same thing we’re doing when we validate it ( cycle through each item in the list and see if it is in the right relative position. If/when we find one that isn’t in the right spot, we pop it out, and re-insert it to the left of the item in rule. Then we start over, at the start of the list. This keeps going until we make it all the way through without finding a mistake.
def correct(rules, update):
i = 1
while i < len(update):
the_rules = rules[update[i]]
for rule in the_rules:
if rule in update:
if i > update.index(rule):
tmp = update.pop(update.index(rule))
update.insert(i, tmp)
i = 1
break
i += 1
return update
I’m sure that there are more efficient ways to do it but this is definitely one of those cases where perfection is the enemy of good enough. You can see my full code on Github.