AdventOfCode 2022 Day 22

作者

— Day 22: Monkey Map —

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

发表评论