— Day 20: Grove Positioning System —
Part One
输入一串数字,按顺序依据数字的值移动该数字,正数向右,负数向左,0不移动。
Initial arrangement: 1, 2, -3, 3, -2, 0, 4
本关并不难,只需要精准找到正确的插入位置即可。假如一共有m个数字,那么可以得出:
- 移动m-1步后,会回到原点
- 👈移动n步,等价于👉移动m-1-n步
m个数字每一轮都有对应位置1,2,3…m,为了方便计算,可以将某个数字移动后的位置标记为小数。比如移动到3,4中间,可以将位置标记为3.5,根据位置排序后,再生成新的位置。
WITH recursive origin AS (
SELECT row_number () over () as rn, line :: INTEGER as num
FROM lance_input
), stats AS (
SELECT max(rn) - 1 as circle, max(rn) as size
FROM origin
), walkthrough AS (
SELECT 0 as seq, num, rn as num_origin_seq, rn as num_seq
FROM origin
UNION ALL
SELECT seq, num, num_origin_seq, row_number() over () as num_seq
FROM (
SELECT seq, num, num_origin_seq,
CASE WHEN num_origin_seq != seq THEN num_seq
ELSE (num_seq + mod_num - 0.5) % (select size from stats) + 1
END as num_seq
FROM (
SELECT x.seq + 1 as seq,
num,
num_origin_seq,
num_seq,
CASE WHEN num < 0 THEN num % (select circle from stats) + (select circle from stats) ELSE num % (select circle from stats) END as mod_num
FROM walkthrough x
WHERE x.seq + 1 <= (select size from stats)
) t
ORDER BY 4
) t
), last_seq AS (
SELECT num, num_seq as seq
FROM walkthrough
WHERE seq = (select circle + 1 from stats)
), zero_seq AS (
SELECT seq FROM last_seq WHERE num = 0
)
SELECT seq, num
FROM last_seq
WHERE seq IN (
((select seq from zero_seq) + 1000 - 1) % (select size from stats) + 1,
((select seq from zero_seq) + 2000 - 1) % (select size from stats) + 1,
((select seq from zero_seq) + 3000 - 1) % (select size from stats) + 1
);
Part Two
数字 * 811589153后,再进行10次完整运算。
因此考虑到每移动m-1步,其实相当于原地,数字再大也是相同的处理方式。
WITH recursive origin AS (
SELECT row_number () over () as rn, line :: BIGINT * 811589153 as num
FROM lance_input
), stats AS (
SELECT max(rn) - 1 as circle, max(rn) as size
FROM origin
), walkthrough AS (
SELECT 0 as seq, num, rn as num_origin_seq, rn as num_seq
FROM origin
UNION ALL
SELECT seq, num, num_origin_seq, row_number() over () as num_seq
FROM (
SELECT seq, num, num_origin_seq,
CASE WHEN num_origin_seq != (seq - 1) % (select size from stats) + 1 THEN num_seq
ELSE (num_seq + mod_num - 0.5) % (select size from stats) + 1
END as num_seq
FROM (
SELECT x.seq + 1 as seq,
num,
num_origin_seq,
num_seq,
CASE WHEN num < 0 THEN num % (select circle from stats) + (select circle from stats) ELSE num % (select circle from stats) END as mod_num
FROM walkthrough x
WHERE x.seq + 1 <= (select size from stats) * 10
) t
ORDER BY 4
) t
), last_seq AS (
SELECT num, num_seq as seq
FROM walkthrough
WHERE seq = (select size from stats) * 10
), zero_seq AS (
SELECT seq FROM last_seq WHERE num = 0
)
SELECT seq, num
FROM last_seq
WHERE seq IN (
((select seq from zero_seq) + 1000 - 1) % (select size from stats) + 1,
((select seq from zero_seq) + 2000 - 1) % (select size from stats) + 1,
((select seq from zero_seq) + 3000 - 1) % (select size from stats) + 1
);