AdventOfCode 2022 Day 9

作者

Day 9: Rope Bridge

Part One

绳子有两个绳结：head和tail，head移动的时候，tail跟随移动。求几步移动操作后，tail的移动轨迹

R 4
U 4
L 3
D 1

假设初始起点的坐标为(100, 100)，记录head和tail的坐标变化。其中head的坐标变化容易记录，只需要依据每一步的移动，简单对坐标进行加减即可。

1
2
3
4
5
6
7
8
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的距离来决定，只有当距离超过范围（绳子已经“完全绷紧了”）时，才需要移动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
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的运算完全根据输入的方向来确定，后续绳结的运算完全根据前一个绳结的位置来确定。

拆解移动步数

将移动步数拆解到每一步，某个方向上行动多少步，就产生多少条记录。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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为当前处理的绳结序号

1
2
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来记录下上一步的坐标

1
2
3
4
5
6
7
8
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中所有的移动走遍历完毕。

1
2
3
4
5
6
7
8
9
10
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中的移动方向来确定

1
2
3
4
5
6
7
8
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

而其他的绳结，则完全根据前一个绳结的坐标来确定。当距离过大时，进行必要的移动

1
2
3
4
5
6
7
8
9
10
11
12
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
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;

发表评论