AdventOfCode 2022 Day 17

作者

— Day 17: Pyroclastic Flow —

Part One

俄罗斯方块的游戏，模拟方块下落时被左右移动，并最终计算2022个方块后的高度。一共5种方块

####

.#.
###
.#.

..#
..#
###

#
#
#
#

##
##

存储结构

为了尽量提升速度，无需插入到表中，只在内存中进行计算。最主要的运算，其实就是方块移动到新位置后，是否与已有的方块冲突。如果无法继续下落时，则方块确定位置，开始掉落下一个方块。

一共只有7列位置可以选择，那么可以用7个字符串来存储已有方块占用的位置信息，比如”1|4″代表y轴的[1-4]被占用，再将多个位置汇集到一起，比如”1|4, 6|7″。

每个方块都有确定的覆盖位置，假如一个方块最左上的坐标为(pos_x, pos_y)，那么可以计算出方块的覆盖位置信息

    IF shape_type = '-' THEN
      origin_array[pos_x] := pos_y || '|' || pos_y;
      origin_array[pos_x + 1] := pos_y || '|' || pos_y;
      origin_array[pos_x + 2] := pos_y || '|' || pos_y;
      origin_array[pos_x + 3] := pos_y || '|' || pos_y;
    END IF;

    IF shape_type = '+' THEN
      origin_array[pos_x] := (pos_y - 1) || '|' || (pos_y - 1);
      origin_array[pos_x + 1] := (pos_y - 2) || '|' || pos_y;
      origin_array[pos_x + 2] := (pos_y - 1) || '|' || (pos_y - 1);
    END IF;

再通过一个函数，来计算方块是否和已有方块位置冲突，从而确定方块是否可以移动到新位置

CREATE OR REPLACE FUNCTION shape_rock_intersect(shape_pos VARCHAR, rock_pos VARCHAR)
RETURNS BOOLEAN AS $$
DECLARE
    shape_min INTEGER;
    shape_max INTEGER;
    rock_array VARCHAR[];
    rock_min INTEGER;
    rock_max INTEGER;
BEGIN
    IF shape_pos IS NULL OR shape_pos = '' OR rock_pos IS NULL OR rock_pos = '' THEN
      RETURN FALSE;
    END IF;

    shape_min := split_part(shape_pos, '|', 1) :: INTEGER;
    shape_max := split_part(shape_pos, '|', 2) :: INTEGER;

    rock_array := string_to_array(rock_pos, ',');

    FOR i IN 1..cardinality(rock_array) LOOP
      rock_min := split_part(rock_array[i], '|', 1) :: INTEGER;
      rock_max := split_part(rock_array[i], '|', 2) :: INTEGER;

      IF rock_min <= shape_max AND rock_max >= shape_min THEN
        RETURN TRUE;
      END IF;
    END LOOP;

    RETURN FALSE;

END;
$$ LANGUAGE plpgsql;

移动方块

移动方块，可以按照输入的方向进行左右移动，随后再下落一层，用<>v来代替对应方向

    -- move the shape to new position
    IF move_direction = 'v' THEN
      new_x := pos_x;
      new_y := pos_y - 1;
    END IF;

    IF move_direction = '>' THEN
      new_x := pos_x + 1;
      new_y := pos_y;
      min_x := min_x + 1;
      max_x := max_x + 1;
    END IF;

    IF move_direction = '<' THEN
      new_x := pos_x - 1;
      new_y := pos_y;
      min_x := min_x - 1;
      max_x := max_x - 1;
    END IF;

移动到新位置后，先判断是否越过了边界。如果左右超过边界，则直接返回，如果向下超过边界，则代表已经触底，停止后续移动

    -- if we cross the border
    IF new_y < 1 THEN
      -- touch the bottom, become stopped
      FOR i IN 1..7 LOOP
        IF origin_array[i] IS NOT NULL THEN
          pos_array[i] := ltrim(coalesce(pos_array[i], '') || ',' || origin_array[i], ',');
        END IF;
      END LOOP;

      RETURN (TRUE, pos_x, pos_y, pos_array);
    END IF;

    IF min_x < 1 OR max_x > 7 THEN
      -- touch the border
      RETURN (FALSE, pos_x, pos_y, pos_array);
    END IF;

如果没有越过边界，则计算是否与现有方块冲突。有冲突的话，则返回旧有位置；无冲突的话，则返回新的位置

    -- if intersect with rocks
    FOR i IN 1..7 LOOP
      IF shape_rock_intersect(moved_array[i], pos_array[i]) THEN
        shape_intersect = TRUE;
      END IF;
    END LOOP;

在有冲突的时候，如果无法继续左右移动，则无需进一步处理；如果是无法继续向下移动，则表示方块已停止，需要更新已有方块信息

    -- stopped, add to the pos_array
    IF move_direction = 'v' THEN
      FOR i IN 1..7 LOOP
        IF origin_array[i] IS NOT NULL THEN
          pos_array[i] := ltrim(coalesce(pos_array[i], '') || ',' || origin_array[i], ',');
        END IF;
      END LOOP;
    END IF;

完整的方块移动函数

CREATE OR REPLACE FUNCTION move_shape(shape_type VARCHAR, pos_x INTEGER, pos_y INTEGER, move_direction VARCHAR, pos_array VARCHAR[7])
RETURNS RECORD AS $$
DECLARE
    origin_array VARCHAR[7];
    moved_array VARCHAR[7];
    shape_intersect BOOLEAN := FALSE;
    min_x INTEGER;
    max_x INTEGER;
    new_x INTEGER;
    new_y INTEGER;
BEGIN
    -- calculate original position array
    IF shape_type = '-' THEN
      origin_array[pos_x] := pos_y || '|' || pos_y;
      origin_array[pos_x + 1] := pos_y || '|' || pos_y;
      origin_array[pos_x + 2] := pos_y || '|' || pos_y;
      origin_array[pos_x + 3] := pos_y || '|' || pos_y;
      min_x := pos_x;
      max_x := pos_x + 3;
    END IF;

    IF shape_type = '+' THEN
      origin_array[pos_x] := (pos_y - 1) || '|' || (pos_y - 1);
      origin_array[pos_x + 1] := (pos_y - 2) || '|' || pos_y;
      origin_array[pos_x + 2] := (pos_y - 1) || '|' || (pos_y - 1);
      min_x := pos_x;
      max_x := pos_x + 2;
    END IF;

    IF shape_type = 'J' THEN
      origin_array[pos_x] := (pos_y - 2) || '|' || (pos_y - 2);
      origin_array[pos_x + 1] := (pos_y - 2) || '|' || (pos_y - 2);
      origin_array[pos_x + 2] := (pos_y - 2) || '|' || pos_y;
      min_x := pos_x;
      max_x := pos_x + 2;
    END IF;


    IF shape_type = '|' THEN
      origin_array[pos_x] := (pos_y - 3) || '|' || pos_y;
      min_x := pos_x;
      max_x := pos_x;
    END IF;

    IF shape_type = '#' THEN
      origin_array[pos_x] := (pos_y - 1) || '|' || pos_y;
      origin_array[pos_x + 1] := (pos_y - 1) || '|' || pos_y;
      min_x := pos_x;
      max_x := pos_x + 1;
    END IF;



    -- move the shape to new position
    IF move_direction = 'v' THEN
      new_x := pos_x;
      new_y := pos_y - 1;
    END IF;

    IF move_direction = '>' THEN
      new_x := pos_x + 1;
      new_y := pos_y;
      min_x := min_x + 1;
      max_x := max_x + 1;
    END IF;

    IF move_direction = '<' THEN
      new_x := pos_x - 1;
      new_y := pos_y;
      min_x := min_x - 1;
      max_x := max_x - 1;
    END IF;

    -- if we cross the border
    IF new_y < 1 THEN
      -- touch the bottom, become stopped
      FOR i IN 1..7 LOOP
        IF origin_array[i] IS NOT NULL THEN
          pos_array[i] := ltrim(coalesce(pos_array[i], '') || ',' || origin_array[i], ',');
        END IF;
      END LOOP;

      RETURN (TRUE, pos_x, pos_y, pos_array);
    END IF;

    IF min_x < 1 OR max_x > 7 THEN
      -- touch the border
      RETURN (FALSE, pos_x, pos_y, pos_array);
    END IF;




    -- calculate the new position array
    IF shape_type = '-' THEN
      moved_array[new_x] := new_y || '|' || new_y;
      moved_array[new_x + 1] := new_y || '|' || new_y;
      moved_array[new_x + 2] := new_y || '|' || new_y;
      moved_array[new_x + 3] := new_y || '|' || new_y;
    END IF;

    IF shape_type = '+' THEN
      moved_array[new_x] := (new_y - 1) || '|' || (new_y - 1);
      moved_array[new_x + 1] := (new_y - 2) || '|' || new_y;
      moved_array[new_x + 2] := (new_y - 1) || '|' || (new_y - 1);
    END IF;

    IF shape_type = 'J' THEN
      moved_array[new_x] := (new_y - 2) || '|' || (new_y - 2);
      moved_array[new_x + 1] := (new_y - 2) || '|' || (new_y - 2);
      moved_array[new_x + 2] := (new_y - 2) || '|' || new_y;
    END IF;

    IF shape_type = '|' THEN
      moved_array[new_x] := (new_y - 3) || '|' || new_y;
    END IF;

    IF shape_type = '#' THEN
      moved_array[new_x] := (new_y - 1) || '|' || new_y;
      moved_array[new_x + 1] := (new_y - 1) || '|' || new_y;
    END IF;

    -- if intersect with rocks
    FOR i IN 1..7 LOOP
      IF shape_rock_intersect(moved_array[i], pos_array[i]) THEN
        shape_intersect = TRUE;
      END IF;
    END LOOP;




    -- no intersection, move to the new position
    IF NOT shape_intersect THEN
      RETURN (FALSE, new_x, new_y, pos_array);
    END IF;


    -- stopped, add to the pos_array
    IF move_direction = 'v' THEN
      FOR i IN 1..7 LOOP
        IF origin_array[i] IS NOT NULL THEN
          pos_array[i] := ltrim(coalesce(pos_array[i], '') || ',' || origin_array[i], ',');
        END IF;
      END LOOP;
    END IF;

    -- intersection exist, return original position
    RETURN (move_direction = 'v', pos_x, pos_y, pos_array);

END;
$$ LANGUAGE plpgsql;

判断已有方块的高度

当下一个方块出现的时候，需要计算已有方块的高度，从而确定方块出现的坐标

CREATE OR REPLACE FUNCTION max_height(pos_array VARCHAR[7])
RETURNS INTEGER AS $$
DECLARE
    height INTEGER := 0;
BEGIN
    FOR i IN 1..7 LOOP
      IF pos_array[i] IS NOT NULL THEN
        height := (SELECT greatest(height, (select max(split_part(h, '|', 2) :: INTEGER) from (select string_to_table(pos_array[i], ',') as h) t)));
      END IF;
    END LOOP;
    RETURN height;
END;
$$ LANGUAGE plpgsql;

下落方块过程

WITH recursive origin AS (
  SELECT string_to_array(line, null) as move_arr, string_to_array('-+J|#', null) as shape_arr, '{1, 3, 3, 4, 2}' :: INTEGER[] as shape_height from lance_input
), shape_move AS (
  SELECT 3 as pos_x, 4 as pos_y, 1 as shape_index, 0 as move_index, '{}' :: varchar[7] as pos_array, false as stopped, false as moved

  UNION ALL

  SELECT r.f2 as pos_x, r.f3 as pos_y, shape_index, move_index, r.f4 as pos_array, r.f1 as stopped, not moved as moved
  FROM (
    SELECT case when moved then 'v' else move_arr[(move_index - 1) % cardinality(move_arr) + 1] end as move, 
           shape_arr[(shape_index - 1) % 5 + 1] as shape,
           shape_index, move_index, pos_array, moved, 
           case when stopped then 3 else pos_x end as pos_x, 
           case when stopped then max_height(pos_array) + 4 + shape_height[(shape_index - 1) % 5 + 1] - 1 else pos_y end as pos_y
    FROM (
      SELECT CASE WHEN stopped THEN shape_index + 1 ELSE shape_index END as shape_index, 
             CASE WHEN NOT moved THEN move_index + 1 ELSE move_index END as move_index,
             pos_x,
             pos_y,
             pos_array, 
             stopped,
             moved
      FROM shape_move
    ) x, origin y 
  ) t, move_shape(shape, pos_x, pos_y, move, pos_array) as r(f1 BOOLEAN, f2 INTEGER, f3 INTEGER, f4 VARCHAR[])
  WHERE shape_index < 2023
)
SELECT max_height(pos_array)
FROM shape_move
WHERE shape_index = 2022 AND stopped

Part Two

第二关，计算1000000000000个方块掉落后的高度

How tall will the tower be after 1000000000000 rocks have stopped?

一万亿，肯定是无法通过正常渠道计算的，所以计算过程中肯定会出现循环，只需要找出这样的规律，就可以直接计算出结果。

寻找规律

将某个方块停止后，7列固定方块的排列形状，当作一个特征。当遇到相同的特征时，则可以判断出现了循环。那么使用一个函数，来计算出当前固定方块的特征。

CREATE OR REPLACE FUNCTION fingerprint(pos_array VARCHAR[7])
RETURNS VARCHAR AS $$
DECLARE
    min_height INTEGER := 2^30;
    height_array INTEGER[7];
BEGIN
    FOR i IN 1..7 LOOP
      IF pos_array[i] IS NOT NULL THEN
        height_array[i] := (SELECT max(split_part(h, '|', 2) :: INTEGER) from (select string_to_table(pos_array[i], ',') as h) t) :: INTEGER;
      ELSE 
        height_array[i] = 0;
      END IF;
      min_height = (select least(min_height, height_array[i]));
    END LOOP;
    RETURN (select string_agg(h ::VARCHAR, ',') from (select h :: INTEGER - min_height as h from (select unnest(height_array) as h) t) s) ;
END;
$$ LANGUAGE plpgsql;

将每一个方块固定后，打印出当时的特征，方块形状，以及总体高度，结果如下所示

     fingerprint     | shape | height 
---------------------+-------+--------
 0,0,1,1,1,1,0       | -     |      1
 0,0,3,4,3,1,0       | +     |      4
 4,4,6,4,3,1,0       | J     |      6
 4,4,6,4,7,1,0       | |     |      7
 4,4,6,4,9,9,0       | #     |      9
 4,10,10,10,10,9,0   | -     |     10
 4,12,13,12,10,9,0   | +     |     13
 4,12,13,13,13,15,0  | J     |     15
 4,12,13,13,17,15,0  | |     |     17

看下第2000个方块，以及当时的特征，确实出现了循环，每35个方块就会重复出现。

postgres=# select * From lance_test where fingerprint = '0,15,15,15,11,12,11' and shape = '#';
fingerprint | shape_index | shape | height
---------------------+-------------+-------+--------
0,15,15,15,11,12,11 | 40 | # | 66
0,15,15,15,11,12,11 | 75 | # | 119
0,15,15,15,11,12,11 | 110 | # | 172
0,15,15,15,11,12,11 | 145 | # | 225
0,15,15,15,11,12,11 | 180 | # | 278
0,15,15,15,11,12,11 | 215 | # | 331
0,15,15,15,11,12,11 | 250 | # | 384
0,15,15,15,11,12,11 | 285 | # | 437
0,15,15,15,11,12,11 | 320 | # | 490
0,15,15,15,11,12,11 | 355 | # | 543
0,15,15,15,11,12,11 | 390 | # | 596

那么后续计算就很简单了，持续循环最后差10个方块，再加上10个方块的高度即可。

postgres=# select 2000 + 35 * 28571428514;
   ?column?   
--------------
 999999999990
(1 row)

postgres=# select * From lance_test limit  11 offset 1999;
     fingerprint     | shape_index | shape | height 
---------------------+-------------+-------+--------
 0,15,15,15,11,12,11 |        2000 | #     |   3034
 0,15,16,16,16,16,11 |        2001 | -     |   3035
 6,7,6,5,5,5,0       |        2002 | +     |   3037
 1,2,1,0,1,1,3       |        2003 | J     |   3038
 1,2,1,0,5,1,3       |        2004 | |     |   3040
 0,1,2,2,4,0,2       |        2005 | #     |   3040
 0,1,5,5,5,5,2       |        2006 | -     |   3041
 0,1,5,5,7,8,7       |        2007 | +     |   3044
 0,1,8,8,10,8,7      |        2008 | J     |   3046
 0,5,8,8,10,8,7      |        2009 | |     |   3046
 0,5,10,10,10,8,7    |        2010 | #     |   3046
(11 rows)

postgres=# select 3034 + 53 * 28571428514 + (3046 - 3034);
   ?column?    
---------------
 1514285714288
(1 row)

发表评论