Advent of Code: A koan

This year, I’m doing the Advent of Code and for career reasons I’m doing it in q.

In many ways q is a terrifying language¹ and this seemed like a good opportunity to get more experience with it.

On the first day of AoC, the problem came to be:

Find the maximum sum of a given set of lists of positive integers. The input will be a flat array of integers with None separating the lists.²

A python solution might have been

max(map(sum, input_list.split(None)))

if python had split for lists. It doesn’t but you get the idea³.

In q we can do something similar:

max sum each cut[where 0N=input_list;] input_list

This partitions the input at the indices where it is None (or 0N), sums each partition and then takes the max.

Golf

It turns out q is a good choice for playing code golf, and I like this as a golfing question.

To start, we can agree to call our input l and we’ll agree that it has the form specified above. We could write our first solution

max(sum')cut[where 0N=l;]l

where I’ve used the ' form of each. We also have only one whitespace for a total of 26 characters.

We can do better.

But first we have to rethink the problem. What if we kept the flat list? We know the numbers are all positive, so could we try keep a running total, resetting it at each 0N and take the maximum over the whole list?

In python, we’d write

from itertools import accumulate

max(accumulate(l, lambda running, x: 0 if x is None else x + running))

Luckily, q has a very brief notation for accumulate called scan or \. The lambda above could be written as the function {[running,y] $[0N=y;0;running+y]}, or after using the name x for running and then recalling that functions in q are given variables x and y without needing to declare them, we have the fantastic solution

max({$[0N=y;0;x+y]}\)l

That’s a total of 22 characters. Not bad.

We can do better though. Recall that 0N means None or null. Also, x+0N is always 0N. Finally, q has the function fill, denoted ^ that replaces null values with a default. Thankfully, it is also evaluated right-to-left so the following has the correct precidence of operations:

max({0^x+y}\)l

Now we are at 14. However, 12 is in sight: we can collapse the function to a meagre (0^+) giving us the succinct

max((0^+)\)l

And at only twelve characters, that’s where we’ll have to leave it in q.

Appendix: More. Less.

A colleage pointed out that we can do better if we discard q and use the underlying k. I won’t go into details except to show the result. Its a good koan:

k)|/(0^+)\l

We have to use the sigil k) to tell q we want to only use k and not q. I suppose with a pure k interpreter, we’d have a nine character solution — not bad!