描述

算24点算是一个古老的算术小游戏了, 简单来说就是给定4个正整数(一般不超过13), 使用四则运算使得最终结果等于24.

比如给定2, 3, 4, 5四个数, 一个可行的解是:

24点算法之Python版(一) - 图1

之前用C和Ruby都做过这个题了, 最近学习Python, 也用Python来做一遍.

算法(伪)

首先考察解空间有多大, 4个数字, 全排列24点算法之Python版(一) - 图2, 按顺序每2个数字进行加减乘除4种运算, 需要算3次, 24点算法之Python版(一) - 图3, 因为已经全排列了, 所有的计算顺序都有了, 就不需要括号的组合了.

所以最终的解空间大小 24点算法之Python版(一) - 图4

对于计算机来说, 一千多次运算搜索算是个事吗? 直接穷举就完事了.

函数式编程

Python比起其他比如C/C++语言有个高级特性, 就是高阶函数, 简单说就是函数本身不再是一段硬代码, 而是可以像普通变量一样被赋值/运算/构造出来的东西, 而实施赋值/运算/构造这些函数的函数就是高阶函数.

这也是通常所说的函数式编程. 用函数式编程在这个算法上就可以将加减乘除函数提供给高阶函数来用, 可以减少很多代码量, 代码也清晰很多.

同时Python也提供了很多实用的类库, 比如我们算法需要的全排列(permutation), 笛卡尔积(product)等函数都有现成的. 代码如下:

  1. def solve(all_nums):
  2.     # 将加减乘除4种函数列在dict中
  3.     all_ops = {
  4.         "+": lambda a, b: a + b,
  5.         "-": lambda a, b: a - b,
  6.         "*": lambda a, b: a * b,
  7.         "/": lambda a, b: a / b,
  8.     }
  10.     # 先全排列所有数字
  11.     for nums in itertools.permutations(all_nums):
  12.         # 再笛卡尔积所有四则运算
  13.         for ops in itertools.product(all_ops, repeat=3):
  14.             # 按顺序运算得到结果
  15.             result = nums[0]
  16.             for i, op in enumerate(ops):
  17.                 result = all_ops[op](result, nums[i + 1])
  18.             if result == 24:
  19.                 # 如果结果是24则打印算式并结束
  20.                 exp = nums[0]
  21.                 for i, op in enumerate(ops):
  22.                     exp = f"({exp}{op}{nums[i + 1]})"
  23.                 print(exp)
  24.                 return
  26.     print("Not Found!")
  28. if __name__ == '__main__':
  29.     solve([2, 3, 4, 5])
  30.     # 输出: (((3-2)+5)*4)

这里要介绍一个特别常用的高阶函数reduce, 代码中顺序求值, 和顺序组合算式字符串的部分可以用reduce函数简化其写法, 其实所有类似求和, 求积, 按顺序的合并都可以用reduce操作, reduce是对这一类操作的抽象, 其实还是比较常见的.

通过map和reduce的组合, 可以干掉不少for循环, 如果熟练掌握这两个函数, 可以让代码变短的同时增加可读性, 现在几乎所有的高级语言都支持函数式编程, 也几乎所有的高级语言都有map/reduce函数了, 连Java这样”古老”的语言都添加了map/reduce的支持, 其他语言更不用说了.

客观的说, 使用map/reduce或者说使用函数式编程一方面提高了代码的抽象层次, 使其晦涩难懂了一些, 但是另一方面, 我们平时使用的各类工具/高级语言/数学模型本来都是在某些基础上做了更高的抽象, 如果你能适应了那个抽象层次, 你就能从那些底层的东西中跳出来, 以更加简洁/清晰的视角看待问题. 就像程序设计的演变, 从机器码到汇编, 到结构化程序设计, 到面向对象, 到函数式程序设计, 每一次进步都伴随着抽象层次的提高, 只有适应这种提高, 才能更好的解决问题. 到这个时候, 你再看函数式的程序就不会再觉得难懂了.

讲解map/reduce的文章很多了, 这里随便放一篇文章, 其他的自己搜索吧.

不过提到函数式编程, 这里强烈推荐一个在线小游戏Cube Composer, 练习使用一系列类似map/reduce/filter之类的高阶函数来完成任务, 能通关说明你已达小成境界, 快来玩吧!

压缩代码

所以上边的程序用reduce改造一下:

  1. def solve2(all_nums):
  2.     all_ops = {
  3.         "+": lambda a, b: a + b,
  4.         "-": lambda a, b: a - b,
  5.         "*": lambda a, b: a * b,
  6.         "/": lambda a, b: a / b,
  7.     }
  8.     # 核心代码只有4行
  9.     for nums in itertools.permutations(all_nums):
  10.         for ops in itertools.product(all_ops, repeat=3):
  11.             if reduce(lambda m, op: all_ops[op[1]](m, nums[op[0] + 1]), enumerate(ops), nums[0]) == 24:
  12.                 print(reduce(lambda m, op: f"({m}{op[1]}{nums[op[0] + 1]})", enumerate(ops), nums[0]))
  15. if __name__ == '__main__':
  16.     solve2([2, 3, 4, 5])
  17. # 这次咱们输出所有结果:
  18. # (((3-2)+5)*4)
  19. # (((3+4)+5)*2)
  20. # (((3+5)-2)*4)
  21. # (((3+5)+4)*2)
  22. # (((4+3)+5)*2)
  23. # (((4+5)+3)*2)
  24. # (((5-2)+3)*4)
  25. # (((5+3)-2)*4)
  26. # (((5+3)+4)*2)
  27. # (((5+4)+3)*2)

但是

虽然核心代码只有4行, 看上去很短, 不明觉历的样子, 但是不知道你有没注意到前面写的算法(伪), 因为这个算法是错的, 或者说并没有覆盖到所有情况.

到底哪里有问题, 要怎么改呢? 请关注下一篇“24点算法(二)”

Good Luck, Have Fun!