Advent of Code 2020: "Encoding Error" - Day 9

Uh oh, either the ice cream at the airport was bad, or the cocktails are not good for you! How else can you explain that you hack the airplane systems with some paperclips and break the XMAS encryption, while the plane is airborne? The plane’s on-board systems emits some cryptic numbers and your task is it to decrypt this. Wait, did I say task? Who gave this task to you? Oh well, please be careful, if you shorten a circuit you might as well crash your own plane.

Task 1: 25 numbers, followed by more numbers. The first 25 are the initial set, in the following numbers if you add two of the last 25 numbers the result might be he current number. You have to find the first one which is not the sum of two of the previous 25 numbers.

Tast 2: Now that you found the first number which does not add up, find a contiguous set of two or more numbers which add up to the result of task 1.

Preparation

This task looks rather easy today, but first I load the data into a table. Since I only have numbers as input I switch the TEXT column for a BIGINT column (the last numbers coming from the on-board system are rather large and don’t fit into a INT4).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
DROP TABLE IF EXISTS day9;

CREATE TABLE day9 (
    id      SERIAL NOT NULL PRIMARY KEY,
    value   BIGINT
);

COPY day9 (value) FROM STDIN;
14
39
44
32
47
15
16
42
35
41
4
...
\.

I have a sound 1000 rows in the input table:

1
2
3
4
5
SELECT COUNT(*) FROM day9;
 count
-------
  1000
(1 row)

Task 1

The query for this task is rather easy: I loop over the input and then compare with everything between pos -1 and pos -25 and see if the sum equals the current value. Oh, and it starts at line 25, since the first 25 lines are not to be considered for the XMAS code.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
SELECT value
  FROM day9 AS t1
 WHERE NOT EXISTS (
       SELECT
         FROM day9 AS t2,
              day9 AS t3
        WHERE t2.id < t3.id
          AND t2.id BETWEEN (t1.id - (25 + 1)) AND (t1.id - 1)
          AND t3.id BETWEEN (t1.id - (25 + 1)) AND (t1.id - 1)
          AND t1.value = t2.value + t3.value
                  )
AND id > 25;

This takes a while until it finds a number which can’t be calculated from the previous 25 rows:

1
2
3
4
  value
----------
 22477624
(1 row)

Task 2

And here I thought today can work without CTE, but if I want to do this properly I need two of them:

The calculation from task 1, wrapped into a CTE
The recursive search

The search joins the data table (day9) against itself and the CTE, and finds the largest and smallest sum. It also uses day9_task1 as input to find sums which are below or equal to task 1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
WITH RECURSIVE day9_task1 AS (
    SELECT value AS task1
      FROM day9 AS t1
     WHERE NOT EXISTS (
           SELECT
             FROM day9 AS t2,
                  day9 AS t3
            WHERE t2.id < t3.id
              AND t2.id BETWEEN (t1.id - (25 + 1)) AND (t1.id - 1)
              AND t3.id BETWEEN (t1.id - (25 + 1)) AND (t1.id - 1)
              AND t1.value = t2.value + t3.value
                      )
    AND id > 25
),
day9_task2 AS (
    SELECT id,
           value AS min,
           value AS max,
           value AS total
      FROM day9 AS t1
     UNION ALL
    SELECT t3.id,
           LEAST(t2.min, t3.value) AS min,
           GREATEST(t2.max, t3.value) AS max,
           (t2.total + t3.value) AS total
      FROM day9_task2 AS t2,
           day9 AS t3
     WHERE t2.id + 1 = t3.id
       AND t2.total + t3.id <= (SELECT task1 FROM day9_task1)
)
SELECT * FROM day9_task2;

The result for the first iteration obviously has the same min, max and total sum:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
  id  |      min       |      max       |     total
------+----------------+----------------+----------------
    1 |             14 |             14 |             14
    2 |             39 |             39 |             39
    3 |             44 |             44 |             44
    4 |             32 |             32 |             32
    5 |             47 |             47 |             47
    6 |             15 |             15 |             15
    7 |             16 |             16 |             16
    8 |             42 |             42 |             42
    9 |             35 |             35 |             35
   10 |             41 |             41 |             41

Only starting with the second iteration the numbers start to add up:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
 1000 | 71799541868837 | 71799541868837 | 71799541868837
    2 |             14 |             39 |             53
    3 |             39 |             44 |             83
    4 |             32 |             44 |             76
    5 |             32 |             47 |             79
    6 |             15 |             47 |             62
    7 |             15 |             16 |             31
    8 |             16 |             42 |             58
    9 |             35 |             42 |             77
   10 |             35 |             41 |             76

Now I need to find the one result where the total equals the result from task 1 (I can just query the CTE again) and where min and max are not equal:

1
2
3
4
SELECT t.min + t.max AS sum
  FROM day9_task2 t
 WHERE t.total = (SELECT task1 FROM day9_task1)
   AND t.min != t.max;

The full query:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
WITH RECURSIVE day9_task1 AS (
    SELECT value AS task1
      FROM day9 AS t1
     WHERE NOT EXISTS (
           SELECT
             FROM day9 AS t2,
                  day9 AS t3
            WHERE t2.id < t3.id
              AND t2.id BETWEEN (t1.id - (25 + 1)) AND (t1.id - 1)
              AND t3.id BETWEEN (t1.id - (25 + 1)) AND (t1.id - 1)
              AND t1.value = t2.value + t3.value
                      )
    AND id > 25
),
day9_task2 AS (
    SELECT id,
           value AS min,
           value AS max,
           value AS total
      FROM day9 AS t1
     UNION ALL
    SELECT t3.id,
           LEAST(t2.min, t3.value) AS min,
           GREATEST(t2.max, t3.value) AS max,
           (t2.total + t3.value) AS total
      FROM day9_task2 AS t2,
           day9 AS t3
     WHERE t2.id + 1 = t3.id
       AND t2.total + t3.id <= (SELECT task1 FROM day9_task1)
)
SELECT t.min + t.max AS total
  FROM day9_task2 t
 WHERE t.total = (SELECT task1 FROM day9_task1)
   AND t.min != t.max;

And the result:

1
2
3
4
  total
---------
 2980044
(1 row)

Cool, and now? What’s next?

Categories: [Sql]

Tags: [Advent] [Advent-of-Code] [Challenge] [Ice-Cream] [Icecream] [Postgresql] [Psql] [Sql]

Preparation

Task 1

Task 2

Friends