helloworld

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
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>

#define MAXITEMS 31
#define ALPHA 26
/*
pesudo code

repeat
for i in all strlen(A)
*/
bool hasRepeatedLetter(char A[]){
   // printf("%zd",strlen(A));
   // return true;
   int count[ALPHA]={0};
   int repeated=0;
   // printf("%s",A);
   // for(int i=0;i<strlen(A);i++){
   //    count[(int)A[i]]++;
   //    if(count[(int)A[i]]>1){
   //       repeated=1;
   //       printf("重复了");
   //       break;
   //    }
   // }
   for (int i = 0; i < strlen(A); i++) {
      // printf("%c",A[i]);
      count[(int)A[i]]++; // 将字符对应的数组元素加1
      if(count[(int)A[i]]>1){
         printf("重复");
         break;
      }
   }
   if(repeated==1){
      return true;
   }else{
      return false;
   }
}

int main(){
   char *str=malloc(sizeof(char)*MAXITEMS);
   scanf("%31s",str);
   bool value=hasRepeatedLetter(str);
   if(value){
      printf("yes");
   }else{
      printf("no");
   }
   free(str);
}

// Hints:
// You may assume that the input consists of lower case letters only.
// You may assume that the input consists of no more than 31 characters (excluding the terminating '\0').
// You can use the standard I/O library function  scanf("%31s",str) to read a word from the input.
// You may use the standard library function  strlen(char[]), defined in  <string.h>, which computes the length of a string (without counting its terminating '\0'-character).

基本素养

杨辉三角

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
'''
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
'''

lines = [[1]]
height = 10
for h in range(1, height):
    line = [1]
    pre_line = lines[-1]
    for i in range(1, h):
        line.append(pre_line[i-1] + pre_line[i])
    line.append(1)
    lines.append(line)

for item in lines:
    print(item)

组合数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
'''
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
'''

from math import comb

height = 10
lines = []
for h in range(1, height + 1):
    line = []
    for i in range(h):
        line.append(comb(h - 1, i))
    lines.append(line)

for item in lines:
    print(item)

divmod

1
2
3
4
5
6
7
8
9
def int2nbase(k,n):
    mid=[]
    while True:
        if k==0:
            break
        k,digit=divmod(k,n)
        mid.append(digit)

    return ''.join(str(x) for x in mid[::-1])

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def binary_search(array,left,right,target):
    if left>right:
        return 
    else:
        #找出每一次的中间值
        mid=left+(right-left)//2
        cnt+=1
        #搜索左边
        if target<mid
            binary_search(array,left,mid-1,target)
        #搜索右边
        elif target<mid:
            binary_search(array,mid+1,right,target)
        else:
            return cnt

cnt=0
print(binary_search([1,3,2,8,7,5,9],2,8,3))

m进制转化为n进制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"


def mbase2int(k, m):
    k = str(k)
    if len(k) == 1:
        return chars.index(k)
    else:
        return mbase2int(k[:-1], m) * m + chars.index(k[-1])


def int2nbase(k, n):
    if k < n:
        return chars[k]
    else:
        return int2nbase(k // n, n) + chars[k % n]


k, m, n = 12345, 16, 8

print(int2nbase(mbase2int(k, m), n))

简单的dfs

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
#  You can assume that i and j are both between 0 and 9 included.
#  i is the row number (indexed from top to bottom),
#  j is the column number (indexed from left to right)
#  of the displayed grid.


from random import seed, randrange


def area(for_seed, sparsity, i, j):
    '''
    >>> area(0, 1, 5, 5)
    The grid is:
    1 1 1 1 1 1 1 1 1 1
    1 1 1 1 1 1 1 1 1 1
    1 1 1 1 1 1 1 1 1 1
    1 1 1 1 1 1 1 1 1 1
    1 1 1 1 1 1 1 1 1 1
    1 1 1 1 1 1 1 1 1 1
    1 1 1 1 1 1 1 1 1 1
    1 1 1 1 1 1 1 1 1 1
    1 1 1 1 1 1 1 1 1 1
    1 1 1 1 1 1 1 1 1 1
    The area of the largest empty region of the grid
    containing the point (5, 5) is: 0
    >>> area(0, 1000, 5, 5)
    The grid is:
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    The area of the largest empty region of the grid
    containing the point (5, 5) is: 100
    >>> area(0, 3, 6, 2)
    The grid is:
    0 0 1 0 0 0 0 0 0 0
    0 1 0 1 0 1 1 0 0 0
    0 0 1 0 1 0 1 0 0 0
    0 1 0 0 0 0 0 1 0 0
    0 0 0 1 0 1 1 0 0 0
    0 0 1 0 0 0 1 0 0 0
    1 1 0 1 1 1 0 0 1 1
    0 0 0 1 0 0 0 0 1 0
    0 0 1 0 0 0 0 0 1 0
    0 0 0 1 0 1 1 1 1 0
    The area of the largest empty region of the grid
    containing the point (6, 2) is: 9
    >>> area(0, 2, 9, 5)
    The grid is:
    0 0 1 0 0 0 0 0 0 1
    1 0 1 1 0 1 0 1 1 0
    0 1 0 0 0 1 0 0 0 1
    1 1 0 1 0 0 1 0 1 1
    1 1 1 0 1 1 0 0 1 0
    0 1 0 1 0 0 1 0 0 1
    0 1 1 1 1 0 0 1 1 1
    1 1 1 0 0 1 1 0 0 0
    0 0 1 0 1 0 0 1 1 1
    0 1 1 0 1 0 0 1 1 1
    The area of the largest empty region of the grid
    containing the point (9, 5) is: 4
    >>> area(0, 2, 2, 7)
    The grid is:
    0 0 1 0 0 0 0 0 0 1
    1 0 1 1 0 1 0 1 1 0
    0 1 0 0 0 1 0 0 0 1
    1 1 0 1 0 0 1 0 1 1
    1 1 1 0 1 1 0 0 1 0
    0 1 0 1 0 0 1 0 0 1
    0 1 1 1 1 0 0 1 1 1
    1 1 1 0 0 1 1 0 0 0
    0 0 1 0 1 0 0 1 1 1
    0 1 1 0 1 0 0 1 1 1
    The area of the largest empty region of the grid
    containing the point (2, 7) is: 22
    >>> area(0, 4, 2, 7)
    The grid is:
    0 0 1 0 0 0 0 0 0 0
    0 0 0 1 0 0 0 1 1 0
    0 1 0 0 0 0 0 0 0 1
    1 1 0 1 0 0 0 0 1 0
    0 0 0 0 1 1 0 0 1 0
    0 1 0 0 0 0 1 0 0 0
    0 0 0 0 1 0 0 1 1 0
    0 1 1 0 0 0 0 0 0 0
    0 0 1 0 1 0 0 0 0 1
    0 1 0 0 0 0 0 1 1 0
    The area of the largest empty region of the grid
    containing the point (2, 7) is: 73
    '''
    seed(for_seed)
    grid = [[int(randrange(sparsity) == 0) for _ in range(10)]
            for _ in range(10)
            ]
    print('The grid is:')
    for row in grid:
        print(*row)
    print('The area of the largest empty region of the grid')
    print(f'containing the point ({i}, {j}) is: ', end='')
    # INSERT YOUR CODE HERE
    row = len(grid)
    col = len(grid[0])
    visited = set()

    def explore(grid, i, j, visited):
        if grid[i][j] == 1:
            return
        visited.add((i, j))
        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        for dir_i, dir_j in directions:
            next_i, next_j = dir_i + i, dir_j + j
            if 0 <= next_i < row and 0 <= next_j < col:
                if grid[next_i][next_j] == 0 and (next_i, next_j) not in visited:
                    explore(grid, next_i, next_j, visited)

    explore(grid, i, j, visited)
    print(len(visited))


# POSSIBLY DEFINE OTHER FUNCTIONS


if __name__ == '__main__':
    # area(0, 2, 2, 7)
    import doctest

    doctest.testmod()

有点难度的dfs

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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
# Exploration proceeds horizontally and vertically (not diagonally).
#
# The coordinate system is the usual one mathematically:
# - x is for the horizontal coordinate, ranging between 1 and size
#   moving from left to right;
# - y is for the vertical coordinate, ranging between 1 and size
#   moving from bottom to top.
#
# <BLANKLINE> is not output by the program, but
# doctest's way to refer to an empty line
# (here, output by the print() statement in the stub).
#
# You can assume that f is called with for_seed and density two integers,
# size an integer at least equal to 1, and x and y two integers between
# 1 and size included.


from random import seed, random


def display(grid):
    for row in grid:
        print(''.join(e and '\N{Black large square}'
                      or '\N{White large square}'
                      for e in row
                      )
              )


def f(for_seed, density, size, x, y):
    '''
    >>> f(3, 0.65, 10, 1, 1)
    ⬛⬛⬛⬛⬛⬛⬛⬜⬛⬛
    ⬜⬛⬜⬛⬛⬛⬛⬜⬛⬜
    ⬜⬛⬜⬛⬛⬛⬜⬛⬜⬜
    ⬜⬜⬛⬜⬛⬜⬜⬛⬛⬛
    ⬜⬛⬛⬛⬛⬛⬛⬛⬛⬜
    ⬜⬜⬜⬜⬜⬛⬜⬜⬜⬛
    ⬜⬛⬜⬛⬛⬛⬜⬜⬛⬜
    ⬛⬛⬛⬜⬜⬛⬛⬛⬜⬛
    ⬜⬜⬛⬜⬛⬛⬛⬛⬛⬛
    ⬛⬛⬛⬜⬛⬜⬜⬛⬛⬛
    <BLANKLINE>
    ⬛⬛⬛⬛⬛⬛⬛⬜⬛⬛
    ⬜⬛⬜⬛⬛⬛⬛⬜⬛⬜
    ⬜⬛⬜⬛⬛⬛⬜⬛⬜⬜
    ⬜⬜⬛⬜⬛⬜⬜⬛⬛⬛
    ⬜⬛⬛⬛⬛⬛⬛⬛⬛⬜
    ⬜⬜⬜⬜⬜⬛⬜⬜⬜⬛
    ⬜🔵⬜⬛⬛⬛⬜⬜⬛⬜
    🔵🔵🔵⬜⬜⬛⬛⬛⬜⬛
    ⬜⬜🔵⬜⬛⬛⬛⬛⬛⬛
    🔴🔵🔵⬜⬛⬜⬜⬛⬛⬛
    >>> f(3, 0.65, 10, 1, 10)
    ⬛⬛⬛⬛⬛⬛⬛⬜⬛⬛
    ⬜⬛⬜⬛⬛⬛⬛⬜⬛⬜
    ⬜⬛⬜⬛⬛⬛⬜⬛⬜⬜
    ⬜⬜⬛⬜⬛⬜⬜⬛⬛⬛
    ⬜⬛⬛⬛⬛⬛⬛⬛⬛⬜
    ⬜⬜⬜⬜⬜⬛⬜⬜⬜⬛
    ⬜⬛⬜⬛⬛⬛⬜⬜⬛⬜
    ⬛⬛⬛⬜⬜⬛⬛⬛⬜⬛
    ⬜⬜⬛⬜⬛⬛⬛⬛⬛⬛
    ⬛⬛⬛⬜⬛⬜⬜⬛⬛⬛
    <BLANKLINE>
    🔴🔵🔵🔵🔵🔵🔵⬜⬛⬛
    ⬜🔵⬜🔵🔵🔵🔵⬜⬛⬜
    ⬜🔵⬜🔵🔵🔵⬜🔵⬜⬜
    ⬜⬜🔵⬜🔵⬜⬜🔵🔵🔵
    ⬜🔵🔵🔵🔵🔵🔵🔵🔵⬜
    ⬜⬜⬜⬜⬜🔵⬜⬜⬜⬛
    ⬜⬛⬜🔵🔵🔵⬜⬜⬛⬜
    ⬛⬛⬛⬜⬜🔵🔵🔵⬜🔵
    ⬜⬜⬛⬜🔵🔵🔵🔵🔵🔵
    ⬛⬛⬛⬜🔵⬜⬜🔵🔵🔵
    >>> f(3, 0.65, 10, 10, 1)
    ⬛⬛⬛⬛⬛⬛⬛⬜⬛⬛
    ⬜⬛⬜⬛⬛⬛⬛⬜⬛⬜
    ⬜⬛⬜⬛⬛⬛⬜⬛⬜⬜
    ⬜⬜⬛⬜⬛⬜⬜⬛⬛⬛
    ⬜⬛⬛⬛⬛⬛⬛⬛⬛⬜
    ⬜⬜⬜⬜⬜⬛⬜⬜⬜⬛
    ⬜⬛⬜⬛⬛⬛⬜⬜⬛⬜
    ⬛⬛⬛⬜⬜⬛⬛⬛⬜⬛
    ⬜⬜⬛⬜⬛⬛⬛⬛⬛⬛
    ⬛⬛⬛⬜⬛⬜⬜⬛⬛⬛
    <BLANKLINE>
    🔵🔵🔵🔵🔵🔵🔵⬜⬛⬛
    ⬜🔵⬜🔵🔵🔵🔵⬜⬛⬜
    ⬜🔵⬜🔵🔵🔵⬜🔵⬜⬜
    ⬜⬜🔵⬜🔵⬜⬜🔵🔵🔵
    ⬜🔵🔵🔵🔵🔵🔵🔵🔵⬜
    ⬜⬜⬜⬜⬜🔵⬜⬜⬜⬛
    ⬜⬛⬜🔵🔵🔵⬜⬜⬛⬜
    ⬛⬛⬛⬜⬜🔵🔵🔵⬜🔵
    ⬜⬜⬛⬜🔵🔵🔵🔵🔵🔵
    ⬛⬛⬛⬜🔵⬜⬜🔵🔵🔴
    >>> f(3, 0.65, 10, 10, 10)
    ⬛⬛⬛⬛⬛⬛⬛⬜⬛⬛
    ⬜⬛⬜⬛⬛⬛⬛⬜⬛⬜
    ⬜⬛⬜⬛⬛⬛⬜⬛⬜⬜
    ⬜⬜⬛⬜⬛⬜⬜⬛⬛⬛
    ⬜⬛⬛⬛⬛⬛⬛⬛⬛⬜
    ⬜⬜⬜⬜⬜⬛⬜⬜⬜⬛
    ⬜⬛⬜⬛⬛⬛⬜⬜⬛⬜
    ⬛⬛⬛⬜⬜⬛⬛⬛⬜⬛
    ⬜⬜⬛⬜⬛⬛⬛⬛⬛⬛
    ⬛⬛⬛⬜⬛⬜⬜⬛⬛⬛
    <BLANKLINE>
    ⬛⬛⬛⬛⬛⬛⬛⬜🔵🔴
    ⬜⬛⬜⬛⬛⬛⬛⬜🔵⬜
    ⬜⬛⬜⬛⬛⬛⬜⬛⬜⬜
    ⬜⬜⬛⬜⬛⬜⬜⬛⬛⬛
    ⬜⬛⬛⬛⬛⬛⬛⬛⬛⬜
    ⬜⬜⬜⬜⬜⬛⬜⬜⬜⬛
    ⬜⬛⬜⬛⬛⬛⬜⬜⬛⬜
    ⬛⬛⬛⬜⬜⬛⬛⬛⬜⬛
    ⬜⬜⬛⬜⬛⬛⬛⬛⬛⬛
    ⬛⬛⬛⬜⬛⬜⬜⬛⬛⬛
    >>> f(3, 0.65, 10, 7, 5)
    ⬛⬛⬛⬛⬛⬛⬛⬜⬛⬛
    ⬜⬛⬜⬛⬛⬛⬛⬜⬛⬜
    ⬜⬛⬜⬛⬛⬛⬜⬛⬜⬜
    ⬜⬜⬛⬜⬛⬜⬜⬛⬛⬛
    ⬜⬛⬛⬛⬛⬛⬛⬛⬛⬜
    ⬜⬜⬜⬜⬜⬛⬜⬜⬜⬛
    ⬜⬛⬜⬛⬛⬛⬜⬜⬛⬜
    ⬛⬛⬛⬜⬜⬛⬛⬛⬜⬛
    ⬜⬜⬛⬜⬛⬛⬛⬛⬛⬛
    ⬛⬛⬛⬜⬛⬜⬜⬛⬛⬛
    <BLANKLINE>
    ⬛⬛⬛⬛⬛⬛⬛⬜⬛⬛
    ⬜⬛⬜⬛⬛⬛⬛⬜⬛⬜
    ⬜⬛⬜⬛⬛⬛⬜⬛⬜⬜
    ⬜⬜⬛⬜⬛⬜⬜⬛⬛⬛
    ⬜⬛⬛⬛⬛⬛⬛⬛⬛⬜
    ⬜⬜⬜⬜⬜⬛⬜⬜⬜⬛
    ⬜⬛⬜⬛⬛⬛⬜⬜⬛⬜
    ⬛⬛⬛⬜⬜⬛⬛⬛⬜⬛
    ⬜⬜⬛⬜⬛⬛⬛⬛⬛⬛
    ⬛⬛⬛⬜⬛⬜⬜⬛⬛⬛
    >>> f(5, 0.4, 10, 1, 3)
    ⬜⬜⬜⬜⬜⬜⬛⬜⬜⬜
    ⬜⬛⬜⬛⬜⬜⬛⬛⬛⬜
    ⬜⬛⬜⬛⬜⬛⬛⬜⬛⬛
    ⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜
    ⬜⬛⬛⬛⬛⬛⬛⬜⬛⬜
    ⬛⬛⬜⬜⬛⬜⬜⬛⬜⬛
    ⬜⬜⬛⬜⬛⬜⬛⬛⬛⬜
    ⬛⬜⬜⬜⬛⬛⬜⬜⬛⬜
    ⬜⬜⬛⬜⬛⬛⬜⬜⬛⬜
    ⬜⬛⬛⬛⬛⬛⬜⬜⬛⬛
    <BLANKLINE>
    ⬜⬜⬜⬜⬜⬜⬛⬜⬜⬜
    ⬜⬛⬜⬛⬜⬜⬛⬛⬛⬜
    ⬜⬛⬜⬛⬜⬛⬛⬜⬛⬛
    ⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜
    ⬜⬛⬛⬛⬛⬛⬛⬜⬛⬜
    ⬛⬛⬜⬜⬛⬜⬜⬛⬜⬛
    ⬜⬜⬛⬜⬛⬜⬛⬛⬛⬜
    🔴⬜⬜⬜⬛⬛⬜⬜⬛⬜
    ⬜⬜⬛⬜⬛⬛⬜⬜⬛⬜
    ⬜⬛⬛⬛⬛⬛⬜⬜⬛⬛
    >>> f(5, 0.4, 10, 3, 7)
    ⬜⬜⬜⬜⬜⬜⬛⬜⬜⬜
    ⬜⬛⬜⬛⬜⬜⬛⬛⬛⬜
    ⬜⬛⬜⬛⬜⬛⬛⬜⬛⬛
    ⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜
    ⬜⬛⬛⬛⬛⬛⬛⬜⬛⬜
    ⬛⬛⬜⬜⬛⬜⬜⬛⬜⬛
    ⬜⬜⬛⬜⬛⬜⬛⬛⬛⬜
    ⬛⬜⬜⬜⬛⬛⬜⬜⬛⬜
    ⬜⬜⬛⬜⬛⬛⬜⬜⬛⬜
    ⬜⬛⬛⬛⬛⬛⬜⬜⬛⬛
    <BLANKLINE>
    ⬜⬜⬜⬜⬜⬜🔵⬜⬜⬜
    ⬜⬛⬜⬛⬜⬜🔵🔵🔵⬜
    ⬜⬛⬜⬛⬜🔵🔵⬜🔵🔵
    ⬜⬜🔴⬜⬜⬜🔵⬜⬜⬜
    ⬜🔵🔵🔵🔵🔵🔵⬜⬛⬜
    🔵🔵⬜⬜🔵⬜⬜⬛⬜⬛
    ⬜⬜⬛⬜🔵⬜⬛⬛⬛⬜
    ⬛⬜⬜⬜🔵🔵⬜⬜⬛⬜
    ⬜⬜🔵⬜🔵🔵⬜⬜⬛⬜
    ⬜🔵🔵🔵🔵🔵⬜⬜⬛⬛
    '''
    seed(for_seed)
    grid = [[random() < density for _ in range(size)]
            for _ in range(size)
            ]
    display(grid)
    print()
    visited = set()
    start = x, y
    # CHANGE THE PREVIOUS ASSIGNMENT SO grid[start[0]][start[1]]
    # IS WHERE EXPLORATION STARTS FROM.
    # (That way, you can just use grid[i][j] without having to bother
    # what the coordinate system happens to be.)
    explore(grid, size, *start, visited)
    display_reachable(grid, size, start, visited)


def explore(grid, size, i, j, visited):
    if grid[size - j][i - 1] == 0:
        return
    visited.add((i, j))
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    for dir_i, dir_j in directions:
        next_i, next_j = dir_i + i, dir_j + j
        if 1 <= next_i <= size and 1 <= next_j <= size:
            if grid[size - next_j][next_i - 1] == 1 and (next_i, next_j) not in visited:
                explore(grid, size, next_i, next_j, visited)

    # REPLACE THE PASS STATEMENT ABOVE WITH YOUR CODE(3,1) (9,2)


def display_reachable(grid, size, start, visited):
    for i in range(size):
        for j in range(size):
            if (j + 1, size - i) in visited:
                if (j + 1, size - i) == start:
                    print(f'\N{Large red circle}', end="")
                else:
                    print(f'\N{Large blue circle}', end="")
            elif grid[i][j] == 1:
                print(f'\N{Black large square}', end="")
            else:
                print(f'\N{White large square}', end="")
        print()

    # pass
    # REPLACE THE PASS STATEMENT ABOVE WITH YOUR CODE
    # It involves (as possible   ways to denote the appropriate
    # Unicode characters):
    # - '\N{Large red circle}'
    # - '\N{Large blue circle}'


if __name__ == '__main__':
    # f(5, 0.4, 10, 3, 7)
    import doctest

    doctest.testmod()

马走日

number of components

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
# Written by *** for COMP9021
#
# Randomly fills an array of size 10x10 with True and False,
# displayed as 1 and 0, and outputs the number of chess knights
# needed to jump from 1s to 1s and visit all 1s (they can jump back
# to locations previously visited).


from random import seed, randrange
import sys

dim = 10


def display_grid():
    for row in grid:
        print('    ', ' '.join(str(int(e)) for e in row))


try:
    for_seed, n = (int(i) for i in input('Enter two integers: ').split())
    if not n:
        n = 1
except ValueError:
    print('Incorrect input, giving up.')
    sys.exit()
seed(for_seed)
if n > 0:
    grid = [[randrange(n) > 0 for _ in range(dim)] for _ in range(dim)]
else:
    grid = [[randrange(-n) == 0 for _ in range(dim)] for _ in range(dim)]
print('Here is the grid that has been generated:')
display_grid()

print()

# INSERT YOUR CODE HERE
directions = [(-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1)]
color = 2


def explore(grid, i, j, color):
    grid[i][j] = color
    for dir_i, dir_j in directions:
        next_i, next_j = dir_i + i, dir_j + j
        if 0 <= next_i < dim and 0 <= next_j < dim:
            if grid[next_i][next_j] == 1:
                explore(grid, next_i, next_j, color)


for i in range(dim):
    for j in range(dim):
        if grid[i][j] == 1:
            explore(grid, i, j, color)
            color += 1

print(f'At least {color - 2} chess knights have explored this board.')

从某个点递增可达的最远的点

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
# Will be tested only with positive integers for for_seed and upper_bound,
# and a strictly positive integer for size.
#
# Exploration can follow up to 8 directions
# (two horizontally, two vertically, and four diagonally).
#
# Travelling from m to n means starting from a cell that stores m,
# moving to a (horizontally, vertically or diagonally) neighbouring
# cell that stores m + 1, then moving to a (horizontally, vertically
# or diagonally) neighbouring cell hat stores m + 2... and eventually
# reaching a cell that stores n.
#
# Most of the code is written already, and there are not many statements
# left for you to write...

from random import seed, randrange


def travel(for_seed, size, upper_bound):
    '''
    >>> travel(0, 2, 0)
    The grid is:
    * * * *
    * 0 0 *
    * 0 0 *
    * * * *
    It is possible to travel from 0 to 0.
    >>> travel(0, 3, 1)
    The grid is:
    * * * * *
    * 1 1 0 *
    * 1 1 1 *
    * 1 1 1 *
    * * * * *
    It is possible to travel from 0 to 1.
    It is possible to travel from 1 to 1.
    >>> travel(0, 4, 4)
    The grid is:
    * * * * * *
    * 3 3 0 2 *
    * 4 3 3 2 *
    * 3 2 4 1 *
    * 4 1 2 1 *
    * * * * * *
    It is possible to travel from 0 to 0, but not from 0 to 1.
    It is possible to travel from 1 to 4.
    It is possible to travel from 2 to 4.
    It is possible to travel from 3 to 4.
    It is possible to travel from 4 to 4.
    >>> travel(0, 6, 8)
    The grid is:
    * * * * * * * *
    * 6 6 0 4 8 7 *
    * 6 4 7 5 3 8 *
    * 2 4 2 1 4 8 *
    * 2 4 1 1 5 7 *
    * 8 1 5 6 5 3 *
    * 8 7 7 8 4 0 *
    * * * * * * * *
    It is possible to travel from 0 to 0, but not from 0 to 1.
    It is possible to travel from 1 to 2, but not from 1 to 3.
    It is possible to travel from 2 to 2, but not from 2 to 3.
    It is possible to travel from 3 to 8.
    It is possible to travel from 4 to 8.
    It is possible to travel from 5 to 8.
    It is possible to travel from 6 to 8.
    It is possible to travel from 7 to 8.
    It is possible to travel from 8 to 8.
    >>> travel(2, 5, 4)
    The grid is:
    * * * * * * *
    * 0 0 0 2 1 *
    * 2 2 4 1 4 *
    * 0 4 1 3 3 *
    * 4 2 4 3 4 *
    * 2 0 0 2 3 *
    * * * * * * *
    It is possible to travel from 0 to 2, but not from 0 to 3.
    It is possible to travel from 1 to 2, but not from 1 to 3.
    It is possible to travel from 2 to 4.
    It is possible to travel from 3 to 4.
    It is possible to travel from 4 to 4.
    '''
    seed(for_seed)
    values = set()
    grid = [['*' for _ in range(size + 2)] for _ in range(size + 2)]
    for i in range(1, size + 1):
        for j in range(1, size + 1):
            value = randrange(upper_bound + 1)
            values.add(value)
            grid[i][j] = value
    print('The grid is:')
    for row in grid:
        print(*row)
    upper_bound = max(values)
    from_to = {_from: _from for _from in values}
    for i in range(1, size + 1):
        for j in range(1, size + 1):
            from_to[grid[i][j]] = max(from_to[grid[i][j]],
                                      explore_from(grid, upper_bound, i, j)
                                      )
    for _from in from_to:
        _to = from_to[_from]
        print(f'It is possible to travel from {_from} to {_to}', end='')
        if _to != upper_bound:
            print(f', but not from {_from} to {_to + 1}', end='')
        print('.')


def explore_from(grid, upper_bound, i, j):
    row = len(grid)
    col = len(grid[0])
    directions = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
    for dir_i, dir_j in directions:
        next_i, next_j = dir_i + i, dir_j + j
        if 0 <= next_i < row and 0 <= next_j < col:
            if grid[next_i][next_j] == grid[i][j] + 1:
                return explore_from(grid, upper_bound, next_i, next_j)
    return grid[i][j]
    # REPLACE THE RETURN STATEMENT ABOVE WITH YOUR CODE


if __name__ == '__main__':
    # travel(2, 5, 4)
    # print()
    import doctest

    doctest.testmod()

深度优先模板题

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
# Here is the contents of grid.txt, separating consecutive
# letters for readability, and numbering rows and columns.
#
#    1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18
#  1 B  L  I  D  F  W  J  R  S  H  Z  G  P  R  T  B  R  T
#  2 T  X  Z  Y  D  O  E  O  B  T  Y  U  I  N  K  N  F  L
#  3 U  O  S  Y  D  V  Q  V  O  R  A  L  W  N  S  O  D  A
#  4 U  O  B  A  Z  F  Z  C  H  H  X  Z  E  D  E  S  O  D
#  5 Q  U  M  P  R  T  H  H  J  H  V  I  A  K  R  I  A  N
#  6 B  C  O  T  G  H  E  R  U  M  G  V  E  M  I  A  B  K
#  7 L  I  J  C  B  Z  Z  C  R  V  O  B  S  Y  O  N  K  J
#  8 X  D  R  M  Y  V  U  V  O  M  K  S  Q  B  W  G  X  O
#  0 V  T  M  T  C  M  X  Y  I  N  O  N  Q  C  Y  L  E  A
# 10 F  S  V  Y  U  V  L  L  K  V  Y  H  Z  L  F  I  I  M
# 11 J  M  R  B  W  Y  Q  R  H  E  M  R  A  N  D  Z  I  X
# 12 M  Q  W  A  X  D  R  R  L  L  E  A  A  J  G  L  T  G
#
# We try and find the "word" provided as first argument,
# starting somewhere in the grid, moving left, right, up or
# down. The third argument, can_reuse, is set to True by default,
# which means that there is no further restriction on the exploration.
# When can_reuse is set to False, no location in the grid can be
# visited more than once.
#
# At least half of the tests will be with can_reuse set to True,
# so at least 50% of marks will be awarded to implementations that
# only deal with the simplest of both scenarios.
#
# If "word" is not found, the function returns None.
# If "word" is found, the function returns the pair
# (row_number, column_number) that marks the beginning of the path.
# In case the path is not unique, the pair that is returned
# minimises row_number, and for a given row_number, minimises
# column_number.
#
# grid.txt is just an example of a file; your program might be
# tested with another file, whose name is arbitrary
# (not necessarily 'grid.txt').
#
# You can assume that the file is stored in the working directory,
# and consists of at least one line, each line consisting of the same
# number (at least equal to 1) of nothing but uppercase letters,
# with no space besides the end of line characters.
#
# You can also assume that word is a nonempty string consisting of
# nothing but uppercase letters.


def find_in(word, filename, can_reuse=True):
    '''
    >>> find_in('LOOKWELL', 'grid.txt')
    >>> find_in('U', 'grid.txt')
    (2, 12)
    >>> find_in('U', 'grid.txt', can_reuse=False)
    (2, 12)
    >>> find_in('RARARARARARARARARARAR', 'grid.txt')
    (3, 10)
    >>> find_in('RARARARARARARARARARAR', 'grid.txt', can_reuse=False)
    >>> find_in('THERC', 'grid.txt')
    (5, 6)
    >>> find_in('THERC', 'grid.txt', can_reuse=False)
    (5, 6)
    >>> find_in('VBSQBYSBOVM', 'grid.txt')
    (6, 12)
    >>> find_in('VBSQBYSBOVM', 'grid.txt', can_reuse=False)
    >>> find_in('ADOSERIMKAIVG', 'grid.txt')
    (3, 18)
    >>> find_in('ADOSERIMKAIVG', 'grid.txt', can_reuse=False)
    (3, 18)
    >>> find_in('DYVLLKHRQYWBYV', 'grid.txt')
    (12, 6)
    >>> find_in('DYVLLKHRQYWBYV', 'grid.txt', can_reuse=False)
    '''

    def explore(grid, i, j, lefts, path, solutions):
        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        if not lefts:
            solutions.append(path)
        else:
            for dir_i, dir_j in directions:
                next_i, next_j = dir_i + i, dir_j + j
                if 0 <= next_i < row and 0 <= next_j < col:
                    if grid[next_i][next_j] == lefts[0]:
                        explore(grid, next_i, next_j, lefts[1:], path + [(next_i, next_j)], solutions)

    with open('grid.txt') as lines:
        grid = []
        for line in lines:
            grid.append(line.strip())

    row = len(grid)
    col = len(grid[0])
    solutions = []
    for i in range(row):
        for j in range(col):
            if grid[i][j] == word[0]:
                # 保留路径的起点，搜索word中下一个元素
                path = [(i, j)]
                explore(grid, i, j, word[1:], path, solutions)

    if solutions:
        if can_reuse:
            # 说明可以复用
            return solutions[0][0][0] + 1, solutions[0][0][1] + 1
        else:
            for solution in solutions:
                if len(solution) == len(set(solution)):
                    return solution[0][0] + 1, solution[0][1] + 1

    # return None or 0, 0
    # REPLACE return None or 0, 0 ABOVE WITH YOUR CODE


# POSSIBLY DEFINE OTHER FUNCTIONS


if __name__ == '__main__':
    import doctest

    doctest.testmod()
    # find_in('U', 'grid.txt')

最左的置换能够使得上下两半和相等

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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
# We explain the task with an example.
#
# Consider the following sequence of integers: 1, 2, 3, 2, 2.
# Here are all permutations of this sequence:
# - 1, 2, 3, 2, 2, starting at index 0
# - 2, 3, 2, 2, 1, starting at index 1
# - 3, 2, 2, 1, 2, starting at index 2
# - 2, 2, 1, 2, 3, starting at index 3
# - 2, 1, 2, 3, 2, starting at index 4
# For each of those permutations, we try and split it in 2 nonempty parts
# so that the sum of the numbers on the left is equal to the sum of the
# numbers on the right.
# - It is not possible with the permutation that starts at index 0.
# - It is possible with the permutation that starts at index 1:
#   2 + 3 = 2 + 2 + 1
#   yielding a solution with 2 terms on the left
#   and 3 terms on the right of the equality.
# - It is possible with the permutation that starts at index 2:
#   3 + 2 = 2 + 1 + 2
#   yielding a solution with 2 terms on the left
#   and 3 terms on the right of the equality.
# - It is possible with the permutation that starts at index 3:
#   2 + 2 + 1 = 2 + 3
#   yielding a solution with 3 terms on the left
#   and 2 terms on the right of the equality.
# - It is possible with the permutation that starts at index 4:
#   2 + 1 + 2 = 3 + 2
#   yielding a solution with 3 terms on the left
#   and 2 terms on the right of the equality.
# For all solutions, the sum is 5.
#
# We want to report whether there is a solution, and in case there is,
# say what is the leftmost permutation that yields a solution
# (so what is the minimal i for which the permutation that starts at
# index i yields a solution), and how many terms it has on the left
# and on the right of the equality.
#
# Do not ask for how large the sequence can be, just do your best.
# For the sample tests, the function should return within a fraction
# of a second. If you think well, it can be pushed way further.
#
# You can assume that the function is provided with nothing but integers
# as arguments.


def f(*numbers):
    '''
    >>> f(1, 2)
    There is no solution.
    >>> f(1, 1, 1)
    There is no solution.
    >>> f(1, 1)
    There is a solution, with a sum of 1.
    The leftmost permutation that yields a solution starts at index 0.
    If has 1 term on the left and 1 term on the right of the equality.
    >>> f(1, 1, 1, 1)
    There is a solution, with a sum of 2.
    The leftmost permutation that yields a solution starts at index 0.
    If has 2 terms on the left and 2 terms on the right of the equality.
    >>> f(1, 1, 1, 3)
    There is a solution, with a sum of 3.
    The leftmost permutation that yields a solution starts at index 0.
    If has 3 terms on the left and 1 term on the right of the equality.
    >>> f(1, 1, 3, 1)
    There is a solution, with a sum of 3.
    The leftmost permutation that yields a solution starts at index 2.
    If has 1 term on the left and 3 terms on the right of the equality.
    >>> f(1, 3, 1, 1)
    There is a solution, with a sum of 3.
    The leftmost permutation that yields a solution starts at index 1.
    If has 1 term on the left and 3 terms on the right of the equality.
    >>> f(3, 1, 1, 1)
    There is a solution, with a sum of 3.
    The leftmost permutation that yields a solution starts at index 0.
    If has 1 term on the left and 3 terms on the right of the equality.
    >>> f(1, 2, 3, 2, 2)
    There is a solution, with a sum of 5.
    The leftmost permutation that yields a solution starts at index 1.
    If has 2 terms on the left and 3 terms on the right of the equality.
    >>> f(*((1,) * 10_000))
    There is a solution, with a sum of 5000.
    The leftmost permutation that yields a solution starts at index 0.
    If has 5000 terms on the left and 5000 terms on the right of the equality.
    >>> f(*((1,) * 1_000 + (2_000,) + (1,) * 1_000))
    There is a solution, with a sum of 2000.
    The leftmost permutation that yields a solution starts at index 1000.
    If has 1 term on the left and 2000 terms on the right of the equality.
    '''
    if len(numbers) < 2:
        return

    # INSERT YOUR CODE HERE
    import sys
    sys.setrecursionlimit(3000000)

    # print(numbers)

    def check_sum(number, digits, lefts, solutions):
        digit_int = []
        if digits:
            digit_int = [int(x) for x in digits]
        # print(digit_int)
        if lefts == sum(digit_int):
            solutions.append(digits)
            return True
        elif not number:
            return False
        elif lefts < 0 or lefts < sum(digit_int):
            return False
        if number:
            start_value = number[0]
            return check_sum(number[1:], digits + [start_value], lefts - start_value, solutions)

    str_numbers = str(numbers).replace('(', '').replace(')', '').split(', ')

    # print(str_numbers)

    tmp = []
    for i in range(len(str_numbers)):
        tmp.append([int(item) for item in str_numbers[i:] + str_numbers[:i]])
    # print(tmp[-1])
    cnt = 0
    for item in tmp:
        solutions = []
        if check_sum(item, [], sum(item), solutions):
            # print(solutions, len(*solutions))
            if solutions:
                print(f'There is a solution, with a sum of {sum(item) // 2}.')
                print(f'The leftmost permutation that yields a solution starts at index {cnt}.')
                if len(*solutions) == 1 and len(str_numbers) - len(*solutions) == 1:
                    print(
                        f'If has 1 term on the left and 1 term on the right of the equality.')
                elif len(*solutions) > 1 and len(str_numbers) - len(*solutions) == 1:
                    print(
                        f'If has {len(*solutions)} terms on the left and 1 term on the right of the equality.')
                elif len(*solutions) == 1 and len(str_numbers) - len(*solutions) > 1:
                    print(
                        f'If has 1 term on the left and {len(str_numbers) - len(*solutions)} terms on the right of the equality.')
                elif len(*solutions) > 1 and len(str_numbers) - len(*solutions) > 1:
                    print(
                        f'If has {len(*solutions)} terms on the left and {len(str_numbers) - len(*solutions)} terms on the right of the equality.')
            return
        cnt += 1
    print('There is no solution.')
    return


if __name__ == '__main__':
    # f(1, 2)
    # f(1, 2, 3, 2, 2)
    # f(3, 1, 1, 1)
    # f(*((1,) * 1_000 + (2_000,) + (1,) * 1_000))
    # f(1,1,1,1,1,1,1,1,10,1,1)
    # f(*((1,) * 10_000))
    import doctest

    doctest.testmod()

子串和能加到某个值

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
# 19T1 PRE FINAL exercise_5.py

# POSSIBLY DEFINE OTHER

def subnumbers_whose_digits_add_up_to(number, sum_of_digits):
    '''
    You can assume that "number" consists of digits not equal to 0
    and that "sum_of_digits" is an integer.

    A solution is obtained by possibly deleting some digits in "number"
    (keeping the order of the remaining digits) so that the sum of
    of the remaining digits is equal to "sum_of_digits".

    The solutions are listed from smallest to largest, with no duplicate.

    >>> subnumbers_whose_digits_add_up_to(13, 2)
    []
    >>> subnumbers_whose_digits_add_up_to(222, 2)
    [2]
    >>> subnumbers_whose_digits_add_up_to(123, 6)
    [123]
    >>> subnumbers_whose_digits_add_up_to(222, 4)
    [22]
    >>> subnumbers_whose_digits_add_up_to(1234, 5)
    [14, 23]
    >>> subnumbers_whose_digits_add_up_to(12341234, 4)
    [4, 13, 22, 31, 112, 121]
    >>> subnumbers_whose_digits_add_up_to(121212, 5)
    [122, 212, 221, 1112, 1121, 1211]
    >>> subnumbers_whose_digits_add_up_to(123454321, 10)
    [145, 154, 235, 244, 253, 343, 352, 442, 451, 532, 541, 1234, 1243, \
1252, 1342, 1351, 1432, 1441, 1531, 2332, 2341, 2431, 2521, 3421, \
4321, 12331, 12421, 13321]
    '''

    def recursion_handler(str_number, digits, lefts, solutions):
        if lefts == 0:
            solutions.append(int(digits))
        elif not str_number:
            return
        elif lefts < 0:
            return
        else:
            first_value = str_number[0]
            recursion_handler(str_number[1:], digits + first_value, lefts - int(first_value), solutions)
            recursion_handler(str_number[1:], digits, lefts, solutions)

    solutions = []
    recursion_handler(str(number), "", sum_of_digits, solutions)
    return sorted(set(solutions))


if __name__ == '__main__':
    import doctest

    doctest.testmod()

字典找环路

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
# Given a dictionary D and a key x, there is a (unique) loop
# containing x if there are keys x_1, ..., x_k such that:
# D maps x to x_1
# D maps x_1 to x_2
# ...
# D maps x_{k-1} to x_k
# x_1, ..., x_{k-1} are all different to x and x_k is x
# (in the particular case where k = 1, D maps x to x).
#
# When the loop does not exist, the function prints out nothing.
# When the loop exists, the function prints out the loop,
# STARTING AND ENDING with the SMALLEST element in the loop.
#
# You can assume that the function is called with as first argument,
# a dictionary having nothing but integers as keys and values,
# and with as second argument, an integer.

def loop(D, x):
    '''
    >>> loop({1: 1}, 0)
    >>> loop({1: 2, 2: 2}, 1)
    >>> loop({1: 2, 2: 3}, 1)
    >>> loop({1: 2, 2: 3, 3: 2}, 1)
    >>> loop({1: 1}, 1)
    1--1
    >>> loop({1: 2, 2: 1}, 2)
    1--2--1
    >>> loop({12: 14, 13: 14, 14: 7, 7: 12, 6: 8, 8: 6, 5: 11}, 14)
    7--12--14--7
    >>> loop({0: 4, 1: 0, 2: 1, 3: 2, 4: 7, 5: 6, 6: 4, 7: 0, 8: 8, 9: 4}, 4)
    0--4--7--0
    >>> loop({0: 7, 1: 7, 2: 3, 3: 8, 4: 6, 5: 8, 6: 6, 7: 4, 8: 9, 9: 2}, 8)
    2--3--8--9--2
    '''

    # REPLACE PASS ABOVE WITH YOUR CODE
    # 先要找到环
    result = []
    if x in D:
        cycle = [x]
        while cycle[-1] in D:
            value = D[cycle[-1]]
            if value == cycle[0]:
                cycle.append(value)
                result = cycle
                break
            elif value in cycle:
                break
            cycle.append(value)

    if result:
        partition_index = result.index(min(result))
        print('--'.join(map(str, result[partition_index:] + result[1:partition_index + 1])))


if __name__ == '__main__':
    # loop({12: 14, 13: 14, 14: 7, 7: 12, 6: 8, 8: 6, 5: 11}, 14)
    import doctest

    doctest.testmod()

升序降序元素间隔

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
def f(L):
    tmp = [L[0]]
    decr = []
    incr = []
    result = []
    flag_incr = 0
    flag_decr = 0
    for item in L[1:]:
        if item > tmp[-1] and item - tmp[-1] > 1:
            cur_item = list(range(tmp[-1] + 1, item))
            if cur_item not in incr:
                incr.append(cur_item)
        elif item - tmp[-1] == 1:
            flag_incr = 1
        elif item < tmp[-1] and tmp[-1] - item > 1:
            cur_item = list(range(tmp[-1] - 1, item, -1))
            if cur_item not in decr:
                decr.append(cur_item)
        elif tmp[-1] - item == 1:
            flag_decr = 1
        else:
            pass
        tmp.append(item)
    if incr or decr:
        if incr:
            result.append(sorted(incr, key=len))
            if flag_incr:
                result.append([])
        if decr:
            result.append(sorted(decr, key=lambda x: (len(x), x[0]), reverse=True))
            if flag_decr:
                result.insert(0, [])
    elif not incr and not decr:
        result = [[], []]
    return result


if __name__ == '__main__':
    print(f([2]))
    print(f([1, 2]))
    print(f([1, 3, 4, 7]))
    print(f([7, 4, 3, 1]))
    print(f([2, 0, 0, 3, 7, 2, 2, 2, -2, 4]))
    print(f([1, -1, 3, 1, 5, 1, 3, 1]))


后一个不同的数字

后一个不同的数字代表前面一个数字的重复次数

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
# Consider a strictly positive integer. Omit all occurrences of 0,
# if any, and write what is left as d_1d_2...d_k.
# Returns the integer consisting of d_2 copies of d_1, followed
# by d_3 copies of d_2, ... followed by d_k copies of d_{k-1},
# followed by d_1 copies of d_k (note that when k = 1, that is
# d_1 copies of d_1).
#
# For instance, if the integer is 40025000170 then removing
# all occurrences of 0, it becomes 42517, and what is returned
# is the integer consisting of
# - 2 copies of 4,
# - followed by 5 copies of 2,
# - followed by 1 copy of 5,
# - followed by 7 copies of 1,
# - followed 4 copies of 7,
# so the integer 4422222511111117777
#
# You can assume that the function is called with a strictly
# positive integer as argument.


def transform(number):
    '''
    >>> transform(1)
    1
    >>> transform(12)
    112
    >>> transform(321)
    332111
    >>> transform(2143)
    2111144433
    >>> transform(3000)
    333
    >>> transform(40025000170)
    4422222511111117777
    '''
    number = str(number)
    number = number.replace('0', '')
    tmp = [number[0]]
    line = ''
    for item in number[1:]:
        if item != tmp[-1]:
            line += tmp[-1] * int(item)
            tmp = [item]
        else:
            continue
    line += tmp[-1] * int(number[0])
    print(line)
    # REPLACE THE RETURN STATEMENT ABOVE WITH YOUR CODE


if __name__ == '__main__':
    # transform(3000)
    # transform(40025000170)
    import doctest

    doctest.testmod()

等差数列

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
# Given a nonzero natural number q, a q-arithmetic progression
# is a sequence of the form x, x + q, x + 2q, ... x + nq
# for some integer x and some natural number n.
#
# q-arithmetic progressions are output from smallest to largest
# first element.
#
# You can assume that the function is called with L a list of integers
# and q an integer at least equal to 1.


from random import seed, randint
from collections import defaultdict


def arithmetic_progressions(L, q):
    '''
    >>> arithmetic_progressions([3, 3, 3, 3], 4)
    The longest 4-arithmetic progressions of members of L are:
    3
    >>> arithmetic_progressions([7, 3], 4)
    The longest 4-arithmetic progressions of members of L are:
    3 -- 7
    >>> arithmetic_progressions([1, 3, 5, 7, 1, 3, 5, 7], 2)
    The longest 2-arithmetic progressions of members of L are:
    1 -- 3 -- 5 -- 7
    >>> arithmetic_progressions([50, 0, 5, 10, 12, 7, 2, 25, 20, 30, 60, 65], 5)
    The longest 5-arithmetic progressions of members of L are:
    0 -- 5 -- 10
    2 -- 7 -- 12
    20 -- 25 -- 30
    >>> arithmetic_progressions([8, -6, 0, 8, 0, 11, 0, 11, -6, -6, 11, 8, 11],\
10)
    The longest 10-arithmetic progressions of members of L are:
    -6
    0
    8
    11
    >>> arithmetic_progressions([10, 9, -1, -2, -6, 0, 9, 4, -6, -2, 7, 3,\
-5, -5, 2, -7, -6, 8], 5)
    The longest 5-arithmetic progressions of members of L are:
    -7 -- -2 -- 3 -- 8
    -6 -- -1 -- 4 -- 9
    >>> seed(0); L = [randint(-100, 100) for _ in range(20000)]
    >>> arithmetic_progressions(L, 19)
    The longest 19-arithmetic progressions of members of L are:
    -100 -- -81 -- -62 -- -43 -- -24 -- -5 -- 14 -- 33 -- 52 -- 71 -- 90
    -99 -- -80 -- -61 -- -42 -- -23 -- -4 -- 15 -- 34 -- 53 -- 72 -- 91
    -98 -- -79 -- -60 -- -41 -- -22 -- -3 -- 16 -- 35 -- 54 -- 73 -- 92
    -97 -- -78 -- -59 -- -40 -- -21 -- -2 -- 17 -- 36 -- 55 -- 74 -- 93
    -96 -- -77 -- -58 -- -39 -- -20 -- -1 -- 18 -- 37 -- 56 -- 75 -- 94
    -95 -- -76 -- -57 -- -38 -- -19 -- 0 -- 19 -- 38 -- 57 -- 76 -- 95
    -94 -- -75 -- -56 -- -37 -- -18 -- 1 -- 20 -- 39 -- 58 -- 77 -- 96
    -93 -- -74 -- -55 -- -36 -- -17 -- 2 -- 21 -- 40 -- 59 -- 78 -- 97
    -92 -- -73 -- -54 -- -35 -- -16 -- 3 -- 22 -- 41 -- 60 -- 79 -- 98
    -91 -- -72 -- -53 -- -34 -- -15 -- 4 -- 23 -- 42 -- 61 -- 80 -- 99
    -90 -- -71 -- -52 -- -33 -- -14 -- 5 -- 24 -- 43 -- 62 -- 81 -- 100
    '''
    print(f'The longest {q}-arithmetic progressions of members of L are:')
    result = []
    mapping = defaultdict(list)
    for item in sorted(set(L)):
        tmp = [item]
        while tmp[-1] + q in L:
            tmp.append(tmp[-1] + q)
        result.append(tmp)
    for item in result:
        mapping[len(item)].append(item)
    for value in list(mapping.values())[0]:
        print(' -- '.join(str(x) for x in value))

    # longest_list=max()

    # REPLACE THE PASS STATEMENT ABOVE WITH YOUR CODE


if __name__ == '__main__':
    # arithmetic_progressions([50, 0, 5, 10, 12, 7, 2, 25, 20, 30, 60, 65], 5)
    import doctest

    doctest.testmod()

因数分解

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
from math import sqrt


def f(n, d):
    '''
    >>> f(2, 1)
    1 is not a proper factor of 2.
    >>> f(2, 2)
    2 is not a proper factor of 2.
    >>> f(16, 2)
    2 is a proper factor of 16 of mutiplicity 4.
    >>> f(100, 20)
    20 is a proper factor of 100 of mutiplicity 1.
    >>> f(8 ** 7 * 3 ** 5 * 11 ** 2, 8)
    8 is a proper factor of 61662560256 of mutiplicity 7.
    >>> f(3 ** 3 * 11 * 13 ** 2 * 40 ** 6, 8)
    8 is a proper factor of 205590528000000 of mutiplicity 6.
    '''

    def is_prime(n):
        if n <= 1:
            return False
        if n <= 3:
            return True
        if n % 2 == 0:
            return False
        return all(n % d for d in range(3, round(sqrt(n)) + 1, 2))

    from collections import defaultdict
    if n <= 2 or is_prime(n):
        print(f'{d} is not a proper factor of {n}.')
        return
    mapping = defaultdict(int)
    n_copy = n
    while n % 2 == 0:
        mapping[2] += 1
        n = n // 2
    i = 3
    while i * i <= n:
        while n % i == 0:
            mapping[i] += 1
            n = n // i
        i = i + 2

    cnt = 0
    d_copy = d
    r = 0
    for k in mapping.keys():
        if d % k == 0:
            while d % k == 0:
                cnt += 1
                d //= k
            r = mapping[k] // cnt
            break

    print(f'{d_copy} is a proper factor of {n_copy} of mutiplicity {r}.')


if __name__ == '__main__':
    # f(2, 1)
    # f(3 ** 3 * 11 * 13 ** 2 * 40 ** 6, 8)
    import doctest

    doctest.testmod()

一组数中最大的最小质因数中

求旋转数字每个数中最小质因数中的最大的那几个

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
# For an example, the rotations of 14238 are
# 14238, 42381, 23814, 38142 and 81423.
# - The smallest prime factor of 14238 is 2 (14238 = 2 x 7119)
# - The smallest prime factor of 42381 is 3 (42381 = 3 x 14127)
# - The smallest prime factor of 23814 is 2 (23814 = 2 x 11907)
# - The smallest prime factor of 38142 is 2 (38142 = 2 x 19071)
# - The smallest prime factor of 81423 is 3 (81423 = 3 x 27141)
# Hence the largest number that is the smallest prime factor
# of a rotation of 14238 is 3.
#
# Leading 0s in a rotation are ignored.
#
# Solutions are output from smallest to largest.
#
# You can assume that the function is called with an integer
# at least equal to 2 as argument.


def largest_smallest_prime_factor_in_rotations(n):
    '''
    >>> largest_smallest_prime_factor_in_rotations(2)
    The largest number that is the smallest prime factor
    of a rotation of 2 is 2.
    This is for the following rotations of 2:
    2, equal to 2 x 1
    >>> largest_smallest_prime_factor_in_rotations(23509)
    The largest number that is the smallest prime factor
    of a rotation of 23509 is 50923.
    This is for the following rotations of 23509:
    50923, equal to 50923 x 1
    >>> largest_smallest_prime_factor_in_rotations(10_000)
    The largest number that is the smallest prime factor
    of a rotation of 10000 is 2.
    This is for the following rotations of 10000:
    10, equal to 2 x 5
    100, equal to 2 x 50
    1000, equal to 2 x 500
    10000, equal to 2 x 5000
    >>> largest_smallest_prime_factor_in_rotations(34305)
    The largest number that is the smallest prime factor
    of a rotation of 34305 is 3.
    This is for the following rotations of 34305:
    5343, equal to 3 x 1781
    34305, equal to 3 x 11435
    43053, equal to 3 x 14351
    >>> largest_smallest_prime_factor_in_rotations(357427)
    The largest number that is the smallest prime factor
    of a rotation of 357427 is 7.
    This is for the following rotations of 357427:
    357427, equal to 7 x 51061
    427357, equal to 7 x 61051
    574273, equal to 7 x 82039
    >>> largest_smallest_prime_factor_in_rotations(4780)
    The largest number that is the smallest prime factor
    of a rotation of 4780 is 13.
    This is for the following rotations of 4780:
    8047, equal to 13 x 619
    >>> largest_smallest_prime_factor_in_rotations(1234567)
    The largest number that is the smallest prime factor
    of a rotation of 1234567 is 191.
    This is for the following rotations of 1234567:
    2345671, equal to 191 x 12281
    '''
    smallest_prime_factor = 1
    winners = []
    # INSERT YOUR CODE HERE
    # 43053
    # 30534
    # 5343
    # 53430
    # 34305
    from math import sqrt
    from collections import defaultdict
    def f(n):
        mapping = defaultdict(int)
        while n % 2 == 0:
            mapping[2] += 1
            n //= 2
        i = 3
        while i * i <= n:
            while n % i == 0:
                mapping[i] += 1
                n //= i
            i += 2
        if n > 2:
            mapping[n] += 1
        if mapping.keys():
            return min(mapping.keys())
        else:
            return 0

    str_n = str(n)
    cur_n = []
    record = {}
    for i in range(len(str_n)):
        cur_n.append(int(str_n[i + 1:] + str_n[:i + 1]))
    for item in cur_n:
        record[item] = f(item)
        smallest_prime_factor = max(f(item), smallest_prime_factor)
    for k, v in record.items():
        if v == smallest_prime_factor:
            winners.append(k)

    winners = sorted(winners)

    print('The largest number that is the smallest prime factor\n'
          f'of a rotation of {n} is {smallest_prime_factor}.\n'
          f'This is for the following rotations of {n}:'
          )
    for winner in winners:
        print(f'{winner}, equal to',
              smallest_prime_factor, 'x', winner // smallest_prime_factor
              )


if __name__ == '__main__':
    # largest_smallest_prime_factor_in_rotations(34305)
    # largest_smallest_prime_factor_in_rotations(10_000)
    import doctest

    doctest.testmod()

最长最左连续升序字串

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
def f(word):
    '''
    Recall that if c is an ascii character then ord(c) returns its ascii code.
    Will be tested on nonempty strings of lowercase letters only.

    >>> f('x')
    The longest substring of consecutive letters has a length of 1.
    The leftmost such substring is x.
    >>> f('xy')
    The longest substring of consecutive letters has a length of 2.
    The leftmost such substring is xy.
    >>> f('ababcuvwaba')
    The longest substring of consecutive letters has a length of 3.
    The leftmost such substring is abc.
    >>> f('abbcedffghiefghiaaabbcdefgg')
    The longest substring of consecutive letters has a length of 6.
    The leftmost such substring is bcdefg.
    >>> f('abcabccdefcdefghacdef')
    The longest substring of consecutive letters has a length of 6.
    The leftmost such substring is cdefgh.
    '''
    from collections import defaultdict

    if word:
        dict_R = defaultdict(list)
        R = []
        TMP = word[0]
        for item in word[1:]:
            if ord(item) - 1 == ord(TMP[-1]):
                TMP += item
            else:
                R.append(TMP)
                TMP = item
        R.append(TMP)
        for item in R:
            dict_R[len(item)].append(item)
        longest_group = sorted(dict_R.items())[-1]
        print(f'The longest substring of consecutive letters has a length of {longest_group[0]}.')
        print(f'The leftmost such substring is {"".join(longest_group[1][0])}.')


if __name__ == '__main__':
    import doctest

    doctest.testmod()

连续素数最大间隔

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
'''
Will be tested with a at equal equal to 2 and b at most equal to 10_000_000.
'''

import sys
from math import sqrt
from itertools import compress

def sieve_of_primes_up_to(n):
    sieve = [True] * (n + 1)
    for p in range(2, round(sqrt(n)) + 1):
        if sieve[p]:
            for i in range(p * p, n + 1, p):
                sieve[i] = False
    return sieve


def f(a, b):
    '''
    >>> f(2, 2)
    There is a unique prime number beween 2 and 2.
    >>> f(2, 3)
    There are 2 prime numbers between 2 and 3.
    >>> f(2, 5)
    There are 3 prime numbers between 2 and 5.
    >>> f(4, 4)
    There is no prime number beween 4 and 4.
    >>> f(14, 16)
    There is no prime number beween 14 and 16.
    >>> f(3, 20)
    There are 7 prime numbers between 3 and 20.
    >>> f(100, 800)
    There are 114 prime numbers between 100 and 800.
    >>> f(123, 456789)
    There are 38194 prime numbers between 123 and 456789.
    >>> f(24, 78)
    There are 12 prime numbers between 24 and 78.
    >>> f(11, 56)
    There are 12 prime numbers between 11 and 56.
    >>> f(23, 534)
    There are 91 prime numbers between 23 and 534.
    >>> f(34, 3463)
    There are 474 prime numbers between 34 and 3463.
    >>> f(143, 342)
    There are 34 prime numbers between 143 and 342.
    >>> f(234, 457)
    There are 37 prime numbers between 234 and 457.
    >>> f(1000, 3434)
    There are 313 prime numbers between 1000 and 3434.
    >>> f(8933, 23414)
    There are 1497 prime numbers between 8933 and 23414.
    >>> f(2342, 235235)
    There are 20505 prime numbers between 2342 and 235235.
    >>> f(235, 3423524)
    There are 245064 prime numbers between 235 and 3423524.
    >>> f(9984, 232454)
    There are 19404 prime numbers between 9984 and 232454.
    >>> f(234554, 3423523)
    There are 224321 prime numbers between 234554 and 3423523.
    >>> f(909812, 2312414)
    There are 98351 prime numbers between 909812 and 2312414.
    >>> f(324235, 3253463)
    There are 205866 prime numbers between 324235 and 3253463.
    >>> f(3, 3125563)
    There are 225208 prime numbers between 3 and 3125563.
    >>> f(555, 5555555)
    There are 384225 prime numbers between 555 and 5555555.
    >>> f(32423, 456346)
    There are 34706 prime numbers between 32423 and 456346.
    >>> f(1, 1232553)
    There are 95234 prime numbers between 1 and 1232553.
    >>> f(9834, 435546)
    There are 35394 prime numbers between 9834 and 435546.
    >>> f(23, 4461224)
    There are 313395 prime numbers between 23 and 4461224.
    >>> f(234235, 5645747)
    There are 369351 prime numbers between 234235 and 5645747.
    >>> f(145667, 7834134)
    There are 515821 prime numbers between 145667 and 7834134.
    >>> f(672342, 9341232)
    There are 569234 prime numbers between 672342 and 9341232.
    >>> f(7823045, 9079934)
    There are 78780 prime numbers between 7823045 and 9079934.
    >>> f(13, 9998734)
    There are 664503 prime numbers between 13 and 9998734.
    '''
    # Insert your code here

    bool_list = sieve_of_primes_up_to(b)
    mapping = {}
    cnt = 2
    for item in bool_list[2:]:
        mapping[cnt] = item
        cnt += 1
    num1, num2 = 0, 0
    for k in mapping.keys():
        if mapping[k]:
            if k < a:
                num1 += 1
            num2 += 1
    nb_of_primes = num2 - num1
    if nb_of_primes == 1:
        print(f'There is a unique prime number beween {a} and {b}.')
    elif nb_of_primes == 0:
        print(f'There is no prime number beween {a} and {b}.')
    else:
        print(f'There are {nb_of_primes} prime numbers between {a} and {b}.')


if __name__ == '__main__':
    # f(13, 9998734)
    import doctest

    doctest.testmod()

数字转字符串去重

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
# A sequence of identical digits is collapsed to one digit
# in the returned integer.
#
# You can assume that the function is called with an integer
# as argument.


def collapse(number):
    '''
    >>> collapse(0)
    0
    >>> collapse(-0)
    0
    >>> collapse(9)
    9
    >>> collapse(-9)
    -9
    >>> collapse(12321)
    12321
    >>> collapse(-12321)
    -12321
    >>> collapse(-1111222232222111)
    -12321
    >>> collapse(1155523335551116111666)
    152351616
    >>> collapse(-900111212777394440300)
    -9012127394030
    '''
    # return 
    negative = 0
    if number < 0:
        number = str(number)[1:]
        negative = 1
    else:
        number = str(number)

    tmp = [number[0]]
    for item in number[1:]:
        if item != tmp[-1]:
            tmp.append(item)
        elif item == tmp[-1]:
            continue

    result = ''.join(tmp)
    if result == 0:
        return 0
    else:
        if negative == 1:
            return int(f'-{result}')
        else:
            return int(result)

    # REPLACE THE RETURN STATEMENT ABOVE WITH YOUR CODE


if __name__ == '__main__':
    # collapse(-900111212777394440300)
    import doctest

    doctest.testmod()

打印菱形

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
# You can assume that the function is called with a strictly positive
# integer as first argument and either True or False as second argument,
# if any.


def rhombus(size, shift_right=False):
    '''
    >>> rhombus(1)
    A
    >>> rhombus(1, True)
    A
    >>> rhombus(2)
     BA
    CD
    >>> rhombus(2, True)
    AB
     DC
    >>> rhombus(3)
      CBA
     DEF
    IHG
    >>> rhombus(3, True)
    ABC
     FED
      GHI
    >>> rhombus(4)
       DCBA
      EFGH
     LKJI
    MNOP
    >>> rhombus(4, True)
    ABCD
     HGFE
      IJKL
       PONM
    >>> rhombus(7)
          GFEDCBA
         HIJKLMN
        UTSRQPO
       VWXYZAB
      IHGFEDC
     JKLMNOP
    WVUTSRQ
    >>> rhombus(7, True)
    ABCDEFG
     NMLKJIH
      OPQRSTU
       BAZYXWV
        CDEFGHI
         PONMLKJ
          QRSTUVW
    '''
    number = 0

    if not shift_right:  # 字母从右向左
        for i in range(size):
            line = ''
            for j in range(size):
                line += chr(ord('A') + number % 26)
                number += 1
            if i % 2:
                print(' ' * (size - i - 1) + line, end="\n")
            else:
                print(' ' * (size - i - 1) + line[::-1], end="\n")
    else:
        for i in range(size):
            line = ''
            for j in range(size):
                line += chr(ord('A') + number % 26)
                number += 1
            if i % 2:
                print(' ' * (i) + line[::-1], end="\n")
            else:
                print(' ' * (i) + line, end="\n")


# REPLACE PASS ABOVE WITH YOUR CODE


if __name__ == '__main__':
    import doctest

    doctest.testmod()

普通三角形

正常三角形

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
'''
Will be tested with height a strictly positive integer.
'''


def f(height):
    '''
    >>> f(1)
    0
    >>> f(2)
     0
    123
    >>> f(3)
      0
     123
    45678
    >>> f(4)
       0
      123
     45678
    9012345
    >>> f(5)
        0
       123
      45678
     9012345
    678901234
    >>> f(6)
         0
        123
       45678
      9012345
     678901234
    56789012345
    >>> f(20)
                       0
                      123
                     45678
                    9012345
                   678901234
                  56789012345
                 6789012345678
                901234567890123
               45678901234567890
              1234567890123456789
             012345678901234567890
            12345678901234567890123
           4567890123456789012345678
          901234567890123456789012345
         67890123456789012345678901234
        5678901234567890123456789012345
       678901234567890123456789012345678
      90123456789012345678901234567890123
     4567890123456789012345678901234567890
    123456789012345678901234567890123456789
    '''
    # Insert your code here
    cnt = 0
    for i in range(height):
        print(" " * (height - i - 1), end="")
        for j in range(2 * i + 1):
            print(cnt % 10, end="")
            cnt += 1
        print()


if __name__ == '__main__':
    import doctest

    doctest.testmod()

倒立三角形

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
def f(height):
    '''
    >>> f(1)
    0
    >>> f(2)
    101
     0
    >>> f(3)
    21012
     101
      0
    >>> f(5)
    432101234
     3210123
      21012
       101
        0
    >>> f(10)
    9876543210123456789
     87654321012345678
      765432101234567
       6543210123456
        54321012345
         432101234
          3210123
           21012
            101
             0
    >>> f(15)
    43210987654321012345678901234
     321098765432101234567890123
      2109876543210123456789012
       10987654321012345678901
        098765432101234567890
         9876543210123456789
          87654321012345678
           765432101234567
            6543210123456
             54321012345
              432101234
               3210123
                21012
                 101
                  0
    >>> f(26)
    543210987654321098765432101234567890123456789012345
     4321098765432109876543210123456789012345678901234
      32109876543210987654321012345678901234567890123
       210987654321098765432101234567890123456789012
        1098765432109876543210123456789012345678901
         09876543210987654321012345678901234567890
          987654321098765432101234567890123456789
           8765432109876543210123456789012345678
            76543210987654321012345678901234567
             654321098765432101234567890123456
              5432109876543210123456789012345
               43210987654321012345678901234
                321098765432101234567890123
                 2109876543210123456789012
                  10987654321012345678901
                   098765432101234567890
                    9876543210123456789
                     87654321012345678
                      765432101234567
                       6543210123456
                        54321012345
                         432101234
                          3210123
                           21012
                            101
                             0
    '''
    # Insert your code here
    for row in range(height, 0, -1):
        print(" " * (height - row), end="")
        for col in range(row - 1, 0, -1):
            print(col % 10, end="")
        for col in range(row):
            print(col % 10, end="")
        print()


if __name__ == '__main__':
    import doctest
    doctest.testmod()
    # f(26)

有难度的三角形

字母表三角形，中轴线字母表顺序，延中轴线展开

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
''' ord(c) returns the encoding of character c.
    chr(e) returns the character encoded by e.
'''


def f(n):
    '''
    >>> f(1)
    A
    >>> f(2)
     A
    CBC
    >>> f(3)
      A
     CBC
    EDCDE
    >>> f(4)
       A
      CBC
     EDCDE
    GFEDEFG
    >>> f(30)
                                 A
                                CBC
                               EDCDE
                              GFEDEFG
                             IHGFEFGHI
                            KJIHGFGHIJK
                           MLKJIHGHIJKLM
                          ONMLKJIHIJKLMNO
                         QPONMLKJIJKLMNOPQ
                        SRQPONMLKJKLMNOPQRS
                       UTSRQPONMLKLMNOPQRSTU
                      WVUTSRQPONMLMNOPQRSTUVW
                     YXWVUTSRQPONMNOPQRSTUVWXY
                    AZYXWVUTSRQPONOPQRSTUVWXYZA
                   CBAZYXWVUTSRQPOPQRSTUVWXYZABC
                  EDCBAZYXWVUTSRQPQRSTUVWXYZABCDE
                 GFEDCBAZYXWVUTSRQRSTUVWXYZABCDEFG
                IHGFEDCBAZYXWVUTSRSTUVWXYZABCDEFGHI
               KJIHGFEDCBAZYXWVUTSTUVWXYZABCDEFGHIJK
              MLKJIHGFEDCBAZYXWVUTUVWXYZABCDEFGHIJKLM
             ONMLKJIHGFEDCBAZYXWVUVWXYZABCDEFGHIJKLMNO
            QPONMLKJIHGFEDCBAZYXWVWXYZABCDEFGHIJKLMNOPQ
           SRQPONMLKJIHGFEDCBAZYXWXYZABCDEFGHIJKLMNOPQRS
          UTSRQPONMLKJIHGFEDCBAZYXYZABCDEFGHIJKLMNOPQRSTU
         WVUTSRQPONMLKJIHGFEDCBAZYZABCDEFGHIJKLMNOPQRSTUVW
        YXWVUTSRQPONMLKJIHGFEDCBAZABCDEFGHIJKLMNOPQRSTUVWXY
       AZYXWVUTSRQPONMLKJIHGFEDCBABCDEFGHIJKLMNOPQRSTUVWXYZA
      CBAZYXWVUTSRQPONMLKJIHGFEDCBCDEFGHIJKLMNOPQRSTUVWXYZABC
     EDCBAZYXWVUTSRQPONMLKJIHGFEDCDEFGHIJKLMNOPQRSTUVWXYZABCDE
    GFEDCBAZYXWVUTSRQPONMLKJIHGFEDEFGHIJKLMNOPQRSTUVWXYZABCDEFG
    '''
    if n < 1:
        return

    from collections import defaultdict
    dict_alp = defaultdict(str)
    cnt = 0
    for value in range(65, 91):
        dict_alp[cnt] = chr(value)
        cnt += 1

    for i in range(n):
        print(" " * (n - i - 1), end="")
        # middle_element=dict_alp[i%26]
        for j in range(i, 0, -1):
            print(dict_alp[(i % 26 + j) % 26], end="")
        for j in range(i + 1):
            print(dict_alp[(i % 26 + j) % 26], end="")
        print()


if __name__ == '__main__':
    # f(30)
    import doctest

    doctest.testmod()

按列打印三角形

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
# Hint: To avoid arithmetic computations, zip columns.
#
# count, from itertools, can be used to push arithmetic laziness
# even further...
#
# You can assume that the function is called with height
# a strictly positive integer.


from itertools import count


def triangle(height):
    '''
    >>> triangle(1)
    A
    >>> triangle(2)
    A
    B
    >>> triangle(3)
    A
    B D
    C
    >>> triangle(4)
    A
    B E
    C F
    D
    >>> triangle(5)
    A
    B F
    C G I
    D H
    E
    >>> triangle(6)
    A
    B G
    C H K
    D I L
    E J
    F
    >>> triangle(7)
    A
    B H
    C I M
    D J N P
    E K O
    F L
    G
    >>> triangle(8)
    A
    B I
    C J O
    D K P S
    E L Q T
    F M R
    G N
    H
    >>> triangle(9)
    A
    B J
    C K Q
    D L R V
    E M S W Y
    F N T X
    G O U
    H P
    I
    >>> triangle(10)
    A
    B K
    C L S
    D M T Y
    E N U Z C
    F O V A D
    G P W B
    H Q X
    I R
    J
    >>> triangle(11)
    A
    B L
    C M U
    D N V B
    E O W C G
    F P X D H J
    G Q Y E I
    H R Z F
    I S A
    J T
    K
    '''
    # pass 11 9 7 5 3 1
    # '''
    # 构造
    # A B C D
    #   E F
    #    G
    # :param height:
    # :return:
    # '''
    from itertools import zip_longest

    cnt = 0
    tmp = []
    while height > 0:
        line = ''
        # height 11 9 7 5...
        for h in range(height):
            line += chr(ord('A') + cnt % 26)
            cnt += 1
        tmp.append(' ' * len(tmp) + line)  # tmp列表 0个元素0个空格，1个空格1个元素
        height -= 2
    for item in zip_longest(*tmp, fillvalue=" "):
        print(' '.join(item).strip())

    # REPLACE THE PASS STATEMENT ABOVE WITH YOUR CODE


if __name__ == '__main__':
    # triangle(10)
    # triangle(11)
    import doctest

    doctest.testmod()

打印长方形

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
# ord(c) returns the encoding of character c.
# chr(e) returns the character encoded by e.


def rectangle(width, height):
    '''
    Displays a rectangle by outputting lowercase letters, starting with a,
    in a "snakelike" manner, from left to right, then from right to left,
    then from left to right, then from right to left, wrapping around when z is reached.

    >>> rectangle(1, 1)
    a
    >>> rectangle(2, 3)
    ab
    dc
    ef
    >>> rectangle(3, 2)
    abc
    fed
    >>> rectangle(17, 4)
    abcdefghijklmnopq
    hgfedcbazyxwvutsr
    ijklmnopqrstuvwxy
    ponmlkjihgfedcbaz
    '''
    from collections import defaultdict
    dict_alp = defaultdict(str)
    cnt = 0
    num_lst = []
    for k in range(97, 123):
        dict_alp[cnt] = chr(k)
        cnt += 1

    for i in range(width * height):
        num_lst.append(dict_alp[i % 26])

    len_single_line = len(num_lst) // height
    cnt = 0
    for h in range(height):
        if h % 2 == 0:
            print(''.join(num_lst[cnt:cnt + len_single_line]))
        else:
            print(''.join(num_lst[cnt:cnt + len_single_line][::-1]))
        cnt = cnt + len_single_line

    # REPLACE THE PREVIOUS LINE WITH YOUR CODE


if __name__ == '__main__':
    # rectangle(17, 4)
    import doctest

    doctest.testmod()

按列打印矩形也许不完整

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
# Will be tested only with strictly positive integers for
# total_nb_of_letters and height.
#
# <BLANKLINE> is not output by the program, but
# doctest's way to refer to an empty line.
# For instance,
#    A
#    B
#    C
#    <BLANKLINE>
#    <BLANKLINE>
# means that 5 lines are output: first a line with A,
# then a line with B, then a line with C,
# and then 2 empty lines.
#
# Note that no line has any trailing space.

def f(total_nb_of_letters, height):
    '''
    >>> f(4, 1)
    ABCD
    >>> f(3, 5)
    A
    B
    C
    <BLANKLINE>
    <BLANKLINE>
    >>> f(4, 2)
    AD
    BC
    >>> f(5, 2)
    ADE
    BC
    >>> f(6, 2)
    ADE
    BCF
    >>> f(7, 2)
    ADE
    BCFG
    >>> f(8, 2)
    ADEH
    BCFG
    >>> f(9, 2)
    ADEHI
    BCFG
    >>> f(17,5)
    AJK
    BIL
    CHM
    DGNQ
    EFOP
    >>> f(100, 6)
    ALMXYJKVWHITUFGRS
    BKNWZILUXGJSVEHQT
    CJOVAHMTYFKRWDIPU
    DIPUBGNSZELQXCJOV
    EHQTCFORADMPYBKN
    FGRSDEPQBCNOZALM
    '''
    # INSERT YOUR CODE HERE
    '''
    构造
    ABCDEF
    LKJIHG
    MOPQRS
    
    '''
    from itertools import zip_longest
    cnt = 0
    cnt_i = 0
    tmp = []
    i = 0
    flag = 0
    if total_nb_of_letters % height:
        amount = (total_nb_of_letters // height + 1) * height
    else:
        amount = total_nb_of_letters
    while i < total_nb_of_letters:
        line = ''
        for h in range(height):
            if flag == 0 and flag == 0:
                line += chr(ord('A') + cnt % 26)
            cnt += 1
            if amount > cnt >= total_nb_of_letters:
                line += '0'
                flag = 1
        if cnt_i % 2:
            line = line[::-1]
        cnt_i += 1
        tmp.append(line)
        i += len(line)
    for item in zip_longest(*tmp):
        print(''.join(' ' if x == '0' else x for x in item).strip())


if __name__ == '__main__':
    # f(17, 5)
    import doctest

    doctest.testmod()

制表蛇形遍历

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
143
144
145
146
147
148
149
150
151
152
# Takes two strings (words) as arguments and checks
# that both consist of nothing but uppercase letters.
#
# If that is the case,
# - displays the first word horizontally,
# - displays the second word vertically,
# - displays 0 at the intersection of a row and a column
#   where the letters are different,
# - displays i at the intersection of a row and a column
#   where the letters are the same and this happens for
#   the i-th time,
#   - processing the first row from left to right,
#   - processing the second row from right to left,
#   - processing the third row from left to right,
#   - processing the fourth row from right to left,
#   - ...
# The number of digits in the maximum number i determines
# the width of columns as shown in the sample tests.
#
# You can assume that both arguments are strings.


def f(word_1, word_2):
    '''
    >>> f('AB', 'C2D')
    Both arguments should consist of nothing but uppercase letters.
    >>> f('Aa', 'BB')
    Both arguments should consist of nothing but uppercase letters.
    >>> f('AB', '')
    >>> f('AB', 'CD')
      A B
    C 0 0
    D 0 0
    >>> f('AA', 'A')
      A A
    A 1 2
    >>> f('AAA', 'AAAA')
       A  A  A
    A  1  2  3
    A  6  5  4
    A  7  8  9
    A 12 11 10
    >>> f('AAAAAAAAAAAAAAA', 'AAAAAAAA')
        A   A   A   A   A   A   A   A   A   A   A   A   A   A   A
    A   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
    A  30  29  28  27  26  25  24  23  22  21  20  19  18  17  16
    A  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45
    A  60  59  58  57  56  55  54  53  52  51  50  49  48  47  46
    A  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75
    A  90  89  88  87  86  85  84  83  82  81  80  79  78  77  76
    A  91  92  93  94  95  96  97  98  99 100 101 102 103 104 105
    A 120 119 118 117 116 115 114 113 112 111 110 109 108 107 106
    >>> f('ABC', 'BCD')
      A B C
    B 0 1 0
    C 0 0 2
    D 0 0 0
    >>> f('ABBC', 'BCDECB')
      A B B C
    B 0 1 2 0
    C 0 0 0 3
    D 0 0 0 0
    E 0 0 0 0
    C 0 0 0 4
    B 0 6 5 0
    >>> f('ABABCDCD', 'ABDEABDE')
       A  B  A  B  C  D  C  D
    A  1  0  2  0  0  0  0  0
    B  0  4  0  3  0  0  0  0
    D  0  0  0  0  0  5  0  6
    E  0  0  0  0  0  0  0  0
    A  7  0  8  0  0  0  0  0
    B  0 10  0  9  0  0  0  0
    D  0  0  0  0  0 11  0 12
    E  0  0  0  0  0  0  0  0
    '''
    # INSERT YOUR CODE HERE
    import numpy as np
    # check
    if not word_1 or not word_2:
        return
    elif not str(word_1).isalpha() or not str(word_2).isalpha() or not str(word_1).isupper() or not str(
            word_2).isupper():
        print('Both arguments should consist of nothing but uppercase letters.')
        return

    # solution
    length_word1 = len(word_1)
    length_word2 = len(word_2)
    # grid=[[0 for _ in range(length_word2)] for _ in range(length_word1)]
    new_grid = [[0 for _ in range(length_word1 + 1)] for _ in range(length_word2 + 1)]

    for idx1 in range(length_word2):
        for idx2 in range(length_word1):
            if word_2[idx1] == word_1[idx2]:
                if idx1 + 1 < len(new_grid) and idx2 + 1 < len(new_grid[0]):
                    new_grid[idx1 + 1][idx2 + 1] = 1

    # for item in new_grid:
    #    print(item)
    # '''
    #  AAAAAAAAAAAAAA
    # A
    # A
    # A
    # A
    # A
    # '''
    x = np.array(new_grid)
    cnt = 1
    height = 0
    for line in x[1:, 1:]:
        #  print(line)
        if height % 2 == 0:
            for idx in range(len(line)):
                if line[idx] == 1:
                    line[idx] = cnt
                    cnt += 1
        else:
            for idx in range(len(line)):
                if line[len(line) - idx - 1] == 1:
                    line[len(line) - idx - 1] = cnt
                    cnt += 1
        height += 1

    max_length = len(str(cnt))
    new_grid = x.tolist()

    new_grid[0][1:] = [x for x in str(word_1)]
    for i in range(1, len(new_grid)):
        new_grid[i][0] = word_2[i - 1]

    for idx1 in range(length_word2):
        for idx2 in range(length_word1):
            pass

    new_grid[0][0] = '*'

    result = []
    for line in new_grid:
        result.append(' '.join(f'{str(x):>{max_length}}' for x in line).lstrip())
    for item in result:
        print(item.replace('*', ' '))


if __name__ == '__main__':
    # f('ABABCDCD', 'ABDEABDE')
    # f('AAAAAAAAAAAAAAA', 'AAAAAAAA')
    import doctest

    doctest.testmod()

几个数列表全共有的元素的平均值

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
def average_of_digits_common_to(*numbers):
    '''
    If there are no numbers, or if the numbers have no digits in common,
    then returns -1.
    Else, returns the average of the digits common to all numbers
    (each common digit being counted only once).

    You can assume that numbers are all valid non-negative integers.

    >>> average_of_digits_common_to()
    -1
    >>> average_of_digits_common_to(0, 12, 456)
    -1
    >>> average_of_digits_common_to(223444)
    3.0
    >>> average_of_digits_common_to(135, 567)
    5.0
    >>> average_of_digits_common_to(234, 345, 2345, 3456, 112233445566)
    3.5
    >>> average_of_digits_common_to(932932, 139139, 395395395)
    6.0
    >>> average_of_digits_common_to(3136823, 665537857, 8363265, 35652385)
    5.666666666666667
    '''
    # print(27/6)
    dict_num = {}
    if len(numbers) == 0:
        return -1
    r = ''
    for item in numbers:
        r += str(item)
    if len(r) == len(set(r)):
        return -1

    for i in range(10):
        dict_num[i] = all(str(x).count(str(i)) for x in numbers)
    num = 0
    result = 0
    for k, v in dict_num.items():
        if v:
            result += k
            num += 1
    return result / num

# REPLACE "return" ABOVE WITH YOUR CODE

if __name__ == '__main__':
    # average_of_digits_common_to(3136823, 665537857, 8363265, 35652385)
    import doctest

    doctest.testmod()

过滤序列

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
def filtered_sequence(L, n):
    '''
    Returns a list LL that keeps from L all elements e
    that are part of a sub-sequence of length at least n.

    All elements of the sub-sequence have the same value as e.

    You can assume that L is a list of valid integers.

    >>> filtered_sequence([], 2)
    []
    >>> filtered_sequence([7], 0)
    [7]
    >>> filtered_sequence([7], 1)
    [7]
    >>> filtered_sequence([7], 2)
    []
    >>> filtered_sequence([1, 3, 1, 2, 5, 6, 8, 2], 1)
    [1, 3, 1, 2, 5, 6, 8, 2]
    >>> filtered_sequence([1, 3, 3, 3, 2, 4, 4, 5, 6, 6, 6, 6], 2)
    [3, 3, 3, 4, 4, 6, 6, 6, 6]
    >>> filtered_sequence([7, 7, 7, 7, 2, 2, 7, 3, 4, 4, 4, 6, 5], 3)
    [7, 7, 7, 7, 4, 4, 4]
    >>> filtered_sequence([1, 1, 1, 1, 5, 5, 1, 1, 1, 1, 5, 5, 5, 5, 5, 6], 4)
    [1, 1, 1, 1, 1, 1, 1, 1, 5, 5, 5, 5, 5]
    '''

    LL = []
    # INSERT YOUR CODE HERE
    mapping_numbers = {}
    if L:
        tmp = [L[0]]
        number = 0
        cnt = 1
        for item in L[1:]:
            if item == tmp[-1]:
                tmp.append(item)
                cnt += 1
            else:
                mapping_numbers[number] = (tmp[-1], cnt)
                tmp = [item]
                number += 1
                cnt = 1
        mapping_numbers[number] = (tmp[-1], cnt)

        target_lst = [(x[0], x[1]) for x in mapping_numbers.values() if x[1] >= n]

        for item in target_lst:
            line = str(item[0]) * item[1]
            LL.extend(line)

        LL = [int(x) for x in LL]
    else:
        return []

    return LL


if __name__ == '__main__':
    # filtered_sequence([1, 3, 3, 3, 2, 4, 4, 5, 6, 6, 6, 6], 2)
    import doctest

    doctest.testmod()

找规律

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
from random import seed, randint
from collections import defaultdict
import sys


# R is the list of lists of members of L that all end in the same digit,
# with duplicates removed,
# - longer lists coming before shorter lists,
# - the list associated with m as last digit coming before
#   the list associated with n as last digit if both lists
#   have the same length and m > n,
# - within a given list,
#   - longer numbers (as measured by their number of digits) coming before
#     shorter numbers,
#   - numbers of the same length keeping the order of
#     their first occurrences within L.
#
# For instance, take L equal to
# [26, 1, 66, 94, 4, 20, 30, 2, 7, 87, 18, 88, 47]
# - Three numbers end in 7, whereas only two numbers end in 6,
#   which explains why [87, 47, 7] comes before [26, 66] in R.
# - Two numbers end in 6 and two numbers end in 4; also, 6 is greater
#   than 4, which explains why [26, 66] comes before [94, 4] in R.
# - 87 and 47 have two digits, where 7 has only one digit,
#   which explains why 87 and 47 come before 7 in [87, 47, 7].
# - The first (unique in this case) occurrence of 87 comes before
#   the first (unique in this case) occurrence of 47 in L,
#   which explains why 87 comes before 47 in [87, 47, 7].

def f(arg_for_seed, nb_of_elements, max_element):
    '''
    >>> f(1, 12, 1)
    Here is L: [0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0]
    Here is R: [[1], [0]]
    >>> f(3, 15, 8)
    Here is L: [3, 8, 2, 5, 7, 1, 0, 7, 4, 8, 3, 3, 7, 8, 8]
    Here is R: [[8], [7], [5], [4], [3], [2], [1], [0]]
    >>> f(6, 12, 50)
    Here is L: [50, 36, 5, 31, 48, 16, 2, 0, 9, 42, 37, 30]
    Here is R: [[50, 30, 0], [36, 16], [42, 2], [9], [48], [37], [5], [31]]
    >>> f(9, 8, 5000)
    Here is L: [3792, 3058, 2188, 1134, 1524, 52, 2771, 4118]
    Here is R: [[3058, 2188, 4118], [1134, 1524], [3792, 52], [2771]]
    >>> f(12, 15, 30)
    Here is L: [15, 8, 21, 16, 21, 11, 4, 12, 0, 11, 15, 8, 20, 25, 14]
    Here is R: [[15, 25], [14, 4], [21, 11], [20, 0], [8], [16], [12]]
    >>> f(15, 13, 100)
    Here is L: [26, 1, 66, 94, 4, 20, 30, 2, 7, 87, 18, 88, 47]
    Here is R: [[87, 47, 7], [18, 88], [26, 66], [94, 4], [20, 30], [2], [1]]
    '''
    if nb_of_elements < 1:
        sys.exit(0)
    seed(arg_for_seed)
    L = [randint(0, max_element) for _ in range(nb_of_elements)]

    R = []
    # INSERT YOUR CODE HERE
    print(f'Here is L: {L}')

    mapping = defaultdict(list)

    for item in L:
        if item not in mapping[str(item)[-1]]:
            mapping[str(item)[-1]].append(item)

    mapping = dict(sorted(mapping.items(), key=lambda x: (len(x[1]), x[0])))

    for key, item in mapping.items():
        mapping[key] = sorted(item, key=lambda x: (len(str(x))), reverse=True)

    print(f'Here is R: {list(mapping.values())[::-1]}')


if __name__ == '__main__':
    # f(15, 13, 100)
    import doctest

    doctest.testmod()

第一个出现第二个出现

排序好的列表，通过取首尾的元素构成序列

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
143
144
145
146
147
148
149
150
151
152
153
from random import seed, shuffle


# Generates a list L consisting of all integers
# between 0 and nb_of_elements - 1, in some random order.
#
# Consider the following lists with at least 2 elements:
# - the members of L from L's smallest element
#   to L's largest element,
#   read from left to right if the former occurs before the latter in L,
#   read from right to left if the former occurs after the latter in L;
# - the members of L from L's second smallest element
#   to L's second largest element,
#   read from left to right if the former occurs before the latter in L,
#   read from right to left if the former occurs after the latter in L;
# - the members of L from L's third smallest element
#   to L's third largest element,
#   read from left to right if the former occurs before the latter in L,
#   read from right to left if the former occurs after the latter in L.
#
# Outputs those lists preceded with some text, that explains the order
# in which they are output.
#
# Note that <BLANKLINE> is doctest's way to express that your code
# should produce a blank line; do not let your code print out <BLANKLINE>...
#
# You can assume that the function is called with integers as arguments.


def f(arg_for_seed, nb_of_elements):
    '''
    >>> f(0, 1)
    Here is L: [0]
    Sequences will appear from shortest to longest.
    >>> f(0, 2)
    Here is L: [0, 1]
    Sequences will appear from shortest to longest.
    Ordered from smallest to largest sum,
    and for a given sum from smallest to largest first element,
    there are sequences of length 2, namely:
        [0, 1] (sum is 1)
    >>> f(0, 3)
    Here is L: [0, 2, 1]
    Sequences will appear from shortest to longest.
    Ordered from smallest to largest sum,
    and for a given sum from smallest to largest first element,
    there are sequences of length 2, namely:
        [0, 2] (sum is 2)
    >>> f(0, 4)
    Here is L: [2, 0, 1, 3]
    Sequences will appear from shortest to longest.
    Ordered from smallest to largest sum,
    and for a given sum from smallest to largest first element,
    there are sequences of length 3, namely:
        [1, 0, 2] (sum is 3)
        [0, 1, 3] (sum is 4)
    >>> f(0, 5)
    Here is L: [2, 1, 0, 4, 3]
    Sequences will appear from shortest to longest.
    Ordered from smallest to largest sum,
    and for a given sum from smallest to largest first element,
    there are sequences of length 2, namely:
        [0, 4] (sum is 4)
    <BLANKLINE>
    Ordered from smallest to largest sum,
    and for a given sum from smallest to largest first element,
    there are sequences of length 4, namely:
        [1, 0, 4, 3] (sum is 8)
    >>> f(0, 6)
    Here is L: [4, 2, 1, 0, 5, 3]
    Sequences will appear from shortest to longest.
    Ordered from smallest to largest sum,
    and for a given sum from smallest to largest first element,
    there are sequences of length 2, namely:
        [0, 5] (sum is 5)
    <BLANKLINE>
    Ordered from smallest to largest sum,
    and for a given sum from smallest to largest first element,
    there are sequences of length 3, namely:
        [1, 2, 4] (sum is 7)
    <BLANKLINE>
    Ordered from smallest to largest sum,
    and for a given sum from smallest to largest first element,
    there are sequences of length 5, namely:
        [2, 1, 0, 5, 3] (sum is 11)
    >>> f(0, 12)
    Here is L: [1, 9, 8, 5, 10, 2, 3, 7, 4, 0, 11, 6]
    Sequences will appear from shortest to longest.
    Ordered from smallest to largest sum,
    and for a given sum from smallest to largest first element,
    there are sequences of length 2, namely:
        [0, 11] (sum is 11)
        [4, 7] (sum is 11)
    <BLANKLINE>
    Ordered from smallest to largest sum,
    and for a given sum from smallest to largest first element,
    there are sequences of length 5, namely:
        [3, 2, 10, 5, 8] (sum is 28)
        [1, 9, 8, 5, 10] (sum is 33)
        [2, 10, 5, 8, 9] (sum is 34)
    <BLANKLINE>
    Ordered from smallest to largest sum,
    and for a given sum from smallest to largest first element,
    there are sequences of length 9, namely:
        [5, 10, 2, 3, 7, 4, 0, 11, 6] (sum is 48)
    '''
    if nb_of_elements < 1:
        return
    L = list(range(nb_of_elements))
    seed(arg_for_seed)
    shuffle(L)
    print('Here is L:', L)
    # INSERT YOUR CODE HERE

    print('Sequences will appear from shortest to longest.')

    sorted_l = sorted(L)
    r = []
    for idx in range(len(sorted_l) // 2):
        small, big = sorted_l[idx], sorted_l[len(sorted_l) - idx - 1]

        if L.index(small) < L.index(big):
            r.append(L[L.index(small):L.index(big) + 1])
        elif L.index(small) > L.index(big):
            r.append(L[L.index(big):L.index(small) + 1][::-1])
    from collections import defaultdict
    mapping = defaultdict(list)

    for item in r:
        mapping[len(item)].append(item)

    for k, v in mapping.items():
        mapping[k] = sorted(v, key=sum)

    cnt = 1
    for k, v in mapping.items():
        print('Ordered from smallest to largest sum,')
        print('and for a given sum from smallest to largest first element,')
        print(f'there are sequences of length {k}, namely:')
        for item in v:
            print(f'    {item} (sum is {sum(item)})')
        if cnt < len(mapping.keys()):
            print()

        cnt += 1


if __name__ == '__main__':
    # f(0, 12)
    import doctest

    doctest.testmod()

读文件1

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
# The words in the file are supposed to consist of nothing but letters
# (no apostrophes, no hyphens...), possibly immediately followed by
# a single full stop, exclamation mark, question mark,
# comma, colon or semicolon.
#
# There can be any amount of space anywhere between words, before the
# first word, and after the last word.
#
# We do not distinguish between words that only differ in cases.
# For instance, millionaires, Millionaires, MILLIONAIRES are
# 3 variants of the same word.
#
# You can assume that filename is the name of a file that exists
# in the working directory. Do NOT use an absolute path.
#
# The words of length greater than 2 are checked against the contents
# of dictionary.txt, also assumed to be stored in the working directory.
# Here too, do NOT use an absolute path.
#
# Unknown words (that is, words of length greater than 2 that are
# not found in dictionary.txt) are output only once, in capitalised form,
# in lexicographic order for each group, a group consisting of words
# all of the same length.
# Groups for shorter words are output before groups for longer words.

# Note that no tab is output anywhere, just single spaces.


from collections import defaultdict


def unknown_words(filename):
    '''
    >>> unknown_words('edgar_poe_1.txt')
    There are no unknown words of length greater than 2.
    >>> unknown_words('edgar_poe_2.txt')
    There are unknown words of length greater than 2.
      - Of length 8:
          Practise
      - Of length 9:
          Fortunato
          Imposture
          Redresser
      - Of length 10:
          Immolation
      - Of length 11:
          Unredressed
      - Of length 12:
          Definitively
      - Of length 14:
          Definitiveness
      - Of length 15:
          Connoisseurship
    >>> unknown_words('oscar_wild_1.txt')
    There are no unknown words of length greater than 2.
    >>> unknown_words('oscar_wild_2.txt')
    There are unknown words of length greater than 2.
      - Of length 5:
          Renan
      - Of length 7:
          Realise
      - Of length 8:
          Flaubert
      - Of length 10:
          Neighbours
      - Of length 11:
          Misdirected
    '''
    with open('dictionary.txt') as dictionary:
        dict_words = set()
        for line in dictionary:
            if line.isspace():
                continue
            dict_words.add(line.strip())
        list_words = list(dict_words)
    # print(list_words)
    lines = []
    words = []
    with open(filename) as file:
        for line in file:
            if line.isspace():
                continue
            lines.append(line.strip())
    for single_line in lines:
        single_line = single_line.replace(',', '').replace(';', '').replace('!', ' ').replace('?', ' ').replace('.',
                                                                                                                ' ')
        words.append(single_line.split())
    R = defaultdict(list)
    for item in words:
        for single_word in item:
            # print(single_word.upper())
            if single_word.upper() not in list_words and len(single_word) > 2:
                R[len(single_word)].append(single_word.capitalize())

    if R:
        print('There are unknown words of length greater than 2.')
        for k, v in sorted(R.items(), key=lambda x: x[0]):
            print(f'  - Of length {k}:')
            for item in sorted(list(set(v))):
                print(f'      {item}')
    else:
        print('There are no unknown words of length greater than 2.')
    # REPLACE THE PASS STATEMENT ABOVE WITH YOUR CODE


if __name__ == '__main__':
    # unknown_words('oscar_wild_2.txt')
    import doctest

    doctest.testmod()

读文件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
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
from collections import defaultdict


# The words in the file are supposed to consist of nothing but letters
# (no apostrophes, no hyphens...), possibly immediately followed by
# a single full stop, exclamation mark, question mark,
# comma, colon or semicolon.
#
# A sentence ends in a full stop, an exclamation mark or a question mark
# (neither in a comma nor in a colon nor in a semicolon).
#
# There can be any amount of space anywhere between words, before the
# first word, and after the last word.
#
# We do not distinguish between words that only differ in cases.
# For instance, millionaires, Millionaires, MILLIONAIRES are
# 3 variants of the same word.
#
# The enumeration of sentences starts with 1.
# Within a given sentence, the enumeration of words starts with 1.
#
# It should all happen naturally, but for a given spotted word:
# - Smaller sentence numbers come before larger sentence numbers.
# - For a given sentence, smaller word numbers come before
#   larger word numbers.
#
# You can assume that filename is the name of a file that exists
# in the working directory. Do NOT use absolute paths.
#
# The code that is already written makes sure that spotted words
# are output in capitalised form, and in lexicographic order, so
# you do not have to take care of it.

def longest_words(filename):
    '''
    >>> longest_words('edgar_poe_1.txt')
    Connoisseurship:
        Spotted as word number 6 in sentence number 10.
    >>> longest_words('edgar_poe_2.txt')
    Retribution:
        Spotted as word number 6 in sentence number 4.
    Unredressed:
        Spotted as word number 4 in sentence number 4.
        Spotted as word number 4 in sentence number 5.
    >>> longest_words('oscar_wild_1.txt')
    Establishment:
        Spotted as word number 9 in sentence number 1.
    Individualism:
        Spotted as word number 17 in sentence number 23.
    Sentimentally:
        Spotted as word number 12 in sentence number 9.
    >>> longest_words('oscar_wild_2.txt')
    Incomparable:
        Spotted as word number 78 in sentence number 1.
        Spotted as word number 83 in sentence number 1.
    Intelligence:
        Spotted as word number 11 in sentence number 6.
    Surroundings:
        Spotted as word number 28 in sentence number 12.
    '''
    longest_words = defaultdict(list)
    line_nb = 0
    word_nb = -1
    # POSSIBLY MODIFY THE PREVIOUS TWO LINE AND INSERT YOUR CODE HERE
    with open(filename) as file:
        lines = ''
        for line in file:
            if line.isspace():
                continue
            lines += " " + line.strip()

        lines = lines.replace(';', '').replace(',', '').replace('?', '.').replace('!', '.')
        lines_group = lines.split('.')
        mapping = defaultdict(list)
        for single_line in lines_group:
            line_nb += 1
            words = single_line.split()
            tmp = []
            no = 1
            for word in words:
                tmp.append((no, word))
                no += 1

            ordered_tmp = sorted(tmp, key=lambda x: len(x[1]))
            if ordered_tmp:
                cur_max_length = len(ordered_tmp[-1][1])

            for item in ordered_tmp[::-1]:
                if len(item[1]) == cur_max_length:
                    mapping[item[1].lower()].append((line_nb, item[0]))
                else:
                    break
    max_length = max(len(x) for x in mapping.keys())
    for k, v in mapping.items():
        if len(k) == max_length:
            longest_words[k] = sorted(v, key=lambda x: x[1])

    for word in sorted(longest_words):
        print(f'{word.capitalize()}:')
        for (sentence_nb, word_nb) in longest_words[word]:
            print(f'    Spotted as word number {word_nb} in sentence '
                  f'number {sentence_nb}.'
                  )


if __name__ == '__main__':
    # longest_words('oscar_wild_1.txt')
    import doctest

    doctest.testmod()

读文件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
# Returns the list of all words in dictionary.txt, expected to be
# stored in the working directory, whose length is minimal and that
# contain all letters in "word", in the same order
# (so if "word" is of the form c_1c_2...c_n, the solution is the list
# of words of minimal length in dictionary.txt that are of the form
# *c_1*c_2*...*c_n* where each occurrence of * denotes any (possibly
# empty) sequence of letters.
#
# The words in the returned list are given in lexicographic order
# (in the order they occur in dictionary.txt).
#
# You can assume that "word" is a nonempty string of nothing but
# uppercase letters.


def f(word):
    '''
    >>> f('QWERTYUIOP')
    []
    >>> f('KIOSKS')
    []
    >>> f('INDUCTIVELY')
    ['INDUCTIVELY']
    >>> f('ITEGA')
    ['INTEGRAL']
    >>> f('ARON')
    ['AARON', 'AKRON', 'APRON', 'ARGON', 'ARSON', 'BARON']
    >>> f('EOR')
    ['EMORY', 'ERROR', 'TENOR']
    >>> f('AGAL')
    ['ABIGAIL', 'MAGICAL']
    '''
    from collections import defaultdict

    with open('dictionary.txt') as dictionary:
        mapping = defaultdict(list)
        for line in dictionary:
            start_index = 0
            for item in word:
                start_index = line.find(item, start_index)
                if start_index == -1:
                    break
            else:
                length_of_line = len(line)
                mapping[length_of_line].append(line.strip())

    if mapping:
        min_keys = min(mapping.keys())
        return mapping[min_keys]
    else:
        return []

        # REPLACE return [] ABOVE WITH YOUR CODE


if __name__ == '__main__':
    # f('AGAL')
    import doctest

    doctest.testmod()

快来参与讨论吧~