这是POINT小数点的第篇文章
飞柳写在前面：
欢迎参观~作为小数点Python课堂的老师，我希望能多提供有趣的Python学习方法。本此分享来讲讲如何用python来解决《戴森球计划》游戏中的问题，欢迎与我们一起解锁更多数据的玩法技能哦！
来回顾下飞柳老师的往期分享：可以用Python编程语言做哪些好玩的事情？干货：超实用的python各个库的功能介绍与运用
目录
如何用Python解决《戴森球计划》中的生产规划问题
Python基础定义
算法背景
第一步：流水线匹配
第二步：链式的解决流水线
在小数点后台输入关键字：戴森球计划获取源代码
—1—如何用Python解决《戴森球计划》中的生产规划问题《戴森球计划》是一款国人工作室（他们只有五个人）出品的游戏，1月22日在Steam上线进入EA（抢先体验阶段）以来，45分钟即占领了销量榜，并创下了1周销量45万的好成绩。
图源笔者
图源笔者
这个游戏的背景很简单：《戴森球计划》的名字来源于戴森球，指的是科技高度达到一定水平的未来世界，这个世界会有能力制作一个包裹住整个恒星的球壳，来收集恒星的全部能量。
如上图所示（图源笔者）
在游戏里，你作为主人公机器人，搭载着科技和工程的知识，在一颗行星着陆，你可以在这个行星上采集资源点，排布熔炉和工厂，建立起一套完整的工业体系，最终建立起一个覆盖整个恒星的戴森球。这个游戏有多好玩呢？不妨以笔者为例，从1月29号周五晚上回到家，买了这个游戏，玩到周一凌晨睡觉准备上班，醒着的时间都在玩这个游戏，这是我的游戏时间：
图源笔者
导致鸽了一篇文章写作，后来掐指一算，不如我们就讲讲这个游戏体现的一个问题，以及如何用Python解决它吧。为什么好玩，这要从游戏的基本元素开始讲起。在这个异世界搭建简化的工业体系，基础元素只有两个：1、自然资源2、工业制成品。而自然资源可以通过工厂制作成工业制成品。总共三个概念，这样简单的概念为什么好玩呢？好玩就好玩在这个体系的关系可以发展得非常复杂。我们以一个游戏的实例作为演示：资源点石油，可以采集“原油”，原油的产量如图所示，是.9每分钟（如果电力充足，产量还可以提高）
图源笔者
而原油可以被原油精炼厂加工，2个单位的原油，可以产出2个单位的精炼油和1个单位的氢：图源笔者同样的工厂，也可以继续加工精炼油，公式是：2个单位的氢和1个单位的精炼油，可以生成个单位的氢和1个单位的高能石墨，每分钟产量是15即45个单位的氢：图源笔者这样一路传递下去的工业链条，就充满了复杂性。我们先从简单的小学应用题开始:每分钟产量的原油，可以产出多少精炼油和氢？答案是个精炼油和50个氢。第二题：如果不产出精炼油，最多可以产出多少氢和多少高能石墨？这就需要比比划划一下才能计算明白了：看上面两个图的公式，可以注意到，原油-精炼油-高能石墨的关系正好是1:1:1，答案是每分钟个高能石墨，再反推：本来生产了高能石墨同时产出了00个氢，生产流水线中，意味着上游一定输入了个氢，从产出中扣除，还有是原油裂解产出的50个氢，最终的答案就是个氢。第三题：如果我们需要在产出的时候，保证高能石墨的数量和精炼油是1:2，那么此时需要安排几个工厂？（这题亦不难，留待读者后续自行回答）。1个资源，4种产物。上述仅仅涉及了1种资源，4种工业制品，如果工业链条更长了，那计算就会更加复杂了。举一个目前笔者的产业链的产品，超级磁场环为例：图源笔者那么需要的链条是：1.1个高能石墨，个磁铁，2个电磁涡轮=1个超级磁场环。每分钟产量20个2.2个电动机，2个磁线圈=1个电磁涡轮。每分钟产量0个.1个铜板，2个磁铁=1个磁线圈。每分钟产量60个4.1个铁矿=1个磁铁。每分钟产量40个5.1个铜矿=1个铜板。每分钟产量60个6.1个磁线圈，1个齿轮，2个铁板=1个电动机。每分钟产量0个7.1个铁矿=1个铁板。每分钟产量60个8.1个铁板=1个齿轮。每分钟产量60个9.上面说过的1单位原油刚好能产出1单位高能石墨里面涉及了种资源：原油、铁矿、铜矿，公式也只有9个，意味着最简单我只需要安排8个工厂，遵循上下游关系就好，但是问题就在于：这每个工厂的输入和产出并不是完全对等的，需要把流水线安排合理，才能达到最大的产量。
第四题：如果要使得超级磁场环产量达到每分钟20个，那么我需要多少资源产量，如何安排上述流水线？
还需要手动计算吗？不，我要用Python来解决这个问题！—2—Python基础定义首先从游戏的基本概念定义起1.资源。不妨直接定义资源的产量2.工厂。工厂输入产品或者资源，经过一个流水线，输出产品.产品。在Python中，我们可以通过类与继承关系完成这样的代码。我们的开发环境是Python.6，使用的也是Python的基础语法，不涉及第三方库。首先从资源和产品开始，因为他们都可以作为工厂的输入，不妨让资源成为一个类
#coding=utf-8from__future__importunicode_literalsclassResource(object)
ef__init__(self,name:str,output:int):self.name=name#资源名self.output=output#产量def__str__(self):return"资源:%s产量%s/分钟"%(self.name,self.output)if__name__=="__main__":iron_res=Resource("铁矿",)print(iron_res)上述代码展示了定义一个类、定义类的初始化函数__init__和魔法方法__str__，这个魔法方法可以让类转换为字符串时，构造出一个字符串来方便展示。运行代码可以得到：
的显示
来和游戏中的铁矿采集等同：图源笔者工厂类的定义则需要思考：输入的每种产品，对应的数量是消耗的数量，而输出的产品，数量对应的即出产的数量。工厂的名称无关紧要，我们其实只关心流水线的输入和输出。
classFactory(object)ef__init__(self,input_products
st,output_productsst):self.input_products=input_productsself.input_str="+".join(["%sx%s"%(p.name,num)forp,numininput_products])self.output_products=output_productsself.output_str="+".join(["%sx%s"%(p.name,num)forp,numinoutput_products])def__str__(self):return"=".join([self.input_str,self.output_str])上面的代码主要涉及了Python的知识点：1.列表推导式
["%sx%s"%(p.name,num)forp,numininput_products]
直接构造出了一个列表2.字符串格式化，join的内置方法，和%sformat那么定义一个流水线的结果如下：这样看起来非常漂亮。上述的第四题，我们可以用一个列表数据结构，来表达我们第四题说到的流水线了
#用一长串文本来定义上面的流水线，
#定义：英文冒号:用来区分名称和数量,英文逗号用来分割多个产品，英语句号.用来分割输入输出,
pipelines="""高能石墨:20,磁铁:60,电磁涡轮:40.超级磁场环:20电动机:60,磁线圈:60.电磁涡轮:0铜板:60,磁铁:.磁线圈:60铁矿:40.磁铁:40铜矿:60.铜板:60磁线圈:0,齿轮:0,铁板:60.电动机:0铁矿:60.铁板:60铁板:60.齿轮:60原油:0.精炼油:0,氢:0氢:0,精炼油:15.氢:45,高能石墨:15"""defname2product_list(string)
因为输入和输出的数据结构一样，我们可以用一个辅助函数来处理相似的字符串products=string.split(",")products=[p.split(":")forpinproducts]return[(Product(name),number)forname,numberinproducts]factories=[]forlineinpipelines.splitlines()ne=line.strip()ifnotline:continueinputs,outputs=line.split(".")input_products=name2product_list(inputs)output_products=name2product_list(outputs)fact=Factory(input_products,output_products)factories.append(fact)print(fact)运行代码的结果如下：有了工厂的定义，接下来就是开始流水线的计算了，也即：如果我们需要最终产物超级磁场环，那么每个流水线都需要几条？这里主要涉及的是算法的知识。——算法背景在算法领域，像这样的生产规划问题，尤其是这种简单的A-B-C的线性流程规划问题，被定义为动态规划问题.。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面都得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。对于复杂的应用场景，动态规划可能会出现许多变形，例如在《戴森球计划》的场景中，不同的流水线可能产出相同的产物，而他们的生产代价显然是不同的。好在我们上面出现的这些流水线，都是简单的流程，因此后面出现的动态规划算法也可以用简单的代价实现。第一步：流水线匹配首先来实现一个小型的功能：给定一个产物的数量、已知上述的所有工厂流水线，找到1条流水线，使得产出的数量匹配
deffind_pipeline(need_product):pass定义的函数如上，这里的need_product是所需的产品和数量，类型是一个元组经过简单的思考，可以想到，这里只需要做一个流水线输出产品到流水线的映射关系就好了，那么通过数据结构dict即可实现。考虑同样的产品，可能由不同的流水线产生，那么我们dict的value应当是一个list，这样用标准库中的defaultdict，可以自带初始化的空列表样子大概长这样：
fromcollectionsimportdefaultdictproduct_map=defaultdict(list)product_map[product.name].append((fact,product_num))而当我们找到了某条流水线，例如原油x0=精炼油x0+氢x0这条好了，流水线的数量和我们需要的产品数量，如何能够完美的匹配起来呢？比如需要氢40个的时候。我们其实有两种策略：1、寻找满足要求的最少的流水线倍数，这会使得需求的资源更为节省2、寻找最小公倍数，这样尽可能会使得资源不会剩余。本期我们实现的是第一种。需求的流水线倍数，即为需求量除以产出量，整数向上取整。用到的是标准库的ceil函数综上，我们可以把“获得单条产品”所需的流水线数量，和产物的数量得到了，实现的代码如下：
fromcollectionsimportdefaultdictfrommathimportceilproduct_map=defaultdict(list)forfactinfactories
orproduct,product_numinfact.outputs:product_map[product.name].append((fact,product_num))deffind_pipeline(need_product):product,require_num=need_productifproductnotinproduct_map:raiseValueError("产品未找到:%s"%product)fact,product_num=product_map[product][0]returnfact,ceil(require_num/product_num)关于产品映射关系的product_map，放在了函数外面，也就是初始化一次即可结果：第二步：链式的解决流水线有了第一步作为基础，接下来的工作也就很简单了，如果我们要一路往上寻找，直到所有的流水线的需求都被满足，那么应当遵循以下原则。1.输入所需的产品和数量，加入“需求池”2.如果需求池不为空，那么1、看需求池能否从供给池直接扣减2、寻找需求池中需要被满足的产品，如果需求池内所有的产品都已经是最基本的资源了，表达都被满足了，那么返回结果，否则往下走.寻找能输出这个产品的流水线，会返回所需流水线的数量4.对于第步找到的流水线，首先将流水线的输出，从需求池中扣除，如果还有多余的，加入“供给池”5.流水线的输入，加入“需求池”，继续回到第二步的循环按照我们上面的例子，需要的产物是超级磁场环，它进一步需要磁铁，那么流水线数量*磁铁的数量加入需求池，继续寻找磁铁的依赖关系。那么加入一点点细节：
fromcollectionsimportCounterbasic_resources={"铁矿","铜矿","原油"}deffilter_pool(pool)过滤掉数量为0的，即为所需要的真正的产品return{key:valueforkey,valueinpool.items()ifvalue}defall_need_is_resources(pool):pool=filter_pool(pool)returnall(map(lambdaprod:prodinbasic_resources,pool.keys()))deffine_link(need_product):require_pool=Counter()#需求的产品:数量provide_pool=Counter()#现有流水线产出的产品:数量pipeline_count=Counter()#fact,pipeline_num,product_num=find_pipeline(need_product)[0]#如果寻找到多条流水线，就用第一条product_name,number=need_productrequire_pool[product_name]+=numberwhile1循环条件：如果需要的池子都已经是资源了，那么退出循环##特别的逻辑：require_pool=Counter(filter_pool(require_pool))provide_pool=Counter(filter_pool(provide_pool))#需求池不为空，那么遍历需求池forproduct_name,numberinlist(require_pool.items()):ifproduct_nameinbasic_resources如果所需的是基础资源，那么直接加就好，不需要寻找流水线require_pool[product_name]+=numberelifnumberact,pipeline_num=find_pipeline((product_name,number))#找到流水线之后：流水线的所有输出乘以数量后放入供给池foroutput_prod,output_numinfact.outputs:provide_pool[output_prod.name]+=(pipeline_num*output_num)pipeline_count[str(fact)]+=pipeline_num#流水线的所有输入乘以数量后放入需求池forinput_prod,input_numinfact.inputs:require_pool[input_prod.name]+=(pipeline_num*input_num)#供给池如果有能满足需求池的，那么需求池减掉供给池forprovide_key,provide_numinprovide_pool.items():ifprovide_keyinrequire_pool:require_num=require_pool[provide_key]require_pool[provide_key]-=min(provide_num,require_num)provide_pool[provide_key]-=min(provide_num,require_num)ifall_need_is_resources(require_pool):breakrequire_pool=Counter(filter_pool(require_pool))provide_pool=Counter(filter_pool(provide_pool))returnrequire_pool,provide_pool,pipeline_count做好啦：
课后作业：
检查上述代码，这段代码有问题吗？
—4—更多的思考我们可以看到现在的这个配方解析，还是能够完成效果的，未来我们应该继续完善：1.如果我们要实现最小公倍数，来达成资源毫不浪费，该怎么办2.如果有多条路径，或者多条路径形成了更大的环状（比如本例中的氢+精炼油=氢+高能石墨）那该如何解决依赖关系？.动态规划中的状态转移矩阵是什么？在本例中如何应用4.文章中的第三题：希望流水线的节点满足一定的条件，比如氢:精炼油=1:2（来让其他产品被构建），那该如何完成代码?那么就到这里，我已经按捺不住要去赶紧优化我的《戴森球计划》的流水线了，同学们下期再见！END
加入POINT.
长按扫码添加小夏
