Part One
仍然是走迷宫，从起点到终点有唯一的通道。假如可以穿墙的话，那么可以节省多少步？
仍然是走迷宫，类似于Day 16，不过这次有些特殊，仔细观察可以看到，从起点到终点只有唯一的一条路，并没有别的分支可以走。
因此在计算迷宫路径的时候，无需考虑最短路径。
with recursive rows as (
SELECT (row_number() over ()) :: INTEGER as _row, line
FROM lance_input
), matrix AS (
SELECT _row :: INTEGER, x.idx :: INTEGER as _col, x.pos
FROM rows, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
), cols AS (
SELECT _col, string_agg(pos, '' order by _row) as line
FROM matrix
GROUP BY _col
), rows_range AS (
SELECT _row, start_pos, end_pos
FROM rows, find_dot_ranges(line) t
WHERE t.start_pos < t.end_pos
), cols_range AS (
SELECT _col, start_pos, end_pos
FROM cols, find_dot_ranges(line) t
WHERE t.start_pos < t.end_pos
), rows_new_range AS (
SELECT t._row, s.start_pos as _col, s.end_pos as next_col
FROM (
SELECT a._row, a.start_pos, a.end_pos, b.pos_array
FROM rows_range a
LEFT JOIN (
SELECT a._row, a.start_pos, a.end_pos, array_agg(b._col order by b._col) as pos_array
FROM rows_range a
JOIN cols_range b
ON a._row between b.start_pos and b.end_pos
AND b._col between a.start_pos and a.end_pos
GROUP BY a._row, a.start_pos, a.end_pos
) b
ON a._row = b._row
AND a.start_pos = b.start_pos
AND a.end_pos = b.end_pos
) t, split_range(start_pos, end_pos, pos_array) s
), cols_new_range AS (
SELECT t._col, s.start_pos as _row, s.end_pos as next_row
FROM (
SELECT a._col, a.start_pos, a.end_pos, b.pos_array
FROM cols_range a
LEFT JOIN (
SELECT b._col, b.start_pos, b.end_pos, array_agg(a._row order by a._row) as pos_array
FROM rows_range a
JOIN cols_range b
ON a._row between b.start_pos and b.end_pos
AND b._col between a.start_pos and a.end_pos
GROUP BY b._col, b.start_pos, b.end_pos
) b
ON a._col = b._col
AND a.start_pos = b.start_pos
AND a.end_pos = b.end_pos
) t, split_range(start_pos, end_pos, pos_array) s
), all_range AS (
SELECT _row as start_row, _col as start_col, _row as end_row, next_col as end_col, 'E' as direction
FROM rows_new_range
UNION ALL
SELECT _row as start_row, next_col as start_col, _row as end_row, _col as end_col, 'W' as direction
FROM rows_new_range
UNION ALL
SELECT _row as start_row, _col as start_col, next_row as end_row, _col as end_col, 'S' as direction
FROM cols_new_range
UNION ALL
SELECT next_row as start_row, _col as start_col, _row as end_row, _col as end_col, 'N' as direction
FROM cols_new_range
), walkthrough AS (
SELECT _row, _col, 'E' as direction, 0 as steps, array[_row * 10000 + _col] as path
FROM matrix
WHERE pos = 'S'
UNION ALL
SELECT *
FROM (
WITH walkthrough_inner as (select * From walkthrough)
SELECT b.end_row as _row,
b.end_col as _col,
b.direction,
a.steps + abs(b.end_row - b.start_row) + abs(b.end_col - b.start_col) as steps,
path || (b.end_row * 10000 + b.end_col) as path
FROM walkthrough_inner a
JOIN all_range b
ON a._row = b.start_row
AND a._col = b.start_col
AND NOT (b.end_row * 10000 + b.end_col) = ANY(a.path)
) t
)
之前为了节省计算步骤，walkthrough中的每一行记录，其实是完整路径上的每一个转向节点，比如：
_row | _col | direction | steps | path
------+------+-----------+-------+-------------------------------------------------------------------------
48 | 26 | E | 0 | {480026}
54 | 26 | S | 6 | {480026,540026}
54 | 28 | E | 8 | {480026,540026,540028}
50 | 28 | N | 12 | {480026,540026,540028,500028}
50 | 30 | E | 14 | {480026,540026,540028,500028,500030}
56 | 30 | S | 20 | {480026,540026,540028,500028,500030,560030}
56 | 32 | E | 22 | {480026,540026,540028,500028,500030,560030,560032}
50 | 32 | N | 28 | {480026,540026,540028,500028,500030,560030,560032,500032}
50 | 40 | E | 36 | {480026,540026,540028,500028,500030,560030,560032,500032,500040}
为了计算“穿墙”之后节省的步数，需要拆分到这条路径经过的每一个节点，并标明达到此节点的步数。
all_steps AS (
SELECT CASE WHEN last_row is null THEN current_row
WHEN last_row < current_row THEN last_row + seq
WHEN last_row > current_row THEN last_row - seq
ELSE current_row
END as _row,
CASE WHEN last_col is null THEN current_col
WHEN last_col < current_col THEN last_col + seq
WHEN last_col > current_col THEN last_col - seq
ELSE current_col
END as _col,
row_number() over (order by rn, seq) as rn
FROM (
SELECT row_number() over () as rn,
lag(_row) over() as last_row,
lag(_col) over() as last_col,
_row as current_row,
_col as current_col
FROM walkthrough
) s, generate_series(1, 15) as seq
WHERE seq <= abs(last_row - current_row)
OR seq <= abs(last_col - current_col)
OR (last_row is null AND seq = 1)
)
经过转换后，完整路径走了多少步，就会有多少条记录，而且步数呈递增。
_row | _col | rn
------+------+----
48 | 26 | 1
49 | 26 | 2
50 | 26 | 3
51 | 26 | 4
52 | 26 | 5
53 | 26 | 6
54 | 26 | 7
54 | 27 | 8
54 | 28 | 9
53 | 28 | 10
(10 rows)
“穿墙“的定义，就是起点和终点，在同一行或者同一列，且两者相差2步。那么节省的步数，就是原始步数差减2即可得出。
SELECT save_steps, count(*)
FROM (
SELECT s._row as start_row, s._col as start_col,
t._row as end_row, t._col as end_col,
t.rn - s.rn - 2 as save_steps
FROM all_steps s
JOIN all_steps t
ON s.rn < t.rn
AND ((abs(s._row - t._row) = 2 AND s._col = t._col)
OR (abs(s._col - t._col) = 2 AND s._row = t._row))
) t
GROUP BY save_steps;
Part Two
如果“无敌穿墙”的步数不限制在两步，而是20步，那么节省的步数分布是什么样的？
从2变成20，简单转换限制条件即可
SELECT save_steps, count(*) as cnt
FROM (
SELECT s._row as start_row, s._col as start_col,
t._row as end_row, t._col as end_col,
t.rn - s.rn - (abs(s._row - t._row) + abs(s._col - t._col)) as save_steps
FROM all_steps s
JOIN all_steps t
ON s.rn < t.rn
AND abs(s._row - t._row) + abs(s._col - t._col) <= 20
) t
GROUP BY save_steps