{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Python 3.5.5 :: Anaconda custom (64-bit)\n"
     ]
    }
   ],
   "source": [
    "!python -V"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 驴啃计算器\n",
    "\n",
    "首先让我们明确这道题的限制和目标，题目中给出了 20 个计算器上常见的一元函数，你需要通过这些一元函数实现逼近任意给定的浮点数。\n",
    "\n",
    "一元函数有：sin, cos, tan, asin, acos, atan, sinh, cosh, tanh, asinh, acosh, atanh, exp, log, x^2, sqrt, -x, 1/x, R2D, D2R，我们把这个集合记为 $F$\n",
    "\n",
    "形式化来说，对于任意 $y_0 \\in \\mathbb{R}$，构造 $\\{f_k\\}$ $(f_k \\in F, k=1,...,n)$ 序列，记 $y = (f_n \\circ f_{n-1} \\circ ... \\circ f_1)(0) = f_n(f_{n-1}(...f_1(0)))$，满足 $|y-y_0| < \\epsilon$\n",
    "\n",
    "本题中为了降低难度，取 $\\epsilon = 10^{-5}$ 且 $y_0 \\in (0, 100)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 解法一：搜索\n",
    "\n",
    "一开始没有想到搜索能完成这道题目，但是在进行流量分析是发现有的 payload 明显没有模式，要么解题者是自己在草稿纸上算出来的，要么是搜索的结果，搜索算法很简单，就是枚举 $f$ 序列即可，但可能要进行适量的剪枝或者固定某些步骤的优化，在本地判断后没有问题，就可以提交了。注意：如果遇到搜不出来的情况，可以提交一个错误答案后尝试新的。\n",
    "\n",
    "这个解法适用的情况很窄，如果取 $\\epsilon = 10^{-9}$ 甚至我们只要求 $\\epsilon > 0$，暴力搜索就不太可能做到。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 解法二：二进制逼近\n",
    "\n",
    "观察题目中的这些函数，我们能很快构造出让屏幕上数字乘 2，除以 2 的序列（这里函数顺序为按键顺序）：\n",
    "\n",
    "乘 2：$x * 2 = exp, x^2, log$\n",
    "\n",
    "除以 2：$x / 2 = exp, sqrt, log$\n",
    "\n",
    "有了这两个新的「一元函数」，我们很容易联想到任何数字都有二进制表示，只要我们能加 1，就能通过一个数的二进制表示来构造任何数字，那么问题是怎么加 1 呢？\n",
    "\n",
    "我们注意到有双曲函数恒等式：\n",
    "\n",
    "$\\cosh 2x\\ = \\cosh^2 x + \\sinh^2 x = 2\\cosh^2 x - 1 = 2\\sinh^2 x + 1$\n",
    "\n",
    "俗话说：一寸长，一寸强，这么长的公式肯定强。 \n",
    "\n",
    "我们将想要的目标形式 $x + 1$ 和这个公式放在一起观察。不难发现：\n",
    "\n",
    "令 $t = 2\\sinh^2 x$，即 $x = \\rm{asinh}(\\rm{sqrt}(t/2))$，那么：\n",
    "\n",
    "$t + 1 = \\cosh 2x = \\cosh(2(\\rm{asinh}(\\rm{sqrt}(t/2))))$，换回去：\n",
    "\n",
    "$x + 1 = \\cosh(2(\\rm{asinh}(\\rm{sqrt}(x/2))))$\n",
    "\n",
    "注意到右边用到了我们发现的两个新一元函数乘 2 和除以 2，仍然是完全的一元函数复合形式，我好了。\n",
    "\n",
    "有了这个理论基础我们就可以编写代码，利用题目提供的 `poc.py`，我们可以编写如下解题脚本："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[35.82831063699986, 80.6361952659885, 88.59694036265915]\n",
      "flag{you_are_good_at_using_calculators_by_amiya}\n"
     ]
    }
   ],
   "source": [
    "import json\n",
    "import requests\n",
    "host = \"http://202.38.93.241:10024\"\n",
    "\n",
    "class Calc:\n",
    "    def __init__(self):\n",
    "        self.ops = []\n",
    "        \n",
    "    def op(self, name, *kws):\n",
    "        if name in dir(self):\n",
    "            getattr(self, name)(*kws)\n",
    "        else:\n",
    "            self.ops.append(name)\n",
    "    \n",
    "    def mul2(self):\n",
    "        # 乘以 2\n",
    "        self.op('exp')\n",
    "        self.op('x^2')\n",
    "        self.op('log')\n",
    "        \n",
    "    def div2(self):\n",
    "        # 除以 2\n",
    "        self.op('exp')\n",
    "        self.op('sqrt')\n",
    "        self.op('log')\n",
    "    \n",
    "    def add1(self):\n",
    "        # 利用双曲函数公式加 1\n",
    "        self.op('div2')\n",
    "        self.op('sqrt')\n",
    "        self.op('asinh')\n",
    "        self.op('mul2')\n",
    "        self.op('cosh')\n",
    "        \n",
    "    def addn(self, n):\n",
    "        # 利用多次加 1 加 n\n",
    "        for _ in range(n):\n",
    "            self.op('add1')\n",
    "\n",
    "def solve(x):\n",
    "    # 二进制小数点后的位数\n",
    "    n = 20\n",
    "    calc = Calc()\n",
    "    \n",
    "    # 利用除以 2 （相当于二进制右移）构造小数部分\n",
    "    for i in range(n):\n",
    "        if int(x * 2 ** (n - i)) % 2:\n",
    "            calc.op('add1')\n",
    "        calc.op('div2')\n",
    "    \n",
    "    calc.op('addn', int(x))\n",
    "    \n",
    "    seq = ','.join(calc.ops)\n",
    "    return seq\n",
    "\n",
    "\n",
    "with requests.session() as sess:\n",
    "    r = sess.get(host + '/challenges')\n",
    "    X = json.loads(r.text)[\"msg\"]\n",
    "    print(X)\n",
    "    data = {\n",
    "        \"a1\": solve(X[0]),\n",
    "        \"a2\": solve(X[1]),\n",
    "        \"a3\": solve(X[2])\n",
    "    }\n",
    "    r = sess.post(host + \"/submit\", data=data)\n",
    "    resp = json.loads(r.text)\n",
    "    print(resp[\"msg\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 解法三：连分数\n",
    "\n",
    "有人可能要问：能不能再给力一点？\n",
    "\n",
    "上面的二进制解法基本可以满足比较高的精度要求，但是有没有一个甚至没有理论误差的方法？\n",
    "\n",
    "答案是显然的：如果我们有一个数的精确连分数表达，那么我们可以用题目限制下的函数构造没有理论误差的计算公式。\n",
    "\n",
    "关于连分数请参看 [维基百科：连分数](https://zh.wikipedia.org/wiki/%E8%BF%9E%E5%88%86%E6%95%B0)，对于有理数，连分数分解算法可以用简单的辗转相除得到，我们这里将目标近似为一个有理数（这里引入了部分误差），然后对其进行连分数分解，最后利用 `addn` 和 `1/x` 完成连分数的计算："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[8.537001664460819, 13.772290777666662, 90.89072584304898]\n",
      "flag{you_are_good_at_using_calculators_by_amiya}\n"
     ]
    }
   ],
   "source": [
    "import json\n",
    "import requests\n",
    "host = \"http://202.38.93.241:10024\"\n",
    "\n",
    "import sympy\n",
    "EPS = 1e-7\n",
    "\n",
    "class Calc:\n",
    "    def __init__(self):\n",
    "        self.ops = []\n",
    "        \n",
    "    def op(self, name, *kws):\n",
    "        if name in dir(self):\n",
    "            getattr(self, name)(*kws)\n",
    "        else:\n",
    "            self.ops.append(name)\n",
    "    \n",
    "    def mul2(self):\n",
    "        # 乘以 2\n",
    "        self.op('exp')\n",
    "        self.op('x^2')\n",
    "        self.op('log')\n",
    "        \n",
    "    def div2(self):\n",
    "        # 除以 2\n",
    "        self.op('exp')\n",
    "        self.op('sqrt')\n",
    "        self.op('log')\n",
    "    \n",
    "    def add1(self):\n",
    "        # 利用双曲函数公式加 1\n",
    "        self.op('div2')\n",
    "        self.op('sqrt')\n",
    "        self.op('asinh')\n",
    "        self.op('mul2')\n",
    "        self.op('cosh')\n",
    "    \n",
    "    def addn(self, n):\n",
    "        # 利用多次加 1 加 n\n",
    "        for _ in range(n):\n",
    "            self.op('add1')\n",
    "\n",
    "def solve(x):\n",
    "    # 将小数化为分数\n",
    "    p = int(x / EPS)\n",
    "    q = int(p / x)\n",
    "    \n",
    "    # 计算连分数数组\n",
    "    cfs = sympy.ntheory.continued_fraction.continued_fraction_periodic(p, q, 0)\n",
    "    \n",
    "    # 利用 addn 和 1/x 计算连分数\n",
    "    calc = Calc()\n",
    "    for k in cfs[::-1]:\n",
    "        calc.op('addn', k)\n",
    "        calc.op('1/x')\n",
    "    calc.op('1/x')\n",
    "    \n",
    "    seq = ','.join(calc.ops)\n",
    "    return seq\n",
    "\n",
    "\n",
    "with requests.session() as sess:\n",
    "    r = sess.get(host + '/challenges')\n",
    "    X = json.loads(r.text)[\"msg\"]\n",
    "    print(X)\n",
    "    data = {\n",
    "        \"a1\": solve(X[0]),\n",
    "        \"a2\": solve(X[1]),\n",
    "        \"a3\": solve(X[2])\n",
    "    }\n",
    "    r = sess.post(host + \"/submit\", data=data)\n",
    "    resp = json.loads(r.text)\n",
    "    print(resp[\"msg\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 附录\n",
    "\n",
    "这道题为了降低难度让很多低精度方法也能通过，所以应该有很多近似方法可以解出本题，如果你有有趣的解法欢迎 PR 投稿。\n",
    "\n",
    "在比赛过程中也有很多人询问为什么会 system error，我想把这个问题连同下面的思考题一起留作课后作业：\n",
    "\n",
    "- 为什么会 system error？\n",
    "\n",
    "- 为什么在构造 `add1` 时，选择了 $[1]\\ \\cosh 2x\\ =[2]\\  \\cosh^2 x + \\sinh^2 x =[3]\\  2\\cosh^2 x - 1 = [4]\\ 2\\sinh^2 x + 1$ 中的 $[1] = [4]$ 而不是 $[1] = [3]$ ？\n",
    "\n",
    "题目代码已经上传到本目录 `src` 下。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [default]",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}