Red-Nosed Reports
For Day 2, we have to find sequences of numbers that are safe to process. For part 1, “safe” means the numbers are in order, either increasing or decreasing, and the step between each is never more than 3.
My approach to this was to pivot each row of numbers into a sequence, which would then let me use the LAG function to compare the numbers in order. Using the sample data, that would provide a list like this…
WITH
data
AS
(SELECT r.str, c.COLUMN_VALUE val, ROWNUM rn
FROM advent.data2rows('advent2024-2sample') r, str2tbl(r.str, ' ') c)
SELECT *
FROM data;
STR VAL RN
---------- --- --
7 6 4 2 1 7 1
7 6 4 2 1 6 2
7 6 4 2 1 4 3
7 6 4 2 1 2 4
7 6 4 2 1 1 5
1 2 7 8 9 1 6
1 2 7 8 9 2 7
1 2 7 8 9 7 8
1 2 7 8 9 8 9
1 2 7 8 9 9 10
9 7 6 2 1 9 11
9 7 6 2 1 7 12
9 7 6 2 1 6 13
9 7 6 2 1 2 14
9 7 6 2 1 1 15
1 3 2 4 5 1 16
1 3 2 4 5 3 17
1 3 2 4 5 2 18
1 3 2 4 5 4 19
1 3 2 4 5 5 20
8 6 4 4 1 8 21
8 6 4 4 1 6 22
8 6 4 4 1 4 23
8 6 4 4 1 4 24
8 6 4 4 1 1 25
1 3 6 7 9 1 26
1 3 6 7 9 3 27
1 3 6 7 9 6 28
1 3 6 7 9 7 29
1 3 6 7 9 9 30
Now that I have my values for each line, it’s just a matter of counting the number of lines that have values between 1 and 3 (for increasing values) or -1 and -3 (for decreasing values). If the number of values that have valid steps is the same as the number of values in that line, then that line is safe.
WITH
data
AS
(SELECT r.str, c.COLUMN_VALUE val, ROWNUM rn
FROM advent.data2rows('advent2024-2sample') r, str2tbl(r.str, ' ') c),
diffs
AS
( SELECT str, cnt, COUNT(*) diffcnt
FROM (SELECT data.*,
NVL(val - LAG(val, 1) OVER(PARTITION BY str ORDER BY rn), -1) diff,
COUNT(*) OVER (PARTITION BY str) cnt
FROM data)
WHERE diff BETWEEN -3 AND -1
GROUP BY str, cnt
HAVING COUNT(*) IN (cnt, cnt - 1)
UNION ALL
SELECT str, cnt, COUNT(*) diffcnt
FROM (SELECT data.*,
NVL(val - LAG(val, 1) OVER(PARTITION BY str ORDER BY rn), 1) diff,
COUNT(*) OVER (PARTITION BY str) cnt
FROM data)
WHERE diff BETWEEN 1 AND 3
GROUP BY str, cnt
HAVING COUNT(*) IN (cnt, cnt - 1))
SELECT COUNT(*)
FROM diffs
WHERE cnt = diffcnt;
COUNT(*)
----------
2
For part 2, the rules change slightly, if we can remove one invalid step, and the rest of the line would still be valid, then we can call that line “safe”. For this I decided it would be easier to use an embedded pl/sql function to iterate through the values of each line and try removing one element of a collection at a time until I either found it to be safe or ran out of elements to try.
The overall strategy is still the same though. Given a line, iterate through the values checking if they either increasing or decreasing and the steps are between 1 and 3 (i.e. less than 4.)
I used some trivial recursion, that is, I check if the original collection is safe, if it is I’m done. If it’s not, then I loop through the elements, removing one at a time, and checking if the remaining list if safe. The recursion is trivial in that the safe function never calls itself more than the second level of depth.
If I find a line is safe, I don’t need to keep trying to remove the rest of the elements, I can declare it safe and move on.
With these new rules, trying it out on the sample data I get the expected result of 4.
WITH
FUNCTION safe(txt IN VARCHAR2, second IN VARCHAR2 DEFAULT 'N')
RETURN VARCHAR2
IS
v_safe BOOLEAN := TRUE;
v_increasing BOOLEAN;
v_sub numtab;
v_cnt INTEGER;
v_newcnt INTEGER;
v_set numtab;
PROCEDURE remove(tbl IN OUT numtab, n INTEGER)
IS
cnt INTEGER := tbl.COUNT;
BEGIN
tbl.delete(n);
FOR i IN n .. cnt - 1
LOOP
tbl(i) := tbl(i + 1);
END LOOP;
tbl.TRIM;
END;
BEGIN
SELECT str2numtab(txt, ' ') INTO v_set FROM DUAL;
v_cnt := v_set.COUNT;
FOR x IN (
SELECT c, LAG(c) OVER (ORDER BY rn) prev, rn
FROM (SELECT COLUMN_VALUE c, ROWNUM rn FROM TABLE(v_set))
)
LOOP
IF x.rn = 2
THEN
v_increasing := x.c > x.prev;
END IF;
v_safe :=
v_safe
AND (x.rn = 1
OR (v_increasing AND x.c > x.prev AND x.c - x.prev < 4)
OR (NOT v_increasing AND x.c < x.prev AND x.prev - x.c < 4));
EXIT WHEN NOT v_safe;
END LOOP;
IF v_safe
THEN
RETURN 'Y';
END IF;
IF second = 'N'
THEN
FOR i IN 1 .. v_cnt
LOOP
v_sub := v_set;
remove(v_sub, i);
v_safe := safe(numtab2str(v_sub, ' '), 'Y') = 'Y';
EXIT WHEN v_safe;
END LOOP;
END IF;
RETURN CASE WHEN v_safe THEN 'Y' ELSE 'N' END;
END;
SELECT COUNT(*)
FROM (
SELECT d.*, safe(str) s
FROM advent.data2rows('advent2024-2sample') d
)
WHERE s = 'Y';
COUNT(*)
----------
4