AdventOfCode 2022 Day 23

作者

— Day 23: Unstable Diffusion —

Part One

#位置为一个Elf，每一轮都会按照一定的顺序移动一个位置，或者停留在本地。最终让每个Elf都互不相邻。

.....
..##.
..#..
.....
..##.
.....

移动函数

其移动规则为首先顺次判断(N,S,W,E)四个方向，哪个方向上不会有邻居，则在该方向上移动一步。四个方向都无邻居，则无需移动。总之，逐渐远离彼此。每一轮会顺延方向判断的优先级，因此需要记录上一次的索引。

CREATE OR REPLACE FUNCTION move_direction(neighbours INTEGER[], last_start INTEGER)
RETURNS INTEGER AS $$
BEGIN
    IF neighbours[1] = 0 AND neighbours[2] = 0 AND neighbours[3] = 0 AND neighbours[4] = 0 THEN
      RETURN 0;
    END IF;

    FOR i IN 1..4 LOOP
      IF neighbours[(last_start + i - 1) % 4 + 1] = 0 THEN
        return (last_start + i - 1) % 4 + 1;
      END IF;
    END LOOP;
 
    RETURN 0;
  
END;
$$ LANGUAGE plpgsql;

行走路径

初始条件，仅需要知晓Elf的位置即可。next_move代表这一轮移动的方向，0代表不移动，1234代表NSWE。

WITH recursive origin AS (
  SELECT rn as _row, x.idx as _col, x.word as pos
  FROM (
    SELECT row_number() over() as rn, line
    FROM lance_input
  ) t, regexp_split_to_table(line, '') with ordinality as x(word, idx)
)
  SELECT _row, _col, 0 as next_move, 0 as last_start
  FROM origin
  WHERE pos = '#'

然后求出每个Elf的8个方向上的邻居

pos_relation AS (
      SELECT x._row, x._col, x.last_start,
             y._row as neighbour_row, y._col as neighbour_col,
             CASE WHEN y._row = x._row - 1 and y._col = x._col - 1 THEN 'NW'
                  WHEN y._row = x._row - 1 and y._col = x._col THEN 'N'
                  WHEN y._row = x._row - 1 and y._col = x._col + 1 THEN 'NE'
                  WHEN y._row = x._row + 1 and y._col = x._col - 1 THEN 'SW'
                  WHEN y._row = x._row + 1 and y._col = x._col THEN 'S'
                  WHEN y._row = x._row + 1 and y._col = x._col + 1 THEN 'SE'
                  WHEN y._row = x._row and y._col = x._col - 1 THEN 'W'
                  WHEN y._row = x._row and y._col = x._col + 1 THEN 'E'
              END as direction
      FROM inner_table x
      JOIN inner_table y
      ON abs(x._row - y._row) <= 1
      AND abs(x._col - y._col) <= 1
    )

从而获取四个大方向上的邻居个数

pos_stats AS (
      SELECT _row, _col, last_start, 
             count(CASE WHEN direction like '%N%' THEN direction END) :: INTEGER as north_neighbours,
             count(CASE WHEN direction like '%S%' THEN direction END) :: INTEGER as south_neighbours,
             count(CASE WHEN direction like '%W%' THEN direction END) :: INTEGER as west_neighbours,
             count(CASE WHEN direction like '%E%' THEN direction END) :: INTEGER as east_neighbours
      FROM pos_relation
      GROUP BY _row, _col, last_start
    )

根据移动函数，计算出下一步移动的方向

pos_move AS (
      SELECT _row, _col,
             CASE WHEN next_move = 1 THEN _row - 1
                  WHEN next_move = 2 THEN _row + 1
                  ELSE _row
              END as target_row,
             CASE WHEN next_move = 3 THEN _col - 1
                  WHEN next_move = 4 THEN _col + 1
                  ELSE _col
              END as target_col,
             last_start,
             next_move
      FROM (
        SELECT _row, _col, last_start,
               move_direction(ARRAY[north_neighbours, south_neighbours, west_neighbours, east_neighbours], last_start) as next_move
        FROM pos_stats
      ) t
    )

最后，由于两个Elf不能移动到同一个位置，因此需要过滤掉位置相同的移动

pos_move_duplicate AS (
      SELECT target_row, target_col
      FROM pos_move
      GROUP BY target_row, target_col
      HAVING count(*) > 1
    ), pos_move_final AS (
      SELECT x._row, x._col,
             CASE WHEN y.target_row is not null THEN x._row ELSE x.target_row END as target_row,
             CASE WHEN y.target_row is not null THEN x._col ELSE x.target_col END as target_col,
             CASE WHEN y.target_row is not null THEN 0 ELSE next_move END as next_move
      FROM pos_move x
      LEFT JOIN pos_move_duplicate y
      ON x.target_row = y.target_row
      AND x.target_col = y.target_col
    )

已知移动位置后，将Elf移动到对应的位置，形成一轮后的新位置，并作为下一轮的输入值

    SELECT CASE WHEN y._row is not null THEN y.target_row ELSE x._row END as _row,
           CASE WHEN y._col is not null THEN y.target_col ELSE x._col END as _col,
           CASE WHEN y.next_move is not null THEN y.next_move ELSE 0 END as next_move,
           x.last_start + 1 as last_start
    FROM inner_table x
    LEFT JOIN pos_move_final y
    ON x._row = y._row
    AND x._col = y._col
    AND next_move != 0

经过10轮迭代后，就能得知各个Elf的位置，就可以很容易计算出结果。

Part Two

目标就是求出多少轮后，Elves之间足够稀疏，不需要再次移动

宇宙膨胀，星系逐渐远离彼此……

终止条件

终止条件就是所有的Elf都无需移动，因此添加此过滤条件即可。

    SELECT CASE WHEN y._row is not null THEN y.target_row ELSE x._row END as _row,
           CASE WHEN y._col is not null THEN y.target_col ELSE x._col END as _col,
           CASE WHEN y.next_move is not null THEN y.next_move ELSE 0 END as next_move,
           x.last_start + 1 as last_start
    FROM inner_table x
    LEFT JOIN pos_move_final y
    ON x._row = y._row
    AND x._col = y._col
    AND next_move != 0
    WHERE EXISTS(SELECT * from pos_move_final WHERE next_move != 0)

不过，运算时间还是比较长的，此算法效率比较低。

推演

大致分析下所有Elves的移动，应该是内圈的Elf逐渐稳定，从内到外逐渐扩散。但是需要注意

  • 某一轮不移动并不代表最终稳定，因为按照NSWE的方向依次移动，很有可能后续轮其他Elf靠近它，导致了再次移动。
  • 大方向上，应该是需要移动的Elf个数逐渐减少，最终全部稳定。

通过统计每一轮的移动Elves个数，验证我们的推测

          95 |      842
          96 |      893
          97 |      848
          98 |      914
          99 |      866
         100 |      937
         101 |      850

可见每一轮的移动个数并不是递减，某一轮不移动并不代表最终停止。

        650 |      915
        700 |      707
        750 |      522
        800 |      393
        850 |      249
        900 |      124
        950 |       43

一个优化方向，就是确定哪些Elves已经确定无需移动了，后续计算也无需考虑，应该可以节省大量的计算时间，方案待补充。

发表评论