Posted by
ads
on
Wednesday, 2020-12-09 Posted in [Sql]

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 XMASencryption, 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).

SELECT COUNT(*) FROM day9;
count
-------
1000
(1row)

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

SELECTvalueFROM day9 AS t1
WHERENOTEXISTS (
SELECTFROM 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
(1row)

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.

WITHRECURSIVE day9_task1 AS (
SELECTvalueAS task1
FROM day9 AS t1
WHERENOTEXISTS (
SELECTFROM 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,
valueAS min,
valueAS max,
valueAS total
FROM day9 AS t1
UNIONALLSELECT 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|142|39|39|393|44|44|444|32|32|325|47|47|476|15|15|157|16|16|168|42|42|429|35|35|3510|41|41|41

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

WITHRECURSIVE day9_task1 AS (
SELECTvalueAS task1
FROM day9 AS t1
WHERENOTEXISTS (
SELECTFROM 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,
valueAS min,
valueAS max,
valueAS total
FROM day9 AS t1
UNIONALLSELECT 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;