Codewars Python练习:Secret knock

题目

Perform the secret knock() to enter…

链接

https://www.codewars.com/kata/secret-knock/train/python

题解

近期做过的一道非常好玩的题目!实际上这道题实在一年前就看过,但是当时CodeWars没有Test Driven Development (TDD) 这个模块,因此被挡在了反汇编那一步。

首先,在solution栏目写一个knock()函数调用,运行结果如下——

knock()
#>>Sorry, that's not the secret knock.

那么,这道题要我们做的,就应该是用某种特殊的技巧调用knock()函数,使得Sorry, that’s not the secret knock. 输出不被触发。

在解题界面中的Test Driven Development (TDD) 有如下代码(由于习惯问题,我对于这些代码做了少量修改,使得其能运行在Python3.4.3环境下)——

def knock():
    def opendoor():
        print("Opened!\n")
        print("Opened, again!\n")

    lineCount=0

    opendoor()

import dis;
print("\n<<FUNCTION: KNOCK()");
dis.dis(knock.__code__);
print("\n<<FUNCTION: KNOCK>OPENDOOR()");
dis.dis(knock.__code__.co_consts[1]);
print("\n<<FUNCTION: KNOCK>CONSTS");
for i,w in enumerate(knock.__code__.co_consts):
    print(i,w)

这一段代码实际上是解题方法的提示(想到一年前我没有这句话能想到尝试反汇编也已经不错了),这段代码使用 RUN SAMPLE TEST 按钮运行后,得到如下输出——

<<FUNCTION: KNOCK()
  4           0 LOAD_CONST               1 (<code object opendoor at 0x7f3e3124a150, file "main.py", line 4>)
              3 LOAD_CONST               2 ('knock.<locals>.opendoor')
              6 MAKE_FUNCTION            0
              9 STORE_FAST               0 (opendoor)

  8          12 LOAD_CONST               3 (0)
             15 STORE_FAST               1 (lineCount)

 10          18 LOAD_FAST                0 (opendoor)
             21 CALL_FUNCTION            0 (0 positional, 0 keyword pair)
             24 POP_TOP
             25 LOAD_CONST               0 (None)
             28 RETURN_VALUE

<<FUNCTION: KNOCK>OPENDOOR()
  5           0 LOAD_GLOBAL              0 (print)
              3 LOAD_CONST               1 ('Opened!\n')
              6 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
              9 POP_TOP

  6          10 LOAD_GLOBAL              0 (print)
             13 LOAD_CONST               2 ('Opened, again!\n')
             16 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             19 POP_TOP
             20 LOAD_CONST               0 (None)
             23 RETURN_VALUE

<<FUNCTION: KNOCK>CONSTS
0 None
1 <code object opendoor at 0x7f3e3124a150, file "main.py", line 4>
2 knock.<locals>.opendoor
3 0

代码中运用到了Python中的反汇编库dis,而使用dis作用到函数的代码储存模块knock.__code__ , 可以输出人类可读的反汇编代码。

为了更加清楚地了解knock.__code__的构造,我们可以使用Python的dir函数查看其具体的成员变量

print(dir(knock.__code__))
#>>['__class__', '__delattr__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__le__', '__lt__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', 'co_argcount', 'co_cellvars', 'co_code', 'co_consts', 'co_filename', 'co_firstlineno', 'co_flags', 'co_freevars', 'co_kwonlyargcount', 'co_lnotab', 'co_name', 'co_names', 'co_nlocals', 'co_stacksize', 'co_varnames']

而我们可以在Python的安装目录(本机/anaconda3/envs/default/include/python3.6m)的code.h文件中,可以看到这些量的具体定义——

typedef struct {
    PyObject_HEAD
    int co_argcount;		/* #arguments, except *args */
    int co_kwonlyargcount;	/* #keyword only arguments */
    int co_nlocals;		/* #local variables */
    int co_stacksize;		/* #entries needed for evaluation stack */
    int co_flags;		/* CO_..., see below */
    int co_firstlineno;   /* first source line number */
    PyObject *co_code;		/* instruction opcodes */
    PyObject *co_consts;	/* list (constants used) */
    PyObject *co_names;		/* list of strings (names used) */
    PyObject *co_varnames;	/* tuple of strings (local variable names) */
    PyObject *co_freevars;	/* tuple of strings (free variable names) */
    PyObject *co_cellvars;      /* tuple of strings (cell variable names) */
    /* The rest aren't used in either hash or comparisons, except for co_name,
       used in both. This is done to preserve the name and line number
       for tracebacks and debuggers; otherwise, constant de-duplication
       would collapse identical functions/lambdas defined on different lines.
    */
    unsigned char *co_cell2arg; /* Maps cell vars which are arguments. */
    PyObject *co_filename;	/* unicode (where it was loaded from) */
    PyObject *co_name;		/* unicode (name, for reference) */
    PyObject *co_lnotab;	/* string (encoding addr<->lineno mapping) See
				   Objects/lnotab_notes.txt for details. */
    void *co_zombieframe;     /* for optimization only (see frameobject.c) */
    PyObject *co_weakreflist;   /* to support weakrefs to code objects */
    /* Scratch space for extra data relating to the code object.
       Type is a void* to keep the format private in codeobject.c to force
       people to go through the proper APIs. */
    void *co_extra;
} PyCodeObject;

其中,co_const表示了函数中定义的常量,而co_code表示函数的代码。这时,我们就能明白 Test Driven Development (TDD) 中的代码究竟在干什么了——

  • 输出了knock函数的反汇编码
  • 输出了knock函数的常量定义
  • 发现第一个常量是一个子函数OpenDoor,进而输出其反汇编代码

Test Driven Development (TDD)  中输出的代码是如下knock()函数的反汇编代码(实际上真实的knock()函数肯定会更加复杂)。

def knock():
    def opendoor():
        print("Opened!\n")

    lineCount=0

    opendoor()

对照反汇编理解Python机器代码的规则——

<<FUNCTION: KNOCK()
  4           0 LOAD_CONST               1 (<code object opendoor at 0x7f275adb7150, file "main.py", line 4>)
              3 LOAD_CONST               2 ('knock.<locals>.opendoor')
              6 MAKE_FUNCTION            0
              9 STORE_FAST               0 (opendoor)

  7          12 LOAD_CONST               3 (0)
             15 STORE_FAST               1 (lineCount)

  9          18 LOAD_FAST                0 (opendoor)
             21 CALL_FUNCTION            0 (0 positional, 0 keyword pair)
             24 POP_TOP
             25 LOAD_CONST               0 (None)
             28 RETURN_VALUE

<<FUNCTION: KNOCK>OPENDOOR()
  5           0 LOAD_GLOBAL              0 (print)
              3 LOAD_CONST               1 ('Opened!\n')
              6 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
              9 POP_TOP
             10 LOAD_CONST               0 (None)
             13 RETURN_VALUE

<<FUNCTION: KNOCK>CONSTS
(None, <code object opendoor at 0x7f275adb7150, file "main.py", line 4>, 'knock.<locals>.opendoor', 0)

基本上就很容易理解了,唯一可能有点晕的是POP_TOP指令,出现在所有函数调用之后,个人猜测适用于处理函数返回值,只是本题中所有返回值POP出来都没有使用而已。

了解了Python机器代码的规则,我们就可以看真正的knock函数怎么写的了:一下输出源代码程序都是基于如下程序改动的,之后就不会再放了

import dis;
print("\n<<FUNCTION: KNOCK()");
dis.dis(knock.__code__);
print("\n<<FUNCTION: KNOCK>OPENDOOR()");
dis.dis(knock.__code__.co_consts[1]);
print("\n<<FUNCTION: KNOCK>LineCount()");
dis.dis(knock.__code__.co_consts[3]);
print("\n<<FUNCTION: KNOCK>deliverLine()");
dis.dis(knock.__code__.co_consts[5]);
print("\n<<FUNCTION: KNOCK>CONSTS");
for i,w in enumerate(knock.__code__.co_consts):
    print(i,w)

整体输出由于太长,放在了文章末尾。不过注意的是,这一次,不只有Opendoor是子函数,还有一个LineCount()和deliverLine()子函数。

knock函数反汇编的结果中,首先注意到有如下几行

 27          48 LOAD_FAST                0 (arg)
             51 LOAD_GLOBAL              0 (knock)
             54 COMPARE_OP               2 (==)
             57 POP_JUMP_IF_FALSE       84

 28          60 LOAD_GLOBAL              1 (print)
             63 LOAD_CONST               7 ('"Knock knock."')
             66 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             69 POP_TOP

 29          70 LOAD_GLOBAL              1 (print)
             73 LOAD_CONST               8 ("Who's there?")
             76 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             79 POP_TOP

 30          80 LOAD_DEREF               0 (deliverLine)
             83 RETURN_VALUE
        >>   84 LOAD_CONST               0 (None)
             87 RETURN_VALUE

其中,将arg和全局变量knock进行了比较,WTF,全局变量knock不是函数自身吗?那是不是我们应该调用knock(knock)?

knock(knock)
#>>"Knock knock."
#>>Who's there?

程序的输出确实变了!但是我们没有利用到其他任何的子程序啊!仔细重读Knock()函数,两次CALL_FUNCTION操作都制定了调用系统print函数,因此除非修改print函数,否则玩不出什么奇怪的花样。那么另外两个函数是怎么被调用的呢?

我尝试去搞懂Knock函数里面唯一一个自己无法理解的指令STORE_DEREF,在StackOverFlow相关问题的引导下,豁然开朗!看下面的程序

def outer():
    var = 1

    def inner():
        return var

    return inner

其反汇编代码如下,恰好用到了STORE_DEREF,而上面这个程序的结构,恰好就和knock函数相似,其返回值是一个可调用的程序!

  4           0 LOAD_CONST               1 (1)
              3 STORE_DEREF              0 (var)

  6           6 LOAD_CLOSURE             0 (var)
              9 BUILD_TUPLE              1
             12 LOAD_CONST               2 (<code object inner at 0x7ff8a7f49150, file "main.py", line 6>)
             15 LOAD_CONST               3 ('outer.<locals>.inner')
             18 MAKE_CLOSURE             0
             21 STORE_FAST               0 (inner)

  9          24 LOAD_FAST                0 (inner)
             27 RETURN_VALUE

knock(knock)返回了一个deliverLine函数闭包,而deliverLine函数定义如下

<<FUNCTION: KNOCK>deliverLine()
 24           0 LOAD_DEREF               1 (lineCount)
              3 CALL_FUNCTION            0 (0 positional, 0 keyword pair)
              6 LOAD_CONST               1 (2)
              9 COMPARE_OP               2 (==)
             12 POP_JUMP_IF_FALSE       25
             15 LOAD_DEREF               2 (openDoor)
             18 CALL_FUNCTION            0 (0 positional, 0 keyword pair)
             21 POP_TOP
             22 JUMP_FORWARD             0 (to 25)

 25     >>   25 LOAD_DEREF               0 (deliverLine)
             28 RETURN_VALUE

这个函数最后返回了自身的一个闭包,也就是说返回值又是可调用的。

每一次调用,函数调用都会增加一个变量varLineCount的值,当变量的值分别为1和2时,输出不同的内容,当变量的值为2时,门被打开了。

<<FUNCTION: KNOCK>LineCount()
 15           0 LOAD_GLOBAL              0 (lineCountVar)
              3 LOAD_CONST               1 (1)
              6 INPLACE_ADD
              7 STORE_GLOBAL             0 (lineCountVar)

 16          10 LOAD_GLOBAL              0 (lineCountVar)
             13 LOAD_CONST               1 (1)
             16 COMPARE_OP               2 (==)
             19 POP_JUMP_IF_FALSE       45

 17          22 LOAD_GLOBAL              1 (print)
             25 LOAD_CONST               2 ('"Harry."')
             28 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             31 POP_TOP

 18          32 LOAD_GLOBAL              1 (print)
             35 LOAD_CONST               3 ('Harry who?')
             38 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             41 POP_TOP
             42 JUMP_FORWARD            25 (to 70)

 19     >>   45 LOAD_GLOBAL              0 (lineCountVar)
             48 LOAD_CONST               4 (2)
             51 COMPARE_OP               2 (==)
             54 POP_JUMP_IF_FALSE       70

 20          57 LOAD_GLOBAL              1 (print)
             60 LOAD_CONST               5 ('"Harry up and open the door, it\'s cold out here!"')
             63 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             66 POP_TOP
             67 JUMP_FORWARD             0 (to 70)

 21     >>   70 LOAD_GLOBAL              0 (lineCountVar)
             73 RETURN_VALUE

最终答案应该是

knock(knock)()()

顺便说一句,Python版本现在有一些问题,提交了会显示错误,将该答案输出到JavaScript版本的题目中即可。

完整反汇编代码

<<FUNCTION: KNOCK()
  5           0 LOAD_CONST               1 (<code object openDoor at 0x7fb0b3296300, file "/home/codewarrior/setup.py", line 5>)
              3 LOAD_CONST               2 ('knock.<locals>.openDoor')
              6 MAKE_FUNCTION            0
              9 STORE_DEREF              2 (openDoor)

 13          12 LOAD_CONST               3 (<code object lineCount at 0x7fb0b3296390, file "/home/codewarrior/setup.py", line 13>)
             15 LOAD_CONST               4 ('knock.<locals>.lineCount')
             18 MAKE_FUNCTION            0
             21 STORE_DEREF              1 (lineCount)

 23          24 LOAD_CLOSURE             0 (deliverLine)
             27 LOAD_CLOSURE             1 (lineCount)
             30 LOAD_CLOSURE             2 (openDoor)
             33 BUILD_TUPLE              3
             36 LOAD_CONST               5 (<code object deliverLine at 0x7fb0b3296420, file "/home/codewarrior/setup.py", line 23>)
             39 LOAD_CONST               6 ('knock.<locals>.deliverLine')
             42 MAKE_CLOSURE             0
             45 STORE_DEREF              0 (deliverLine)

 27          48 LOAD_FAST                0 (arg)
             51 LOAD_GLOBAL              0 (knock)
             54 COMPARE_OP               2 (==)
             57 POP_JUMP_IF_FALSE       84

 28          60 LOAD_GLOBAL              1 (print)
             63 LOAD_CONST               7 ('"Knock knock."')
             66 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             69 POP_TOP

 29          70 LOAD_GLOBAL              1 (print)
             73 LOAD_CONST               8 ("Who's there?")
             76 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             79 POP_TOP

 30          80 LOAD_DEREF               0 (deliverLine)
             83 RETURN_VALUE
        >>   84 LOAD_CONST               0 (None)
             87 RETURN_VALUE

<<FUNCTION: KNOCK>OPENDOOR()
  7           0 LOAD_CONST               1 ('')
              3 LOAD_ATTR                0 (join)
              6 LOAD_CONST               2 (<code object <genexpr> at 0x7fb0b3296270, file "/home/codewarrior/setup.py", line 7>)
              9 LOAD_CONST               3 ('knock.<locals>.openDoor.<locals>.<genexpr>')
             12 MAKE_FUNCTION            0
             15 LOAD_GLOBAL              1 (range)
             18 LOAD_CONST               4 (16)
             21 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             24 GET_ITER
             25 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             28 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             31 STORE_GLOBAL             2 (success)

  8          34 LOAD_CONST               5 (True)
             37 LOAD_GLOBAL              3 (globals)
             40 CALL_FUNCTION            0 (0 positional, 0 keyword pair)
             43 LOAD_GLOBAL              2 (success)
             46 STORE_SUBSCR

  9          47 LOAD_GLOBAL              4 (print)
             50 LOAD_CONST               1 ('')
             53 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             56 POP_TOP

 10          57 LOAD_GLOBAL              4 (print)
             60 LOAD_CONST               6 ('Groan. That\'s the worst "knock knock" joke I\'ve ever heard.')
             63 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             66 POP_TOP

 11          67 LOAD_GLOBAL              4 (print)
             70 LOAD_CONST               7 ("Oh well, I suppose you'd better come in.")
             73 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             76 POP_TOP

 12          77 LOAD_GLOBAL              4 (print)
             80 LOAD_CONST               8 ('Welcome to the annual meeting of the Knock Knock Joke Society.')
             83 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             86 POP_TOP
             87 LOAD_CONST               0 (None)
             90 RETURN_VALUE

<<FUNCTION: KNOCK>LineCount()
 15           0 LOAD_GLOBAL              0 (lineCountVar)
              3 LOAD_CONST               1 (1)
              6 INPLACE_ADD
              7 STORE_GLOBAL             0 (lineCountVar)

 16          10 LOAD_GLOBAL              0 (lineCountVar)
             13 LOAD_CONST               1 (1)
             16 COMPARE_OP               2 (==)
             19 POP_JUMP_IF_FALSE       45

 17          22 LOAD_GLOBAL              1 (print)
             25 LOAD_CONST               2 ('"Harry."')
             28 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             31 POP_TOP

 18          32 LOAD_GLOBAL              1 (print)
             35 LOAD_CONST               3 ('Harry who?')
             38 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             41 POP_TOP
             42 JUMP_FORWARD            25 (to 70)

 19     >>   45 LOAD_GLOBAL              0 (lineCountVar)
             48 LOAD_CONST               4 (2)
             51 COMPARE_OP               2 (==)
             54 POP_JUMP_IF_FALSE       70

 20          57 LOAD_GLOBAL              1 (print)
             60 LOAD_CONST               5 ('"Harry up and open the door, it\'s cold out here!"')
             63 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             66 POP_TOP
             67 JUMP_FORWARD             0 (to 70)

 21     >>   70 LOAD_GLOBAL              0 (lineCountVar)
             73 RETURN_VALUE

<<FUNCTION: KNOCK>deliverLine()
 24           0 LOAD_DEREF               1 (lineCount)
              3 CALL_FUNCTION            0 (0 positional, 0 keyword pair)
              6 LOAD_CONST               1 (2)
              9 COMPARE_OP               2 (==)
             12 POP_JUMP_IF_FALSE       25
             15 LOAD_DEREF               2 (openDoor)
             18 CALL_FUNCTION            0 (0 positional, 0 keyword pair)
             21 POP_TOP
             22 JUMP_FORWARD             0 (to 25)

 25     >>   25 LOAD_DEREF               0 (deliverLine)
             28 RETURN_VALUE

<<FUNCTION: KNOCK>CONSTS
0 None
1 <code object openDoor at 0x7fb0b3296300, file "/home/codewarrior/setup.py", line 5>
2 knock.<locals>.openDoor
3 <code object lineCount at 0x7fb0b3296390, file "/home/codewarrior/setup.py", line 13>
4 knock.<locals>.lineCount
5 <code object deliverLine at 0x7fb0b3296420, file "/home/codewarrior/setup.py", line 23>
6 knock.<locals>.deliverLine
7 "Knock knock."
8 Who's there?

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据