Advent of Code 2020: "Password Philosophy" - Day 2
Posted by
ads' corner
on
Wednesday, 2020-12-02 Posted in [Sql]
Day 2, another challenge: fix a broken password database. In order to do that, the passwords which violate the policy must be identified.
Task 1: I get a string, consisting of 2 numbers, a letter, and a password string. Check how many passwords have count(letter) which is between number 1 and number 2.
Task 2: The numbers are positions in the password string (beginning by 1, not 0). Exactly one of the two letters in the string must match the letter.
Preparation
Let’s start by creating a table in PostgreSQL, and load the data into it. Since the input data comes as a single string, I decided to take this challenge and not pre-process the data. Hence everything goes into a single TEXT field. I also briefly checked the two numbers, if the first one is always smaller than the second one - that seems to be the case.
SELECT COUNT(*) FROM day2;
count
-------
1000
(1row)
Since the data is a single string, I need to split, slice and dice this into pieces. Like yesterday I’m using a CTE for this which breaks the string into the 4 separate fields:
1
2
3
4
5
6
7
8
9
WITH l1 AS (
SELECTSUBSTRING(value, '^([0-9]+)')::INTAS num1,
SUBSTRING(value, '^[0-9]+-([0-9]+)')::INTAS num2,
SUBSTRING(value, '.*? ([a-z]):') AS letter,
SUBSTRING(value, '.*? [a-z]: (.*)$') ASpassword,
valueFROM day2
)
SELECT*FROM l1;
The result is 4 columns which I can access:
1
2
3
4
5
6
7
8
9
10
11
12
13
num1 | num2 | letter |password|value------+------+--------+----------------------+-------------------------------
1|14| b | bbbbbbbbbbbbbbbbbbb |1-14 b: bbbbbbbbbbbbbbbbbbb
3|14| v | vvpvvvmvvvvvvvv |3-14 v: vvpvvvmvvvvvvvv
2|5| m | mfvxmmm |2-5 m: mfvxmmm
15|20| z | zdzzzrjzzzdpzzdzzzzz |15-20 z: zdzzzrjzzzdpzzdzzzzz
6|8| g | tggjggggrg |6-8 g: tggjggggrg
2|3| l | nlllw |2-3 l: nlllw
1|5| j | jjjjj |1-5 j: jjjjj
4|5| t | prttt |4-5 t: prttt
2|4| v | vvrqzp |2-4 v: vvrqzp
4|6| v | vvvvvqvvv |4-6 v: vvvvvqvvv
7|8| d | mpntdwkd |7-8 d: mpntdwkd
Task 1
From here I have a couple different options. I could move the string manipulations which are necessary to find the passwords into the CTE. That will make the overall query easier, as I get the manipulated string as a column. Otherwise if I do that in the “main” query, I have to repeat the manipulation in the WHERE clause (at least if I also want to see the extracted data). I decided to keep things separated, leave the CTE as it is and do the heavy lifting in the outer query.
The task is to identify the number of letters in the password string matching the one letter I have in the task. I solve this by replacing all other characters with an empty string, just leaving this one letter. And since the letter is not static, but changes per row, I dynamically build the string inside REGEXP_REPLACE:
1
REGEXP_REPLACE(l1.password, '[^'|| letter ||']', '', 'g')
This leaves a string with only the letters, which I then use to count the LENGTH.
The full query:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
WITH l1 AS (
SELECTSUBSTRING(value, '^([0-9]+)')::INTAS num1,
SUBSTRING(value, '^[0-9]+-([0-9]+)')::INTAS num2,
SUBSTRING(value, '.*? ([a-z]):') AS letter,
SUBSTRING(value, '.*? [a-z]: (.*)$') ASpassword,
valueFROM day2
)
SELECT*,
REGEXP_REPLACE(l1.password, '[^'|| letter ||']', '', 'g') AS found,
LENGTH(REGEXP_REPLACE(l1.password, '[^'|| letter ||']', '', 'g')) AS length
FROM l1
WHERE LENGTH(REGEXP_REPLACE(l1.password, '[^'|| letter ||']', '', 'g')) >= l1.num1
AND LENGTH(REGEXP_REPLACE(l1.password, '[^'|| letter ||']', '', 'g')) <= l1.num2;
WITH l1 AS (
SELECTSUBSTRING(value, '^([0-9]+)')::INTAS num1,
SUBSTRING(value, '^[0-9]+-([0-9]+)')::INTAS num2,
SUBSTRING(value, '.*? ([a-z]):') AS letter,
SUBSTRING(value, '.*? [a-z]: (.*)$') ASpassword,
valueFROM day2
)
SELECT COUNT(*) AS count
FROM l1
WHERE LENGTH(REGEXP_REPLACE(l1.password, '[^'|| letter ||']', '', 'g')) >= l1.num1
AND LENGTH(REGEXP_REPLACE(l1.password, '[^'|| letter ||']', '', 'g')) <= l1.num2;
And get the same result back:
1
2
3
4
count
-------
548
(1row)
Task 2
This is easier than the first task, I only have to pick two specific characters from the password, the position is known and the length for the pick is always 1. Since SQL starts SUBSTRING() with position 1 and not 0, I don’t even have to calculate a different starting position either.
1
2
3
4
5
6
7
8
9
10
11
12
WITH l1 AS (
SELECTSUBSTRING(value, '^([0-9]+)')::INTAS num1,
SUBSTRING(value, '^[0-9]+-([0-9]+)')::INTAS num2,
SUBSTRING(value, '.*? ([a-z]):') AS letter,
SUBSTRING(value, '.*? [a-z]: (.*)$') ASpassword,
valueFROM day2
)
SELECT*,
SUBSTRING(l1.passwordFROM l1.num1 FOR1) AS c1,
SUBSTRING(l1.passwordFROM l1.num2 FOR1) AS c2
FROM l1;
The resulting data:
1
2
3
4
5
6
7
8
9
10
11
12
13
num1 | num2 | letter |password|value| c1 | c2
------+------+--------+----------------------+-------------------------------+----+----
1|14| b | bbbbbbbbbbbbbbbbbbb |1-14 b: bbbbbbbbbbbbbbbbbbb | b | b
3|14| v | vvpvvvmvvvvvvvv |3-14 v: vvpvvvmvvvvvvvv | p | v
2|5| m | mfvxmmm |2-5 m: mfvxmmm | f | m
15|20| z | zdzzzrjzzzdpzzdzzzzz |15-20 z: zdzzzrjzzzdpzzdzzzzz | d | z
6|8| g | tggjggggrg |6-8 g: tggjggggrg | g | g
2|3| l | nlllw |2-3 l: nlllw | l | l
1|5| j | jjjjj |1-5 j: jjjjj | j | j
4|5| t | prttt |4-5 t: prttt | t | t
2|4| v | vvrqzp |2-4 v: vvrqzp | v | q
4|6| v | vvvvvqvvv |4-6 v: vvvvvqvvv | v | q
7|8| d | mpntdwkd |7-8 d: mpntdwkd | k | d
From here all I have to do is make sure that either c1 or c2 matches the letter, but not both:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
WITH l1 AS (
SELECTSUBSTRING(value, '^([0-9]+)')::INTAS num1,
SUBSTRING(value, '^[0-9]+-([0-9]+)')::INTAS num2,
SUBSTRING(value, '.*? ([a-z]):') AS letter,
SUBSTRING(value, '.*? [a-z]: (.*)$') ASpassword,
valueFROM day2
)
SELECT*FROM l1
WHERE (SUBSTRING(l1.passwordFROM l1.num1 FOR1) = l1.letter ANDSUBSTRING(l1.passwordFROM l1.num2 FOR1) != l1.letter) OR
(SUBSTRING(l1.passwordFROM l1.num1 FOR1) != l1.letter ANDSUBSTRING(l1.passwordFROM l1.num2 FOR1) = l1.letter);
Oh, and of course count the result set:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
WITH l1 AS (
SELECTSUBSTRING(value, '^([0-9]+)')::INTAS num1,
SUBSTRING(value, '^[0-9]+-([0-9]+)')::INTAS num2,
SUBSTRING(value, '.*? ([a-z]):') AS letter,
SUBSTRING(value, '.*? [a-z]: (.*)$') ASpassword,
valueFROM day2
)
SELECT COUNT(*) AS count
FROM l1
WHERE (SUBSTRING(l1.passwordFROM l1.num1 FOR1) = l1.letter ANDSUBSTRING(l1.passwordFROM l1.num2 FOR1) != l1.letter) OR
(SUBSTRING(l1.passwordFROM l1.num1 FOR1) != l1.letter ANDSUBSTRING(l1.passwordFROM l1.num2 FOR1) = l1.letter);