AdventOfCode 2024 Day 11

作者

— Day 11: Plutonian Pebbles —

Part One

某组数字按照一定的规律进行裂变，求这组数字裂变25次后的结果有多少数字？

按照递归查询的写法，并且裂变后的数字用空格分隔

with recursive stones AS (
    SELECT line, 0 as blink
    FROM lance_input

    UNION ALL

    SELECT string_agg(num, ' ') as line, blink + 1
    FROM (
        SELECT blink, 
               CASE WHEN num = '0' then '1'
                    WHEN length(num) % 2 = 0 THEN substr(num, 1, length(num) / 2) :: BIGINT || ' ' || 
                         substr(num, length(num) / 2 + 1, length(num) / 2) :: BIGINT
                    ELSE (num :: BIGINT * 2024) :: VARCHAR
                END as num
        FROM (
            SELECT x.pos as num, blink
            FROM stones, regexp_split_to_table(line, ' ') with ordinality as x(pos, idx)
        ) t
    ) t
    WHERE blink < 25
    GROUP BY blink
)
SELECT * FROM stones;

Part Two

裂变规则未变，但是需要求出裂变75次后的结果

如果仍然按照第一轮的逻辑去写，75次的运算计算量巨大，基本无法运算出来。

仔细分析下，可以有以下几点推论

  • 数字裂变后，会出现重复的数字，如果可以缓存下结果，那么后续就无需计算了。
  • 裂变后的数字，顺序不重要，只要求数字的数量。

因此我们需要将某个数字，裂变N轮后数字的数量保存起来，供后续查询。

postgres=# \d cache;
                  Table "public.cache"
   Column    |  Type   | Collation | Nullable | Default 
-------------+---------+-----------+----------+---------
 cache_num   | bigint  |           |          | 
 cache_blink | integer |           |          | 
 cache_stone | bigint  |           |          | 
Indexes:
    "idx_cache" UNIQUE, btree (cache_num, cache_blink)

再通过一个函数递归，来查询某个数字N轮后的结果

CREATE OR REPLACE FUNCTION count_stones(num bigint, blink_left integer)
RETURNS BIGINT AS $$
DECLARE
  query_num BIGINT;
  stone_num BIGINT;
BEGIN
    IF blink_left = 0 THEN
        RETURN 1;
    END IF;

    query_num := (SELECT cache_stone FROM cache WHERE cache_num = num AND cache_blink = blink_left);

    IF query_num IS NOT NULL THEN
        return query_num;
    END IF;

    IF num = 0 THEN
        stone_num := count_stones(1, blink_left - 1);
    ELSE 
        IF length(num :: VARCHAR) % 2 = 0 THEN
            stone_num := count_stones(substr(num :: VARCHAR, 1, length(num :: VARCHAR) / 2) :: BIGINT, blink_left - 1) 
                       + count_stones(substr(num :: VARCHAR, length(num :: VARCHAR) / 2 + 1, length(num :: VARCHAR) / 2) :: BIGINT, blink_left - 1);
        ELSE
            stone_num := count_stones(num * 2024, blink_left - 1);
        END IF;
    END IF;

    query_num := (SELECT cache_stone FROM cache WHERE cache_num = num AND cache_blink = blink_left);
    IF query_num IS NULL THEN
        INSERT INTO cache values(num, blink_left, stone_num);
        RAISE NOTICE 'add map: %', (num || ' ' || blink_left);
    END IF;
    
    RETURN stone_num;
END;
$$ LANGUAGE plpgsql;

发表评论