分类：CodeWars

Codewars C++练习：Insane Coloured Triangles

题目

题目链接：

This Kata is an insane step-up from Avanta’s Kata, so I recommend to solve it first before trying this one.

A coloured triangle is created from a row of colours, each of which is red, green or blue. Successive rows, each containing one fewer colour than the last, are generated by considering the two touching colours in the previous row. If these colours are identical, the same colour is used in the new row. If they are different, the missing colour is used in the new row. This is continued until the final row, with only a single colour, is generated.

For example, different possibilities are:

1
2
Colour here:            G G        B G        R G        B R
Becomes colour here:     G          R          B          G

With a bigger example:

1
2
3
4
5
6
7
8
R R G B R G B B
R B R G B R B
  G G B R G G
   G R G B G
    B B R R
     B G R
      R B
       G

You will be given the first row of the triangle as a string and its your job to return the final colour which would appear in the bottom row as a string. In the case of the example above, you would be given ‘RRGBRGBB’, and you should return ‘G’.

1 <= length(row) <= 10 ** 5

题解

核心规律

找到所有递推方程的共性：“所有递推小三角形，都满足RGB的个数在模3意义下相同”。

1
2
Colour here:            G G        B G        R G        B R
Becomes colour here:     G          R          B          G

单独考虑任意一个大三角形的第一行和第二行，倘若我们知道了第一行RGB分别有多少个，我们也可以通过“RGB的个数在模3意义下相同”这个性质，计算出第二行分别有多少个RGB。这个是一个很有启发作用的思路，虽然这个思路无法解决更多的行，但是从该思路出发，我们可以得到如下的算法——

用三元组S_{x,y}=(r,g,b)表示一个位置的颜色。一方面，我们定义映射f来求任意三元组对应的颜色.

f = \{(r,g,b) r,g,b \in \mathbb{Z}\} \rightarrow \{\boldsymbol{R},\boldsymbol{G},\boldsymbol{B}\}

另一方面，不同的三元组有很多，但是颜色的种类总共就3种，所以我们需要对于该三元组建立若干“等价类”，规则如下:

  1. (1,0,0)\rightarrow \boldsymbol{R}，(0,1,0) \rightarrow \boldsymbol{G}，(0,0,1)\rightarrow \boldsymbol{B}
  2. f((r,g,b)) = f((r \bmod 3, g \bmod 3, b \bmod 3))
  3. f((r,g,b)) = f((r-v,g-v,b-v))

规则1定义了三元组到颜色的映射，而规则2和规则3将所有三元组分为了3类。

仔细理解一下这三条规则，我们很容易求出一个三元组对应的颜色，例如f((123,123,400)) = f((0,0,277))=f((0,0,1)) \rightarrow \boldsymbol{B}。当然，并不是所有三元组都可以通过这种方法计算出值，倘若一个三元组无法求出值，如(0,0,0)，那么在本题中，它就是不合法的。

但看三元组的定义或许会莫名其妙，但是我们可以将本题的规则引入，得到一个暴力的迭代方式——

对于整个三角形的第一行，可以直接按照定义式生成：

S_{0,y} = ([row[0]==\boldsymbol{R}],[row[0]==\boldsymbol{G}],[row[0]==\boldsymbol{B}])

例如，一个\boldsymbol{G}颜色可以用三元组(0,1,0)表示。

对于后续的行，我们可以按照递推式生成——

S_{x,y} = -S_{x-1,y} - S_{x-1,y+1}

例如，倘若S_{x-1,y} = (1,0,0) \rightarrow \boldsymbol{R}，S_{x-1,y+1} = (0,1,0) \rightarrow \boldsymbol{G}，那么S_{x,y} = (-1,-1,0) \equiv (0,0,1) \rightarrow \boldsymbol{B}

读者到这里应该就可以发现，实际上我们的三元组完全是为了反映递推方程中的等价信息而设计的。这里，我们已经可以设计出时间复杂度O(N^2)的算法了。

force.cpp
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
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
#include<iostream>
using namespace std;
#define MAXN 1010
 
char buf[MAXN];
 
class status {
private:
int v[3];
public:
status() {
v[0] = v[1] = v[2] = 0;
}
status(int x,int y,int z) {
v[0] = x%3;
v[1] = y%3;
v[2] = z%3;
}
static status createFromChar(char c) {
status num;
switch (c) {
case 'R':num.v[0] = 1;break;
case 'G':num.v[1] = 1;break;
case 'B':num.v[2] = 1;break;
}
return num;
}
char getChar() {
v[1] -= v[0];
v[2] -= v[0];
v[0] = 0;
v[1] = (v[1]%3+3)%3;
v[2] = (v[2]%3+3)%3;
if (v[1] == 2 && v[2] == 2)
return 'R';
if (v[1] == 1 && v[2] == 0)
return 'G';
if (v[1] == 0 && v[2] == 1)
return 'B';
return '?';
}
void show() {
printf("[% 3d % 3d % 3d]\t",v[0],v[1],v[2]);
}
friend status operator + (const status& a,const status& b);
friend status operator - (const status& a);
};
status operator + (const status& a,const status& b) {
return status(a.v[0]+b.v[0],a.v[1]+b.v[1],a.v[2]+b.v[2]);
}
status operator - (const status& a) {
return status(-a.v[0],-a.v[1],-a.v[2]);
}
 
status mat[MAXN][MAXN];
 
 
int main() {
freopen("input.txt","r",stdin);
scanf("%s\n",buf);
int n = (int)strlen(buf);
for (int i=0;i<n;i++) {
mat[0][i] = status::createFromChar(buf[i]);
}
for (int i=1;i<n;i++) {
for (int j=0;j<n-i;j++) {
mat[i][j] = -(mat[i-1][j]+mat[i-1][j+1]);
}
}
for (int i=0;i<n;i++) {
for (int j=0;j<n-i;j++) {
mat[i][j].show();
}
printf("\n");
}
printf("%c\n",mat[n-1][0].getChar());
}

既然我们已经借助三元组的加减运算，定义出了一个新的数域来解决这个问题，并且该数域很容易证明满足封闭性。反映到代码上，就是我们成功定义出了一个支持加操作和相反数操作的“数”status，那么我们完全可以不再考虑status类的实现细节。

所有细节略去之后，我们的代码实际上就是上面的65-69这5行。有一些编程基础的读者已经发现这里非常像一个组合数的递推方程（或者说是杨辉三角形的生成代码）。

对于一个稍微简单一些的例子，我们对于第一行的所有值赋予一个标号，看看最终结果长什么样的：

1
2
3
4
5
a          b          c          d          e
-a-b       -b-c       -c-d       -d-e
a+2b+c     b+2c+d     c+2d+e
-a-3b-3c-d -b-3c-3d-e
a+4b+6c+4d+e

上表中，a,b,c,d,e分别是我们读入的第一行的三元组表示，而最后一行就是答案！因此，假设读入三元组列表为s_i那么答案就是

ans =(-1)^{n-1}\sum_{i=0}^{n-1} C(n-1,i) \cdot S_i

最后一步比较tricky，需要一些较深的数论知识，最后一步我们需要求出C(n-1,i)在模3意义下的值。这一步有两个做法——

  • 有现成的Lucas定理专门用来计算这个问题。
  • 可以手工迭代求出C(n-1,0),\dots,C(n-1,n-1)的值，可以用递推式C(n-1,i+1) = C(n-1,i) \cdot (i+1) / (n-1-i)求，这其中又有两个要点
    • 在迭代的乘法需要将所有的因子3提出来
    • 在迭代的除法中需要计算除数在模3同余系下的逆元

在标程中使用了第二种做法。

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
#include<iostream>
using namespace std;
#define MAXN 101000
 
char buf[MAXN];
 
class status {
private:
int v[3];
public:
status() {
v[0] = v[1] = v[2] = 0;
}
status(int x,int y,int z) {
v[0] = x%3;
v[1] = y%3;
v[2] = z%3;
}
static status createFromChar(char c) {
status num;
switch (c) {
case 'R':num.v[0] = 1;break;
case 'G':num.v[1] = 1;break;
case 'B':num.v[2] = 1;break;
}
return num;
}
char getChar() {
v[1] -= v[0];
v[2] -= v[0];
v[0] = 0;
v[1] = (v[1]%3+3)%3;
v[2] = (v[2]%3+3)%3;
if (v[1] == 2 && v[2] == 2)
return 'R';
if (v[1] == 1 && v[2] == 0)
return 'G';
if (v[1] == 0 && v[2] == 1)
return 'B';
return '?';
}
void show() {
printf("[% 3d % 3d % 3d]\t",v[0],v[1],v[2]);
}
friend status operator + (const status& a,const status& b);
friend status operator - (const status& a);
friend status operator * (const status& a,int k);
};
status operator + (const status& a,const status& b) {
return status(a.v[0]+b.v[0],a.v[1]+b.v[1],a.v[2]+b.v[2]);
}
status operator - (const status& a) {
return status(-a.v[0],-a.v[1],-a.v[2]);
}
status operator * (const status& a,int k) {
return status(a.v[0]*k,a.v[1]*k,a.v[2]*k);
}
 
/*
int pow_mod(int x,int y,int mod) {
int ret = x%mod;
while (y) {
if (y&1)
ret = ret*x%mod;
x = x*x%mod;
y>>=1;
}
return ret;
}*/
 
char triangle(const string &buf)
{
int n = buf.length();
status res;
int k=1,b=0;//k*3^b
for (int i=0;i<n;i++) {
status s = status::createFromChar(buf[i]);
res = res + s * (b?0:k);
if (i == n-1)
break;
int x = i+1;
while (x%3 == 0)
x /= 3,b--;
k = k*x%3;
//k = k*pow_mod(x,1);
x = (n-1)-i;
while (x%3 == 0)
x /= 3,b++;
k = k*x%3;
}
if (n%2 == 0)
res = -res;
return res.getChar();
}

 

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?

 

Codewars Java练习：Maximum subarray sum

题目

The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:

1
2
3
Max.sequence(<span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[]{-<span class="hljs-number">2</span>, <span class="hljs-number">1</span>, -<span class="hljs-number">3</span>, <span class="hljs-number">4</span>, -<span class="hljs-number">1</span>, <span class="hljs-number">2</span>, <span class="hljs-number">1</span>, -<span class="hljs-number">5</span>, <span class="hljs-number">4</span>});
<span class="hljs-comment">// should be 6: {4, -1, 2, 1}</span>
 

Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.

Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.

题解

哇，终于做到动态规划了耶，将数组A本身转化为前缀和数组B，那么本题就是要求在前缀和数组B上找一前一后两个数，使得他们的差尽量大。

当然，这样的做法较为繁琐，可以一个for语句解决的事情就不要用多个，下面是我的代码——

其中，sum储存的是在某个位置结束的数组A的子序列最大字段和，为什么有这样的更新方法读者自己试一组样例就知道了。

Java
1
2
3
4
5
6
7
8
9
10
public class Max {
  public static int sequence(int[] arr) {
    int sum = 0, ans = 0;
    for (int w : arr) {
      sum = Math.max(0,sum+w);
      ans = Math.max(ans,sum);
    }
    return ans;
  }
}

Codewars Java练习：Next bigger number with the same digits

题目

You have to create a function that takes a positive integer number and returns the next bigger number formed by the same digits:

1
2
3
4
Kata.nextBiggerNumber(<span class="hljs-number">12</span>)==<span class="hljs-number">21</span>
Kata.nextBiggerNumber(<span class="hljs-number">513</span>)==<span class="hljs-number">531</span>
Kata.nextBiggerNumber(<span class="hljs-number">2017</span>)==<span class="hljs-number">2071</span>
 

If no bigger number can be composed using those digits, return -1:

1
2
3
4
Kata.nextBiggerNumber(<span class="hljs-number">9</span>)==-<span class="hljs-number">1</span>
Kata.nextBiggerNumber(<span class="hljs-number">111</span>)==-<span class="hljs-number">1</span>
Kata.nextBiggerNumber(<span class="hljs-number">531</span>)==-<span class="hljs-number">1</span>
 

题解

题意大概是找到一个数组成数字相同的，大一点的那个数。

实际上只要使用程序将我们解决这道题的思路翻译一遍就行了，先找出最低的可以变大的位（这个位的更低位有一个尽量小，但是比他大的数），交换后，将比他低的位从小到大排序。

Java
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
import java.util.*;
 
public class Kata
{
    public static long nextBiggerNumber(long n)
    {
      char[] s = Long.valueOf(n).toString().toCharArray();
      boolean flag = false;
      for (int i=s.length-1;i>=0;i--) {
        int pos = -1;
        for (int j=s.length-1;j>i;j--) {
          if (s[j] > s[i] && (pos == -1 || s[j] < s[pos])) {
            pos = j;
          }
        }
        if (pos != -1) {
          char t = s[pos];
          s[pos] = s[i];
          s[i] = t;
          Arrays.sort(s,i+1,s.length);
          flag = true;
          break;
        }
      }
      if (flag == false)
        return -1;
      else
        return Long.valueOf(new String(s)).longValue();
    }
}

 

Codewars Java练习：Perimeter of squares in a rectangle

题目

The drawing shows 6 squares the sides of which have a length of 1, 1, 2, 3, 5, 8. It’s easy to see that the sum of the perimeters of these squares is : 4 * (1 + 1 + 2 + 3 + 5 + 8) = 4 * 20 = 80

Could you give the sum of the perimeters of all the squares in a rectangle when there are n + 1 squares disposed in the same manner as in the drawing:

alternative text

#Hint: See Fibonacci sequence

#Ref: http://oeis.org/A000045

The function perimeter has for parameter n where n + 1 is the number of squares (they are numbered from 0 to n) and returns the total perimeter of all the squares.

1
2
perimeter(5)  should return 80
perimeter(7)  should return 216

题解

题目大意就是求斐波那契前缀和第N项的值的四倍。斐波那契数列本身有很好的性质，我们可以考虑如何变幻前缀和的项，而保证和不变

(1)   \begin{align*} &1+1+2+3+5+8+13+...+fib(n-1)+fib(n) \\ =&2+5+13+..+fib(n-2)+fib(n+1) \\ =&(-1)+1+2+5+13+...+fib(n-2)+fib(n+1) \\ =&(-1)+fib(n)+fib(n+1) =&fib(n+2)-1 \end{align*}

 

上述推导，表示了fibonacci数列的前缀和恰好是一个fibonacci数列-1的数列。

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.math.BigInteger;
 
public class SumFct {
public static BigInteger perimeter(BigInteger n) {
    int _n = n.intValue();
    BigInteger x = BigInteger.valueOf(1);
    BigInteger y = BigInteger.valueOf(2);
    BigInteger _x = null, _y = null;
    for (int i=0;i<_n;i++) {
      _x = x;
      _y = y;
      y = _x.add(_y);
      x = _y;
    }
    return y.subtract(BigInteger.valueOf(1)).multiply(BigInteger.valueOf(4));
}
}

 

Codewars Java练习：Number of trailing zeros of N!

题目

Write a program that will calculate the number of trailing zeros in a factorial of a given number.

N! = 1 * 2 * 3 * ... * N

Be careful 1000! has 2568 digits…

For more info, see: http://mathworld.wolfram.com/Factorial.html

Examples

1
2
3
4
5
6
zeros(6) = 1
# 6! = 1 * 2 * 3 * 4 * 5 * 6 = 720 --> 1 trailing zero
 
zeros(12) = 2
# 12! = 479001600 --> 2 trailing zeros
 

Hint: You’re not meant to calculate the factorial. Find another way to find the number of zeros.

题解

这也是5级题？？？升级好慢==

统计1-n中5出现了多少次就好了。

Java
1
2
3
4
5
6
7
8
9
10
public class Solution {
  public static int zeros(int n) {
      int result = 0;
      while (n!=0) {
        result += n/5;
        n /= 5;
      }
      return result;
  }
}

 

 

Codewars Java练习：Gap in Primes

题目

The prime numbers are not regularly spaced. For example from 2 to 3 the gap is 1. From 3 to 5 the gap is 2. From 7 to 11 it is 4. Between 2 and 50 we have the following pairs of 2-gaps primes: 3-5, 5-7, 11-13, 17-19, 29-31, 41-43

A prime gap of length n is a run of n-1 consecutive composite numbers between two successive primes (see: http://mathworld.wolfram.com/PrimeGaps.html).

We will write a function gap with parameters:

g (integer >= 2) which indicates the gap we are looking for

m (integer > 2) which gives the start of the search (m inclusive)

n (integer >= m) which gives the end of the search (n inclusive)

In the example above gap(2, 3, 50) will return [3, 5] or (3, 5) or {3, 5} which is the first pair between 3 and 50 with a 2-gap.

So this function should return the first pair of two prime numbers spaced with a gap of g between the limits m, n if these numbers exist otherwise nil or null or None or Nothing (depending on the language).

In C++ return in such a case {0, 0}. In F# return [||]. In Kotlin return []

#Examples: gap(2, 5, 7) --> [5, 7] or (5, 7) or {5, 7}

gap(2, 5, 5) --> nil. In C++ {0, 0}. In F# [||]. In Kotlin return[]`

gap(4, 130, 200) --> [163, 167] or (163, 167) or {163, 167}

([193, 197] is also such a 4-gap primes between 130 and 200 but it’s not the first pair)

gap(6,100,110) --> nil or {0, 0} : between 100 and 110 we have 101, 103, 107, 109 but 101-107is not a 6-gap because there is 103in between and 103-109is not a 6-gap because there is 107in between.

题解

看讨论区说这道题不能用for循环，还在想是不是MillerRabin素性判定过不了==，结果标准解法不就是一个for循环吗_(:з」∠)_

Java
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
import java.util.*;
import java.io.*;
 
class GapInPrimes {
static long pow_mod(long x,long y,long mod) {
long res = 1;
while (y!=0) {
if ((y&1) == 1)
res = res * x % mod;
x = x*x%mod;
y >>= 1;
}
return res;
}
static boolean Miller_Rabbin(long n,int a) {
if ((n%a) == 0)return false;
int r=0;
long d=n-1;
while ((d&1) == 0) {
d>>=1;
r++;
}
long k=pow_mod(a,d,n);
if (k==1)return true;
for (int i=0;i<r;i++) {
if (k==n-1)return true;
k=k*k%n;
}
return false;
}
static int[] prime_test = {2,3,5,7,11,13,17,23,27,31,37};
static boolean isPrime(long x) {
if (x<2)return false;
for (int w:prime_test) {
if (!Miller_Rabbin(x,w)) {
return false;
}
}
return true;
}
 
public static long[] gap(int g, long m, long n) {
long last = -12345;
for (long i=m;i<n;i++) {
if (isPrime(i)) {
if (i - last == g) {
long []result = new long[2];
result[0] = last;
result[1] = i;
return result;
}
last = i;
}
}
return null;
}
}

 

 

Codewars Java练习：Decode the Morse code

题目

Part of Series 1/3
This kata is part of a series on the Morse code. After you solve this kata, you may move to the next one.

In this kata you have to write a simple Morse code decoder. While the Morse code is now mostly superceded by voice and digital data communication channels, it still has its use in some applications around the world.

The Morse code encodes every character as a sequence of “dots” and “dashes”. For example, the letter A is coded as ·−, letter Q is coded as −−·−, and digit 1 is coded as ·−−−−. The Morse code is case-insensitive, traditionally capital letters are used. When the message is written in Morse code, a single space is used to separate the character codes and 3 spaces are used to separate words. For example, the message HEY JUDE in Morse code is ···· · −·−− ·−−− ··− −·· ·.

NOTE: Extra spaces before or after the code have no meaning and should be ignored.

In addition to letters, digits and some punctuation, there are some special service codes, the most notorious of those is the international distress signal SOS (that was first issued by Titanic), that is coded as ···−−−···. These special codes are treated as single special characters, and usually are transmitted as separate words.

Your task is to implement a function that would take the morse code as input and return a decoded human-readable string.

For example:

1
2
3
MorseCodeDecoder.decode(<span class="hljs-string">".... . -.--   .--- ..- -.. ."</span>)
<span class="hljs-comment">//should return "HEY JUDE"</span>
 

NOTE: For coding purposes you have to use ASCII characters . and -, not Unicode characters.

The Morse code table is preloaded for you as a dictionary, feel free to use it:

  • Coffeescript/C++/Go/JavaScript/PHP/Python/Ruby/TypeScript: MORSE_CODE['.--']
  • C#: MorseCode.Get(".--") (returns string)
  • Elixir: morse_codes variable
  • Haskell: morseCodes ! ".--" (Codes are in a Map String String)
  • Java: MorseCode.get(".--")
  • Kotlin: MorseCode[".--"] ?: "" or MorseCode.getOrDefault(".--", "")
  • Rust: self.morse_code

All the test strings would contain valid Morse code, so you may skip checking for errors and exceptions. In C#, tests will fail if the solution code throws an exception, please keep that in mind. This is mostly because otherwise the engine would simply ignore the tests, resulting in a “valid” solution.

Good luck!

After you complete this kata, you may try yourself at Decode the Morse code, advanced.

题解

感觉字符串首尾有一些莫名其妙的空白字符。。。需要使用String.trim()函数先去掉他们。

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class MorseCodeDecoder {
    public static String decode(String morseCode) {
      String result = new String();
 
      for (String word : morseCode.trim().split("   ")) {
        for (String w : word.trim().split(" ")) {
          //System.out.println(w+"$"+MorseCode.get(w));
          result = result.concat(MorseCode.get(w));
        }
        result = result.concat(" ");
      }
      return result.substring(0,result.length()-1);
    }
}

这个代码和标准答案基本一致。

Codewars Java练习：Counting Duplicates

题目

Count the number of Duplicates

Write a function that will return the count of distinct case-insensitive alphabetic characters and numeric digits that occur more than once in the input string. The input string can be assumed to contain only alphabets (both uppercase and lowercase) and numeric digits.

Example

“abcde” -> 0 # no characters repeats more than once
“aabbcde” -> 2 # 'a' and 'b'
“aabBcde” -> 2 # 'a' occurs twice and 'b' twice (bandB)
“indivisibility” -> 1 # 'i' occurs six times
“Indivisibilities” -> 2 # 'i' occurs seven times and 's' occurs twice
“aA11” -> 2 # 'a' and '1'
“ABBA” -> 2 # 'A' and 'B' each occur twice

题解

做了这么几道题，基本上对于Collection和Stream有了一些了解，不用每次写搜索引擎了。思路非常直接，就是先生成一个词频映射，然后对于词频映射的Value值找大于1的个数——

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.*;
import java.io.*;
import java.util.stream.*;
 
class CountingDuplicates {
  public static int duplicateCount(String text) {
  HashMap<Character,Integer> map = new HashMap<Character,Integer>();
  for (int i=0;i<text.length();i++) {
  Character c = new Character(text.charAt(i));
  Integer v = map.get(c);
  if (v == null)
  map.put(c,1);
  else
  map.put(c,v+1);
  }
  Stream<Integer> si = map.values().stream();
  return (int)si.filter(x->(x>1)).count();
  }
}

标准解法没有什么非常特别的。

Codewars Java练习：Your order, please

题目

Your task is to sort a given string. Each word in the String will contain a single number. This number is the position the word should have in the result.

Note: Numbers can be from 1 to 9. So 1 will be the first word (not 0).

If the input String is empty, return an empty String. The words in the input String will only contain valid consecutive numbers.

For an input: “is2 Thi1s T4est 3a” the function should return “Thi1s is2 3a T4est”

1
2
your_order(<span class="hljs-string">"is2 Thi1s T4est 3a"</span>)
[<span class="hljs-number">1</span>] <span class="hljs-string">"Thi1s is2 3a T4est"</span>

题解

数字的提取可以使用正则表达式(java.util.regex)完成，提取出数值之后，按照数值排序，这里需要使用自定义比较器，自定义比较器的一种做法是直接实例化Comparator接口。代码如下——

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;
import java.io.*;
import java.util.stream.*;
import java.util.regex.*;
 
class MyCmp implements Comparator<String> {
public int compare(String s1,String s2) {
Matcher m1 = Pattern.compile("\\d+").matcher(s1);
Matcher m2 = Pattern.compile("\\d+").matcher(s2);
m1.find();
m2.find();
return Integer.parseInt(m1.group()) - Integer.parseInt(m2.group());
}
}
class Order {
public static String order(String words) {
String[] sarr = words.split(" ");
Arrays.sort(sarr ,new MyCmp());
Stream<String> ss = Arrays.stream(sarr);
String res = ss.reduce((x,y)->x+" "+y).get();
System.out.println(res);
return res;
}
}

当然，如果觉得类的重载MyCmp显得有些多余，Java支持了类的匿名重载，可以将比较器的定义实现在order函数内，代码变成了——

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;
import java.io.*;
import java.util.stream.*;
import java.util.regex.*;
 
class Order {
public static String order(String words) {
String[] sarr = words.split(" ");
Arrays.sort(sarr ,new Comparator<String>() {
public int compare(String s1,String s2) {
Matcher m1 = Pattern.compile("\\d+").matcher(s1);
Matcher m2 = Pattern.compile("\\d+").matcher(s2);
m1.find();
m2.find();
return Integer.parseInt(m1.group()) - Integer.parseInt(m2.group());
}
});
Stream<String> ss = Arrays.stream(sarr);
String res = ss.reduce((x,y)->x+" "+y).get();
System.out.println(res);
return res;
}
}

在完成排序之后，将数组转换为stream，方便后续处理，stream支持reduce函数，reduce函数传入合并两项的lambda表达式，返回一个Optional<T>类，Optional<T>类实在T的基础上，增加了一个表示是否为null的指示符，在这里，我们不需要关心为null的情况，故直接使用Optional<T>.get()得到最终答案。

不过笔者确实很傻逼，别人一行能解决的事情自己写了那么久——

1
2
3
4
5
6
7
8
9
10
import java.util.Arrays;
import java.util.Comparator;
 
public class Order {
  public static String order(String words) {
    return Arrays.stream(words.split(" "))
      .sorted(Comparator.comparing(s -> Integer.valueOf(s.replaceAll("\\D", ""))))
      .reduce((a, b) -> a + " " + b).get();
  }
}