Part One
这道题很有意思，类似于抓娃娃机，需要人来控制机器人进行移动，操控对应按钮。但是人无法直接控制目标机器人，需要操控中间若干个代理机器人，代理机器人再来操作目标机器人。需要求出2个代理机器人情况下，完整的操控路径是什么。
初始化keypad
+---+---+
| ^ | A |
+---+---+---+
| < | v | > |
+---+---+---+
create table direct_keypad(direction varchar(1), _row integer, _col integer);
insert into direct_keypad values('^', 1, 2);
insert into direct_keypad values('A', 1, 3);
insert into direct_keypad values('<', 2, 1);
insert into direct_keypad values('v', 2, 2);
insert into direct_keypad values('>', 2, 3);
+---+---+---+
| 7 | 8 | 9 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 0 | A |
+---+---+
create table numeric_keypad(num varchar(1), _row integer, _col integer);
insert into numeric_keypad values('1', 3, 1);
insert into numeric_keypad values('2', 3, 2);
insert into numeric_keypad values('3', 3, 3);
insert into numeric_keypad values('4', 2, 1);
insert into numeric_keypad values('5', 2, 2);
insert into numeric_keypad values('6', 2, 3);
insert into numeric_keypad values('7', 1, 1);
insert into numeric_keypad values('8', 1, 2);
insert into numeric_keypad values('9', 1, 3);
insert into numeric_keypad values('0', 4, 2);
insert into numeric_keypad values('A', 4, 3);
最优移动路径
当需要从一个点移动到另一个点的时候，比如从3移动到7，那么可能的路径有多种：
+---+---+---+
| 7 < 8 | 9 |
+---+-^-+---+
| 4 | 5 | 6 |
+---+-^-+---+
| 1 | 2 < 3 |
+---+---+---+
| 0 | A |
+---+---+
但是在这个场景中，由于可以停留在A按钮处，按动多次，从而触发对应机器人连续前进多步，所以这里需要尽量多的直线，少走弯路。
+---+---+---+
| 7 < 8 < 9 |
+---+---+-^-+
| 4 | 5 | 6 |
+---+---+-^-+
| 1 | 2 | 3 |
+---+---+---+
| 0 | A |
+---+---+
避免路径超出范围
由于不允许移动路径超出范围，所以设定按照如下图中的规则，先>再v，或者先^再<，这样可以保证不会超过范围
WITH numeric_path AS (
SELECT start_num, end_num, path || 'A' as path
FROM (
SELECT a.num as start_num, b.num as end_num,
CASE WHEN a._row <= b._row and a._col <= b._col THEN repeat('>', b._col - a._col) || repeat('v', b._row - a._row)
WHEN a._row >= b._row and a._col <= b._col THEN repeat('>', b._col - a._col) || repeat('^', a._row - b._row)
WHEN a._row <= b._row and a._col >= b._col THEN repeat('v', b._row - a._row) || repeat('<', a._col - b._col)
WHEN a._row >= b._row and a._col >= b._col THEN repeat('^', a._row - b._row) || repeat('<', a._col - b._col)
END as path
FROM numeric_keypad a
JOIN numeric_keypad b
ON a.num != b.num
) t
), direction_path AS (
SELECT start_direction, end_direction, path || 'A' as path
FROM (
SELECT a.direction as start_direction, b.direction as end_direction,
CASE WHEN a._row <= b._row and a._col <= b._col THEN repeat('>', b._col - a._col) || repeat('v', b._row - a._row)
WHEN a._row >= b._row and a._col <= b._col THEN repeat('>', b._col - a._col) || repeat('^', a._row - b._row)
WHEN a._row <= b._row and a._col >= b._col THEN repeat('v', b._row - a._row) || repeat('<', a._col - b._col)
WHEN a._row >= b._row and a._col >= b._col THEN repeat('^', a._row - b._row) || repeat('<', a._col - b._col)
END as path
FROM direct_keypad a
JOIN direct_keypad b
ON a.direction != b.direction
) t
)
完整的路径查找
origin AS (
SELECT row_number() over () as rn, line
FROM lance_input
), move AS (
SELECT rn, coalesce(lag(button) over (partition by rn order by idx), 'A') as pre_button, button, idx
FROM origin, regexp_split_to_table(line, '') with ordinality as x(button, idx)
), path_1 AS (
SELECT a.rn, string_agg(b.path, '' order by idx) as path
FROM move a
JOIN numeric_path b
ON a.pre_button = b.start_num
AND a.button = b.end_num
GROUP by a.rn
), robot_move AS (
SELECT rn, coalesce(lag(button) over (partition by rn order by idx), 'A') as pre_button, button, idx
FROM path_1, regexp_split_to_table(path, '') with ordinality as x(button, idx)
), path_2 AS (
SELECT a.rn, string_agg(coalesce(b.path, 'A'), '' order by idx) as path
FROM robot_move a
LEFT JOIN direction_path b
ON a.pre_button = b.start_direction
AND a.button = b.end_direction
GROUP by a.rn
), robot_move_2 AS (
SELECT rn, coalesce(lag(button) over (partition by rn order by idx), 'A') as pre_button, button, idx
FROM path_2, regexp_split_to_table(path, '') with ordinality as x(button, idx)
), path_3 AS (
SELECT a.rn, string_agg(coalesce(b.path, 'A'), '' order by idx) as path
FROM robot_move_2 a
LEFT JOIN direction_path b
ON a.pre_button = b.start_direction
AND a.button = b.end_direction
GROUP by a.rn
)
SELECT substring(line, 1, 3) :: INTEGER as num, length(path) as path_len
FROM path_3 a
JOIN origin b
ON a.rn = b.rn;
按照numeric_path计算出path_1，再根据direction_path计算出path_2，再根据direction_path计算出path_3，最后的结果如下。可以看出379对应的长度不正确，因此这里的最优路径并不是最优。
num | path_len
-----+----------
29 | 68
980 | 60
179 | 68
456 | 64
379 | 68
(5 rows)
最优路径并不超过范围
因此之前的最优路径存在问题，需要调整下方向，先<再^，或者先v再>，但是这样就有可能超过范围，因此需要特殊考虑下特殊case，比如0->7、4->A的场景。
WITH numeric_path AS (
SELECT start_num, end_num, path || 'A' as path
FROM (
SELECT a.num as start_num, b.num as end_num,
CASE WHEN a.num in ('1','4','7') AND b.num in ('0','A') THEN repeat('>', b._col - a._col) || repeat('v', b._row - a._row)
WHEN b.num in ('1','4','7') AND a.num in ('0','A') THEN repeat('^', a._row - b._row) || repeat('<', a._col - b._col)
WHEN a._row <= b._row and a._col <= b._col THEN repeat('v', b._row - a._row) || repeat('>', b._col - a._col)
WHEN a._row >= b._row and a._col <= b._col THEN repeat('^', a._row - b._row) || repeat('>', b._col - a._col)
WHEN a._row <= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('v', b._row - a._row)
WHEN a._row >= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('^', a._row - b._row)
END as path
FROM numeric_keypad a
JOIN numeric_keypad b
ON a.num != b.num
) t
), direction_path AS (
SELECT start_direction, end_direction, path || 'A' as path
FROM (
SELECT a.direction as start_direction, b.direction as end_direction,
CASE WHEN a.direction in ('^','A') AND b.direction in ('<') THEN repeat('v', b._row - a._row) || repeat('<', a._col - b._col)
WHEN b.direction in ('^','A') AND a.direction in ('<') THEN repeat('>', b._col - a._col) || repeat('^', a._row - b._row)
WHEN a._row <= b._row and a._col <= b._col THEN repeat('v', b._row - a._row) || repeat('>', b._col - a._col)
WHEN a._row >= b._row and a._col <= b._col THEN repeat('^', a._row - b._row) || repeat('>', b._col - a._col)
WHEN a._row <= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('v', b._row - a._row)
WHEN a._row >= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('^', a._row - b._row)
END as path
FROM direct_keypad a
JOIN direct_keypad b
ON a.direction != b.direction
) t
)
这样调整之后，得出的结果就是正确的了
num | path_len
-----+----------
29 | 68
980 | 60
179 | 68
456 | 64
379 | 64
(5 rows)
Part Two
不出所料，第二部分果然是增加中间代理机器人的数量，从2个增加到25个。
递归查询路径
最直观的想法，就是通过递归查询，递归25次后求出最后的路径
WITH recursive numeric_path AS (
SELECT start_num, end_num, path || 'A' as path
FROM (
SELECT a.num as start_num, b.num as end_num,
CASE WHEN a.num in ('1','4','7') AND b.num in ('0','A') THEN repeat('>', b._col - a._col) || repeat('v', b._row - a._row)
WHEN b.num in ('1','4','7') AND a.num in ('0','A') THEN repeat('^', a._row - b._row) || repeat('<', a._col - b._col)
WHEN a._row <= b._row and a._col <= b._col THEN repeat('v', b._row - a._row) || repeat('>', b._col - a._col)
WHEN a._row >= b._row and a._col <= b._col THEN repeat('^', a._row - b._row) || repeat('>', b._col - a._col)
WHEN a._row <= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('v', b._row - a._row)
WHEN a._row >= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('^', a._row - b._row)
END as path
FROM numeric_keypad a
JOIN numeric_keypad b
ON a.num != b.num
) t
), direction_path AS (
SELECT start_direction, end_direction, path || 'A' as path
FROM (
SELECT a.direction as start_direction, b.direction as end_direction,
CASE WHEN a.direction in ('^','A') AND b.direction in ('<') THEN repeat('v', b._row - a._row) || repeat('<', a._col - b._col)
WHEN b.direction in ('^','A') AND a.direction in ('<') THEN repeat('>', b._col - a._col) || repeat('^', a._row - b._row)
WHEN a._row <= b._row and a._col <= b._col THEN repeat('v', b._row - a._row) || repeat('>', b._col - a._col)
WHEN a._row >= b._row and a._col <= b._col THEN repeat('^', a._row - b._row) || repeat('>', b._col - a._col)
WHEN a._row <= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('v', b._row - a._row)
WHEN a._row >= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('^', a._row - b._row)
END as path
FROM direct_keypad a
JOIN direct_keypad b
ON a.direction != b.direction
) t
), origin AS (
SELECT row_number() over () as rn, line
FROM lance_input
), move AS (
SELECT rn, coalesce(lag(button) over (partition by rn order by idx), 'A') as pre_button, button, idx
FROM origin, regexp_split_to_table(line, '') with ordinality as x(button, idx)
), robot_path AS (
SELECT 0 as step, a.rn, string_agg(b.path, '' order by idx) as path
FROM move a
JOIN numeric_path b
ON a.pre_button = b.start_num
AND a.button = b.end_num
GROUP by a.rn
UNION ALL
SELECT a.step + 1 as step, a.rn, string_agg(coalesce(b.path, 'A'), '' order by idx) as path
FROM (
SELECT step, rn, coalesce(lag(button) over (partition by rn order by idx), 'A') as pre_button, button, idx
FROM robot_path, regexp_split_to_table(path, '') with ordinality as x(button, idx)
) a
LEFT JOIN direction_path b
ON a.pre_button = b.start_direction
AND a.button = b.end_direction
WHERE a.step < 25
GROUP by a.step, a.rn
)
SELECT substring(line, 1, 3) :: INTEGER as num, length(path) as path_len
FROM robot_path a
JOIN origin b
ON a.rn = b.rn;
不过这种算法效率太低，因此这个路径长度的变化，基本是呈指数级增长，越到后面运算越慢，到了最后基本计算不出来了。
step | num | path_len
------+-----+----------
0 | 593 | 12
0 | 283 | 12
0 | 670 | 14
0 | 459 | 14
0 | 279 | 14
1 | 593 | 30
1 | 283 | 28
1 | 670 | 28
1 | 459 | 30
1 | 279 | 32
2 | 593 | 74
2 | 283 | 68
2 | 670 | 68
2 | 459 | 74
2 | 279 | 72
14 | 593 | 4156364
14 | 283 | 3830460
14 | 670 | 3731814
14 | 459 | 4013060
14 | 279 | 4048166
15 | 593 | 10339444
15 | 283 | 9529004
15 | 670 | 9283562
15 | 459 | 9982652
15 | 279 | 10070134
缓存路径长度
参考Day 11，最终计算的只是一个长度而已，而中间很多的路径其实是重复的，因此只需要缓存中间结果即可。
CREATE OR REPLACE FUNCTION count_path(start_button text, end_button text, robots_left integer)
RETURNS BIGINT AS $$
DECLARE
query_num BIGINT;
origin_path TEXT;
BEGIN
-- same button
IF start_button = end_button THEN
RETURN 1;
END IF;
-- get path length from direction_path
origin_path := (select path from direction_path where start_direction = start_button and end_direction = end_button);
IF robots_left = 0 THEN
RETURN length(origin_path);
END IF;
-- get length from cache
query_num := (SELECT path_length FROM cache_path WHERE cache_start = start_button AND cache_end = end_button AND robot_num = robots_left);
IF query_num IS NOT NULL THEN
return query_num;
END IF;
query_num := (
SELECT SUM(CASE WHEN b.start_direction IS NULL THEN 1 ELSE count_path(pre_button, button, robots_left - 1) END)
FROM (
SELECT coalesce(lag(button) over (order by idx), 'A') as pre_button, button, idx
FROM regexp_split_to_table(origin_path, '') with ordinality as x(button, idx)
) a
LEFT JOIN direction_path b
ON a.pre_button = b.start_direction
AND a.button = b.end_direction
);
INSERT INTO cache_path values(start_button, end_button, robots_left, query_num);
RAISE NOTICE 'add map: %', (query_num || ' ' || robots_left);
RETURN query_num;
END;
$$ LANGUAGE plpgsql;
接下来就比较简单了，直接使用函数即可
WITH numeric_path AS (
SELECT start_num, end_num, path || 'A' as path
FROM (
SELECT a.num as start_num, b.num as end_num,
CASE WHEN a.num in ('1','4','7') AND b.num in ('0','A') THEN repeat('>', b._col - a._col) || repeat('v', b._row - a._row)
WHEN b.num in ('1','4','7') AND a.num in ('0','A') THEN repeat('^', a._row - b._row) || repeat('<', a._col - b._col)
WHEN a._row <= b._row and a._col <= b._col THEN repeat('v', b._row - a._row) || repeat('>', b._col - a._col)
WHEN a._row >= b._row and a._col <= b._col THEN repeat('^', a._row - b._row) || repeat('>', b._col - a._col)
WHEN a._row <= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('v', b._row - a._row)
WHEN a._row >= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('^', a._row - b._row)
END as path
FROM numeric_keypad a
JOIN numeric_keypad b
ON a.num != b.num
) t
), direction_path AS (
SELECT start_direction, end_direction, path || 'A' as path
FROM (
SELECT a.direction as start_direction, b.direction as end_direction,
CASE WHEN a.direction in ('^','A') AND b.direction in ('<') THEN repeat('v', b._row - a._row) || repeat('<', a._col - b._col)
WHEN b.direction in ('^','A') AND a.direction in ('<') THEN repeat('>', b._col - a._col) || repeat('^', a._row - b._row)
WHEN a._row <= b._row and a._col <= b._col THEN repeat('v', b._row - a._row) || repeat('>', b._col - a._col)
WHEN a._row >= b._row and a._col <= b._col THEN repeat('^', a._row - b._row) || repeat('>', b._col - a._col)
WHEN a._row <= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('v', b._row - a._row)
WHEN a._row >= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('^', a._row - b._row)
END as path
FROM direct_keypad a
JOIN direct_keypad b
ON a.direction != b.direction
) t
), origin AS (
SELECT row_number() over () as rn, line
FROM lance_input
), move AS (
SELECT rn, coalesce(lag(button) over (partition by rn order by idx), 'A') as pre_button, button, idx
FROM origin, regexp_split_to_table(line, '') with ordinality as x(button, idx)
), path AS (
SELECT a.rn, string_agg(b.path, '' order by idx) as path
FROM move a
JOIN numeric_path b
ON a.pre_button = b.start_num
AND a.button = b.end_num
GROUP by a.rn
), robot_move AS (
SELECT rn, coalesce(lag(button) over (partition by rn order by idx), 'A') as pre_button, button, idx
FROM path, regexp_split_to_table(path, '') with ordinality as x(button, idx)
)
SELECT substring(line, 1, 3) :: INTEGER as num, sum(count_path(pre_button, button, 24)) as path_length
FROM robot_move a
JOIN origin b
ON a.rn = b.rn
GROUP BY substring(line, 1, 3)
可以看出中途很多结果进行了缓存，无需额外计算
NOTICE: add map: 928140922 22
NOTICE: add map: 3680843457 23
NOTICE: add map: 9686334009 24
NOTICE: add map: 9009012838 24
NOTICE: add map: 5743602246 24
NOTICE: add map: 10218188222 24
NOTICE: add map: 2308871594 23
NOTICE: add map: 9156556999 24
NOTICE: add map: 12192864309 24
NOTICE: add map: 9009012838 24
num | path_length
-----+-------------
279 | 91387668328
283 | 86475783008
459 | 90594397580
593 | 93831469524
670 | 84248089344
(5 rows)