## 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).

```
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:

```
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*.

```
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:

```
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*.

```
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:

```
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:

```
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:

```
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:

```
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:

```
total
---------
2980044
(1 row)
```

Cool, and now? What's next?

## Comments

Display comments as Linear | Threaded