Advent of Code: A koan

This post first appeared 12 December 2022.

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 language1 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.2

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 idea3.

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.


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


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:


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


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:


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!

  1. For example, the symbol $ is overloaded to mean:

    • Cast, as in `short$12 casts 12 to a short, or
    • Enumerate, as in x$y makes a list of enumeration indices out of y4, or
    • Parse or tok as its called in q, where "D"$"2000-01-01" parses the string as a date ("D"), or
    • Pad a string so 9$"abc" gives the string left justified with spaces to width 9, or
    • Condition like the ternary ? in c so $[x=2; `foo; `bar] is either `foo if x=2 or `bar otherwise.
    • Matrix multiplication
    Its not even my least favourite operator in q↩︎

  2. I’ve stripped out all the IO from the question. Its not that important. ↩︎

  3. A side note about this. One of the oddities of q is its evaluation order — it always evaluates right-to-left. That means that 2*3+1 = 2*(3+1) = 8. This is absurd and nobody else would do such a thing. However, it does mean that you can read the imperitive instructions easily. In the python code max(sum(input_list.split(None))), to work out what is going on, we have to start in the middle and work our way right, then left. I don’t necessarily think that q is right in this, but it is food for thought. ↩︎

  4. There isn’t the space in this blog post to explain this. Look here if you really want to know. ↩︎