Solving Advent of Code problems using range types in Postgres

I’ve been revisiting some old Advent of Code (AoC)¹ puzzles and noticed that a handful of them reduce to interval arithmetic: identifying gaps, merging intervals, detecting overlaps. Postgres range types are built for exactly that kind of problem, so I tried them out on a couple of the puzzles.

Range types

Let’s start with a quick overview of range types. The documentation covers the full type system, but the core idea is that range types represent a range of values of a given type. For example, here’s how to create a range of integers:

SELECT int4range(2, 10); -- [2,10)

This creates a range from 2 to 10, where 2 is included and 10 is excluded. Postgres supports several range types out of the box:

-- Available range types:
-- int4range: 32-bit integer ranges
-- int8range: 64-bit integer ranges
-- numrange: decimal numbers
-- tsrange: timestamps without time zone
-- tstzrange: timestamps with time zone
-- daterange: dates

-- Bounds can be inclusive [...] or exclusive (...).
-- The default is lower inclusive, upper exclusive:
SELECT int4range(1, 5);       -- [1,5)
SELECT int4range(1, 5, '[)'); -- [1,5)

-- Postgres rewrites integer ranges into the [) form, so an inclusive 5 becomes 6:
SELECT int4range(1, 5, '[]'); -- [1,6)

Several operators let you check containment, overlaps, and other relationships:

-- Containment (@>): checks if a range contains a value or another range
SELECT int4range(1, 5) @> 4; -- true
SELECT int4range(1, 5) @> 5; -- false
SELECT int4range(1, 10) @> int4range(3, 7); -- true

-- Overlap (&&): checks if ranges share any values
SELECT int4range(1, 5) && int4range(2, 7); -- true

-- upper() returns the exclusive upper bound of the range
SELECT upper(int4range(1, 5, '[]')); -- 6

Postgres provides many operators for working with range types (see the documentation for the full list), but in the examples below we’ll mainly use containment (@>) and overlap (&&).

A practical example: calendar appointments

Before jumping into the AoC problems, here’s a canonical example of range types in practice: representing calendar appointments.

CREATE TABLE appointments (
    appointment_id int GENERATED ALWAYS AS IDENTITY,
    user_id int,
    appointment_time tsrange,
    EXCLUDE USING gist (appointment_time WITH &&, user_id WITH =)
);

-- These inserts would work:
INSERT INTO appointments (user_id, appointment_time)
VALUES (1, tsrange('2024-10-24 09:00', '2024-10-24 10:00'));

INSERT INTO appointments (user_id, appointment_time)
VALUES (1, tsrange('2024-10-24 10:00', '2024-10-24 11:00'));

-- This fails due to overlap:
INSERT INTO appointments (user_id, appointment_time)
VALUES (1, tsrange('2024-10-24 09:30', '2024-10-24 10:30'));
-- ERROR: conflicting key value violates exclusion constraint "appointments_appointment_time_user_id_excl"

The table definition guarantees that each user only has one appointment at a time. Implementing the same logic using start time and duration is possible, but more awkward. The constraints on ranges section of the documentation contains more details on this pattern.

CREATE EXTENSION btree_gist;

AoC 2022 - Day 4: Containment and overlaps

Let’s start with Day 4 from 2022. The input is a list of section-assignment pairs in this format:

2-4,6-8
2-3,4-5

In part one, we count pairs where one range fully contains the other. In part two, we count pairs that overlap at all.

We can parse the input into a temporary table, then use string splitting to build the ranges. To follow along, copy the input into a file called ranges-2022.txt.

CREATE TEMP TABLE data (range1 text, range2 text);
\copy data FROM 'ranges-2022.txt' WITH (format csv, delimiter ',');

CREATE TABLE ranges (range1 int4range, range2 int4range);

-- Build inclusive ranges from the dash-separated text pairs.
INSERT INTO ranges (range1, range2)
SELECT
    int4range(
        split_part(range1, '-', 1)::int,
        split_part(range1, '-', 2)::int,
        '[]'
    ) AS range1,
    int4range(
        split_part(range2, '-', 1)::int,
        split_part(range2, '-', 2)::int,
        '[]'
    ) AS range2
FROM data;

Once the data has been parsed, both parts are straightforward. For part one, check whether either range contains the other:

SELECT count(*)
FROM ranges
WHERE range1 @> range2 OR range2 @> range1;

Part two is even simpler, since it reduces directly to an overlap check:

SELECT count(*)
FROM ranges
WHERE range1 && range2;

AoC 2016 - Day 20: Merging ranges and multiranges

Before tackling Day 20 from 2016, we need to briefly cover multiranges, which were introduced in Postgres 14. A multirange is an ordered list of non-contiguous, non-empty, non-null ranges, and you can construct one much like a normal range:

SELECT int4multirange(int4range(1, 4), int4range(7, 10)); -- {[1,4),[7,10)}

You can also build multiranges with the range_agg aggregate, which combines multiple ranges into a single multirange:

SELECT range_agg(r)
FROM unnest(ARRAY[int4range(1, 3), int4range(2, 4), int4range(8, 10)]) r;
-- {[1,4),[8,10)}

Now let’s use that to solve Day 20. The input is a list of blocked IP ranges:

5-8
0-2
4-7

Part one asks for the lowest-valued IP that is not blocked. Part two asks for the total number of IPs that are not blocked.

Parsing the data is similar to the previous example. Here we use int8range to avoid overflow issues:

CREATE TEMP TABLE data (range text);
\copy data FROM 'ranges-2016.txt' WITH (format csv, delimiter ',');

CREATE TABLE ranges (ip_range int8range);

INSERT INTO ranges (ip_range)
SELECT
    int8range(
        split_part(range, '-', 1)::bigint,
        split_part(range, '-', 2)::bigint,
        '[]'
    )
FROM data;

For part one, we can merge the blocked ranges with range_agg, unnest the resulting multirange into individual ranges, and then use upper to get the first unblocked value. This only works because the lowest blocked range in the puzzle input starts at 0, so the first unblocked IP lies after a blocked range rather than before it.

SELECT upper(unnest(range_agg(ip_range))) AS first_unblocked_ip_after_block
FROM ranges
ORDER BY 1
LIMIT 1;

To compute the total number of unblocked IPs, we can:

1. Start with the full range of possible IPs ([0, 4294967295])
2. Subtract the blocked ranges with the - operator
3. Sum the sizes of the remaining ranges

In SQL, that looks like this:

-- Unblocked IPs: subtract the aggregated blocked ranges from the full IPv4 space.
WITH missing (r) AS (
    SELECT unnest(
        '{[0, 4294967295]}'::int8multirange - (SELECT range_agg(ip_range) FROM ranges)
    )
)

SELECT sum(upper(r) - lower(r))
FROM missing;

Pretty neat. The fiddliest part was parsing the input, which is always a little awkward in SQL. But once the data was parsed into range types, Postgres’s built-in functions handled most of the real work for us.