Part One
走迷宫，限制就是遇到箭头，只能按照箭头的方向前进，此外不能重复走同一空格，求最长路径。
#.>.>.#
#.#v#.#
#.#.#..
走迷宫的话比较简单，注意加上两个限制条件即可
- 前进方向和箭头方向冲突时，则无需继续
- 不走回头路
最终SQL
WITH RECURSIVE maze AS (
SELECT _row, row_number() over (partition by _row) as _col, pos
FROM (
SELECT row_number() over () as _row, unnest(regexp_split_to_array(line, '')) as pos
FROM lance_input
)t
),
path AS (
SELECT 1 as _row, 2 as _col, '{}' :: integer[] as trail, true as valid
UNION ALL
SELECT t._row, t._col,
t.trail + (t._row * 1000 + t._col) as trail,
case when t.direction = 'E' and s.pos = '<' then false
when t.direction = 'W' and s.pos = '>' then false
when t.direction = 'N' and s.pos = 'v' then false
when t.direction = 'S' and s.pos = '^' then false
else true
end as valid
FROM (
SELECT case when y.direction = 'N' then x._row - 1
when y.direction = 'S' then x._row + 1
else x._row
end as _row,
case when y.direction = 'E' then x._col + 1
when y.direction = 'W' then x._col - 1
else x._col
end as _col,
x.trail,
y.direction
FROM path x, (select unnest(regexp_split_to_array('ESWN', '')) as direction) y
WHERE x.valid
) t
JOIN maze s
ON t._row = s._row
AND t._col = s._col
AND s.pos != '#'
AND t.trail # (t._row * 1000 + t._col) = 0
)
SELECT max(#trail) FROM path where _row = 141 and _col = 140;
Part Two
第二关去除了前进方向和箭头方向冲突的限制，再次求最长的路径。
穷举路径
使用第一关相同的方法，只是去除了限制。但是运行很久都未计算出最终结果，尝试先获取前1500W条的记录，看看分布的情况。
step | count
------+-------
1645 | 7155
1646 | 7147
1647 | 7218
1648 | 7203
1649 | 7281
1650 | 7261
1651 | 7344
1652 | 7317
1653 | 4889
由于有太多的可能分支可以走，且没有约束条件（仅剩余不能重走的限制），因此越往后分支数越多，1600多步时，达到了7000多个分支，性能下降严重。而且1500W条的记录，才走到了1600多步，按照这个迷宫的设计，应该在1w步左右。
精简迷宫
迷宫中有很多条路都是无岔路的，因此一次可以在横向或者纵向方向上移动多步。首先，需要找出一行输入中，可以无岔路移动的最大距离。
CREATE OR REPLACE FUNCTION find_shortcut(line VARCHAR, pre_line VARCHAR, next_line VARCHAR)
RETURNS VARCHAR[] AS $$
DECLARE
shortcut VARCHAR[];
start_index INTEGER := 0;
end_index INTEGER := 0;
BEGIN
IF pre_line is null OR next_line is null THEN
RETURN null;
END IF;
FOR i IN 1..length(line) LOOP
IF substring(line, i, 1) != '#' THEN
IF start_index = 0 THEN
-- if next position is a wall, ignore this position
IF substring(line, i+1, 1) != '#' THEN
start_index := i;
end_index := i;
END IF;
ELSE
-- no other way to go
CONTINUE WHEN substring(pre_line, i ,1) = '#' AND substring(next_line, i, 1) = '#' AND i < length(line);
end_index := i;
-- add to shortcut
IF start_index != end_index THEN
shortcut := shortcut || (start_index || ',' || end_index);
END IF;
-- if next position is not a wall, current position is a fork.
IF substring(line, i+1, 1) != '#' THEN
start_index := i;
end_index := 1;
ELSE
start_index := 0;
end_index := 0;
END IF;
END IF;
END IF;
END LOOP;
RETURN shortcut;
END;
$$ LANGUAGE plpgsql;
通过上面的函数，就可以计算出一行输入中，可以无岔路移动的起点和终点。
postgres=# select find_shortcut('###.....#.>.>.###.#.###', '#######.#########.#.###', '###v#####.#v#.###.#.###');
find_shortcut
-------------------------
{"4,8","10,12","12,14"}
(1 row)
接着就可以根据这个函数，计算出走迷宫的捷径，从而一次可以多走几步。
WITH RECURSIVE maze AS (
SELECT _row, row_number() over (partition by _row) as _col, pos
FROM (
SELECT row_number() over () as _row, unnest(regexp_split_to_array(line, '')) as pos
FROM lance_input
)t
),
rows AS (
SELECT _row,
lag(line) over (order by _row) as pre_line,
lead(line) over (order by _row) as next_line,
line
FROM (
SELECT _row, string_agg(pos, '' order by _col) as line
FROM maze
GROUP BY _row
) t
),
cols AS (
SELECT _col,
lag(line) over (order by _col) as pre_line,
lead(line) over (order by _col) as next_line,
line
FROM (
SELECT _col, string_agg(pos, '' order by _row) as line
FROM maze
GROUP BY _col
) t
),
short_cut AS (
SELECT _row as start_row, split_part(shortcut, ',', 1) :: integer as start_col,
_row as finish_row, split_part(shortcut, ',', 2) :: integer as finish_col,
'E' as type
FROM (
SELECT _row, unnest(shortcuts) as shortcut
FROM (
SELECT _row, find_shortcut(line, pre_line, next_line) as shortcuts
FROM rows
) t
WHERE shortcuts IS NOT NULL
) s
UNION ALL
SELECT _row as start_row, split_part(shortcut, ',', 2) :: integer as start_col,
_row as finish_row, split_part(shortcut, ',', 1) :: integer as finish_col,
'W' as type
FROM (
SELECT _row, unnest(shortcuts) as shortcut
FROM (
SELECT _row, find_shortcut(line, pre_line, next_line) as shortcuts
FROM rows
) t
WHERE shortcuts IS NOT NULL
) s
UNION ALL
SELECT split_part(shortcut, ',', 1) :: integer as start_row, _col as start_col,
split_part(shortcut, ',', 2) :: integer as finish_row, _col as finish_col,
'S' as type
FROM (
SELECT _col, unnest(shortcuts) as shortcut
FROM (
SELECT _col, find_shortcut(line, pre_line, next_line) as shortcuts
FROM cols
) t
WHERE shortcuts IS NOT NULL
) s
UNION ALL
SELECT split_part(shortcut, ',', 2) :: integer as start_row, _col as start_col,
split_part(shortcut, ',', 1) :: integer as finish_row, _col as finish_col,
'N' as type
FROM (
SELECT _col, unnest(shortcuts) as shortcut
FROM (
SELECT _col, find_shortcut(line, pre_line, next_line) as shortcuts
FROM cols
) t
WHERE shortcuts IS NOT NULL
) s
),
path AS (
SELECT 1 as _row, 2 as _col, '{}' :: integer[] as trail, 0 as steps
UNION ALL
SELECT t._row :: integer, t._col :: integer,
t.trail + (t._row * 1000 + t._col)::integer as trail, steps::integer
FROM (
SELECT case when z.type IS NOT NULL then z.finish_row
when y.direction = 'N' then x._row - 1
when y.direction = 'S' then x._row + 1
else x._row
end as _row,
case when z.type IS NOT NULL then z.finish_col
when y.direction = 'E' then x._col + 1
when y.direction = 'W' then x._col - 1
else x._col
end as _col,
x.trail,
case when z.type IS NOT NULL then x.steps + abs(z.finish_row - z.start_row) + abs(z.finish_col - z.start_col)
else x.steps + 1
end as steps
FROM path x
JOIN (select unnest(regexp_split_to_array('ESWN', '')) as direction) y
ON 1 = 1
LEFT JOIN short_cut z
ON x._row = z.start_row
AND x._col = z.start_col
AND y.direction = z.type
) t
JOIN maze s
ON t._row = s._row
AND t._col = s._col
AND s.pos != '#'
AND t.trail # (t._row * 1000 + t._col)::integer = 0
)
SELECT max(steps) from path where _row = 141 and _col = 140;
但是，运行速度仍然很慢，分析后发现，虽然迭代次数少了，但是分支数仍然很多。其实和之前的做法差别不大，迭代次数少了，但是一次迭代的步数多了，相应的分支数仍然很多。而且需要将走过的路径记录下来，因此耗费的存储也比较大。
iter | count
------+-------
519 | 12615
520 | 12771
521 | 12955
522 | 13139
523 | 13321
524 | 13516
525 | 13741
526 | 13952
527 | 14184
528 | 14398
529 | 14613
分岔路口之间距离
前面记录的是水平或者垂直方向上的捷径，其实我们只需要关注分岔路口之间的距离即可，中途无论水平方向还是垂直方向的移动，只要中途没有分岔，都无需关注，仅计算出分岔口之间的距离。
分岔路口的计算方式，就是根据前面的short_cut，计算出某个点出发的分支数。2个分支代表是一个90度弯或起点终点，3个分支代表三岔路口，4个分支代表四岔路口。在计算的时候，还需要将起点和终点加进去。
SELECT start_row as _row, start_col as _col
FROM short_cut
GROUP BY start_row, start_col
HAVING COUNT(*) > 2
UNION ALL
SELECT 1, 2
UNION ALL
SELECT 141, 140
通过递归查询，计算出这些岔路口之间的距离
short_route AS (
SELECT s.start_row, s.start_col, t.finish_row, t.finish_col,
abs(t.finish_row - s.start_row) + abs(t.finish_col - s.start_col) as distance,
case when p._row is not null then false else true end as valid,
'{}' ::integer[] || (t.start_row * 1000 + t.start_col)::integer || (t.finish_row * 1000 + t.finish_col)::integer as trail
FROM (
SELECT start_row, start_col
FROM short_cut
GROUP BY start_row, start_col
HAVING COUNT(*) > 2
UNION ALL
SELECT 1, 2
UNION ALL
SELECT 141, 140
) s
JOIN short_cut t
ON s.start_row = t.start_row
AND s.start_col = t.start_col
LEFT JOIN (
SELECT start_row as _row, start_col as _col
FROM short_cut
GROUP BY start_row, start_col
HAVING COUNT(*) > 2
UNION ALL
SELECT 1, 2
UNION ALL
SELECT 141, 140
) p
ON t.finish_row = p._row
AND t.finish_col = p._col
UNION ALL
SELECT s.start_row, s.start_col, t.finish_row, t.finish_col,
s.distance + abs(t.finish_row - s.finish_row) + abs(t.finish_col - s.finish_col) as distance,
case when p._row is not null then false else true end as valid,
s.trail || (t.finish_row * 1000 + t.finish_col)::integer as trail
FROM short_route s
JOIN short_cut t
ON s.finish_row = t.start_row
AND s.finish_col = t.start_col
AND s.valid
AND s.trail # (t.finish_row * 1000 + t.finish_col)::integer = 0
LEFT JOIN (
SELECT start_row as _row, start_col as _col
FROM short_cut
GROUP BY start_row, start_col
HAVING COUNT(*) > 2
UNION ALL
SELECT 1, 2
UNION ALL
SELECT 141, 140
) p
ON t.finish_row = p._row
AND t.finish_col = p._col
)
start_row | start_col | finish_row | finish_col | distance
-----------+-----------+------------+------------+----------
20 | 16 | 8 | 38 | 158
20 | 16 | 38 | 10 | 164
20 | 16 | 1 | 2 | 177
(3 rows)
最终SQL
有了这个分岔路口之间的距离数据后，计算就比较简单了，最终耗时100秒左右。
path AS (
SELECT 1 as _row, 2 as _col,
'{}' :: integer[] || 1002 as trail, 0 as steps
UNION ALL
SELECT y.finish_row :: integer,
y.finish_col :: integer,
x.trail || (y.finish_row * 1000 + y.finish_col)::integer,
(x.steps + y.distance) :: integer
FROM path x
JOIN short_route y
ON x._row = y.start_row
AND x._col = y.start_col
AND y.valid = false
AND x.trail # (y.finish_row * 1000 + y.finish_col)::integer = 0
)
SELECT max(steps) from path where _row = 141 and _col = 140;
max
------
6334
(1 row)
Time: 100189.855 ms (01:40.190)