Today we play with sort functions and explore neat tricks in the match-case.

What is Advent of Code?

In this little series, I want to write about the thought processes I have behind solving the puzzles presented in Advent of Code.

During the Advent of Code small coding puzzles are presented with varying levels of difficulty. They're always Christmas-themed text puzzles where you help elves out of some mess to save the holidays. The puzzles are deliberately ambiguous to not bias puzzlers into a certain solution, they always have an example input in the text to explain some details and an input file for each day that comes in the form of a text file you can download. The solution is a simple number or a string you enter, which is checked by the website automatically. After you finish part 1, part 2 unlocks, which is a variation on part 2. This can be a little twist on part 1 or a large twist that changes the problem formulation into a problem that would take brute force solutions to compute longer than the heat death of the universe would take.

Find my solutions here: github.com/JesperDramsch/advent-of-code

These descriptions won't be a perfect narrative, but rather how I think about these problems and where I see different solutions. I apologise for the possibility of rambling!

The example input

Looks like we're parsing pairs today!

[1,1,3,1,1]
[1,1,5,1,1]

[[1],[2,3,4]]
[[1],4]

[9]
[[8,7,6]]

[[4,4],4,4]
[[4,4],4,4,4]

[7,7,7,7]
[7,7,7]

[]
[3]

[[[]]]
[[]]

[1,[2,[3,[4,[5,6,7]]]],8,9]
[1,[2,[3,[4,[5,6,0]]]],8,9]

But how do we do this safely without eval?

The implementation

Well... Python knows us.

Python knows that sometimes you get a datastructure as a string and there is nothing more gruesome than manually parsing a data structure that maps 1-to-1 to a Python structure.

So we simply import literal_eval from ast which is in the standard Python repertoire.

Remember kids: Don't blindly execute code you download from the internet!

The literal_eval function checks the string before evaluating, and will only permit standard data types.

I think it's quite cool that we are working through lists and integers. In fact, we can use a match - case statement here!

Yes, this is a match-case fan-page now.

We can use match, to execute code according to type!

def compare(left, right):
    # Match types
    match left, right:
        case int(), int():
            pass
        case list(), list():
            pass

Dope right?!

So now we simply implement the logic!

The integers are easy, we have 3 state, lower, equal, and higher. So calculating the difference gives us a nice check-able below, equal, and higher than 0.

case int(), int():
    return left - right

The we go for the lists. This is where the recursion starts where the recursion starts.

Simply zip together the lists and compare the items. Here the power of the difference shines, since the 0 is boolean-ish in Python, that value isn't returned, either going to the next iteration, or if we're out of items.

When we run out of items, we have to know whether it's the fault of the left or right part. Now we can simply feed that into our compare function, to re-use the integer logic of the compare function.

case list(), list():
    for items in zip(left, right):
        out = compare(*items)
        if out:
            return out
    return compare(len(left), len(right))

But now that we have some recursion, we need some more recursion some more recursion.

When the types don't match, we upcast integers to lists. Then we can simply feed it back to the compare logic to figure out the rest.

case int(), list():
    return compare([left], right)
case list(), int():
    return compare(left, [right])

Then it's time to filter the result and sum:

sum(i for i, outcome in enumerate(day.data, 1) if compare(*outcome) < 0)

I used two steps for this before, writing out a tuple of the index and the results of compare(*outcome) but that somehow made it less readable.

Also notice the lovely 1 in enumerate() again, which sets the starting number. So neat I learned about that!

Part Deux

So this one is sorting all items.

Do I actually implement a sort for this? Maybe we can hack Python to do our bidding...

We also have an additional "distress signal"

[[2]]
[[6]]

We can!

I read the wrong Python documentation first, working with Python 2. But one error later, I found cmp_to_key in functools here which can be used the supply a pair-wise compare function, like the one we implemented, into a key function!

So it's really just this one:

sorted_list = sorted(flat, key=cmp_to_key(compare))

and then find the index (1-based!) of the distress signal:

[i for i, item in enumerate(sorted_list, 1) if item in distress]

Not too bad!

Error Log

A couple problems here, a couple there, but overall I think this was going quite alright.

• def main(day, part=1): IndentationError: expected an indented block after function definition on line 4 Good ol' suddenly working on a different idea and forgetting a pass
• indices = [i, compare(outcome) for i, outcome in enumerate(day.data)] SyntaxError: did you forget parentheses around the comprehension target? Yes I did.
• indices = [(i, compare(outcome)) for i, outcome in enumerate(day.data)] TypeError: compare() missing 1 required positional argument: 'right' Whoops. *outcome
• raise ValueError(msg + f': {node!r}') ValueError: malformed node or string: [4, 3, 4, [2]] forgot to escape the string evaluation in a recursive function.
• if value in {u"", b"", None, b"None", u"None"}: TypeError: unhashable type: 'list' forgot to actually do the math.
• return sum(i[0] for i in indices if i[1]]) SyntaxError: closing parenthesis ']' does not match opening parenthesis '(' Hello autocomplete...
• wrong answer: 662 oh no. Off by one!
• return sorted(day.data, cmp=compare) TypeError: 'cmp' is an invalid keyword argument for sort() It helps reading the documentation for Python 3 instead of 2...
• return sorted([item for sublist in day.data for item in sublist], key=compare) TypeError: compare() missing 1 required positional argument: 'right' ok... this time actually read the full paragraph and import cmp_to_key() from functools facepalm