— Day 19: Not Enough Minerals —
Part One
robot可以采集资源，制作robot需要资源，设计最佳的策略让采集的资源最多
Blueprint 1:
Each ore robot costs 4 ore.
Each clay robot costs 2 ore.
Each obsidian robot costs 3 ore and 14 clay.
Each geode robot costs 2 ore and 7 obsidian.
问题分析
robot可以采集资源，但是同样消耗资源。很多SLG游戏就是类似的玩法，比如红警、星际等。如果前期优先采集资源，那么后期资源充足，但是没有足够的兵力；如果前期资源优先投入在兵力上，后期兵力生产效率就会降低。
Day 16，问题与本文中的问题比较相似，都是找出一定的排列，从而让某个目标最大。但是还是有一定的差异的，Day 16的问题，是找出一条路径途径每个节点，且每个节点只会经过一次。而这里，在24分钟的限制内，需要决定在哪一分钟建造哪种robot，或者不做任何建造。
每一分钟，就会有5种选择，build ore / build clay / build obsidian / build geode / no build。5的24次方，数量级无法想象。因此，需要针对可能的路径做裁剪，裁剪方式有如下几种：
- 如果上一分钟没有建造robot，那么只可能是为了积累资源建造更贵的robot。比如ore robot需要4个ore，因此当前有两个ore时，可以选择clay robot，但是也可以选择不造，积累ore。如果上一轮的资源足够建造clay robot，那么这一轮也必要造了，因为故意推迟一轮，最后的资源肯定是要少的。
- 如果当前资源足够建造最贵的robot，那么要尽快建造出来，积累资源而不转化为生产效率，无疑是愚蠢的。最终的目标是geode最多，其他的资源再多也没有用。
- 如果当前某种类型的robot，已经足够产生该类型最贵的资源，那么就没有必要继续建造robot了，因此每一轮产生的资源足够消耗了。
路径裁剪
用RCBG，分别代表建造ore/clay/obsidian/geode类型的robot，N代表不建造任何robot，每一轮最多会膨胀5倍。同时，计算出每一轮最多需要的资源数
WITH recursive origin AS (
SELECT rtrim(split_part(line, ' ', 2), ':') :: INTEGER as blueprint,
split_part(line, ' ', 7) :: INTEGER as ore_robot_ore,
split_part(line, ' ', 13) :: INTEGER as clay_robot_ore,
split_part(line, ' ', 19) :: INTEGER as obsidian_robot_ore,
split_part(line, ' ', 22) :: INTEGER as obsidian_robot_clay,
split_part(line, ' ', 28) :: INTEGER as geode_robot_ore,
split_part(line, ' ', 31) :: INTEGER as geode_robot_obsidian
FROM lance_input
), possible_actions AS (
SELECT regexp_split_to_table('RCBGN', '') as action
)
greatest(ore_robot_ore, clay_robot_ore, obsidian_robot_ore, geode_robot_ore) as max_need_ore,
obsidian_robot_clay as max_need_clay,
geode_robot_obsidian as max_need_obsidian,
下面就会去实现三种裁剪方式
- 上一轮不造，这一轮也不去造了
WHEN y.action = 'R' THEN minerals[1] >= ore_robot_ore
AND NOT (last_action = 'N' AND last_minerals[1] >= ore_robot_ore)
WHEN y.action = 'C' THEN minerals[1] >= clay_robot_ore
AND NOT (last_action = 'N' AND last_minerals[1] >= clay_robot_ore)
WHEN y.action = 'B' THEN minerals[1] >= obsidian_robot_ore
AND minerals[2] >= obsidian_robot_clay AND NOT (last_action = 'N' AND last_minerals[1] >= obsidian_robot_ore AND last_minerals[2] >= obsidian_robot_clay)
WHEN y.action = 'G' THEN minerals[1] >= geode_robot_ore AND minerals[3] >= geode_robot_obsidian
AND NOT (last_action = 'N' AND last_minerals[1] >= geode_robot_ore AND last_minerals[3] >= geode_robot_obsidian)
- 当前资源足够，则一定要建造robot。就像在游戏中，行动点足够的时候，一定要做些事情，而不是直接跳过本轮。
WHEN y.action = 'N' THEN minerals[1] < max_need_ore OR minerals[2] < max_need_clay OR minerals[3] < max_need_obsidian
- robot足够的时候，没有必要继续生产了
WHEN y.action = 'R' THEN minerals[1] >= ore_robot_ore
AND robots[1] < max_need_ore
WHEN y.action = 'C' THEN minerals[1] >= clay_robot_ore
AND robots[2] < max_need_clay
WHEN y.action = 'B' THEN minerals[1] >= obsidian_robot_ore
AND robots[3] < max_need_obsidian
完整SQL
WITH recursive origin AS (
SELECT rtrim(split_part(line, ' ', 2), ':') :: INTEGER as blueprint,
split_part(line, ' ', 7) :: INTEGER as ore_robot_ore,
split_part(line, ' ', 13) :: INTEGER as clay_robot_ore,
split_part(line, ' ', 19) :: INTEGER as obsidian_robot_ore,
split_part(line, ' ', 22) :: INTEGER as obsidian_robot_clay,
split_part(line, ' ', 28) :: INTEGER as geode_robot_ore,
split_part(line, ' ', 31) :: INTEGER as geode_robot_obsidian
FROM lance_input
), possible_actions AS (
SELECT regexp_split_to_table('RCBGN', '') as action
), walkthrough AS (
SELECT blueprint,
ore_robot_ore,
clay_robot_ore,
obsidian_robot_ore,
obsidian_robot_clay,
geode_robot_ore,
geode_robot_obsidian,
greatest(ore_robot_ore, clay_robot_ore, obsidian_robot_ore, geode_robot_ore) as max_need_ore,
obsidian_robot_clay as max_need_clay,
geode_robot_obsidian as max_need_obsidian,
24 as remain_minutes,
'{1, 0, 0, 0}' :: INTEGER[] as robots,
'{0, 0, 0, 0}' :: INTEGER[] as minerals,
'' as path,
'' as last_action,
'{0, 0, 0, 0}' :: INTEGER[] as last_minerals
FROM origin
UNION ALL
SELECT blueprint,
ore_robot_ore,
clay_robot_ore,
obsidian_robot_ore,
obsidian_robot_clay,
geode_robot_ore,
geode_robot_obsidian,
max_need_ore,
max_need_clay,
max_need_obsidian,
remain_minutes - 1,
ARRAY[robots[1] + CASE WHEN action= 'R' THEN 1 ELSE 0 END,
robots[2] + CASE WHEN action= 'C' THEN 1 ELSE 0 END,
robots[3] + CASE WHEN action= 'B' THEN 1 ELSE 0 END,
robots[4] + CASE WHEN action= 'G' THEN 1 ELSE 0 END],
ARRAY[minerals[1] + robots[1] - CASE WHEN action = 'R' THEN ore_robot_ore
WHEN action = 'C' THEN clay_robot_ore
WHEN action = 'B' THEN obsidian_robot_ore
WHEN action = 'G' THEN geode_robot_ore
ELSE 0
END,
minerals[2] + robots[2] - CASE WHEN action = 'B' THEN obsidian_robot_clay ELSE 0 END,
minerals[3] + robots[3] - CASE WHEN action = 'G' THEN geode_robot_obsidian ELSE 0 END,
minerals[4] + robots[4]],
path || y.action,
y.action as last_action,
minerals as last_minerals
FROM walkthrough x, possible_actions y
WHERE CASE WHEN y.action = 'R' THEN minerals[1] >= ore_robot_ore
AND NOT (last_action = 'N' AND last_minerals[1] >= ore_robot_ore)
AND robots[1] < max_need_ore
WHEN y.action = 'C' THEN minerals[1] >= clay_robot_ore
AND NOT (last_action = 'N' AND last_minerals[1] >= clay_robot_ore)
AND robots[2] < max_need_clay
WHEN y.action = 'B' THEN minerals[1] >= obsidian_robot_ore
AND minerals[2] >= obsidian_robot_clay AND NOT (last_action = 'N' AND last_minerals[1] >= obsidian_robot_ore AND last_minerals[2] >= obsidian_robot_clay)
AND robots[3] < max_need_obsidian
WHEN y.action = 'G' THEN minerals[1] >= geode_robot_ore AND minerals[3] >= geode_robot_obsidian
AND NOT (last_action = 'N' AND last_minerals[1] >= geode_robot_ore AND last_minerals[3] >= geode_robot_obsidian)
WHEN y.action = 'N' THEN minerals[1] < max_need_ore OR minerals[2] < max_need_clay OR minerals[3] < max_need_obsidian
END
AND x.remain_minutes > 0
)
SELECT SUM(blueprint * blueprint)
FROM (
SELECT blueprint, max(minerals[4]) as geode_cnt
FROM walkthrough
GROUP BY blueprint
) t
Part Two
时间从24分钟延长至32分钟，输入不变。迭代轮次增加了8轮，很有可能结果膨胀很大，需要继续进行裁剪。
问题分析
用例子的第一条记录测试了下，果然速度非常慢，从24分钟增加到28分钟，花费了4分钟才得出结果。
postgres=# select remain_minutes, count(*) from lance_test group by remain_minutes;
remain_minutes | count
----------------+---------
0 | 8881990
1 | 2940004
2 | 991089
3 | 343090
4 | 123991
5 | 46817
6 | 19058
7 | 8382
8 | 3883
9 | 1823
从上图可以看出，最后几步，基本都是按照3倍的指数级膨胀，因此会越来越慢。再看下，最终结果中，采集的geode数量的分布。
postgres=# select minerals[4] as geode_cnt, count(*) from lance_test where remain_minutes = 0 group by minerals[4];
geode_cnt | count
-----------+---------
0 | 1518051
1 | 677504
2 | 699417
3 | 944477
4 | 940016
5 | 1108704
6 | 954078
7 | 745418
8 | 508224
9 | 400113
10 | 220047
11 | 108580
12 | 45170
13 | 10421
14 | 1472
15 | 298
(16 rows)
由分布可见，大部分的路径，其产生的geode_cnt非常少，可以在更早的时候直接淘汰掉。可以从以下几点尽早过滤掉某些路径。
- 首先，假设总的轮次是m，那么m-1轮至少要有一个geode robot。
- 其次，一个geode消耗7个obsidian，那么在(m-1)-4轮，至少有一个obsidian_robot。因此n轮的时间，从0开始，最多生产(n-1) * n / 2个资源。4轮生产6个，并不足够满足生产geode robot的需求。
- 同理，推理出clay robot生产的最晚时机。
- 最后，每轮结束之后，都淘汰掉最终geode个数肯定非最高的路径。这里的最终结果，指的是，计算剩下的轮次，每一轮都建造一个geode robot，也肯定无法追上的。
路径裁剪
首先，定义出三个最晚生产的时机。n轮最多生产(n-1) * n / 2 = m，则n = sqrt(2m + 1/4) + 1/2。
1 as latest_time_geode,
1 + ceil(sqrt(2 * geode_robot_obsidian + 0.25) + 0.5) as latest_time_obsidian,
1 + ceil(sqrt(2 * geode_robot_obsidian + 0.25) + 0.5) + ceil(sqrt(2 * obsidian_robot_clay + 0.25) + 0.5) as latest_time_clay,
关于geode数量淘汰策略，一种路径最后至少产生的geode数量，就是已有geode + robot * remain_minutes。而一种路径最多生产的geode数量，就是已有geode + robot * remain_minutes + (remain_minutes – 1) * remain_minutes / 2，意思就是剩下的时间，每一分钟都生产一个geode robot。
如果一条路径，其最多生产的数量，还不如其他路径最少生产的，那么这个路径就可以淘汰掉了。
max_geode AS (
SELECT blueprint, max(minerals[4] + robots[4] * remain_minutes) as geode_cnt
FROM tmp
GROUP BY blueprint
)
SELECT a.*
FROM tmp a JOIN max_geode b
ON a.blueprint = b.blueprint
WHERE NOT (minerals[4] = 0 AND remain_minutes <= latest_time_geode)
AND NOT (minerals[3] = 0 AND remain_minutes <= latest_time_obsidian)
AND NOT (minerals[2] = 0 AND remain_minutes <= latest_time_clay)
AND NOT (minerals[4] + robots[4] * remain_minutes + (remain_minutes - 1) * remain_minutes / 2 < geode_cnt)
经过裁剪后，从下面的统计看出，越接近结尾，裁剪的效果越明显。
postgres=# select remain_minutes, count(*) from lance_test group by remain_minutes order by 1;
remain_minutes | count
----------------+--------
0 | 69
1 | 18
2 | 42
3 | 34
4 | 4611
5 | 101794
6 | 129627
7 | 221994
8 | 123987
9 | 46813
10 | 19054
11 | 8378
完整SQL
WITH recursive origin AS (
SELECT rtrim(split_part(line, ' ', 2), ':') :: INTEGER as blueprint,
split_part(line, ' ', 7) :: INTEGER as ore_robot_ore,
split_part(line, ' ', 13) :: INTEGER as clay_robot_ore,
split_part(line, ' ', 19) :: INTEGER as obsidian_robot_ore,
split_part(line, ' ', 22) :: INTEGER as obsidian_robot_clay,
split_part(line, ' ', 28) :: INTEGER as geode_robot_ore,
split_part(line, ' ', 31) :: INTEGER as geode_robot_obsidian,
32 as remain_minutes
FROM lance_input
), possible_actions AS (
SELECT regexp_split_to_table('RCBGN', '') as action
), walkthrough AS (
SELECT blueprint,
ore_robot_ore,
clay_robot_ore,
obsidian_robot_ore,
obsidian_robot_clay,
geode_robot_ore,
geode_robot_obsidian,
greatest(ore_robot_ore, clay_robot_ore, obsidian_robot_ore, geode_robot_ore) as max_need_ore,
obsidian_robot_clay as max_need_clay,
geode_robot_obsidian as max_need_obsidian,
remain_minutes,
1 as latest_time_geode,
1 + ceil(sqrt(2 * geode_robot_obsidian + 0.25) + 0.5) as latest_time_obsidian,
1 + ceil(sqrt(2 * geode_robot_obsidian + 0.25) + 0.5) + ceil(sqrt(2 * obsidian_robot_clay + 0.25) + 0.5) as latest_time_clay,
'{1, 0, 0, 0}' :: INTEGER[] as robots,
'{0, 0, 0, 0}' :: INTEGER[] as minerals,
'' as path,
'' as last_action,
'{0, 0, 0, 0}' :: INTEGER[] as last_minerals
FROM origin
UNION ALL
SELECT *
FROM (
WITH tmp AS (
SELECT blueprint,
ore_robot_ore,
clay_robot_ore,
obsidian_robot_ore,
obsidian_robot_clay,
geode_robot_ore,
geode_robot_obsidian,
max_need_ore,
max_need_clay,
max_need_obsidian,
remain_minutes - 1 as remain_minutes,
latest_time_geode,
latest_time_obsidian,
latest_time_clay,
ARRAY[robots[1] + CASE WHEN action= 'R' THEN 1 ELSE 0 END,
robots[2] + CASE WHEN action= 'C' THEN 1 ELSE 0 END,
robots[3] + CASE WHEN action= 'B' THEN 1 ELSE 0 END,
robots[4] + CASE WHEN action= 'G' THEN 1 ELSE 0 END] as robots,
ARRAY[minerals[1] + robots[1] - CASE WHEN action = 'R' THEN ore_robot_ore
WHEN action = 'C' THEN clay_robot_ore
WHEN action = 'B' THEN obsidian_robot_ore
WHEN action = 'G' THEN geode_robot_ore
ELSE 0
END,
minerals[2] + robots[2] - CASE WHEN action = 'B' THEN obsidian_robot_clay ELSE 0 END,
minerals[3] + robots[3] - CASE WHEN action = 'G' THEN geode_robot_obsidian ELSE 0 END,
minerals[4] + robots[4]] as minerals,
path || y.action as path,
y.action as last_action,
minerals as last_minerals
FROM walkthrough x, possible_actions y
WHERE CASE WHEN y.action = 'R' THEN minerals[1] >= ore_robot_ore
AND NOT (last_action = 'N' AND last_minerals[1] >= ore_robot_ore)
AND robots[1] < max_need_ore
WHEN y.action = 'C' THEN minerals[1] >= clay_robot_ore
AND NOT (last_action = 'N' AND last_minerals[1] >= clay_robot_ore)
AND robots[2] < max_need_clay
WHEN y.action = 'B' THEN minerals[1] >= obsidian_robot_ore
AND minerals[2] >= obsidian_robot_clay AND NOT (last_action = 'N' AND last_minerals[1] >= obsidian_robot_ore AND last_minerals[2] >= obsidian_robot_clay)
AND robots[3] < max_need_obsidian
WHEN y.action = 'G' THEN minerals[1] >= geode_robot_ore AND minerals[3] >= geode_robot_obsidian
AND NOT (last_action = 'N' AND last_minerals[1] >= geode_robot_ore AND last_minerals[3] >= geode_robot_obsidian)
WHEN y.action = 'N' THEN minerals[1] < max_need_ore OR minerals[2] < max_need_clay OR minerals[3] < max_need_obsidian
END
AND x.remain_minutes > 0
), max_geode AS (
SELECT blueprint, max(minerals[4] + robots[4] * remain_minutes) as geode_cnt
FROM tmp
GROUP BY blueprint
)
SELECT a.*
FROM tmp a JOIN max_geode b
ON a.blueprint = b.blueprint
WHERE NOT (minerals[4] = 0 AND remain_minutes <= latest_time_geode)
AND NOT (minerals[3] = 0 AND remain_minutes <= latest_time_obsidian)
AND NOT (minerals[2] = 0 AND remain_minutes <= latest_time_clay)
AND NOT (minerals[4] + robots[4] * remain_minutes + (remain_minutes - 1) * remain_minutes / 2 < geode_cnt)
) t
)
SELECT blueprint, max(minerals[4]) as geode_cnt
FROM walkthrough
GROUP BY blueprint