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()函数调用，运行结果如下——

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

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

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

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 按钮运行后，得到如下输出——

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
<<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函数查看其具体的成员变量

1
2
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文件中，可以看到这些量的具体定义——

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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()函数肯定会更加复杂）。

Python
1
2
3
4
5
6
7
def knock():
    def opendoor():
        print("Opened!\n")
 
    lineCount=0
 
    opendoor()

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
<<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函数怎么写的了：一下输出源代码程序都是基于如下程序改动的，之后就不会再放了

Python
1
2
3
4
5
6
7
8
9
10
11
12
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函数反汇编的结果中，首先注意到有如下几行

16
17
18
19
30          80 LOAD_DEREF               0 (deliverLine)
             83 RETURN_VALUE
        >>   84 LOAD_CONST               0 (None)
             87 RETURN_VALUE

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

Python
1
2
3
knock(knock)
#>>"Knock knock."
#>>Who's there?

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

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

Python
1
2
3
4
5
6
7
def outer():
    var = 1
 
    def inner():
        return var
 
    return inner

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

1
2
3
4
5
6
7
8
9
10
11
12
  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函数定义如下

1
2
3
4
5
6
7
8
9
10
11
12
13
<<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时，门被打开了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
<<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

最终答案应该是

1
knock(knock)()()

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

完整反汇编代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
<<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来减少垃圾评论。了解我们如何处理您的评论数据。