Advent of Code 2024 - Day 5: Print Queue

:: programming, python, puzzle

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
 
from advent import parse, ints, mapt, defaultdict, cmp_to_key

rules, updates = parse(5, lambda s: mapt(ints, str.split(s)), sep='\n\n')
order_dict     = defaultdict(set)
for p1, p2 in rules: order_dict[p1].add(p2)

is_ordered = lambda t: list(t) == sort_pages(t)
middle     = lambda t: t[len(t) // 2]
sort_pages = lambda t: sorted(t, key=cmp_to_key(lambda a, b: -1 if b in order_dict[a] else 1))

assert sum(middle(t) for t in updates if is_ordered(t)) == 6949 # Part 1

assert sum(middle(sort_pages(t)) for t in updates if not is_ordered(t)) == 4145 # Part 2

Parsing

Today’s input comes in two parts. First, a list of rules of the form:

96|54
79|47
79|13
69|79
69|67
...

Each rule consists of a pair of numbers (before, after) which indicate page before must come before page after when printed.

Second, a lilst of updates of the form:

78,18,57,52,59,14,87,53,15,28,94
55,88,31,49,93,59,53,13,46,57,86,43,15,18,78,94,52,27,14
33,19,35,67,62,21,47
49,93,59,53,13,64,46,57,15,94,27,96,69
47,31,57,86,78,14,37
...

Each update is a list of pages to be printed.

Our parse() function accepts a separator, sep, argument. Specifying sep='\n\n' will split the input into two tuples, one for rules, one for updates. Each of the two sections will be a single string with newline characters. We want a tuple of integers for each rule and update, so we first split into separate lines, and then map the ints function over each line to obtain a tuple of integers:

1
 
rules, updates = parse(5, lambda s: mapt(ints, str.split(s)), sep='\n\n')

Prerequisites

The key element of today’s puzzle is to be able to properly order the pages in an update. To do this, we need a predicate to indicate whether one page is less than another page. To represent the ordering information, we’ll create a dictionary where the key is a page number, and the value is a set of page numbers that must come after the key page number.

To simplify the logic of dealing with the first addition to the set vs. subsequent additions, we’ll use a defaultdict(set). This will allow us to add the first page to the set without having to first create the set. Then we load the dictionary from the rules:

1
2
 
order_dict = defaultdict(set)
for p1, p2 in rules: order_dict[p1].add(p2)

Next we need a function to sort pages according to the ordering information in the dictionary. Python’s sorted() function accepts a key, but we want to use a comparator i.e. a predicate that accepts two pages and indicates if the first is less than the second. Fortunately, functools.cmp_to_key() can convert a comparator into a key function:

1
 
sort_pages = lambda t: sorted(t, key=cmp_to_key(lambda a, b: -1 if b in order_dict[a] else 1))

With that in place, we can create an is_ordered() predicate which simply compares the original tuple to the sorted tuple:

1
 
is_ordered = lambda t: list(t) == sort_pages(t)

We’ll need another helper to return the middle page of a tuple:

1
 
middle = lambda t: t[len(t) // 2]

Part 1

With the prerequisites in place, part 1 is simple. Generate & sum() the middle page for each ordered update:

1
 
sum(middle(t) for t in updates if is_ordered(t))

Part 2

For part 2, we need to fix the unordered updates by sorting them. Part 2 is very similar to part 1, except we negate the filter, and we sum the middle of the sorted pages:

1
 
sum(middle(sort_pages(t)) for t in updates if not is_ordered(t))

New Python Concepts

  • ’defaultdict`
  • // divfloor operator
  • functools.cmp_to_key()
  • str.split()

Conclusion

Python has been very productive for Advent of Code thus far. I’m looking forward to the remaining puzzles!