《Calculator: The Game》游戏解决方案
本文将介绍手机游戏《Calculator: The Game》的完整解决方案。
开源解决方案代码地址为：https://github.com/FunkyKoki/Calculator_Game
《Calculator: The Game》这款游戏是Simple Machine开发的一款益智类解谜游戏，在一局游戏中，你务必在有限步骤[MOVES]内，使用该局提供的“操作”——如加减乘除、翻转、镜像等，将原始数字转化为目标数字[GOAL]。
游戏总关卡数[LEVEL]为200，目前我已全部通关。另外，游戏内的植入广告颇多，我的建议是关闭该游戏的联网权限，包括无线局域网与蜂窝网络，之后就可以尽享游戏乐趣了。
如需了解游戏的详细介绍，请移步：
- 【Android】https://play.google.com/store/apps/details?id=com.sm.calculateme&hl=en_US
- 【iOS】https://itunes.apple.com/us/app/calculator-the-game/id1243055750
游戏界面如下图所示（整体看来还是比较呆萌的），类似于计算器LCD显示屏上显示的数字即当前计算得到的数字（在游戏开始时即为初始化的数字），MOVES显示可用的步骤数，GOAL显示目标数字，CLR用于清空之前的所有操作（即还原该局游戏），‘+4’、‘*4’、‘/4’就是我们在这一局游戏中可用的“操作”了，HINTS和设置就不用我再多说了：
在进行这款游戏的破解工作前，首先要保证自己对整个游戏有一个基本了解才可以，而我在试玩前十几关时注意到了一个重要现象，这对之后破解这款游戏起到了非常关键的作用，即：一局游戏中，界面上给出的“操作”都是需要用到的操作，不存在冗余无关项。我将这一点称为1号公理，仅这一点就大大降低了编程破解的难度。
另外值得注意的一点是：步骤数永远大于等于操作数（这由1号公理可以显然推出），且在步骤数大于操作数的情况下，最多仅大出5。我将这一点称为2号公理。我们定义一局游戏给出的步骤数为MOVES，给出的”操作”的数量为OPS，则OPS<=MOVES<=OPS+5。
根据以上两个公理，我们就有了暴力破解的“理论指导”，说白了，我们将有理有据地穷举所有可行的操作序列，并依序测试操作序列的正确与否。
第一个问题，如何列举所有可行的操作序列？
这个问题往简单了说，就是一个排列问题，即将可用的操作以不同的排列顺序全部列举出来。但是，它又不仅仅是一个排列问题。需要注意到，步骤数MOVES与操作数OPS之间有两种关系，一种是MOVES==OPS，另一种是在满足2号定理的前提下，MOVES!=OPS，这就将排列问题划分为了两种情况。
1. MOVES==OPS
如果步骤数等于操作数，则问题变得很简单。根据1号公理，我们知道所有的操作都必然被使用，因此为了穷举所有可行的操作序列，我们所要解决的就是一个很简单的全排列问题。
设步骤数MOVES=4，OPS分别为A、B、C、D，此时MOVES==OPS，问题转化为全排列问题。我们使用下面的代码来解决这个全排列问题：
1 # 递归全排列 2 def Permutation(l, beg, endl, result): 3 if beg == endl - 1: 4 res = l[:] 5 result.append(res) 6 return 7 for i in range(beg, endl): 8 if l[i] in l[beg:i]: 9 continue 10 l[i], l[beg] = l[beg], l[i] 11 Permutation(l, beg+1, endl, result) 12 l[beg], l[i] = l[i], l[beg]
这个全排列的Python代码主要借鉴自https://blog.csdn.net/zhoufen12345/article/details/53560099，不过我做了一些改变，原代码主要用于打印所有可能的排列，但这不是我的目的，我的主要目的在于得到所有的排列，而不是显式地打印出来，也就是说，要将这些排列结果保存下来。这里需要注意，第4、5行不可简写为 result.append(l) ，这是由于在递归过程中， l位于堆栈之中，不能直接拿来使用，因此需要使用一个中间变量进行过渡。
如此，我们就可以获得全部可用排列，再送至后面的检验部门测试哪个排列结果是可用的。
2. MOVES!=OPS
在这种情况下，表明有至少一个“操作”被重复使用了，这可如何解决是好呢？
我的解决方案是，基于每一个操作都必然被使用的前提，对于后(MOVES-OPS)步，我们使用for循环强行将每一种可能重复使用的操作的情况添加进一个待排列的序列中，再对这个增加了重复操作的序列进行全排列。
举个例子，如MOVES=4，OPS为A、B、C，无论如何必然会使用ABC这三个操作，接着对这个序列添加所有可能的重复操作，则得到ABCA、ABCB、ABCC这三个序列，最后，我们将这三个序列分别进行全排列并将结果添加至result中。
说白了，想尽办法穷举所有可能的排列情况。
这里我的代码是这样写的，还值得优化，但是太懒了，所以就来了个“硬编码”：
1 if moves > ops_num: # moves为步骤数，ops_num为操作数 2 if moves - ops_num == 1: 3 for i in range(ops_num): 4 ops = copy.copy(init_ops) 5 ops.append(init_ops[i]) 6 Permutation(ops, beg, endl, all_ops) 7 if moves - ops_num == 2: 8 for i in range(ops_num): 9 for j in range(ops_num): 10 ops = copy.copy(init_ops) 11 ops.append(init_ops[i]) 12 ops.append(init_ops[j]) 13 Permutation(ops, beg, endl, all_ops) 14 if moves - ops_num == 3: 15 for i in range(ops_num): 16 for j in range(ops_num): 17 for k in range(ops_num): 18 ops = copy.copy(init_ops) 19 ops.append(init_ops[i]) 20 ops.append(init_ops[j]) 21 ops.append(init_ops[k]) 22 Permutation(ops, beg, endl, all_ops) 23 if moves - ops_num == 4: 24 for i in range(ops_num): 25 for j in range(ops_num): 26 for k in range(ops_num): 27 for q in range(ops_num): 28 ops = copy.copy(init_ops) 29 ops.append(init_ops[i]) 30 ops.append(init_ops[j]) 31 ops.append(init_ops[k]) 32 ops.append(init_ops[q]) 33 Permutation(ops, beg, endl, all_ops) 34 if moves - ops_num == 5: 35 for i in range(ops_num): 36 for j in range(ops_num): 37 for k in range(ops_num): 38 for q in range(ops_num): 39 for p in range(ops_num): 40 ops = copy.copy(init_ops) 41 ops.append(init_ops[i]) 42 ops.append(init_ops[j]) 43 ops.append(init_ops[k]) 44 ops.append(init_ops[q]) 45 ops.append(init_ops[p]) 46 Permutation(ops, beg, endl, all_ops) 47 if moves - ops_num == 6: 48 for i in range(ops_num): 49 for j in range(ops_num): 50 for k in range(ops_num): 51 for q in range(ops_num): 52 for p in range(ops_num): 53 for w in range(ops_num): 54 ops = copy.copy(init_ops) 55 ops.append(init_ops[i]) 56 ops.append(init_ops[j]) 57 ops.append(init_ops[k]) 58 ops.append(init_ops[q]) 59 ops.append(init_ops[p]) 60 ops.append(init_ops[w]) 61 Permutation(ops, beg, endl, all_ops) 62 elif moves == ops_num: 63 Permutation(init_ops, beg, endl, all_ops)
以上的代码只列举到了 moves – ops_num == 6 的情况，这是基于2号公理写的。2号公理指出，步骤数如果大于操作数，最多只大5，为了防止万一，我增加了上限，扩展成了6。
通过以上操作，我们可以说基本上完成了可用操作序列的完全列举。为什么说是基本上呢？因为在游戏后期，大概是LEVEL为155处，游戏增加了一个有趣的操作，称为“Store”，它将迫使我们继续深层次地列举所有可用操作序列。
第二个问题，如何测试所有操作序列？
看起来比较简单，不过是依序测试每个操作罢了，那么我们就先来看看整个游戏有哪些操作吧。
- +
- –
- *
- /
- 末尾插入数字（如当前数字为1234，插入7，则数字变为12347），插入数字的操作方块为浅紫色背景
- 数字代换C23=>14（如当前数字为1234，将23代换为14，则数字变为1144）
- 删除末尾数字<<（如当前数字为1234，删除一个数字，则数字变为123）
- 翻转数字Reverse（如当前数字为1234，翻转一个数字，则数字变为4321）
-
Shift<<（如当前数字为1234，向左Shift一个数字，则数字变为2341）
- Shift>>（如当前数字为1234，向右Shift一个数字，则数字变为4123）
- 立方x3（如当前数字为4，立方一个数字，则数字变为64）
- SUM（如当前数字为1234，SUM一个数字即求各位数字之和，则数字变为10）
- Mirror（如当前数字为123，Mirror一个数字即镜像拼接一个数字，则数字变为123321）
- +/-（如当前数字为1234，经此操作，则数字变为-1234）
- Inv10（如当前数字为1250，Inv10一个数字，则数字变为9850）
- [+]x（将当前所有可用的操作的数值全部加x，如当前所有可用操作为/2、+3、插入2，经过[+]1操作，则变为/3、+4、插入3）
- [-]x，同上，只是变为减x
- Store，长按该键保存当前计算得到的数值，在这之后其功能变为插入键的功能，即在末尾插入其保存的数字，注意，长按保存这一步骤并不消耗步骤数
- 标记求和，这个操作是没进行一个操作后，若满足条件自动完成的，具体来说将在下面详细介绍
这里有些操作比较简单，我主要讲一下[+]x、[-]x、Store以及标记求和这几个操作的处理细节，而前两个又可以归为一类。
在详细介绍这几个操作的实现之前，我觉得还有几点需要特意提一下，也是整个编程过程中的细节：
- 所有的操作都是整数操作，因此切忌在整个计算过程中误使数字变为浮点数；
- 一些操作在对正负数进行处理时需要注意细节，如左右Shift的时候，需要将数字和符号先分开（当然，这是我的实现方式，欢迎指出其他方法）；
- python有深浅拷贝的区别，需要特别注意。
1. [+]x
细细分析该操作，我将其定义为“摄动”操作符，即该操作影响了其他操作的操作数，为此，我引入了摄动因子 influence ，每当进行该操作时，即改变了摄动因子，而摄动因子又全面影响了其他所有摄动操作符将会影响到的操作。
代码如下：
1 influence = 0 2 for j in all_ops[i]: 3 if j[0] == '[': 4 if j[1] == '+': 5 influence += int(j[3:]) 6 elif j[1] == '-': 7 influence -= int(j[3:]) 8 elif j[0] == 'I': 9 if calc_num >= 0: 10 if int(j[1:]) + influence == 0: 11 calc_num = calc_num * 10 12 else: 13 calc_num = calc_num * pow(10, int(math.log10(int(j[1:]) + influence)) + 1) + int(j[1:])+influence 14 else: 15 if int(j[1:]) == 0: 16 calc_num = calc_num * 10 17 else: 18 calc_num = calc_num * pow(10, int(math.log10(int(j[1:]) + influence)) + 1) - int(j[1:])-influence 19 elif j[0] == '+': 20 calc_num += (int(j[1:]) + influence) 21 elif j[0] == '-': 22 calc_num -= (int(j[1:]) + influence) 23 elif j[0] == '*': 24 calc_num *= (int(j[1:]) + influence) 25 elif j[0] == '/': 26 if math.modf(calc_num/(int(j[1:])+influence))[0] != 0: 27 break 28 calc_num = calc_num // (int(j[1:])+influence)
此处我仅列举了摄动操作会影响到的操作，如插入、加减乘除，事实上，正如之前介绍的，Store本身也是一个插入操作，只是这里还没有详细介绍，因此暂时不提。
2. Store
Store运算符在这之前稍微介绍了一下，这个操作符最骚的一点是，长按能够保存当前计算得到的数字，而长按本身并不消耗步骤数，这一点大大提升了解谜的难度，在保存了数字后，短按该键将执行类似于插入数字的操作，短按插入数字时消耗步骤数。
在编程时需要解决的难题也就是这个长按与短按的问题，短按可以看作普通按键，长按就有些不可理喻了，不过经过一阵摸索，我也得到了一些经验，即长按保存数字的操作，在一局游戏中至多使用两次。
如此一来，我们就又有了穷举所有排列可能性的理论依据。
不外乎两种情况，插入一个长按Store操作和插入两个长按Store操作，且值得注意的是，长按Store操作在整个操作序列末尾是没有意义的，因此经过一通分析后，事情瞬间easy。
另外还有一点很关键，要能够分析到，根据1号公理，所有按键均需要使用到，因此在所有含有Store操作的游戏对局中，为了确保Store操作被使用，其必然经过了至少1次长按Store操作。于是，以下代码就诞生了：
1 store_index = [] 2 for i in range(len(all_ops)): 3 for it in all_ops[i]: 4 if it == 'Store': 5 store_index.append(i) 6 break 7 for i in range(len(store_index)): # 插入一个Store_S 8 temp = copy.deepcopy(all_ops[store_index[i]]) 9 for index in range(len(temp)): 10 temp_a = copy.deepcopy(temp) 11 temp_a.insert(index, 'Store_S') 12 all_ops.insert(len(all_ops), temp_a) 13 14 for i in range(len(store_index)): # 插入两个Store_S 15 temp = copy.deepcopy(all_ops[store_index[i]]) 16 for index in range(len(temp)-1): 17 temp_a = copy.deepcopy(temp) 18 temp_a.insert(index, 'Store_S') 19 for ttt in range(3-index): 20 temp_b = copy.deepcopy(temp_a) 21 temp_b.insert(index + ttt + 2, 'Store_S') 22 all_ops.insert(len(all_ops), temp_b) 23 24 for i in range(len(store_index)): 25 all_ops.pop(0)
这段代码的作用就是在全排列得到所有操作后，分别插入1个Store_S（即长按Store操作）与2个Store_S得到可用的全部操作序列，由于必然需要使用Store_S，因此，result队列最前面不含有Store_S的操作序列均可删去。
最后，在进行某一操作序列的测试时，我们定义变量 Store_num 用以保存Store_S操作保存的数字，并得到以下操作代码：
1 elif j == 'Store_S': 2 Store_num = calc_num 3 elif j == 'Store': 4 if calc_num >= 0: 5 if Store_num + influence == 0: 6 calc_num = calc_num * 10 7 else: 8 calc_num = calc_num * pow(10, int(math.log10(Store_num + influence)) + 1) + Store_num+influence 9 else: 10 if int(j[1:]) == 0: 11 calc_num = calc_num * 10 12 else: 13 calc_num = calc_num * pow(10, int(math.log10(Store_num + influence)) + 1) - Store_num-influence
如此一来，我们就完成了这个骚气的Store操作，效果杠杠的。
3. Patrol
这个Patrol操作，我将其中文名称为标记求和，大致长成下面这个样子：
所谓的标记求和，就是指对两个小三角所指的那两位数字进行求和，低于最左边三角所在位数的其余位数保持不变，高于最左边三角所在位数的数字自动向右移动一位。语言解释起来没什么感觉，我们来看一个实际的例子：
假设当前数字为123，设小三角所指位数从最右向最左由1依次增大，假设左三角指向第4位，右三角指向第1位，则在插入数字1后，数字变为1231，此时，两个三角所指的位数都有了数字，因此求和第1位和第4位的数字，得2，其余数字位数不变，最后转化为232。
再假设当前数字为1234，左三角指向第5位，右三角指向第1位，插入数字56，数字变成123456，第5位数字为2，第1位数字为6，求和得到8，由于1所在的位数为第6位，高于左三角所在位数，因此数字变为13458，此时第1和第5位仍有数字，所以继续自动进行标记求和操作，最终变为3459。
根据以上陈述，我们可以在经过一个操作序列的其中一个操作后，对得到的数字进行自动处理：
1 if patrol_flag == 1: 2 ss = calc_num//abs(calc_num) 3 calc_num = list(str(abs(calc_num))) 4 while len(calc_num) >= patrol_l: 5 patrol_sum = (int(calc_num[len(calc_num)-patrol_l])+int(calc_num[len(calc_num)-patrol_r]))*pow(10, patrol_r-1) 6 patrol_else_sum = 0 7 for zzz in range(len(calc_num)): 8 if zzz != patrol_l-1 and zzz != patrol_r-1 and zzz < patrol_l: 9 patrol_else_sum += int(calc_num[len(calc_num) - zzz - 1]) * pow(10, zzz) 10 if zzz >= patrol_l: 11 patrol_else_sum += int(calc_num[len(calc_num) - zzz - 1]) * pow(10, zzz - 1) 12 calc_num = patrol_sum + patrol_else_sum 13 calc_num = list(str(calc_num)) 14 calc_num = ss * int(''.join(calc_num))
这里我们使用的是while，为的就是保证数字送进去之后会一直自动变换，直至标记的位数不再同时含有数字。
总结
本来以为写个几行代码就能通关的，没想到这个游戏一直给我惊喜，各式各类的操作符花样迭出，因此最终完成的这版代码也是相当粗糙，目前还有以下几点值得优化：
- 对MOVES!=OPS的情况下，获取所有可能的操作序列的代码仍待优化，目前的代码太暴力了（不过很懒，可能就不改了hhh）
- 不同操作符对应的操作代码可以进行包装，形成函数，整个代码看起来应该会更清爽
不得不说，Python是一个相当妙的语言，它的编程逻辑与C还是有很大不同的，在写代码的过程中，才发现我对Python掌握得并不是很好，有很多语言特性还没有把握到，这也正表明了不断用类似的小项目去磨练自己的必要性。
我的代码也没怎么加注释，那这篇博文就当是注释啦hh