Part One
绳子有两个绳结：head和tail，head移动的时候，tail跟随移动。求几步移动操作后，tail的移动轨迹
R 4
U 4
L 3
D 1
假设初始起点的坐标为(100, 100)，记录head和tail的坐标变化。其中head的坐标变化容易记录，只需要依据每一步的移动，简单对坐标进行加减即可。
CASE WHEN x.direction = 'U' THEN z.head_row - y.id
WHEN x.direction = 'D' THEN z.head_row + y.id
ELSE z.head_row
END as head_row,
CASE WHEN x.direction = 'L' THEN z.head_col - y.id
WHEN x.direction = 'R' THEN z.head_col + y.id
ELSE z.head_col
END as head_col
而tail的坐标变化，需要依据和tail的距离来决定，只有当距离超过范围（绳子已经“完全绷紧了”）时，才需要移动
CASE WHEN (abs(tail_row - head_row) > 1) OR (abs(tail_col - head_col) > 1) THEN
CASE WHEN direction = 'U' THEN head_row + 1
WHEN direction = 'D' THEN head_row - 1
ELSE head_row
END
ELSE tail_row
END as tail_row,
CASE WHEN (abs(tail_row - head_row) > 1) OR (abs(tail_col - head_col) > 1) THEN
CASE WHEN direction = 'L' THEN head_col + 1
WHEN direction = 'R' THEN head_col - 1
ELSE head_col
END
ELSE tail_col
END as tail_col
最终的SQL如下
with recursive origin AS (
SELECT row_number() over () as rn, split_part(line, ' ', 1) as direction, split_part(line, ' ', 2) :: integer as steps
FROM lance_input
), seq AS (
SELECT 1 as id
UNION ALL
SELECT id + 1 as id
FROM seq
), positions AS (
SELECT 100 as head_row, 100 as head_col, 100 as tail_row, 100 as tail_col, 0 :: bigint as rn, 0 :: bigint as steps
UNION ALL
SELECT *
FROM (
WITH last_record AS (
SELECT head_row, head_col, tail_row, tail_col, rn, steps
FROM (
SELECT head_row, head_col, tail_row, tail_col, rn, steps,
row_number() over(order by steps desc) as row_num
FROM positions
) t
WHERE row_num = 1
)
SELECT head_row, head_col,
CASE WHEN (abs(tail_row - head_row) > 1) OR (abs(tail_col - head_col) > 1) THEN
CASE WHEN direction = 'U' THEN head_row + 1
WHEN direction = 'D' THEN head_row - 1
ELSE head_row
END
ELSE tail_row
END as tail_row,
CASE WHEN (abs(tail_row - head_row) > 1) OR (abs(tail_col - head_col) > 1) THEN
CASE WHEN direction = 'L' THEN head_col + 1
WHEN direction = 'R' THEN head_col - 1
ELSE head_col
END
ELSE tail_col
END as tail_col,
rn, steps
FROM (
SELECT CASE WHEN x.direction = 'U' THEN z.head_row - y.id
WHEN x.direction = 'D' THEN z.head_row + y.id
ELSE z.head_row
END as head_row,
CASE WHEN x.direction = 'L' THEN z.head_col - y.id
WHEN x.direction = 'R' THEN z.head_col + y.id
ELSE z.head_col
END as head_col,
z.tail_row,
z.tail_col,
x.rn as rn,
z.steps + y.id as steps,
x.direction
FROM origin x,
(select id from seq limit (select max(steps) from origin)) y,
last_record z
WHERE x.rn = z.rn + 1
AND y.id <= x.steps
) t
) t
)
select count(distinct tail_row || ',' || tail_col) From positions;
Part Two
绳子不再只有head和tail，而是变成了10个绳结，求出最后一个绳结的移动轨迹。
head - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - tail
先分析下，现在变成了10个绳结，head移动的时候，会通过连带触发后续绳结的移动。因此，需要计算每一个绳结的移动轨迹，才能确定tail的移动轨迹。
因此这里每移动一步，需要迭代10次运算，才能确定tail的移动轨迹。在这10次运算中，head的运算完全根据输入的方向来确定，后续绳结的运算完全根据前一个绳结的位置来确定。
拆解移动步数
将移动步数拆解到每一步，某个方向上行动多少步，就产生多少条记录。
postgres=# with recursive origin AS (
postgres(# SELECT row_number() over () as rn, split_part(line, ' ', 1) as direction, split_part(line, ' ', 2) :: integer as steps
postgres(# FROM lance_input
postgres(# ), seq AS (
postgres(# SELECT 1 as id
postgres(# UNION ALL
postgres(# SELECT id + 1 as id
postgres(# FROM seq
postgres(# ), moves AS (
postgres(# SELECT row_number() over () as step, x.direction
postgres(# FROM origin x
postgres(# JOIN (select id from seq limit (select max(steps) from origin)) y
postgres(# ON y.id <= x.steps
postgres(# )
postgres-# SELECT * FROM moves limit 10;
step | direction
------+-----------
1 | D
2 | U
3 | U
4 | R
5 | R
6 | U
7 | R
8 | U
9 | U
10 | L
(10 rows)
每一步10次运算
每一步需要10次运算，可以通过10次子查询，并且将10个绳结的坐标打宽来实现，不过这样可读性较差。也可以用纵表的方式，通过每个绳结1条记录来实现。
初始化10个绳结的坐标，step为当前步数，knot_seq为绳结的序号，current_knot为当前处理的绳结序号
SELECT 100 as _row, 100 as _col, seq.id as knot_seq, 0 :: bigint as step, 10 as current_knot
FROM seq limit 10
再通过CTE来记录下上一步的坐标
WITH ps AS (
SELECT * FROM positions
), pre_position AS (
SELECT _row, _col, current_knot as knot
FROM ps
WHERE knot_seq = current_knot
LIMIT 1
)
每一步迭代，将current_knot持续递增，直到knot=10的时候，执行下一步的移动，再继续下一轮10次运算。因此，每一步移动会生成100条记录。这里的终止条件，就是处理到了第10个knot，且moves中所有的移动走遍历完毕。
SELECT ps.knot_seq,
coalesce(moves.step, ps.step) as step,
ps.current_knot % 10 + 1 as current_knot
FROM ps
LEFT JOIN moves
ON ps.current_knot = 10
AND ps.step + 1 = moves.step
JOIN pre_position pre
ON 1 = 1
WHERE NOT (ps.current_knot = 10 AND moves.step is null)
绳结坐标计算
knot_seq=1，即head，其坐标完全根据moves中的移动方向来确定
CASE WHEN moves.direction = 'U' THEN ps._row - 1
WHEN moves.direction = 'D' THEN ps._row + 1
ELSE ps._row
END as _row,
CASE WHEN moves.direction = 'L' THEN ps._col - 1
WHEN moves.direction = 'R' THEN ps._col + 1
ELSE ps._col
END as _col
而其他的绳结，则完全根据前一个绳结的坐标来确定。当距离过大时，进行必要的移动
CASE WHEN pre._row < ps._row - 1 THEN pre._row + 1
WHEN pre._row > ps._row + 1 THEN pre._row - 1
WHEN pre._col < ps._col - 1 THEN pre._row
WHEN pre._col > ps._col + 1 THEN pre._row
ELSE ps._row
END as _row,
CASE WHEN pre._col < ps._col - 1 THEN pre._col + 1
WHEN pre._col > ps._col + 1 THEN pre._col - 1
WHEN pre._row < ps._row - 1 THEN pre._col
WHEN pre._row > ps._row + 1 THEN pre._col
ELSE ps._col
END as _col
当前处理的不是自己的时候，则保持不变即可
最终SQL
with recursive origin AS (
SELECT row_number() over () as rn, split_part(line, ' ', 1) as direction, split_part(line, ' ', 2) :: integer as steps
FROM lance_input
), seq AS (
SELECT 1 as id
UNION ALL
SELECT id + 1 as id
FROM seq
), moves AS (
SELECT row_number() over () as step, x.direction
FROM origin x
JOIN (select id from seq limit (select max(steps) from origin)) y
ON y.id <= x.steps
), positions AS (
SELECT *
FROM (
SELECT 100 as _row, 100 as _col, seq.id as knot_seq, 0 :: bigint as step, 10 as current_knot
FROM seq limit 10
) t
UNION ALL
SELECT *
FROM (
WITH ps AS (
SELECT * FROM positions
), pre_position AS (
SELECT _row, _col, current_knot as knot
FROM ps
WHERE knot_seq = current_knot
LIMIT 1
)
SELECT CASE WHEN moves.step is not null AND knot_seq = 1 THEN
CASE WHEN moves.direction = 'U' THEN ps._row - 1
WHEN moves.direction = 'D' THEN ps._row + 1
ELSE ps._row
END
WHEN moves.step is not null AND knot_seq != 1 THEN ps._row
WHEN moves.step is null AND knot_seq = pre.knot + 1 THEN
CASE WHEN pre._row < ps._row - 1 THEN pre._row + 1
WHEN pre._row > ps._row + 1 THEN pre._row - 1
WHEN pre._col < ps._col - 1 THEN pre._row
WHEN pre._col > ps._col + 1 THEN pre._row
ELSE ps._row
END
WHEN moves.step is null AND knot_seq != pre.knot + 1 THEN ps._row
END as _row,
CASE WHEN moves.step is not null AND knot_seq = 1 THEN
CASE WHEN moves.direction = 'L' THEN ps._col - 1
WHEN moves.direction = 'R' THEN ps._col + 1
ELSE ps._col
END
WHEN moves.step is not null AND knot_seq != 1 THEN ps._col
WHEN moves.step is null AND knot_seq = pre.knot + 1 THEN
CASE WHEN pre._col < ps._col - 1 THEN pre._col + 1
WHEN pre._col > ps._col + 1 THEN pre._col - 1
WHEN pre._row < ps._row - 1 THEN pre._col
WHEN pre._row > ps._row + 1 THEN pre._col
ELSE ps._col
END
WHEN moves.step is null AND knot_seq != pre.knot + 1 THEN ps._col
END as _col,
ps.knot_seq,
coalesce(moves.step, ps.step) as step,
ps.current_knot % 10 + 1 as current_knot
FROM ps
LEFT JOIN moves
ON ps.current_knot = 10
AND ps.step + 1 = moves.step
JOIN pre_position pre
ON 1 = 1
WHERE NOT (ps.current_knot = 10 AND moves.step is null)
) t
)
SELECT count(distinct _row || ',' || _col) FROM positions where knot_seq = 10 and current_knot = 10;