Since starting my new job I’ve been using KDB and thus q, the programming language the KDB database uses. Now in an attempt to stop being an advanced beginner I’m using q for this year’s Advent of Code.


Enjoy these types of posts? Then you should sign up for my newsletter.


Advent of Code is a yearly programming challenge where each day you are set two puzzles to complete. Each puzzle has an input file and you need to do some programming to get to the answer. It starts easy, but the difficulty ramps up and it is a good way to flex your programming skills.

Last year I did a few of the days in Java and it was a complete horror story. Java is not a pick-up-and-play language, there was so much boilerplate code around each of the solutions I gave up pretty quickly. But Dean, why did you choose Java? I thought I would be using Java in my new job more, so far I’ve only had to edit a few lines, so that was a wasted effort!

I do use q every day though so this is how I’m trying to get better at this array language. I’ll be explaining my solutions so any new q people also have a chance of (hopefully) learning something.

Day 1 - Calorie Counting

You have a list of integers grouped via blank lines. You need to calculate the sum of each group and find both the maximum and the sum of the largest three groups.

inp: "I"$read0 `$"input1";
ml: where a = 0N;
f: {sum x[y _til z]};
res: {[i] f[inp; 0^ml[i-1]; ml[i]]} each til count ml;
(1#desc res), (sum 3#desc res)

inp is where we store the data read from the file “input1” and convert it to integers. This returns an array of our data. We use the $ function to convert the string into a symbol and the strings into integers "I"$.

ml finds the indexes where there is a number missing (0N). This is our group separator as each line with a missing number breaks up the different elves.

f is the function that sums each group by selecting between each missing index. The y_ til z lets you index the array from y to z. In python, it would be the same as x[y:z].

res is where we apply the function to each index of the missing arrays. Iterating through the ml indexes we just need to make sure we replace the ml[-1] statement with 0 using the ^ operator.

And the last line is where we return both the max and the sum of three largest groups.

So all in, a pretty simple task for q. It’s a simple input file that doesn’t need complicated parsing and we can write a simple function to iterate through each group.

After posting this on Reddit a user made a good comment that each solution should take in the read0 output and produce the answer. I took that advice doing forward.

Day 2 - Rock, Paper, Scissors

Next up we are trying to solve some rock, paper scissor (RPS) problems. We are given a file where each line represents an RPS match and we have to score the match based on the outcome and what value we chose.

This file needed a little bit of parsing. It’s a space-separated file where the first column is your opponent’s choice and the second column is your choice. We iterate through each line, split on the space " " vs x and create a dictionary that all collapses into a final table nicely.

inp: read0 `input_2.txt;
inpClean: {`a`b!`$" " vs x} each inp;

Now to solve the first part, we just have to classify whether its a win or a loss. Forgive me for my sins, but I just brute force it.

score_1:{[b]
    score: `X`Y`Z!1 2 3;
    remap: `X`Y`Z!`A`B`C;

    b: update score: score@b, b2: remap@b from b;
    b: update res: 3 from b where a = b2;
    b: update res: 0 from b where a = `A, b2 = `C;
    b: update res: 0 from b where a = `B, b2 = `A;
    b: update res: 0 from b where a = `C, b2 = `B;

    b: update res: 6 from b where b2 = `A, a = `C;
    b: update res: 6 from b where b2 = `B, a = `A;
    b: update res: 6 from b where b2 = `C, a = `B;

    b: update res: 3 from b where a = b2;

    b: update final_score: score + res from b;

    show select sum final_score from b

};
score_1[b]

The score dictionary and remap dictionary use the @ operator to map to each value of b, it’s an easy left-join. Then from then on we just use the SQL command to annotate whether it was a win loss or a draw.

And for the second part, you find out the input file is telling you whether you should win, lose or draw. You need to work out which RPS to choose for each round and again work out the final score. Pretty much the same as the above, but working backward.

score_2:{[b]
    score2: `A`B`C!1 2 3;
    score: `X`Y`Z!0 3 6;
    remap: `X`Y`Z!`A`B`C;

    b: update score: score@b from b;

    b: update b2: a from b where score = 3;

    b: update b2:`C from b where a = `A, score = 0;
    b: update b2:`A from b where a = `B, score = 0;
    b: update b2:`B from b where a = `C, score = 0;
    
    b: update b2:`B from b where a = `A, score = 6;
    b: update b2:`C from b where a = `B, score = 6;
    b: update b2:`A from b where a = `C, score = 6;
    
    b: update score2: score2@b2 from b;
    b: update final_score: score + score2 from b;
    :b
    };

show select sum final_score from score_2[b]

Again, some remapping and where clauses sorts it all out.

This is not the most efficient way of solving this, but alas, onto the next one!

Day 3 - Rucksack Reorg and Letter Priority

Next up was a simpler input format, which always makes me happy. Each line contained a string the first half represented one compartment of a rucksack and the second half of the string the other compartment. You have to find out which item is repeated in each compartment. An item was represented via a lowercase or uppercase letter. We need to sum up the priority of all the repeated letters across the string.

First, we create the priority object that uses the .Q namespace to get the list of all the letters and make a table with the priority for each letter.

priority: (.Q.a, .Q.A)!(1 + til 52);

We then need to go through each line of the input file, find out how long it is using count and then divide that by two (or multiply by 0.5).

The inter function returns a common character between two strings, so we select the first and second half of the string (n#a and neg n#a). This means finally we use the priority dictionary to pull out the value of the letter.

gr:{[a]
    n: "i"$0.5*(count a);
    res: first (((neg n)#a) inter (n#a));
    :priority@res
    };
dt: read0 `:input_3.txt
sum gr each dt

Sum the function across the input and we get our answer.

For part two we now have to find the common letter between the three consecutive lines rather than just one line.

Again, inter does all the heavy lifting and we use the / function to consecutively apply the inter function on the first two elements, then the result of that to the next element. A bit like a map reduce. The result gives us the common letter which we just use to pull out the correct element of the priority dictionary.

badge:{[elvs]
       res: first (inter/) elvs;
       :priority@res
    };

dt: read0 `:input_3.txt
sum {badge[dt[(x*3) + til 3]]} each til ("i"$((count dt)%3))

Again, just a little bit of iteration around pulling three lines at a time.

This was a nice problem that I feel I solved quite elegantly using the power of q.

Day 4 - Cleaning Overlap

Next up we are looking at whether two integer sequences overlap each other. Each row provides two start and two end numbers and we have to deduce whether one of the ranges fully contains the other range.

For this problem, we need a q function that can produce an integer sequence from mn to mx:

seq:{[mn; mx]
    :(mn - 1) _ (1 + til mx)
    };

We then parse each line by first replacing the comma and hyphen with a space (ssr[a0; "[,-]"; " "]) and then splitting by the space.

We create each of the sequences and check if all of the values are in either sequence.

overlap:{[a0]

    ints: "J"$ " " vs ssr[a0; "[,-]"; " "];

    res1: seq[ints[0]; ints[1]];
    res2: seq[ints[2]; ints[3]];

    :(all res1 in res2)|(all res2 in res1)
    };
dt: read0 `:input_4.txt;
sum overlap each dt

Then part two was just about whether any of the elements overlapped each other. So this is just replacing all with any and we get the correct result. Simple!

Day 5 - TBD

Day 5 is where the input started to get more complicated and I found myself spending more time wrangling the input rather than solving the problem. Plus I went back to work and thus the free time disappeared!

Conclusion

So that’s it. Four days of Advent of Code in q. Hopefully a useful applied intro to the language that is a bit different from the usual. Or perhaps a horrible display of how not to use q? Who knows!

If you want to read some proper solutions to the problems there is this Github: https://github.com/qbists/studyq/tree/main/aoc/2022 where proper q programmers solve the problems in much fewer lines and much more elegantly than me. Still much more work on my side to progress beyond an advanced beginner.

Happy Christmas people!