#!/usr/bin/env python
# coding: utf-8

# In[1]:


get_ipython().system('python -V')


# # 驴啃计算器
# 
# 首先让我们明确这道题的限制和目标，题目中给出了 20 个计算器上常见的一元函数，你需要通过这些一元函数实现逼近任意给定的浮点数。
# 
# 一元函数有：sin, cos, tan, asin, acos, atan, sinh, cosh, tanh, asinh, acosh, atanh, exp, log, x^2, sqrt, -x, 1/x, R2D, D2R，我们把这个集合记为 $F$
# 
# 形式化来说，对于任意 $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$
# 
# 本题中为了降低难度，取 $\epsilon = 10^{-5}$ 且 $y_0 \in (0, 100)$

# ## 解法一：搜索
# 
# 一开始没有想到搜索能完成这道题目，但是在进行流量分析是发现有的 payload 明显没有模式，要么解题者是自己在草稿纸上算出来的，要么是搜索的结果，搜索算法很简单，就是枚举 $f$ 序列即可，但可能要进行适量的剪枝或者固定某些步骤的优化，在本地判断后没有问题，就可以提交了。注意：如果遇到搜不出来的情况，可以提交一个错误答案后尝试新的。
# 
# 这个解法适用的情况很窄，如果取 $\epsilon = 10^{-9}$ 甚至我们只要求 $\epsilon > 0$，暴力搜索就不太可能做到。

# ## 解法二：二进制逼近
# 
# 观察题目中的这些函数，我们能很快构造出让屏幕上数字乘 2，除以 2 的序列（这里函数顺序为按键顺序）：
# 
# 乘 2：$x * 2 = exp, x^2, log$
# 
# 除以 2：$x / 2 = exp, sqrt, log$
# 
# 有了这两个新的「一元函数」，我们很容易联想到任何数字都有二进制表示，只要我们能加 1，就能通过一个数的二进制表示来构造任何数字，那么问题是怎么加 1 呢？
# 
# 我们注意到有双曲函数恒等式：
# 
# $\cosh 2x\ = \cosh^2 x + \sinh^2 x = 2\cosh^2 x - 1 = 2\sinh^2 x + 1$
# 
# 俗话说：一寸长，一寸强，这么长的公式肯定强。 
# 
# 我们将想要的目标形式 $x + 1$ 和这个公式放在一起观察。不难发现：
# 
# 令 $t = 2\sinh^2 x$，即 $x = \rm{asinh}(\rm{sqrt}(t/2))$，那么：
# 
# $t + 1 = \cosh 2x = \cosh(2(\rm{asinh}(\rm{sqrt}(t/2))))$，换回去：
# 
# $x + 1 = \cosh(2(\rm{asinh}(\rm{sqrt}(x/2))))$
# 
# 注意到右边用到了我们发现的两个新一元函数乘 2 和除以 2，仍然是完全的一元函数复合形式，我好了。
# 
# 有了这个理论基础我们就可以编写代码，利用题目提供的 `poc.py`，我们可以编写如下解题脚本：

# In[5]:


import json
import requests
host = "http://202.38.93.241:10024"

class Calc:
    def __init__(self):
        self.ops = []
        
    def op(self, name, *kws):
        if name in dir(self):
            getattr(self, name)(*kws)
        else:
            self.ops.append(name)
    
    def mul2(self):
        # 乘以 2
        self.op('exp')
        self.op('x^2')
        self.op('log')
        
    def div2(self):
        # 除以 2
        self.op('exp')
        self.op('sqrt')
        self.op('log')
    
    def add1(self):
        # 利用双曲函数公式加 1
        self.op('div2')
        self.op('sqrt')
        self.op('asinh')
        self.op('mul2')
        self.op('cosh')
        
    def addn(self, n):
        # 利用多次加 1 加 n
        for _ in range(n):
            self.op('add1')

def solve(x):
    # 二进制小数点后的位数
    n = 20
    calc = Calc()
    
    # 利用除以 2 （相当于二进制右移）构造小数部分
    for i in range(n):
        if int(x * 2 ** (n - i)) % 2:
            calc.op('add1')
        calc.op('div2')
    
    calc.op('addn', int(x))
    
    seq = ','.join(calc.ops)
    return seq


with requests.session() as sess:
    r = sess.get(host + '/challenges')
    X = json.loads(r.text)["msg"]
    print(X)
    data = {
        "a1": solve(X[0]),
        "a2": solve(X[1]),
        "a3": solve(X[2])
    }
    r = sess.post(host + "/submit", data=data)
    resp = json.loads(r.text)
    print(resp["msg"])


# ## 解法三：连分数
# 
# 有人可能要问：能不能再给力一点？
# 
# 上面的二进制解法基本可以满足比较高的精度要求，但是有没有一个甚至没有理论误差的方法？
# 
# 答案是显然的：如果我们有一个数的精确连分数表达，那么我们可以用题目限制下的函数构造没有理论误差的计算公式。
# 
# 关于连分数请参看 [维基百科：连分数](https://zh.wikipedia.org/wiki/%E8%BF%9E%E5%88%86%E6%95%B0)，对于有理数，连分数分解算法可以用简单的辗转相除得到，我们这里将目标近似为一个有理数（这里引入了部分误差），然后对其进行连分数分解，最后利用 `addn` 和 `1/x` 完成连分数的计算：

# In[7]:


import json
import requests
host = "http://202.38.93.241:10024"

import sympy
EPS = 1e-7

class Calc:
    def __init__(self):
        self.ops = []
        
    def op(self, name, *kws):
        if name in dir(self):
            getattr(self, name)(*kws)
        else:
            self.ops.append(name)
    
    def mul2(self):
        # 乘以 2
        self.op('exp')
        self.op('x^2')
        self.op('log')
        
    def div2(self):
        # 除以 2
        self.op('exp')
        self.op('sqrt')
        self.op('log')
    
    def add1(self):
        # 利用双曲函数公式加 1
        self.op('div2')
        self.op('sqrt')
        self.op('asinh')
        self.op('mul2')
        self.op('cosh')
    
    def addn(self, n):
        # 利用多次加 1 加 n
        for _ in range(n):
            self.op('add1')

def solve(x):
    # 将小数化为分数
    p = int(x / EPS)
    q = int(p / x)
    
    # 计算连分数数组
    cfs = sympy.ntheory.continued_fraction.continued_fraction_periodic(p, q, 0)
    
    # 利用 addn 和 1/x 计算连分数
    calc = Calc()
    for k in cfs[::-1]:
        calc.op('addn', k)
        calc.op('1/x')
    calc.op('1/x')
    
    seq = ','.join(calc.ops)
    return seq


with requests.session() as sess:
    r = sess.get(host + '/challenges')
    X = json.loads(r.text)["msg"]
    print(X)
    data = {
        "a1": solve(X[0]),
        "a2": solve(X[1]),
        "a3": solve(X[2])
    }
    r = sess.post(host + "/submit", data=data)
    resp = json.loads(r.text)
    print(resp["msg"])


# ## 附录
# 
# 这道题为了降低难度让很多低精度方法也能通过，所以应该有很多近似方法可以解出本题，如果你有有趣的解法欢迎 PR 投稿。
# 
# 在比赛过程中也有很多人询问为什么会 system error，我想把这个问题连同下面的思考题一起留作课后作业：
# 
# - 为什么会 system error？
# 
# - 为什么在构造 `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]$ ？
# 
# 题目代码已经上传到本目录 `src` 下。