Day 14: Parabolic Reflector Dish
Part One
将下文中的字符“向北滚动”，直到遇到障碍，计算最终所有O的最终位置之和。
O....#....
O.OO#....#
.....##...
行列转换
先将输入进行行列转换，相当于将图向左旋转90度。
------------
O....#....
O.OO#....#
.....##...
OO.#O....O
.O.....O#.
O.#..O.#.#
..O..#O..O
.......O..
#....###..
#OO..#....
(10 rows)
转换为
id | column_str
----+------------
10 | .#.O.#O...
9 | ....#.....
8 | ....O#.O#.
7 | ..#...O.#.
6 | #.#..O#.##
5 | .#.O......
4 | .O.#......
3 | .O...#O..O
2 | ...OO....O
1 | OO.O.O..##
(10 rows)
后续就是字符串正则匹配替换，将…O替换为O…即可，直到无可替换字符串。
正则替换？
期望的是直接正则替换即可，但是regexp_replace函数的第三个参数，无法使用自定义函数。先执行了函数，再执行了replace，无法实现预期目标。
postgres=# SELECT REGEXP_REPLACE('OO.O.O..##','(\.+O)','|\1|', 'g');
regexp_replace
----------------
OO|.O||.O|..##
(1 row)
postgres=# SELECT REGEXP_REPLACE('OO.O.O..##','(\.+O)',reverse('|\1|'), 'g');
regexp_replace
----------------
OO|1\||1\|..##
(1 row)
经过一番搜索，终于找到了相关解决方案，可以完美实现函数替换。
postgres=# SELECT *
postgres-# FROM ROWS FROM (
postgres(# regexp_split_to_table('..OO.O###.O..##..O','(\.+O)'),
postgres(# regexp_matches('..OO.O###.O..##..O','(\.+O)', 'g')
postgres(# ) AS m(l, u);
l | u
------+-------
| {..O}
O | {.O}
### | {.O}
..## | {..O}
|
(5 rows)
postgres=# SELECT string_agg(concat(l, reverse(u[1])), '')
postgres-# FROM ROWS FROM (
postgres(# regexp_split_to_table('..OO.O###.O..##..O','(\.+O)'),
postgres(# regexp_matches('..OO.O###.O..##..O','(\.+O)', 'g')
postgres(# ) AS m(l, u);
string_agg
--------------------
O..OO.###O...##O..
(1 row)
因此创建个函数，用来向前滚动字符串
CREATE OR REPLACE FUNCTION roll_left(str TEXT)
RETURNS TEXT AS $$
DECLARE
result VARCHAR;
BEGIN
result := str;
WHILE result ~ '\.+O' LOOP
result := (
SELECT string_agg(concat(l, reverse(u[1])), '')
FROM ROWS FROM (
regexp_split_to_table(result,'(\.+O)'),
regexp_matches(result,'(\.+O)', 'g')
) AS m(l, u)
);
END LOOP;
RETURN result;
END;
$$ LANGUAGE plpgsql;
再次行列转换
经过向前滚动后，字符变成了如下所示
id | column_str
----+------------
10 | .#O..#O...
9 | ....#.....
8 | O....#O.#.
7 | ..#O....#.
6 | #.#O..#.##
5 | .#O.......
4 | O..#......
3 | O....#OO..
2 | OOO.......
1 | OOOO....##
(10 rows)
再次行列转换后，向右转动90度，变成了
id | column_str
----+------------
1 | OOOO.#.O..
2 | OO..#....#
3 | OO..O##..O
4 | O..#.OO...
5 | ........#.
6 | ..#....#.#
7 | ..O..#.O.O
8 | ..O.......
9 | #....###..
10 | #....#....
(10 rows)
最终SQL
WITH RECURSIVE origin AS (
SELECT row_number() over () as _row, line
FROM lance_input
), seq AS (
SELECT 1 as id
UNION ALL
SELECT id + 1 as id
FROM seq
), roll_result AS (
SELECT id, roll_left(column_str) as column_str
FROM (
SELECT t.id, string_agg(substring(line from t.id for 1) , '' order by _row) as column_str
FROM origin
JOIN (SELECT id FROM seq limit (select length(line) from origin limit 1)) t
ON 1 = 1
GROUP BY t.id
) t
ORDER BY id desc
), final_result AS (
SELECT line_len.cnt - id + 1 as score, str
FROM (
SELECT t.id, string_agg(substring(column_str from t.id for 1) , '' order by roll_result.id) as str
FROM roll_result
JOIN (SELECT id FROM seq limit (select length(column_str) from roll_result limit 1)) t
ON 1 = 1
GROUP BY t.id
) t, (select length(column_str) as cnt from roll_result limit 1) line_len
)
SELECT SUM((length(str) - length(replace(str, 'O', ''))) * score)
FROM final_result;
Part Two
第二关更加复杂，按照北西南东的方向各滚动一次，算做是一个循环。经过10亿次循环后的结果是？
Each cycle tilts the platform four times so that the rounded rocks roll north, then west, then south, then east.
一次循环
首先先写出北、西、南、东一次循环的SQL，通过roll_left和roll_right两个函数来实现
SELECT t.id, roll_right(string_agg(substring(str from t.id for 1) , '' order by south.id)) as str
FROM (
SELECT t.id, roll_right(string_agg(substring(str from t.id for 1) , '' order by west.id)) as str
FROM (
SELECT t.id, roll_left(string_agg(substring(str from t.id for 1) , '' order by north.id)) as str
FROM (
SELECT t.id, roll_left(string_agg(substring(str from t.id for 1) , '' order by origin.id)) as str
FROM origin
JOIN (SELECT id FROM seq limit 10) t ON 1 = 1
GROUP BY t.id
ORDER BY 1 DESC
) north
JOIN (SELECT id FROM seq limit 10) t ON 1 = 1
GROUP BY t.id
) west
JOIN (SELECT id FROM seq limit 10) t ON 1 = 1
GROUP by t.id
ORDER BY 1 DESC
) south
JOIN (SELECT id FROM seq limit 10) t ON 1 = 1
GROUP by t.id
十亿次循环？
当然不可能真的循环十亿次，有限时间内根本计算不出。先尝试循环若干次看看结果，因此CTE中无法对递归表使用aggregate function，因此只能在自定义function中循环插入到表中。
CREATE OR REPLACE FUNCTION trans(cnt INTEGER)
RETURNS INTEGER AS $$
BEGIN
DELETE FROM input;
INSERT INTO input
SELECT row_number() over () as _row, line
FROM lance_input;
FOR i IN 1..CNT LOOP
WITH recursive seq AS (
SELECT 1 as id
UNION ALL
SELECT id + 1 as id
FROM seq
)
INSERT INTO input
SELECT t.id, roll_right(string_agg(substring(str from t.id for 1) , '' order by south.id)) as str
FROM (
SELECT t.id, roll_right(string_agg(substring(str from t.id for 1) , '' order by west.id)) as str
FROM (
SELECT t.id, roll_left(string_agg(substring(str from t.id for 1) , '' order by north.id)) as str
FROM (
SELECT t.id, roll_left(string_agg(substring(str from t.id for 1) , '' order by input_bak.id)) as str
FROM input_bak
JOIN (SELECT id FROM seq limit 100) t ON 1 = 1
GROUP BY t.id
ORDER BY 1 DESC
) north
JOIN (SELECT id FROM seq limit 100) t ON 1 = 1
GROUP BY t.id
) west
JOIN (SELECT id FROM seq limit 100) t ON 1 = 1
GROUP by t.id
ORDER BY 1 DESC
) south
JOIN (SELECT id FROM seq limit 100) t ON 1 = 1
GROUP by t.id;
END LOOP;
RETURN 0;
END;
$$ LANGUAGE plpgsql;
期望是循环若干次后，这个结果能够最终保持稳定，就像例子中的那样，但是结果却大不相同。无论多少次迭代后，总会有8条记录不一致，而且还不是固定的8条记录。
postgres=# select a.* from input a JOIN input_bak b on a.id = b.id and a.str != b.str;
id | str
----+------------------------------------------------------------------------------------------------------
38 | .....OO#.O#.....OO#....OO#.....O#.........#...O#.#.#.....OOO#......O#.......O#...#..#..#....#.O#....
41 | #..#.....O#...#......OO#....#........OOO#.....OOOO#...#O#O#....................OO#.##OO#.O#......OOO
57 | ......OOOOO#........##...O#........O#...#...OO#.....OOO#O#......OO#....#...#.............OO#....O#.#
59 | .OOO#....OO#.......#.#.......OOO#..#........#........#..#...#..#.O#.......#..OO#.......#..##......O#
63 | .OO#O#....#....................OOOOOOOOOO#...........O#...........#..#...O#............#.......O##..
65 | .#.......................OOOO##..OOOOO#....O#.........OOOO#............OO##..#..OO#...###.#...#....O
77 | .....#....OO#........O#....O#.....#.O#..#.O#....#.......O##...#............OOOOOO#...#..#....O#OOO#.
89 | ##.O#.#..O#...OO#.......OO#..#..##.OOOO#..O#......OOOO#...O#....O####........OO#..O#.....OOO#..#....
(8 rows)
找规律
因此，有理由相信，这个循环肯定是有规律可循。因此，先迭代200次，并记录下每次循环后前后的结果都有哪些差异。
10 | {6,7,8,9,10,11,15,16,19,20,25,27,32,33,35,37,38,42,44,46,47,51,53,57,58,63,72,73,74,84,85,86,89,93,97,98,99}
11 | {5,6,11,12,13,15,19,22,25,27,28,31,33,35,41,43,44,46,51,53,54,55,62,63,70,75,78,79,84,86,89,92,95,97,100}
12 | {2,5,7,10,11,15,18,24,25,28,34,35,37,40,42,44,45,51,52,54,55,56,57,66,67,69,75,80,83,85,87,88,90,92,95,96,98}
13 | {2,5,8,10,13,14,15,20,21,25,27,40,43,44,45,46,51,54,57,63,64,65,70,72,75,80,85,91,96,97}
14 | {1,9,10,14,16,17,22,24,35,37,42,43,44,46,52,55,60,63,64,65,70,73,76,80,83,88,92,97}
15 | {8,10,13,14,15,20,26,27,37,41,42,44,45,56,61,64,67,70,73,79,85,89,94,96}
16 | {1,10,12,13,20,25,27,31,35,44,45,46,61,64,65,69,70,73,81,84,86,89,90,91}
17 | {6,8,13,15,18,24,34,35,37,43,44,46,58,63,69,72,73,75,79,82,92}
18 | {6,12,18,21,27,28,37,44,45,47,61,65,73,74,75,76,81,96,100}
19 | {9,15,20,24,25,26,27,34,35,45,46,67,73,75,82,91,99,100}
一开始的差异还是非常大的，随着更多的循环，差异也逐渐收敛到8条记录
161 | {22,24,57,59,63,65,89,94}
162 | {15,36,57,59,63,65,82,91}
163 | {24,38,57,59,63,65,77,94}
164 | {36,38,57,59,63,65,76,82}
165 | {38,41,57,59,63,65,77,89}
166 | {38,45,57,59,63,65,76,91}
167 | {41,47,57,59,63,65,89,94}
再分析下是否有规律可循，果然看到了规律
postgres=# select diff, array_agg(id order by id) from (select * From record limit 100 offset 100) t group by diff having count(*) = 2;
diff | array_agg
---------------------------+-----------
{15,26,57,59,63,65,77,94} | {121,199}
{15,26,57,59,63,65,82,91} | {108,186}
{15,36,57,59,63,65,76,82} | {110,188}
{22,24,57,59,63,65,76,82} | {122,200}
{22,24,57,59,63,65,77,94} | {109,187}
{22,25,57,59,63,65,82,91} | {120,198}
{22,25,57,59,63,65,89,94} | {107,185}
{24,38,57,59,63,65,77,89} | {111,189}
{25,35,57,59,63,65,76,91} | {118,196}
{25,35,57,59,63,65,77,89} | {105,183}
{26,33,57,59,63,65,76,91} | {106,184}
{26,33,57,59,63,65,89,94} | {119,197}
{33,47,57,59,63,65,76,82} | {104,182}
{33,47,57,59,63,65,77,89} | {117,195}
{35,45,57,59,63,65,76,82} | {116,194}
{35,45,57,59,63,65,77,94} | {103,181}
{36,38,57,59,63,65,76,91} | {112,190}
{38,41,57,59,63,65,89,94} | {113,191}
{38,45,57,59,63,65,82,91} | {114,192}
{38,45,57,59,63,65,89,94} | {101,179}
{41,47,57,59,63,65,77,94} | {115,193}
{41,47,57,59,63,65,82,91} | {102,180}
因此，每78轮循环后就会回到原点，因此十亿次后的状态等同于142次后的状态。