Advent of Code 2024, day 1, in ClickHouse SQL

Advent of Code 2024 started with a puzzle that looks designed for arrays. You get two lists of numbers, one per column of a text file. Pair the smallest number in the left list with the smallest in the right, the second smallest with the second smallest, and so on. The distance of each pair is the absolute difference; the answer is the sum of the distances.

The sample input from the puzzle:

The expected answer is 11. The two lists are 3 4 2 1 3 3 and 4 3 5 3 9 3; sorted, they are 1 2 3 3 3 4 and 3 3 3 4 5 9; the pair distances are 2, 1, 0, 1, 2, 5, and they sum to 11.

The solution below is one SELECT. It was run with clickhouse local 26.4, with the sample saved as aoc.txt.

Getting the input in

The puzzle input is plain text, three spaces between the numbers. Read each line as one string column named c1:

CREATE TABLE input1 (c1 String) ENGINE = Memory;
INSERT INTO input1 SELECT line FROM file('aoc.txt', 'LineAsString', 'line String');
SELECT * FROM input1;

The LineAsString format puts every line, untouched, into a single string. You do not need to define the table: file('aoc.txt', 'LineAsString', 'c1 String') is enough if you substitute it for input1. A table is just convenient while experimenting, because the same name can be queried many times.

Step 1: split each line into two numbers

SELECT
    splitByString('   ', c1) AS cs,
    CAST(cs[1], 'Int64') AS left,
    CAST(cs[2], 'Int64') AS right
FROM input1;

['3','4']	3	4
['4','3']	4	3
['2','5']	2	5
['1','3']	1	3
['3','9']	3	9
['3','3']	3	3

splitByString(' ', c1) splits on the exact three-space separator and gives an array of two strings. ClickHouse arrays are 1-indexed, so cs[1] and cs[2] are the two columns, and CAST(..., 'Int64') turns them into numbers. Notice that left and right are also names of string functions, and ClickHouse is happy to let you reuse them as aliases. Aliases can be used by the expressions that follow them in the same query, which is what lets us write the three definitions as a WITH list and keep the SELECT clean.

Step 2: one row of arrays per list

The trick of the whole solution is to stop thinking in rows. Aggregate each column into an array, then sort the arrays:

WITH
    splitByString('   ', c1) AS cs,
    CAST(cs[1], 'Int64') AS left,
    CAST(cs[2], 'Int64') AS right
SELECT
    arraySort(groupArray(left)) AS la,
    arraySort(groupArray(right)) AS ra
FROM input1;

[1,2,3,3,3,4]	[3,3,3,4,5,9]

groupArray collects all values of a column into one array; arraySort sorts it. The two columns are sorted independently, which is exactly what the puzzle asks. The query now returns a single row with two arrays of the same length.

Step 3: zip with ARRAY JOIN

ARRAY JOIN turns arrays into rows. When you list several arrays of the same length in one ARRAY JOIN, they are unrolled in parallel, so the first elements pair up, then the second elements, and so on. That is the pairing the puzzle wants:

SELECT la, ra, abs(la - ra) AS distance
FROM (SELECT [1, 2, 3, 3, 3, 4] AS la, [3, 3, 3, 4, 5, 9] AS ra)
ARRAY JOIN la, ra;

Six rows: the distances 2, 1, 0, 1, 2, 5. (Here I typed the two arrays in by hand to show the step in isolation.) A different join would have been a mistake: the two lists have no key, only a position.

The whole solution

Putting the steps together, with sum on the outside:

SELECT sum(distance)
FROM
(
    SELECT
        la,
        ra,
        abs(la - ra) AS distance
    FROM
    (
        WITH
            splitByString('   ', CAST(c1, 'String')) AS cs,
            CAST(cs[1], 'Int64') AS left,
            CAST(cs[2], 'Int64') AS right
        SELECT
            arraySort(groupArray(left)) AS la,
            arraySort(groupArray(right)) AS ra
        FROM input1
    )
    ARRAY JOIN
        la,
        ra
);

That is the expected answer for the sample. For the real puzzle, replace the sample file with your input; the query does not change.

The same thing without ARRAY JOIN

ARRAY JOIN is one way to pair two arrays. arrayMap with a two-argument lambda is another, and it removes the subquery: the lambda receives the matching element of each array.

WITH
    splitByString('   ', c1) AS cs,
    CAST(cs[1], 'Int64') AS left,
    CAST(cs[2], 'Int64') AS right
SELECT arraySum(arrayMap((l, r) -> abs(l - r), arraySort(groupArray(left)), arraySort(groupArray(right)))) AS total
FROM input1;

Both forms return 11. I prefer ARRAY JOIN while exploring, because you can stop at any step and look at the pairs, and the lambda form when the result is the only thing you want.

Part two, as an exercise

Part two of the puzzle asks for a similarity score: for each number in the left list, multiply it by how many times it appears in the right list, then add everything up. The source solution for this post covers part one only, so this version is mine, written for the article. It reuses the same idea (collect into arrays) and countEqual, which counts occurrences of a value in an array:

WITH
    splitByString('   ', c1) AS cs,
    CAST(cs[1], 'Int64') AS left,
    CAST(cs[2], 'Int64') AS right
SELECT sum(l * countEqual(rs, l))
FROM (SELECT groupArray(left) AS ls, groupArray(right) AS rs FROM input1)
ARRAY JOIN ls AS l;

31 is the sample answer for part two in the puzzle text.

What this shows

Advent of Code puzzles are not what ClickHouse is for, but they are a good way to learn the array toolbox, which is genuinely useful for real data. The points to take away: groupArray is how you leave row-land and ARRAY JOIN is how you come back; sort-then-pair is a position-based join and wants parallel ARRAY JOIN, not a key; and WITH aliases keep a multi-step transformation readable in a single statement. For a longer treatment, see arrays and ARRAY JOIN, and for running a script like this against files without a server, running SQL scripts in batch.