Tutorial Instructions

Advent of Code - Day 4

AOC Day 4

This challenge was actually simpler than the previous day's ones, as we were able to lean heavily on some Postgres features such as:

  • file_fdw, a built-in foreign data wrapper for Postgres
  • The function split_part()
  • The int4range data type
  • The range operators @> <@ and &&

For Day 4, we are given a text file containing two ranges of numbers on each line, like so:

71-89,66-70
24-70,23-55
19-85,18-86
50-90,50-95
55-55,56-72
3-65,5-66
98-99,66-99
14-67,14-14
4-79,78-79
13-98,10-98

Part one of the puzzle asks us to see which of the lines has one range of numbers completely inside another one. In other words, either all the numbers in the left range are contained by the numbers in the right range, or vice-versa.

This one was very easy, for Postgres contains support for doing operations such as seeing if one group of things is inside another. As these are ranges of integers, it seemed best to turn these into int4range columns, in which we only provide the start and stop values. 

SELECT * FROM aoc_day4 LIMIT 10;

   a   |   b
-------+-------
 71-89 | 66-70
 24-70 | 23-55
 19-85 | 18-86
 50-90 | 50-95
 55-55 | 56-72
 3-65  | 5-66
 98-99 | 66-99
 14-67 | 14-14
 4-79  | 78-79
 13-98 | 10-98

Next we need to change each of those rows into an actual range of integers. We will use the int4range() function to do this, which expects a bottom range, and a top range. Because the puzzle also contains items such as 6-6, we also need to tell the int4range() function that we want our edges to be inclusive, which we can do by giving a third argument of []:

SELECT a, b,
  int4range(split_part(a,'-',1)::int, split_part(a,'-',2)::int, '[]') AS aa
  ,int4range(split_part(b,'-',1)::int, split_part(b,'-',2)::int, '[]') AS bb
FROM aoc_day4 LIMIT 10;

   a   |   b   |    aa    |    bb
-------+-------+----------+----------
 71-89 | 66-70 | [71,90)  | [66,71)
 24-70 | 23-55 | [24,71)  | [23,56)
 19-85 | 18-86 | [19,86)  | [18,87)
 50-90 | 50-95 | [50,91)  | [50,96)
 55-55 | 56-72 | [55,56)  | [56,73)
 3-65  | 5-66  | [3,66)   | [5,67)
 98-99 | 66-99 | [98,100) | [66,100)
 14-67 | 14-14 | [14,68)  | [14,15)
 4-79  | 78-79 | [4,80)   | [78,80)
 13-98 | 10-98 | [13,99)  | [10,99)

The output of those last two columns looks a little weird, but it does represent exactly the range we want: inclusive of the "lower bound" number as represented by a left bracket [, and exclusive of the "upper bound" number, as shown by a right parenthesis ).

Postgres has a lot of support for doing things with ranges, including precisely what the puzzle is asking for, which is determining if one range fits completely into another one. For that, we will use the built-in @> and <@range functions, which test if a left range contains the second, and if the left range is contained by the second. Both of these return true or false, so we get this:

WITH q AS (
  SELECT a, b,
    int4range(split_part(a,'-',1)::int, split_part(a,'-',2)::int, '[]') AS aa
    ,int4range(split_part(b,'-',1)::int, split_part(b,'-',2)::int, '[]') AS bb
  FROM aoc_day4
)
SELECT *, aa @> bb AS l, aa <@ bb AS m FROM q LIMIT 10;

   a   |   b   |    aa    |    bb    | l | m
-------+-------+----------+----------+---+---
 71-89 | 66-70 | [71,90)  | [66,71)  | f | f
 24-70 | 23-55 | [24,71)  | [23,56)  | f | f
 19-85 | 18-86 | [19,86)  | [18,87)  | f | t
 50-90 | 50-95 | [50,91)  | [50,96)  | f | t
 55-55 | 56-72 | [55,56)  | [56,73)  | f | f
 3-65  | 5-66  | [3,66)   | [5,67)   | f | f
 98-99 | 66-99 | [98,100) | [66,100) | f | t
 14-67 | 14-14 | [14,68)  | [14,15)  | t | f
 4-79  | 78-79 | [4,80)   | [78,80)  | t | f
 13-98 | 10-98 | [13,99)  | [10,99)  | f | t

Now it's just a matter of counting up how many rows satisfy either condition:

WITH q AS (
  SELECT a, b,
    int4range(split_part(a,'-',1)::int, split_part(a,'-',2)::int, '[]') AS aa
    ,int4range(split_part(b,'-',1)::int, split_part(b,'-',2)::int, '[]') AS bb
  FROM aoc_day4
)
,r AS (SELECT *, aa @> bb AS l, aa <@ bb AS m FROM q)
SELECT count(*) FROM r WHERE l OR m;

 count
-------
     573

Done with part one! For part two, we need to get a count, but now we need to know how many of the two sections overlap at all. This was a three-second solve, as Postgres also has an overlaps operator, so we simply replace our containment operators with the overlaps operator && :

WITH q AS (
  SELECT a, b,
    int4range(split_part(a,'-',1)::int, split_part(a,'-',2)::int, '[]') AS aa
    ,int4range(split_part(b,'-',1)::int, split_part(b,'-',2)::int, '[]') AS bb
  FROM aoc_day4
)
,r AS (SELECT *, aa && bb AS yes_overlap FROM q)
SELECT count(*) FROM r WHERE yes_overlap;
 count
-------
     867

That's the end! Onwards to Day 5...

Loading terminal...

Loading terminal...