Day 16: The Floor Will Be Lava
Part One
很像Day 10的走迷宫，一束光进来，遇到\ / 可以反射，遇到｜—产生散射。求最后光走过的路径长度。
.|...\....
|.-.\.....
.....|-...
already_visited
需要判断某处位置是否已经走过，否则递归查询无法终止。因此通过一张表来记录所有访问过的记录。
CREATE OR REPLACE FUNCTION already_visit(_row integer, _col integer, _move text) RETURNS INTEGER AS $$
DECLARE
_result INTEGER;
BEGIN
_result := (SELECT COUNT(*) FROM path WHERE r = _row AND c = _col AND move = _move);
IF _result = 0 THEN
INSERT INTO PATH(r, c, move) values(_row, _col, _move);
END IF;
RETURN _result;
END;
$$ LANGUAGE plpgsql;
反射与散射
通过记录next_move来决定下一次光的走向。
反射，修改下方向即可。
WHEN obj = '\' AND pre_move = 'E' THEN 'S'
WHEN obj = '\' AND pre_move = 'W' THEN 'N'
WHEN obj = '\' AND pre_move = 'N' THEN 'W'
WHEN obj = '\' AND pre_move = 'S' THEN 'E'
WHEN obj = '/' AND pre_move = 'E' THEN 'N'
WHEN obj = '/' AND pre_move = 'W' THEN 'S'
WHEN obj = '/' AND pre_move = 'N' THEN 'E'
WHEN obj = '/' AND pre_move = 'S' THEN 'W'
散射的话，后续会有两个方向
WHEN obj = '|' AND pre_move IN ('N', 'S') THEN pre_move
WHEN obj = '|' AND pre_move IN ('E', 'W') THEN 'NS'
WHEN obj = '-' AND pre_move IN ('E', 'W') THEN pre_move
WHEN obj = '-' AND pre_move IN ('N', 'S') THEN 'EW'
最终SQL
WITH RECURSIVE maze AS (
SELECT _row, row_number() over (partition by _row) as _col, obj
FROM (
SELECT row_number() over () as _row, unnest(regexp_split_to_array(line, '')) as obj
FROM lance_input
) t
),
path as (
SELECT 1 as _row, 0 as _col, 'E' as next_move, false as already_visited
UNION ALL
SELECT _row, _col, next_move, already_visit(_row, _col, next_move) != 0 as already_visited
FROM (
SELECT a._row, a._col,
CASE WHEN obj = '.' THEN pre_move
WHEN obj = '|' AND pre_move IN ('N', 'S') THEN pre_move
WHEN obj = '|' AND pre_move IN ('E', 'W') THEN 'NS'
WHEN obj = '-' AND pre_move IN ('E', 'W') THEN pre_move
WHEN obj = '-' AND pre_move IN ('N', 'S') THEN 'EW'
WHEN obj = '\' AND pre_move = 'E' THEN 'S'
WHEN obj = '\' AND pre_move = 'W' THEN 'N'
WHEN obj = '\' AND pre_move = 'N' THEN 'W'
WHEN obj = '\' AND pre_move = 'S' THEN 'E'
WHEN obj = '/' AND pre_move = 'E' THEN 'N'
WHEN obj = '/' AND pre_move = 'W' THEN 'S'
WHEN obj = '/' AND pre_move = 'N' THEN 'E'
WHEN obj = '/' AND pre_move = 'S' THEN 'W'
END as next_move
FROM (
SELECT CASE WHEN next_move = 'N' then _row - 1 WHEN next_move = 'S' then _row + 1 ELSE _row END as _row,
CASE WHEN next_move = 'E' then _col + 1 WHEN next_move = 'W' then _col - 1 ELSE _col END as _col,
next_move as pre_move
FROM (
SELECT _row, _col, unnest(regexp_split_to_array(next_move, '')) as next_move
FROM path
WHERE NOT already_visited
) t
) a JOIN maze b
ON a._row = b._row
AND a._col = b._col
) t
)
SELECT COUNT(distinct _row * 110 + _col)
FROM (
SELECT _row, _col, next_move
FROM path
) t
Part Two
第二关增加了入口，可以从外围任意入口进入，从而找出路径最长的入口。
the beam enters from any edge tile and heading away from that edge
生成入口
第一关的入口是最左上角向东发出，可以看作起点为(1, 0)。现在外围都可以进入的话，那么就会有4*N个入口
entrance AS (
SELECT _row, _col, next_move
FROM (
SELECT id as _row, 0 as _col, 'E' as next_move
FROM seq limit 110
)t
UNION ALL
SELECT _row, _col, next_move
FROM (
SELECT id as _row, 111 as _col, 'W' as next_move
FROM seq limit 110
)t
UNION ALL
SELECT _row, _col, next_move
FROM (
SELECT 0 as _row, id as _col, 'S' as next_move
FROM seq limit 110
)t
UNION ALL
SELECT _row, _col, next_move
FROM (
SELECT 111 as _row, id as _col, 'N' as next_move
FROM seq limit 110
)t
)
已访问函数
CREATE OR REPLACE FUNCTION already_visit2(_entrance integer, _row integer, _col integer, _move text) RETURNS INTEGER AS $$
DECLARE
_result INTEGER;
BEGIN
_result := (SELECT COUNT(*) FROM path2 WHERE e = _entrance AND r = _row AND c = _col AND move = _move);
IF _result = 0 THEN
INSERT INTO PATH2(e, r, c, move) values(_entrance, _row, _col, _move);
END IF;
RETURN _result;
END;
$$ LANGUAGE plpgsql;
最终SQL
WITH RECURSIVE maze AS (
SELECT _row, row_number() over (partition by _row) as _col, obj
FROM (
SELECT row_number() over () as _row, unnest(regexp_split_to_array(line, '')) as obj
FROM lance_input
) t
),
seq AS (
SELECT 1 as id
UNION ALL
SELECT id + 1 as id
FROM seq
),
entrance AS (
SELECT _row, _col, next_move
FROM (
SELECT id as _row, 0 as _col, 'E' as next_move
FROM seq limit 110
)t
UNION ALL
SELECT _row, _col, next_move
FROM (
SELECT id as _row, 111 as _col, 'W' as next_move
FROM seq limit 110
)t
UNION ALL
SELECT _row, _col, next_move
FROM (
SELECT 0 as _row, id as _col, 'S' as next_move
FROM seq limit 110
)t
UNION ALL
SELECT _row, _col, next_move
FROM (
SELECT 111 as _row, id as _col, 'N' as next_move
FROM seq limit 110
)t
),
path as (
SELECT _row * 110 + _col as _entrance, _row, _col, next_move, false as already_visited
FROM entrance
UNION ALL
SELECT _entrance, _row, _col, next_move, already_visit2(_entrance, _row, _col, next_move) != 0 as already_visited
FROM (
SELECT a._row, a._col, _entrance,
CASE WHEN obj = '.' THEN pre_move
WHEN obj = '|' AND pre_move IN ('N', 'S') THEN pre_move
WHEN obj = '|' AND pre_move IN ('E', 'W') THEN 'NS'
WHEN obj = '-' AND pre_move IN ('E', 'W') THEN pre_move
WHEN obj = '-' AND pre_move IN ('N', 'S') THEN 'EW'
WHEN obj = '\' AND pre_move = 'E' THEN 'S'
WHEN obj = '\' AND pre_move = 'W' THEN 'N'
WHEN obj = '\' AND pre_move = 'N' THEN 'W'
WHEN obj = '\' AND pre_move = 'S' THEN 'E'
WHEN obj = '/' AND pre_move = 'E' THEN 'N'
WHEN obj = '/' AND pre_move = 'W' THEN 'S'
WHEN obj = '/' AND pre_move = 'N' THEN 'E'
WHEN obj = '/' AND pre_move = 'S' THEN 'W'
END as next_move
FROM (
SELECT CASE WHEN next_move = 'N' then _row - 1 WHEN next_move = 'S' then _row + 1 ELSE _row END as _row,
CASE WHEN next_move = 'E' then _col + 1 WHEN next_move = 'W' then _col - 1 ELSE _col END as _col,
next_move as pre_move, _entrance
FROM (
SELECT _entrance, _row, _col, unnest(regexp_split_to_array(next_move, '')) as next_move
FROM path
WHERE NOT already_visited
) t
) a JOIN maze b
ON a._row = b._row
AND a._col = b._col
) t
)
SELECT _entrance, COUNT(distinct _row * 110 + _col)
FROM (
SELECT _entrance, _row, _col, next_move
FROM path
) t
GROUP BY _entrance
ORDER BY 2 DESC;