AdventOfCode 2023 Day 17

作者

Day 17: Clumsy Crucible

Part One

同样的走迷宫，计算从左上走到右下的数字之和最小的路径。有同一方向最多三步的限制。

2413432311323
3215453535623
3255245654254
3446585845452

计算最短距离，应该使用Dijkstra算法，但是这题不是简单的计算最短路径，有同一方向最多三步的约束，导致无法直接使用该算法。还是先使用SQL的递归查询，看看如何解这个问题。

最短路径选择

首先，一个位置上是否仅保留一个最短路径即可？举例来说，(1, 6)位置上的最短距离，其路径是(2,4,1,1,5,4,4,3)，而正确答案中的路径是(2,4,1,1,5,4,5,3)，并不是最短路径。因此如果丢失了这条路径，那么最终的最短路径也忽略了这一条路径了。

因此每个位置需要保留不同来源的最短路径，这个来源的意思如下

分析到达这个位置的前三步方向

NEE, SEE是等价的，因为到达这个位置后，最多再往东行走一步。
NNE, WNE, WWE, SSE等，这些也是等价的，到达这个位置后，在东方向上只行走了一步

因为可以根据达到位置之前的三步，精简为[EEE, EE, E]等，这样每个位置仅保留有限的路径数

CREATE OR REPLACE FUNCTION trim_move(moves VARCHAR)
RETURNS VARCHAR AS $$
DECLARE 
    last_char VARCHAR;
    return_char VARCHAR := '';
BEGIN
    IF moves = '' THEN
      return '';
    END IF;

    last_char := substring(moves, length(moves), 1);
    FOR i IN 1 .. length(moves) LOOP
      IF substring(moves, length(moves) - i + 1, 1) != last_char THEN
        EXIT;
      ELSE
        return_char := return_char || substring(moves, length(moves) - i + 1, 1);
      END IF;
    END LOOP;

    return return_char;
END;
$$ LANGUAGE plpgsql;

再通过一个函数，来计算当前路径是否仍然有效，判断依据就是路径长度是否最短。如果不是最短，则无需再继续了。

CREATE OR REPLACE FUNCTION visit(row_id INTEGER, col_id INTEGER, _direction VARCHAR, _total_loss INTEGER)
RETURNS BIGINT AS $$
DECLARE
    loss INTEGER;
BEGIN
    INSERT INTO matrix VALUES(row_id, col_id, _direction, _total_loss) 
    ON CONFLICT(_row, _col, direction) DO UPDATE SET sum_loss = _total_loss WHERE _total_loss < matrix.sum_loss returning matrix.sum_loss INTO loss;
    RETURN loss;
END;
$$ LANGUAGE plpgsql;

最终SQL

WITH RECURSIVE origin AS (
  SELECT _row, row_number() over (partition by _row) as _col, loss :: integer
  FROM (
    SELECT row_number() over () as _row, unnest(regexp_split_to_array(line, '')) as loss
    FROM lance_input
  )t
),
maze AS (
  SELECT _row :: INTEGER, _col :: INTEGER, 0 as total_loss, '' last_3_moves, true as is_valid
  FROM origin
  WHERE _row = 1 AND _col = 1

  UNION ALL

  SELECT t._row, t._col, t.total_loss + origin.loss as total_loss, t.last_3_moves,
  CASE WHEN visit(t._row, t._col, trim_move(last_3_moves), t.total_loss + origin.loss) IS NOT NULL THEN true
  ELSE false
  END as is_valid
  FROM (
    SELECT CASE WHEN b.direction = 'S' THEN _row + 1 WHEN b.direction = 'N' THEN _row - 1 ELSE _row END as _row,
    CASE WHEN b.direction = 'E' THEN _col + 1 WHEN b.direction = 'W' THEN _col - 1 ELSE _col END as _col,
    a.total_loss,
    CASE WHEN length(last_3_moves) < 3 THEN last_3_moves || b.direction ELSE substring(last_3_moves, 2, 2) || b.direction END AS last_3_moves,
    last_3_moves || direction as last_moves
    FROM (SELECT DISTINCT * FROM maze) a, (SELECT unnest(regexp_split_to_array('ESWN', '')) as direction) b
    WHERE a.is_valid
  ) t JOIN origin
  ON t._row = origin._row
  AND t._col = origin._col
  AND last_moves NOT IN ('EEEE', 'SSSS', 'WWWW', 'NNNN')
  AND last_moves NOT LIKE '%EW'
  AND last_moves NOT LIKE '%WE'
  AND last_moves NOT LIKE '%NS'
  AND last_moves NOT LIKE '%SN'
)
SELECT * FROM maze;

最终查找该位置的最短距离即可

postgres=# select * from matrix where _row = 141 and _col = 141; 
 _row | _col | direction | sum_loss 
------+------+-----------+----------
  141 |  141 | E         |      758
  141 |  141 | EE        |      762
  141 |  141 | EEE       |      762
  141 |  141 | S         |      760
  141 |  141 | SS        |      762
  141 |  141 | SSS       |      764
(6 rows)

Part Two

第二关，在之前的基础上增加了新的限制，同方向至少4步，至多10步。

1>>>>>>>1111
9999999v9991
9999999v9991
9999999v9991
9999999v>>>>

移动方向是否有效

基础的SQL应该不用改，只是修改下判断当前方向是否有效的逻辑即可。

CASE WHEN last_3_moves = '' THEN true
    WHEN length(trim_move(last_3_moves)) < 4 THEN substring(last_3_moves, length(last_3_moves), 1) = b.direction
    WHEN length(trim_move(last_3_moves)) >= 10 THEN substring(last_3_moves, length(last_3_moves), 1) != b.direction
    ELSE true
END as valid_move,

还有一个陷阱，最后一步到达终点的时候也需要遵循这个逻辑，否则上文中的例子，结果应该是47，而不是71了。

postgres=# select * from matrix order by 1 desc , 2 desc;
 _row | _col | direction  | sum_loss 
------+------+------------+----------
    5 |   12 | SSSS       |      111
    5 |   12 | EEEEEEEEEE |      203
    5 |   12 | EEEEEEEEE  |      193
    5 |   12 | EEEEEEEE   |      183
    5 |   12 | EEEEEEE    |       95
    5 |   12 | EEEEEE     |       87
    5 |   12 | EEEEE      |       79
    5 |   12 | EEEE       |       71
    5 |   12 | EEE        |       63
    5 |   12 | EE         |       55
    5 |   12 | E          |       47

最终SQL

WITH RECURSIVE origin AS (
  SELECT _row, row_number() over (partition by _row) as _col, loss :: integer
  FROM (
    SELECT row_number() over () as _row, unnest(regexp_split_to_array(line, '')) as loss 
    FROM lance_input
  )t
),
maze AS (
  SELECT _row :: INTEGER, _col :: INTEGER, 0 as total_loss, '' last_3_moves, true as is_valid
  FROM origin
  WHERE _row = 1 AND _col = 1

  UNION ALL

  SELECT t._row, t._col, t.total_loss + origin.loss as total_loss, t.last_3_moves, 
         CASE WHEN visit(t._row, t._col, trim_move(last_3_moves), t.total_loss + origin.loss) IS NOT NULL THEN true
              ELSE false
         END as is_valid 
  FROM (
    SELECT CASE WHEN b.direction = 'S' THEN _row + 1 WHEN b.direction = 'N' THEN _row - 1 ELSE _row END as _row,
           CASE WHEN b.direction = 'E' THEN _col + 1 WHEN b.direction = 'W' THEN _col - 1 ELSE _col END as _col,
           a.total_loss,
           CASE WHEN last_3_moves = '' THEN true
                WHEN length(trim_move(last_3_moves)) < 4 THEN substring(last_3_moves, length(last_3_moves), 1) = b.direction
                WHEN length(trim_move(last_3_moves)) >= 10 THEN substring(last_3_moves, length(last_3_moves), 1) != b.direction
                ELSE true
           END as valid_move,
           CASE WHEN length(last_3_moves) < 10 THEN last_3_moves || b.direction ELSE substring(last_3_moves, 2, 9) || b.direction END AS last_3_moves,
           last_3_moves || direction as last_moves
    FROM (SELECT DISTINCT * FROM maze) a, (SELECT unnest(regexp_split_to_array('ESWN', '')) as direction) b
    WHERE a.is_valid
  ) t JOIN origin
  ON t._row = origin._row
  AND t._col = origin._col
  AND valid_move
  AND last_moves NOT LIKE '%EW'
  AND last_moves NOT LIKE '%WE'
  AND last_moves NOT LIKE '%NS'
  AND last_moves NOT LIKE '%SN'
) 
SELECT * FROM maze;

最终答案，需要找到至少4步的结果

postgres=# select * from matrix where _row = 141 and _col = 141 order by sum_loss;
 _row | _col | direction  | sum_loss 
------+------+------------+----------
  141 |  141 | E          |      887
  141 |  141 | SSSSSSSS   |      892
  141 |  141 | SS         |      893
  141 |  141 | S          |      894
  141 |  141 | SSS        |      894
  141 |  141 | SSSSS      |      894
  141 |  141 | SSSS       |      895
  141 |  141 | EEE        |      896
  141 |  141 | SSSSSS     |      897
  141 |  141 | SSSSSSSSSS |      897
  141 |  141 | EE         |      897
  141 |  141 | EEEE       |      898
  141 |  141 | SSSSSSSSS  |      898
  141 |  141 | EEEEEE     |      899
  141 |  141 | SSSSSSS    |      899
  141 |  141 | EEEEE      |      900
  141 |  141 | EEEEEEE    |      904
  141 |  141 | EEEEEEEE   |      908
  141 |  141 | EEEEEEEEE  |      911
  141 |  141 | EEEEEEEEEE |      911

发表评论