[PPC] mathGame - CirQ

xp0int Posted on Mar 12 2018

? PPC ? ? math game ?

差不多暴力破解过去的一道题，很有《最强大脑》的风格，分几个步骤：

根据题目确定A是 $xy$ 平面后，需要把其他五个平面中点的坐标映射到以A面为参考系的坐标中。方法是将每个平面的边和A的四条边匹配，这样就能确定包括A在内的五个平面，然后第六个平面也出来了。匹配的过程是对B-F平面做等效变换，可以避免对四条边的匹配顺序无从下手。一共使用了八种变换，分别是：无旋转、水平翻转、垂直翻转、顺时针旋转90、180、270度、沿主对角线翻转、副对角线翻转。实现时用了一些函数式编程的特性，如lambda、reduce等。

确定了每个点的坐标后，就是找出特殊的7个数字，题目给出了两条规则，奇偶和是否质数，其实第五题有另外一条隐藏规则：有7个数字是9位数，其他都是10位数，也很容易找到这个规则。这一步就能确定7个特殊点的坐标了。

最后要找出符合要求的两条直线，7个点两两配对能够得到21条直线，这里我用的表示方法是空间直线的点斜式，记录一个方向向量和一个过该直线的点（实际上两个点都记录了），回忆下高数的知识，应该不难。先找两条直线是否垂直，用点乘等于0判断。最后一步很坑，要找的是两条直线共同经过的方块，而不是相交的，没找到定量的方法计算，只用了近似的算法，也因此挺多回答是错误的，但暴力多跑几遍总能有一次五道题全过的（实际上大概跑了10次吧23333）。

近似的算法是枚举内部的 $5^3=125$个点，计算它们到这两条直线的距离之和，把值最小的那一个点作为答案。这里涉及到计算点到空间直线的距离，例如点C到直线AB的距离，等于两倍三角形ABC的面积除以AB的长度，实际上代码用了其他计算方法。

直接贴代码，代码中用到了思考过程中的自定义变量，可能不是很直观，有希望详细了解的可以来直接找我（虽然应该是没有的233333）。

```python
from pwn import *
from hashlib import sha256
from string import *
from math import sqrt
from itertools import product, combinations
from sympy import isprime
import re

context.log_level = 'debug'

r7 = range(7)

def enter(sh): # 工作量证明
    condition = sh.recvuntil('str\n\n').split()[0]
    def POW(x):
        r = condition.replace('str', '"'+x+'"')
        return eval(r) == True
    postfix = util.iters.mbruteforce(POW, ascii_letters+digits, 5)
    sh.sendline(postfix)

number_re = re.compile(r'\d{10}')
surface_re = re.compile(r'\s+[A-F][\s\S]+?\*{5,}\s')

def getsurfaces(sh, ret): # 通过正则表达式匹配得到数据
    allinone = sh.recvuntil('answer:')
    for s, surface in zip(uppercase[:6], surface_re.findall(allinone)):
        numbers = number_re.findall(surface)
        surface = [[None for i in r7] for j in r7]
        for order, number in enumerate(numbers):
            i, j = order % 7, 6 - order / 7
            surface[i][j] = number
        ret[s] = surface[:]
    return ret

nrot = lambda m: m[:]
hrot = lambda m: m[::-1]
vrot = lambda m: [x[::-1] for x in m]
rot90 = lambda m: [x[::-1] for x in zip(*m)]
rot180 = lambda m: rot90(rot90(m))
rot270 = lambda m: rot180(rot90(m))
trot = lambda m: zip(*m)
rtrot = lambda m: hrot(rot90(m))

transitions = [nrot, hrot, vrot, rot90, rot180, rot270, trot, rtrot]

# 分别匹配边，b-f是除A面之外五个面的别称，不解释了

def check_b(sA, s):
    for trans in transitions:
        sp = trans(s)
        if reduce(lambda x,r:sA[x][0]==sp[x][6] and r, r7, True): # 一行代码匹配七个坐标点，算是比较优雅的写法了
            return sp

def check_c(sA, s):
    for trans in transitions:
        sp = trans(s)
        if reduce(lambda y,r:sA[0][y]==sp[6][y] and r, r7, True):
            return sp

def check_d(sC, s):
    for trans in transitions:
        sp = trans(s)
        if reduce(lambda y,r:sC[0][y]==sp[0][y] and r, r7, True):
            return sp

def check_e(sA, s):
    for trans in transitions:
        sp = trans(s)
        if reduce(lambda x,r:sA[x][6]==sp[x][6] and r, r7, True):
            return sp

def check_f(sA, s):
    for trans in transitions:
        sp = trans(s)
        if reduce(lambda y,r:sA[6][y]==sp[6][y] and r, r7, True):
            return sp

def getpuzzle(sh): # 获取六个面的数据并做坐标转换，得到的puzzle是一个三维数组
    sh.recvregex(r'={5,}[\s\S]+={5,}\s')
    puzzle = [[[None for i in r7] for j in r7] for k in r7]

surfaces = getsurfaces(sh, {})
    for x, y in product(r7, r7):
        puzzle[x][y][0] = int(surfaces['A'][x][y])
        
    for s, surface in surfaces.items():
        if s == 'A' or not surface: continue
        b = check_b(surfaces['A'], surface)
        if b:
            for x, y in product(r7, r7):
                puzzle[x][0][6-y] = int(b[x][y])
            surfaces[s] = {}
            break

for s, surface in surfaces.items():
        if s == 'A' or not surface: continue
        c = check_c(surfaces['A'], surface)
        if c:
            for x, y in product(r7, r7):
                puzzle[0][y][6-x] = int(c[x][y])
            surfaces[s] = {}
            break

for s, surface in surfaces.items():
        if s == 'A' or not surface: continue
        d = check_d(c, surface)
        if d:
            for x, y in product(r7, r7):
                puzzle[x][y][6] = int(d[x][y])
            surfaces[s] = {}
            break

for s, surface in surfaces.items():
        if s == 'A' or not surface: continue
        e = check_e(surfaces['A'], surface)
        if e:
            for x, y in product(r7, r7):
                puzzle[x][6][6-y] = int(e[x][y])
            surfaces[s] = {}
            break

for s, surface in surfaces.items():
        if s == 'A' or not surface: continue
        f = check_f(surfaces['A'], surface)
        if f:
            for x, y in product(r7, r7):
                puzzle[6][y][6-x] = int(f[x][y])
            surfaces[s] = {}
            break

return puzzle

def parity_and_primarity_test(mp): # 检测奇偶等条件，一共五种情况
    odd = [cor for cor, d in mp.items() if d and d%2==1]
    if len(odd) == 7:
        return odd
    even = [cor for cor, d in mp.items() if d and d%2==0]
    if len(even) == 7:
        return even
    prime = [cor for cor, d in mp.items() if d and isprime(d)]
    if len(prime) == 7:
        return prime
    compo = [cor for cor, d in mp.items() if d and (cor not in prime)]
    if len(compo) == 7:
        return compo
    less = [cor for cor, d in mp.items() if d and len(str(d))<10]
    if len(less) == 7:
        return less
    return []

r5 = range(1, 6)

def distance(c, a, b): # 计算点c到空间直线ab的距离
    ab2 = (a[0]-b[0])**2 + (a[1]-b[1])**2 + (a[2]-b[2])**2
    ac2 = (a[0]-c[0])**2 + (a[1]-c[1])**2 + (a[2]-c[2])**2
    cb2 = (c[0]-b[0])**2 + (c[1]-b[1])**2 + (c[2]-b[2])**2
    cosa2 = (ab2 + ac2 - cb2)**2 / (4.0 * ac2 * ab2)
    return sqrt(ac2 * (1 - cosa2))

def calintersect(points): # 得到21条直线，计算共同经过点的坐标
    lines = []
    for p, q in combinations(points, 2):
        lines.append((p[0]-q[0], p[1]-q[1], p[2]-q[2], p, q))

ret = (None, 1000.0)
    for l1, l2 in combinations(lines, 2):
        if l1[0]*l2[0]+l1[1]*l2[1]+l1[2]*l2[2] == 0:
            least = (None, 1000.0)
            for point in product(r5, r5, r5):
                dist = distance(point, l1[3], l1[4]) + distance(point, l2[3], l2[4])
                if dist < least[1]:
                    least = (point, dist)
            if least[1] < ret[1]:
                ret = least
    return ret[0]

def solvepuzzle(puzzle): # 输入三维数组，输出最接近的一个坐标点
    mapping = {}
    for i, j, k in product(r7, r7, r7):
        number = puzzle[i][j][k]
        mapping[(i, j, k)] = number
    p = parity_and_primarity_test(mapping)
    if p:
        print p
        assert len(p) == 7
        cloest = calintersect(p)
        return cloest

def sendresult(sh, r): # 发送答案的封装函数
    sh.recvuntil('x:')
    sh.sendline(str(r[0]))
    sh.recvuntil('y:')
    sh.sendline(str(r[1]))
    sh.recvuntil('z:')
    sh.sendline(str(r[2]))

def attemp(sh): # 一次游戏有五道题
    for _ in range(5):
        pzl = getpuzzle(sh)
        clst = solvepuzzle(pzl)
        sendresult(sh, clst)

def session(sh): # 一个完整的游戏过程，包括工作量证明和最后的切换输入流
    enter(sh)
    attemp(sh)
    sh.interactive()

def wrapper(): # 由于答案会错，要进行多次尝试，这里用递归的方式做重复执行
    try:
        p = remote('47.98.54.1', 11011)
        session(p)
    except EOFError:
        p.shutdown()
        wrapper()

wrapper()
```

比赛环境现在应该不能用，就不写flag了hhhhhhh。

打赏还是打残，这是个问题