Python——Tchisla求解器(暴力搜索法)

Tchisla简介

最近玩到一个挺有意思的数字解密小游戏《Tchisla》,其规则类似算24点,也是利用一些数学运算和初始数字计算出目标数字,与算24点不同的是,Tchisla允许不限次数地使用一种初始数字(1~9),运算操作除了加减乘除外还包括了幂、平方根和阶乘,以及重复这个数字形成多位数(比如初始数字为7,那么777也可以使用)。游戏中的题目以“target # seed”的形式给出,我们的目标就是使用尽量少的初始数字seed加以各种计算得到目标数字target,比如题目11 # 7,最简解法就是11 = 77 / 7,比如题目5 # 9,最简解法为5 = √9 + (√9)! / √9。这里有篇文章更详细地介绍了这个游戏插电数字游戏——Tchisla 。
在这里插入图片描述
在这里插入图片描述

Tchisla求解器

这个游戏讲道理还是挺难的,尤其是挑战题目中的目标数都上千了,手动解题很难找到最优解,因此我花了半天用python写了个求解器,目前看起来效果不错,几十秒钟就帮我找到了了2016 # 1~9的所有最优解:
在这里插入图片描述

在求解Tchisla题目的过程中我相信是有一些内在的数学规律的,不过似乎很难总结出一套普适的最优求解算法,还是得暴力求解。暴力求解的思路其实挺简单的,从1个初始数字开始,找到所有合理的可达值及其表达式,放入一个列表中,这个称为第1代。后面再继续搜索第2代、第3代等等,对于第n代,其中的可达值就是n个初始数字可以表示的所有结果,计算第n代时我们可以根据前面的n-1代结果进行组合来生成新一代数据,比如5个初始数字可以得到的目标值就是第1代结果+第4代结果的各种算数组合加上第2代结果+第3代结果的各种算数组合。过程中一但发现目标值,我们就得到答案了。

虽然思路很简单,不过其中有些要注意的点,首先开方和阶乘运算这样的单目运算符不消耗初始数字,可以对一个表达式无限操作,为了避免无限搜索下去,所以第一点限制就是开方只对整数做、阶乘只对小于一定值的整数做。另外浮点数的精度丢失问题比较麻烦,需要合适的取整。此外,为了避免一些不太可能的无效搜索,合理的限制搜索数据的最大值也是必要的。

除了以上思路之外,为了得到结果,我们还需要一套表达式系统来跟踪我们的计算步骤,毕竟我们需要知道的最终是如何运算得到目标值而不仅仅是可以得到目标值的一个肯定。

以下放出代码,除了阶乘调用了系统库外,没有依赖别的库。代码前半部分是表达式系统,后半部分是求解器:

from math import factorial


class Expr:
  threshold = 1e-10

  def __init__(self, value):
    if isinstance(value, float):
      if value.is_integer():
        value = int(value)
      elif abs(value - round(value)) < Expr.threshold:
        value = round(value)
    self.value = value

  def __str__(self):
    raise TypeError("Should not call Expr.__str__()")


class LiteralExpr(Expr):
  def __init__(self, value):
    Expr.__init__(self, value)
    self.literal = str(value)

  def __str__(self):
    return self.literal


class FactorialExpr(Expr):
  def __init__(self, expr: Expr):
    Expr.__init__(self, factorial(expr.value))
    self.child = expr

  def __str__(self):
    if isinstance(self.child, BinaryExpr):
      return '({})!'.format(str(self.child))
    else:
      return str(self.child) + '!'


class SqrtExpr(Expr):
  def __init__(self, expr: Expr):
    Expr.__init__(self, expr.value ** 0.5)
    self.child = expr

  def __str__(self):
    if isinstance(self.child, LiteralExpr):
      return '√{}'.format(str(self.child))
    else:
      return '√({})'.format(str(self.child))


class BinaryExpr(Expr):
  def __init__(self, oper: str, left: Expr, right: Expr, value):
    Expr.__init__(self, value)
    self.oper = oper
    self.left = left
    self.right = right

  def __str__(self):
    format_str = '({})' if isinstance(self.left, BinaryExpr) else '{}'
    format_str += ' {} '
    format_str += '({})' if isinstance(self.right, BinaryExpr) else '{}'
    return format_str.format(str(self.left), self.oper, str(self.right))


class AddExpr(BinaryExpr):
  def __init__(self, left: Expr, right: Expr):
    BinaryExpr.__init__(self, '+', left, right, left.value + right.value)


class SubExpr(BinaryExpr):
  def __init__(self, left: Expr, right: Expr):
    BinaryExpr.__init__(self, '-', left, right, left.value - right.value)


class MulExpr(BinaryExpr):
  def __init__(self, left: Expr, right: Expr):
    BinaryExpr.__init__(self, '*', left, right, left.value * right.value)


class DivExpr(BinaryExpr):
  def __init__(self, left: Expr, right: Expr):
    BinaryExpr.__init__(self, '/', left, right, left.value / right.value)


class PowExpr(BinaryExpr):
  def __init__(self, left: Expr, right: Expr):
    BinaryExpr.__init__(self, '^', left, right, left.value ** right.value)


class TchislaSolver:
  value_limit = 10 ** 8
  power_limit = 30
  factorial_limit = 15

  class Found(BaseException):
    pass

  def __init__(self, target: int, seed: int):
    self.target = target
    self.seed = seed

    self.all_candidates = set()
    self.current_candidates = []
    self.generations = []
    self.result = None

  def solve(self, search_depth=10):
    try:
      while search_depth > 0:
        begin, end = 0, len(self.generations) - 1
        while begin <= end:
          self.cross_candidates(self.generations[begin], self.generations[end])
          begin += 1
          end -= 1
        self.add_literal(len(self.generations) + 1)
        self.next_generation()
        search_depth -= 1
    except TchislaSolver.Found:
      pass
    return self.result

  def cross_candidates(self, c1, c2):
    for expr1 in c1:
      for expr2 in c2:
        self.add_addition(expr1, expr2)
        self.add_subtraction(expr1, expr2)
        self.add_multiplication(expr1, expr2)
        self.add_division(expr1, expr2)
        self.add_power(expr1, expr2)

  def add_candidate(self, expr):
    if expr.value == self.target:
      self.result = expr
      raise TchislaSolver.Found()
    if expr.value > TchislaSolver.value_limit:
      return
    if expr.value not in self.all_candidates:
      self.all_candidates.add(expr.value)
      self.current_candidates.append(expr)
      self.add_factorial(expr)
      self.add_square_root(expr)

  def next_generation(self):
    self.generations.append(self.current_candidates)
    self.current_candidates = []

  def add_literal(self, repeats: int):
    self.add_candidate(LiteralExpr(int(str(self.seed) * repeats)))

  def add_addition(self, expr1: Expr, expr2: Expr):
    self.add_candidate(AddExpr(expr1, expr2))

  def add_subtraction(self, expr1: Expr, expr2: Expr):
    if expr1.value > expr2.value:
      self.add_candidate(SubExpr(expr1, expr2))
    else:
      self.add_candidate(SubExpr(expr2, expr1))

  def add_multiplication(self, expr1: Expr, expr2: Expr):
    self.add_candidate(MulExpr(expr1, expr2))

  def add_division(self, expr1: Expr, expr2: Expr):
    if expr1.value == 0 or expr2.value == 0:
      return
    self.add_candidate(DivExpr(expr1, expr2))
    self.add_candidate(DivExpr(expr2, expr1))

  def add_power(self, expr1: Expr, expr2: Expr):
    if isinstance(expr2.value, int) and expr2.value <= TchislaSolver.power_limit:
      self.add_candidate(PowExpr(expr1, expr2))
    if isinstance(expr1.value, int) and expr1.value <= TchislaSolver.power_limit:
      self.add_candidate(PowExpr(expr2, expr1))

  def add_factorial(self, expr: Expr):
    if isinstance(expr.value, int) and expr.value <= TchislaSolver.factorial_limit:
      self.add_candidate(FactorialExpr(expr))

  def add_square_root(self, expr: Expr):
    if isinstance(expr.value, int) and expr.value > 0:
      self.add_candidate(SqrtExpr(expr))

测试

这个求解器用起来很简单,可以编写一个简单的例子进行测试,计算2016 # 1~9的最优解:

for i in range(1, 10):
  ts = TchislaSolver(2016, i)
  print('2016 = ' + str(ts.solve()))

结果如下:
在这里插入图片描述
代码中对搜索和运算是有一些限制的,默认搜索10代,可达值最大只接受10^8,幂指数最大30,阶乘数最大15,这些限制可以加快搜索速度,一般是够用的,如果没搜索到最优解,也可以尝试修改以下值来调整并重新搜索:

  value_limit = 10 ** 8
  power_limit = 30
  factorial_limit = 15

从上面的结果图里还可以发现表达式系统还有优化的空间,有些括号是多余的,不过懒得搞了,能用就行~

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/415125.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

MySQL篇—持久化和非持久化统计信息介绍(第一篇,总共三篇)

☘️博主介绍☘️&#xff1a; ✨又是一天没白过&#xff0c;我是奈斯&#xff0c;DBA一名✨ ✌✌️擅长Oracle、MySQL、SQLserver、Linux&#xff0c;也在积极的扩展IT方向的其他知识面✌✌️ ❣️❣️❣️大佬们都喜欢静静的看文章&#xff0c;并且也会默默的点赞收藏加关注❣…

科技论文编写思路

科技论文编写思路 1.基本框架2.课题可行性评估1.研究目标和意义2.研究方法和技术3.可行性和可操作性4.风险和不确定性5.经济性和资源投入6.成果预期和评估 3.写作思路4.利用AI读论文5.实验流程 1.基本框架 IntroductionRelated worksMethodExperiment and analysisDiscussionC…

JavaScript作用域及预解析

文章目录 1. 作用域介绍2. 变量的作用域*3. JS中没有块级作用域4. 作用域链5. 预解析预解析案例 1. 作用域介绍 全局作用域局部作用域相同的变量名称在不同的作用域中是不会相互影响的&#xff01; 2. 变量的作用域 全局变量&#xff1a;在全局下都可以使用&#xff1b;局部变…

集群分发脚本xsync

集群分发脚本xsync 一、简介二、环境准备三、添加到机器的 hosts 文件四、ping 命令测试五、SSH 配置5.1.本地先生成公钥和私钥5.2.将公钥拷贝到其他机器 六、xsync 脚本编写6.1.安装 rsync6.2.新建 xsync.sh6.3.xsync.sh脚本6.4.赋予脚本执行权限6.5.测试 endl 一、简介 配置…

学习笔记-李沐动手学深度学习(七)(19-21,卷积层、填充padding、步幅stride、多输入多输出通道)

总结 19-卷积层 【补充】看评论区建议的卷积动画视频 数学中的卷积 【链接】https://www.bilibili.com/video/BV1VV411478E/?fromsearch&seid1725700777641154181&vd_sourcee81e116c4ffe5e79d4bc44738263eda4 【可判断是否为卷积的典型标志】两个函数中自变量相加…

Unity零基础到进阶 | Unity中的 RectTransformUtility 方法整理汇总

Unity零基础到进阶 ☀️| RectTransformUtility 方法整理汇总一、RectTransformUtility 官方文档1.1 RectTransformUtility.CalculateRelativeRectTransformBounds&#xff08;重&#xff09;1.2 RectTransformUtility.FlipLayoutAxes1.3 RectTransformUtility.FlipLayoutOnAxi…

Unity中URP实现水体(水的焦散)

文章目录 前言一、原理1、 通过深度图&#xff0c;得到 对应像素 在 世界空间下的Z值2、得到模型顶点在 观察空间 下的坐标3、由以上两点得到 深度图像素 对应的 xyz 值4、最后&#xff0c;转化到 模型本地空间下&#xff0c;用其对焦散纹理采样 二、实现1、获取深度图2、在顶点…

[WebUI Forge]ForgeUI的安装与使用 | 相比较于Auto1111 webui 6G显存速度提升60-75%

ForgeUI的github主页地址:https://github.com/lllyasviel/stable-diffusion-webui-forge Stable Diffusion WebUI Forge 是一个基于Stable Diffusion WebUI(基于Gradio)的平台,可简化开发、优化资源管理并加快推理速度。 “Forge”这个名字的灵感来自于“Minecraft Forge”…

《Vite 基础知识》Vitepress 技术文档站点搭建与配置

前言 简介 VitePress 是一个静态站点生成器 (SSG)&#xff0c;专为构建快速、以内容为中心的站点而设计。 简而言之&#xff0c;可构建你自己的 技术文档站点&#xff1b; 环境要求 Node.js 18 及以上版本。我使用 v20.11.0 创建 第一步&#xff1a; 全局安装 npm i vitep…

图搜索基础-深度优先搜索

图搜索基础-深度优先搜索 参考原理引入流程解析手推例子 代码实现运行结果结果分析 参考 理论参考&#xff1a;深蓝学院 实现参考&#xff1a;github项目 原理 引入 对于这样一个图&#xff0c;我们试图找到S到G的通路&#xff1a; 计算机程序不会像人眼一样&#xff0c;一…

鸿蒙应用程序包安装和卸载流程

开发者 开发者可以通过调试命令进行应用的安装和卸载&#xff0c;可参考多HAP的调试流程。 图1 应用程序包安装和卸载流程&#xff08;开发者&#xff09; 多HAP的开发调试与发布部署流程 多HAP的开发调试与发布部署流程如下图所示。 图1 多HAP的开发调试与发布部署流程 …

线性DP-前缀和

哪种连续子字符串更长 思路 我们遍历输入字符串s中的每个字符。对于每个字符&#xff0c;我们检查它是1还是0&#xff0c;并相应地更新currentLength1和currentLength0。当我们遇到一个1时&#xff0c;我们增加currentLength1的值&#xff0c;并将currentLength0重置为0&#…

2023秋季飞书未来无限大会--随笔

这个时代的飞书 数字时代 工作协同平台 AI时代 帮助企业和个人用好AI 企业如何引用大模型能力&#xff1f; 智慧体— 接近人&#xff0c;有进步空间智能伙伴 用时代的科技打造爱不释手的好产品 移动互联网 – 改变信息分发方式 大模型 –自然的人机交互方式 业务协同 …

Swagger接口文档管理工具

Swagger 1、Swagger1.1 swagger介绍1.2 项目集成swagger流程1.3 项目集成swagger 2、knife4j2.1 knife4j介绍2.2 项目集成knife4j 1、Swagger 1.1 swagger介绍 官网&#xff1a;https://swagger.io/ Swagger 是一个规范和完整的Web API框架&#xff0c;用于生成、描述、调用和…

kali linux通过aircrack-ng命令破解wifi密码

相关阅读&#xff1a;如何破解攻击WiFi 百度安全验证https://baijiahao.baidu.com/s?id1764248756021219497&wfrspider&forpc上面2篇文章写得都很不错 一、前期准备工作 1、将无线网卡挂载到Kali上 ​ 将无线网卡插到电脑上&#xff0c;如果弹出检测到新的USB设备&…

break,continue

break&#xff1a;跳出并结束循环 continue:跳过本次循环&#xff0c;执行下一次循环 代码演示&#xff1a; package com.zhang.loop;public class BreakAndContinueDemo8 {public static void main(String[] args) {//掌握break和continue的作用//1. break&#xff1a;跳出循…

​LeetCode解法汇总2673. 使二叉树所有路径值相等的最小代价

目录链接&#xff1a; 力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目&#xff1a; https://github.com/September26/java-algorithms 原题链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 给你一个整数 n 表示一棵 满二叉树 里面节…

Java设计模式 | 七大原则之迪米特法则

基本介绍 一个对象应该对其他对象保持最少的了解类与类关系越密切&#xff0c;耦合度越大迪米特法则&#xff08;Demeter Principle&#xff09;又叫最少知道法则&#xff0c;即一个类对自己依赖的类知道的越少越好。也就是说&#xff0c;对于被依赖的类不管多么复杂&#xff…

虚拟机 VMware 安装 Windows2000 (iso 光盘镜像)

上篇博客关于 kali 的安装&#xff0c;我们下载的直接是 vmx 文件 这次我们以 iso 文件为例&#xff0c;因此配置过程会有些许不同 先在本地新建一个文件夹用于存放我们一会儿下载的 iso 镜像文件 下载好后是一个后缀为 .iso 的文件 同样我们先打开 VMware 依次点击文件 -&g…

亚信安慧AntDB开启超融合数据库新纪元

&#xff08;一&#xff09; 前言 据统计&#xff0c;在信息化时代的今天&#xff0c;人们一天所接触到的信息量&#xff0c;是古人一辈子所能接收到的信息量的总和。当今社会中除了信息量“多”以外&#xff0c;人们对信息处理的“效率”和“速度”的要求也越来越高。譬如&…