Part One
按照指令走迷宫，遇到墙就停止，求出最后的终点位置。指令中的方向仅有L和R。
10R5L5R10L4R5L5
预处理
先将指令进行拆分，拆分为具体方向以及行动距离
WITH recursive origin AS (
SELECT row_number() over () as rn, line
FROM lance_input
), path AS (
SELECT row_number() over () as seq,
substring(move, 1, 1) as direction,
substring(move, 2) :: INTEGER as steps
FROM (
SELECT string_to_table('E' || replace(replace(line, 'R', '|R'), 'L', '|L'), '|') as move
FROM origin
WHERE rn = (select max(rn) from origin)
) t
)
seq | direction | steps
------+-----------+-------
1 | E | 13
2 | L | 2
3 | R | 45
4 | R | 31
5 | R | 34
6 | R | 41
7 | L | 14
8 | L | 26
9 | L | 47
因为有大量的空窗，需要确定每一行列的起始位置和结束位置。同时，也找出每一行列的墙的所有位置，方便后续的处理
maps AS (
SELECT rn :: INTEGER as _row, x.idx :: INTEGER as _col, x.word as tile
FROM origin, regexp_split_to_table(line, '') with ordinality as x(word, idx)
WHERE rn <= (select max(rn) from origin) - 2
), column_stats AS (
SELECT _col,
COUNT(CASE WHEN tile = '#' THEN 1 END) as wall_cnt,
MIN(CASE WHEN tile IN ('#', '.') THEN _row END) as min_pos,
MAX(CASE WHEN tile IN ('#', '.') THEN _row END) as max_pos,
ARRAY_AGG(_row) FILTER (WHERE tile = '#') as wall_arr
FROM maps
GROUP BY _col
), row_stats AS (
SELECT _row,
COUNT(CASE WHEN tile = '#' THEN 1 END) as wall_cnt,
MIN(CASE WHEN tile IN ('#', '.') THEN _col END) as min_pos,
MAX(CASE WHEN tile IN ('#', '.') THEN _col END) as max_pos,
ARRAY_AGG(_col) FILTER (WHERE tile = '#') as wall_arr
FROM maps
GROUP BY _row
)
迷宫行走
如果某一行列完全没有墙，则无需做复杂的计算，直接移动到最终位置即可
WHEN direction = 'N' AND c.wall_cnt = 0 THEN
CASE WHEN start_row >= steps + c.min_pos THEN start_row - steps
ELSE start_row - steps - c.min_pos + c.max_pos + 1
END
WHEN direction = 'S' AND c.wall_cnt = 0 THEN
CASE WHEN start_row <= c.max_pos - steps THEN start_row + steps
ELSE start_row + steps + c.min_pos - c.max_pos - 1
END
WHEN direction = 'W' AND c.wall_cnt = 0 THEN
CASE WHEN start_col >= steps + r.min_pos THEN start_col - steps
ELSE start_col - steps - r.min_pos + r.max_pos + 1
END
WHEN direction = 'E' AND c.wall_cnt = 0 THEN
CASE WHEN start_col <= r.max_pos - steps THEN start_col + steps
ELSE start_col + steps + r.min_pos - r.max_pos - 1
END
如果有墙，则需要判断遇墙停止的问题，通过一个函数来判断最终位置
CREATE OR REPLACE FUNCTION move_tile(start_pos INTEGER, new_pos INTEGER, wall_arr INTEGER[], min_pos INTEGER, max_pos INTEGER)
RETURNS INTEGER AS $$
DECLARE
wall_pos INTEGER;
BEGIN
IF new_pos > max_pos AND start_pos > wall_arr[#wall_arr] THEN
IF wall_arr[1] = min_pos THEN
RETURN max_pos;
END IF;
start_pos := min_pos;
new_pos := min_pos + (new_pos - max_pos) - 1;
ELSIF new_pos < min_pos AND start_pos < wall_arr[1] THEN
IF wall_arr[#wall_arr] = max_pos THEN
RETURN min_pos;
END IF;
start_pos := max_pos;
new_pos := max_pos - (min_pos - new_pos) + 1;
END IF;
FOR i IN 1..#wall_arr LOOP
IF start_pos < new_pos THEN
wall_pos := wall_arr[i];
ELSE
wall_pos := wall_arr[(#wall_arr) - i + 1];
END IF;
IF wall_pos > start_pos AND wall_pos <= new_pos THEN
RETURN wall_pos - 1;
ELSIF wall_pos < start_pos AND wall_pos >= new_pos THEN
RETURN wall_pos + 1;
END IF;
END LOOP;
RETURN new_pos;
END;
$$ LANGUAGE plpgsql;
行走路径
walkthrough AS (
SELECT _row, min(CASE WHEN tile = '.' THEN _col END) _col, 0 as move_seq, null as last_direction, 0 as steps
FROM maps
WHERE _row = 1
GROUP BY _row
UNION ALL
SELECT CASE WHEN direction IN ('E', 'W') THEN start_row
WHEN direction = 'N' AND c.wall_cnt = 0 THEN
CASE WHEN start_row >= steps + c.min_pos THEN start_row - steps
ELSE start_row - steps - c.min_pos + c.max_pos + 1
END
WHEN direction = 'S' AND c.wall_cnt = 0 THEN
CASE WHEN start_row <= c.max_pos - steps THEN start_row + steps
ELSE start_row + steps + c.min_pos - c.max_pos - 1
END
WHEN direction = 'N' THEN move_tile(start_row, start_row - steps, c.wall_arr, c.min_pos, c.max_pos)
WHEN direction = 'S' THEN move_tile(start_row, start_row + steps, c.wall_arr, c.min_pos, c.max_pos)
END as _row,
CASE WHEN direction IN ('N', 'S') THEN start_col
WHEN direction = 'W' AND c.wall_cnt = 0 THEN
CASE WHEN start_col >= steps + r.min_pos THEN start_col - steps
ELSE start_col - steps - r.min_pos + r.max_pos + 1
END
WHEN direction = 'E' AND c.wall_cnt = 0 THEN
CASE WHEN start_col <= r.max_pos - steps THEN start_col + steps
ELSE start_col + steps + r.min_pos - r.max_pos - 1
END
WHEN direction = 'W' THEN move_tile(start_col, start_col - steps, r.wall_arr, r.min_pos, r.max_pos)
WHEN direction = 'E' THEN move_tile(start_col, start_col + steps, r.wall_arr, r.min_pos, r.max_pos)
END as _col,
move_seq,
direction,
steps
FROM (
SELECT x._row as start_row,
x._col as start_col,
x.move_seq + 1 as move_seq,
CASE WHEN x.last_direction IS NULL THEN y.direction
WHEN y.direction = 'L' AND x.last_direction = 'E' THEN 'N'
WHEN y.direction = 'L' AND x.last_direction = 'S' THEN 'E'
WHEN y.direction = 'L' AND x.last_direction = 'W' THEN 'S'
WHEN y.direction = 'L' AND x.last_direction = 'N' THEN 'W'
WHEN y.direction = 'R' AND x.last_direction = 'E' THEN 'S'
WHEN y.direction = 'R' AND x.last_direction = 'S' THEN 'W'
WHEN y.direction = 'R' AND x.last_direction = 'W' THEN 'N'
WHEN y.direction = 'R' AND x.last_direction = 'N' THEN 'E'
END as direction,
y.steps
FROM walkthrough x, path y
WHERE y.seq = x.move_seq + 1
) t
JOIN column_stats c
ON t.start_col = c._col
JOIN row_stats r
ON t.start_row = r._row
)
SELECT *
FROM walkthrough;
Part Two
从二维平面上升到三维空间，之前的迷宫其实是一个立方体展开的6个面，求新的终点位置。
从二维上升到三维，那么三维空间的移动在二维空间，那就是一个个的“虫洞”。通过虫洞后，不仅位置发生了改变，而且移动方向也发生了变化。
寻找虫洞
1111
1111
1111
1111
222233334444
222233334444
222233334444
222233334444
55556666
55556666
55556666
55556666
以示例中的立方体为例。立方体总共有12条边，例子中，(1,4)(2,3)(3,4)(4,5)(5,6)这5条边已经相邻了，剩余的7条边在平面上并不相邻，因此需要构建虫洞。
剩余的7条边
1,3
SELECT _row as start_row,
_col as start_col,
'W' as start_direction,
5 as end_row,
4 + _row as end_col,
'S' as end_direction
FROM maps
WHERE _row between 1 and 4
AND _col = 9
3,5
SELECT _row as start_row,
_col as start_col,
'S' as start_direction,
17 - _col as end_row,
9 as end_col,
'E' as end_direction
FROM maps
WHERE _row = 8
AND _col between 5 and 8
4,6
SELECT _row as start_row,
_col as start_col,
'E' as start_direction,
9 as end_row,
21 - _row as end_col,
'S' as end_direction
FROM maps
WHERE _row between 5 and 8
AND _col = 12
1,2
SELECT _row as start_row,
_col as start_col,
'N' as start_direction,
5 as end_row,
13 - _col as end_col,
'S' as end_direction
FROM maps
WHERE _row = 1
AND _col between 9 and 12
2,5
SELECT _row as start_row,
_col as start_col,
'S' as start_direction,
12 as end_row,
13 - _col as end_col,
'N' as end_direction
FROM maps
WHERE _row = 8
AND _col between 1 and 4
1,6
SELECT _row as start_row,
_col as start_col,
'E' as start_direction,
13 - _row as end_row,
16 as end_col,
'W' as end_direction
FROM maps
WHERE _row between 1 and 4
AND _col = 12
2,6
SELECT _row as start_row,
_col as start_col,
'W' as start_direction,
12 as end_row,
21 - _row as end_col,
'N' as end_direction
FROM maps
WHERE _row between 5 and 8
AND _col = 1
虫洞是双向的，因此反方向的记录也要构建出来
wormholes AS (
SELECT start_row, start_col, start_direction, end_row, end_col, end_direction
FROM wormhole
UNION ALL
SELECT end_row as start_row,
end_col as start_col,
CASE when end_direction = 'E' THEN 'W'
when end_direction = 'W' THEN 'E'
when end_direction = 'N' THEN 'S'
when end_direction = 'S' THEN 'N'
END as start_direction,
start_row as end_row,
start_col as end_col,
CASE when start_direction = 'E' THEN 'W'
when start_direction = 'W' THEN 'E'
when start_direction = 'N' THEN 'S'
when start_direction = 'S' THEN 'N'
END as end_direction
FROM wormhole
)
仅单面行走
之前的行走函数，并没有考虑跨多个面的情况，这里就需要考虑仅在单个面上进行移动。只能移动到墙，或者移动到边缘。函数的返回结果，包含最终位置以及剩余步数。如果移动到边缘后，还剩余一些步数，这时就需要后续通过虫洞进入到另一面进行后续移动。
CREATE OR REPLACE FUNCTION move_tile_in_one_face(start_pos INTEGER, new_pos INTEGER, wall_arr INTEGER[], min_pos INTEGER, max_pos INTEGER)
RETURNS INTEGER[] AS $$
DECLARE
wall_pos INTEGER;
BEGIN
-- no walls
IF wall_arr IS NULL THEN
IF new_pos > max_pos THEN
return ARRAY[max_pos, new_pos - max_pos];
ELSIF new_pos < min_pos THEN
return ARRAY[min_pos, min_pos - new_pos];
ELSE
return ARRAY[new_pos, 0];
END IF;
END IF;
-- with walls
IF new_pos > max_pos AND start_pos > wall_arr[#wall_arr] THEN
return ARRAY[max_pos, new_pos - max_pos];
ELSIF new_pos < min_pos AND start_pos < wall_arr[1] THEN
return ARRAY[min_pos, min_pos - new_pos];
END IF;
FOR i IN 1..#wall_arr LOOP
IF start_pos < new_pos THEN
wall_pos := wall_arr[i];
ELSE
wall_pos := wall_arr[(#wall_arr) - i + 1];
END IF;
IF wall_pos > start_pos AND wall_pos <= new_pos THEN
RETURN ARRAY[wall_pos - 1, 0];
ELSIF wall_pos < start_pos AND wall_pos >= new_pos THEN
RETURN ARRAY[wall_pos + 1, 0];
END IF;
END LOOP;
RETURN ARRAY[new_pos, 0];
END;
$$ LANGUAGE plpgsql;
行走路径
因此，指令中的每一步，可能要分多次进行。每次移动到边缘，通过虫洞后，再进行后续移动，直到剩余步数为0。这里的意思，就是先判断当前位置是否需要通过虫洞继续进行，如果虫洞后面是墙则不再移动，剩余步数清零；如果虫洞后面不是墙，则剩余步数减一后，移动到新的位置上。
SELECT CASE WHEN z.tile != '#' THEN y.end_row
ELSE x._row
END as _row,
CASE WHEN z.tile != '#' THEN y.end_col
ELSE x._col
END as _col,
x.move_seq,
CASE WHEN z.tile != '#' THEN y.end_direction
ELSE x.last_direction
END as last_direction,
CASE WHEN z.tile = '#' THEN 0
WHEN z.tile != '#' AND x.remain_steps > 0 THEN x.remain_steps - 1
ELSE x.remain_steps
END as remain_steps
FROM walkthrough x
LEFT JOIN wormholes y
ON x._row = y.start_row
AND x._col = y.start_col
AND x.last_direction = y.start_direction
AND x.remain_steps > 0
LEFT JOIN maps z
ON y.end_row = z._row
AND y.end_col = z._col
后续，则按照前一步类似的方法，持续进行即可
walkthrough AS (
SELECT _row, min(CASE WHEN tile = '.' THEN _col END) _col, 0 as move_seq, null as last_direction, 0 as remain_steps
FROM maps
WHERE _row = 1
GROUP BY _row
UNION ALL
SELECT CASE WHEN direction IN ('E', 'W') THEN start_row
ELSE move_result[1]
END as _row,
CASE WHEN direction IN ('N', 'S') THEN start_col
ELSE move_result[1]
END as _col,
move_seq,
direction,
move_result[2] as remain_steps
FROM (
SELECT start_row, start_col, move_seq, direction,
CASE WHEN direction = 'N' THEN move_tile_in_one_face(start_row, start_row - steps, c.wall_arr, c.min_pos, c.max_pos)
WHEN direction = 'S' THEN move_tile_in_one_face(start_row, start_row + steps, c.wall_arr, c.min_pos, c.max_pos)
WHEN direction = 'W' THEN move_tile_in_one_face(start_col, start_col - steps, r.wall_arr, r.min_pos, r.max_pos)
WHEN direction = 'E' THEN move_tile_in_one_face(start_col, start_col + steps, r.wall_arr, r.min_pos, r.max_pos)
END as move_result
FROM (
SELECT x._row as start_row,
x._col as start_col,
case when remain_steps = 0 then x.move_seq + 1 else x.move_seq end as move_seq,
CASE WHEN x.remain_steps > 0 THEN x.last_direction
WHEN x.last_direction IS NULL THEN y.direction
WHEN y.direction = 'L' AND x.last_direction = 'E' THEN 'N'
WHEN y.direction = 'L' AND x.last_direction = 'S' THEN 'E'
WHEN y.direction = 'L' AND x.last_direction = 'W' THEN 'S'
WHEN y.direction = 'L' AND x.last_direction = 'N' THEN 'W'
WHEN y.direction = 'R' AND x.last_direction = 'E' THEN 'S'
WHEN y.direction = 'R' AND x.last_direction = 'S' THEN 'W'
WHEN y.direction = 'R' AND x.last_direction = 'W' THEN 'N'
WHEN y.direction = 'R' AND x.last_direction = 'N' THEN 'E'
END as direction,
case when x.remain_steps = 0 then y.steps else x.remain_steps end as steps
FROM (
SELECT CASE WHEN z.tile != '#' THEN y.end_row
ELSE x._row
END as _row,
CASE WHEN z.tile != '#' THEN y.end_col
ELSE x._col
END as _col,
x.move_seq,
CASE WHEN z.tile != '#' THEN y.end_direction
ELSE x.last_direction
END as last_direction,
CASE WHEN z.tile = '#' THEN 0
WHEN z.tile != '#' AND x.remain_steps > 0 THEN x.remain_steps - 1
ELSE x.remain_steps
END as remain_steps
FROM walkthrough x
LEFT JOIN wormholes y
ON x._row = y.start_row
AND x._col = y.start_col
AND x.last_direction = y.start_direction
AND x.remain_steps > 0
LEFT JOIN maps z
ON y.end_row = z._row
AND y.end_col = z._col
) x, path y
WHERE y.seq = case when remain_steps = 0 then x.move_seq + 1 else x.move_seq end
) t
JOIN column_stats c
ON t.start_col = c._col
JOIN row_stats r
ON t.start_row = r._row
) t
)
立方体展开
实际题目与示例略有不同，实际的题目展开的形状不同，对应的虫洞也需要重新计算。
11112222
11112222
11112222
11112222
3333
3333
3333
3333
55554444
55554444
55554444
55554444
6666
6666
6666
6666
需要构建虫洞的7条边为
2,3
2,4
2,6
1,5
1,6
3,5
4,6