2020-04
20

更爽

By xrspook @ 12:00:26 归类于: 扮IT

战胜参考答案从昨晚开始貌似就成了我最大的快乐。互锁词的生成要比昨天的回文词复杂一些,因为这意味着搜索的次数更多了。虽然都是用二分法搜索的思路,但我就是要比参考答案快接近30倍肿么破。至于为什么会这样,我没有研究,或许我应该仔细研究一下。

10万条的单词表里:二词互锁1254条,我用时1.4秒,参考答案用时39.1秒;三词互锁991条,我用时1.5秒,参考答案用时43.4秒。一箩筐的成就感啊啊啊啊啊啊啊~~~

Exercise 12: Two words “interlock” if taking alternating letters from each forms a new word. For example, “shoe” and “cold” interlock to form “schooled”. Solution: http://thinkpython2.com/code/interlock.py. Credit: This exercise is inspired by an example at http://puzzlers.org. Write a program that finds all pairs of words that interlock. Hint: don’t enumerate all pairs! Can you find any words that are three-way interlocked; that is, every third letter forms a word, starting from the first, second or third?

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
import time
def in_bisect(library, first, last, myword): # 二分法搜索,10万数据查询最多只需不到20步
    if first > last: # 这是一句拯救了我的条件
        return -1
    else:
        mid = (first + last)//2
        if myword == library[mid]:
            return mid
        elif library[mid] > myword:
            return in_bisect(library, first, mid-1, myword)
        else:
            return in_bisect(library, mid+1, last, myword)
def interlock(library, i, num):
    m = 0
    n = num
    while m < num:
        if in_bisect(library, 0, len(library)-1, library[i][m::n]) == -1:
            return False
        else:
            m += 1
            n -+ 1
    return True
count = 0
library = []
fin = open('words.txt')
for line in fin:
    word = line.strip()
    library.append(word)
library.sort()
start = time.time()
# for i in range(len(library)-1): # 二词互锁
#     if interlock(library, i, 2):
#         print(library[i], library[i][::2], library[i][1::2])
#         count += 1
for i in range(len(library)-1): # 三词互锁
    if interlock(library, i, 3):
        print(library[i], library[i][::3], library[i][1::3], library[i][2::3])
        count += 1
print(count)
end = time.time()
print(end - start)
# 1254, 1.3558001518249512 # 二词互锁 xrspook解法
# 1254, 39.10080027580261  # 二词互锁 参考答案
# 991, 1.4504001140594482  # 三词互锁 xrspook解法
# 991, 43.366000175476074  # 三次互锁 参考答案
2020-04
19

秒杀的感觉真爽!

By xrspook @ 20:06:17 归类于: 扮IT

配合我的二分法搜索,10万单词找出397对回文词,我只需1.7秒。list.index()需要291秒,期间如果不输出单词,你绝对认为自己的电脑卡死了!参考答案用了70秒,而且搜出了885对,其中91对准确来说是91个,那些词自己跟自己回文,自己跟自己根本算不上两个词好吗!余下的397对是因为A词和B词算一对,B词和A词他们又输出了一遍。参考答案的语句很精炼,但特殊情况没有处理好。

赢了参考答案,真爽!!!

练习11:两个词如果互为逆序,就称它们是『翻转配对』。写一个函数来找一下在这个词汇表中所有这样的词对。

Exercise 11: Two words are a “reverse pair” if each is the reverse of the other. Write a program that finds all the reverse pairs in the word list. Solution: http://thinkpython2.com/code/reverse_pair.py.

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
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
import time
def in_bisect(library, first, last, myword): # 二分法搜索,10万数据查询最多只需不到20步
    if first > last: # 这是一句拯救了我的条件
        return -1
    else:
        mid = (first + last)//2
        if myword == library[mid]:
            return mid
        elif library[mid] > myword:
            return in_bisect(library, first, mid-1, myword)
        else:
            return in_bisect(library, mid+1, last, myword)
j = 0
count = 0
library = []
fin = open('words.txt')
for line in fin:
    word = line.strip()
    library.append(word)
library.sort()
start = time.time()
for i in range(len(library)-1): # 二分法搜索 
    j = in_bisect(library, 0, len(library)-1, library[i][::-1])
    if j > -1 and library[i] < library[j]:
        print(library[i], library[j])
        count += 1
# for i in range(len(library)-1): # list.index()搜索
#     if library[i][::-1] in library:
#         j = library.index(library[i][::-1], 0, len(library)-1)
#         if library[i] < library[j]:
#             print(library[i], library[j])
#             j = 0
#             count += 1
print(count)
end = time.time()
print(end - start)
# abut tuba
# ad da
# ados soda
# agar raga
# agas saga
# agenes senega
# ah ha
# aider redia
# airts stria
# ajar raja
# alif fila
# am ma
# amen nema
# amis sima
# an na
# anger regna
# animal lamina
# animes semina
# anon nona
# ante etna
# are era
# ares sera
# aril lira
# arris sirra
# arum mura
# at ta
# ate eta
# ates seta
# auks skua
# avid diva
# avo ova
# ay ya
# bad dab
# bag gab
# bal lab
# bals slab
# ban nab
# bard drab
# bas sab
# bat tab
# bats stab
# bed deb
# ben neb
# bid dib
# big gib
# bin nib
# bins snib
# bird drib
# bis sib
# bog gob
# bos sob
# bots stob
# bows swob
# brad darb
# brag garb
# bud dub
# bun nub
# buns snub
# bur rub
# burd drub
# burg grub
# bus sub
# but tub
# buts stub
# cam mac
# cap pac
# cares serac
# cod doc
# cram marc
# cud duc
# dag gad
# dah had
# dahs shad
# dam mad
# dap pad
# dart trad
# daw wad
# debut tubed
# decal laced
# dedal laded
# deem meed
# deep peed
# deeps speed
# deer reed
# dees seed
# defer refed
# degami imaged
# deifier reified
# deil lied
# deke eked
# del led
# delf fled
# deliver reviled
# dels sled
# demit timed
# denier reined
# denies seined
# denim mined
# dens sned
# depot toped
# depots stoped
# derat tared
# derats stared
# dessert tressed
# desserts stressed
# devas saved
# devil lived
# dew wed
# dewans snawed
# dexes sexed
# dial laid
# dialer relaid
# diaper repaid
# dig gid
# dim mid
# dinar ranid
# diols sloid
# dirts strid
# do od
# dog god
# dom mod
# don nod
# doom mood
# door rood
# dor rod
# dormin nimrod
# dorp prod
# dos sod
# dot tod
# drail liard
# draw ward
# drawer reward
# draws sward
# dray yard
# dual laud
# ducs scud
# duel leud
# duo oud
# dup pud
# dups spud
# eat tae
# edile elide
# edit tide
# eel lee
# eh he
# elides sedile
# em me
# emes seme
# emir rime
# emit time
# emits stime
# enol lone
# er re
# ergo ogre
# eros sore
# ervil livre
# etas sate
# even neve
# evil live
# eviler relive
# fer ref
# fires serif
# flog golf
# flow wolf
# fool loof
# gal lag
# gals slag
# gam mag
# gan nag
# gar rag
# gas sag
# gat tag
# gats stag
# gel leg
# gelder redleg
# get teg
# gip pig
# girt trig
# gnar rang
# gnat tang
# gnats stang
# gnaws swang
# gnus sung
# got tog
# gul lug
# gulp plug
# guls slug
# gum mug
# gums smug
# guns snug
# gut tug
# habus subah
# hahs shah
# hales selah
# hap pah
# hay yah
# hey yeh
# ho oh
# hoop pooh
# hop poh
# is si
# it ti
# jar raj
# kay yak
# keel leek
# keels sleek
# keep peek
# keets steek
# kips spik
# knaps spank
# knar rank
# knits stink
# lager regal
# lair rial
# lap pal
# lares seral
# larum mural
# las sal
# leer reel
# lees seel
# leets steel
# leper repel
# lever revel
# levins snivel
# liar rail
# lin nil
# lion noil
# lit til
# lobo obol
# loom mool
# loons snool
# loop pool
# loops spool
# loot tool
# looter retool
# loots stool
# lop pol
# lotos sotol
# macs scam
# maes seam
# map pam
# mar ram
# marcs scram
# mart tram
# mat tam
# maws swam
# may yam
# meet teem
# meter retem
# mho ohm
# mils slim
# mir rim
# mis sim
# mon nom
# moor room
# moot toom
# mot tom
# mures serum
# mus sum
# muts stum
# namer reman
# nap pan
# naps span
# neep peen
# net ten
# neves seven
# new wen
# nip pin
# nips spin
# nit tin
# no on
# nolos solon
# nos son
# not ton
# notes seton
# now won
# nu un
# nus sun
# nut tun
# nuts stun
# oat tao
# oohs shoo
# oot too
# os so
# ow wo
# pacer recap
# pals slap
# pans snap
# par rap
# part trap
# parts strap
# pas sap
# pat tap
# paw wap
# paws swap
# pay yap
# peels sleep
# pees seep
# per rep
# pets step
# pins snip
# pis sip
# pit tip
# pols slop
# pools sloop
# poons snoop
# port trop
# ports strop
# pot top
# pots stop
# pow wop
# pows swop
# prat tarp
# pupils slipup
# puris sirup
# pus sup
# put tup
# raps spar
# rat tar
# rats star
# raw war
# ray yar
# rebus suber
# rebut tuber
# recaps spacer
# redes seder
# redips spider
# redraw warder
# redrawer rewarder
# rees seer
# reflet telfer
# reflow wolfer
# reknit tinker
# reknits stinker
# relit tiler
# remeet teemer
# remit timer
# rennet tenner
# repins sniper
# res ser
# rot tor
# sallets stellas
# saps spas
# sat tas
# saw was
# scares seracs
# secret terces
# seeks skees
# selahs shales
# sirs sris
# sit tis
# six xis
# skeets steeks
# skips spiks
# sleeps speels
# sleets steels
# slit tils
# sloops spools
# smart trams
# smuts stums
# snaps spans
# snaw wans
# snaws swans
# snips spins
# snit tins
# snoops spoons
# snoot toons
# snot tons
# snow wons
# sow wos
# spat taps
# spay yaps
# spirt trips
# spirts strips
# spit tips
# sports strops
# spot tops
# spots stops
# sprat tarps
# sprits stirps
# staw wats
# stew wets
# stow wots
# stows swots
# straw warts
# strow worts
# struts sturts
# swat taws
# sway yaws
# swot tows
# tav vat
# taw wat
# tew wet
# tort trot
# tow wot
# trow wort
# way yaw
# tort trot 
# tow wot
# trow wort
# way yaw
# 397, 291.1146504878998 # list.index()搜索
# 397, 1.7120981216430664 # 二分法搜索
# 885, 70.3680248260498 # 参考答案运行结果
2020-04
17

51%的概率

By xrspook @ 22:15:06 归类于: 扮IT

思路很简单,但要得出这个概率结论要重复多少次呢?脚本写好以后我先用了10次,100次,1000次,效果都不好,数字太漂浮,于是我都怀疑自己了。搜索之后发现别人用MATLAB写了个大体意思跟我一样的程序,他重复了100万次,好吧,我懂了!本来这种扔随机数进去的测试重复就应该趋向于无穷,但试过你就知道,100万次绝对让你的电脑卡到怀疑死机了。所以我狡猾地控制百分数只输出整数,10万次有点卡(我的破电脑等待结果大概需要4秒),但还可以接受。

Exercise 8:This exercise pertains to the so-called Birthday Paradox, which you can read about at http://en.wikipedia.org/wiki/Birthday_paradox. If there are 23 students in your class, what are the chances that two of you have the same birthday? You can estimate this probability by generating random samples of 23 birthdays and checking for matches. Hint: you can generate random birthdays with the randint function in the random module. You can download my solution from http://thinkpython2.com/code/birthday.py.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import random
def chance(num):
    n = 0
    x = 100000 # 越大越好,但太大了运行慢到怀疑人生…… 1W小卡,10W卡,100W非常卡!
    for i in range(x):
        birth = []
        for i in range(num):
            birth.append(random.randint(1, 365))
        birth.sort()
        for i in range(num - 1):
            if birth[i] == birth[i+1]:
                n += 1
                break
    return n/x
num = 23
print('chance is', '{:.0%}'.format(chance(num)))
# chance is 51%  x = 10W 百分数显示小数将会是个测试噩梦!!!
2020-04
16

循环,循环

By xrspook @ 19:58:07 归类于: 扮IT

觉得自己虽然见过递归,但几乎不用,不逼着我我都不用,循环用得越来越遛。前两题我和参考答案得出的结论一致,最后一题,我觉得参考答案有问题。下面的都是我的脚本。下面要用到的words.txt在这里

Exercise 7:This question is based on a Puzzler that was broadcast on the radio program Car Talk: Give me a word with three consecutive double letters. I’ll give you a couple of words that almost qualify, but don’t. For example, the word committee, c-o-m-m-i-t-t-e-e. It would be great except for the ‘i’ that sneaks in there. Or Mississippi: M-i-s-s-i-s-s-i-p-p-i. If you could take out those i’s it would work. But there is a word that has three consecutive pairs of letters and to the best of my knowledge this may be the only word. Of course there are probably 500 more but I can only think of one. What is the word? Write a program to find it. Solution: http://thinkpython2.com/code/cartalk1.py.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def double_letter(word):
    num = 0
    i = 0
    if len(word) >= 6:
        while i < len(word)-1:
            if word[i] == word[i+1]: 
                num = num + 1
                i = i + 2
            elif i > 2 and word[i-2] != word[i-3]:
                break
            else:
                i = i + 1
        if num == 3:
            print(word)
fin = open('words.txt')
n = 0
for line in fin:
    word = line.strip()
    double_letter(word)
# bookkeeper
# bookkeepers
# bookkeeping
# bookkeepings

Exercise 8: Here’s another Car Talk Puzzler: “I was driving on the highway the other day and I happened to notice my odometer. Like most odometers, it shows six digits, in whole miles only. So, if my car had 300,000 miles, for example, I’d see 3-0-0-0-0-0. “Now, what I saw that day was very interesting. I noticed that the last 4 digits were palindromic; that is, they read the same forward as backward. For example, 5-4-4-5 is a palindrome, so my odometer could have read 3-1-5-4-4-5. “One mile later, the last 5 numbers were palindromic. For example, it could have read 3-6-5-4-5-6. One mile after that, the middle 4 out of 6 numbers were palindromic. And you ready for this? One mile later, all 6 were palindromic! “The question is, what was on the odometer when I first looked?” Write a Python program that tests all the six-digit numbers and prints any numbers that satisfy these requirements. Solution: http://thinkpython2.com/code/cartalk2.py.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def is_palindrome(word):
    if word[::-1] == word:
        return True 
def test_palindrome(number):
    if is_palindrome(str(number)[2:]):
        if is_palindrome(str(number+1)[1:]):
            if is_palindrome(str(number+2)[1:1]):
                if is_palindrome(str(number+3)):
                    return True
for number in range(100000, 999999):
    if test_palindrome(number):
        print(number)
# 198888
# 199999

Exercise 9: Here’s another Car Talk Puzzler you can solve with a search: “Recently I had a visit with my mom and we realized that the two digits that make up my age when reversed resulted in her age. For example, if she’s 73, I’m 37. We wondered how often this has happened over the years but we got sidetracked with other topics and we never came up with an answer. “When I got home I figured out that the digits of our ages have been reversible six times so far. I also figured out that if we’re lucky it would happen again in a few years, and if we’re really lucky it would happen one more time after that. In other words, it would have happened 8 times over all. So the question is, how old am I now?” Write a Python program that searches for solutions to this Puzzler. Hint: you might find the string method zfill useful. Solution: http://thinkpython2.com/code/cartalk3.py.

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
year = 99
meet = int(input('how many times have we met?(1-8): '))
print('mom born me at', '\t','my age', '\t',"mon's age")
for i in range(10, 80): # 假设你妈生你的最低年龄是10,最高年龄是80
    n = 0
    for age in range(1, year):
        if age < int(str(age).zfill(2)[::-1]) and int(str(age).zfill(2)[::-1]) - age == i:            
            # print(i, '\t\t', age, '\t\t', str(age).zfill(2)[::-1])             
            n = n + 1
            if n == meet:
                print(i, '\t\t', age, '\t\t', str(age).zfill(2)[::-1])
 
# how many times have we met?(1-8): 6
# mom born me at   my age          mon's age
# 18               57              75
# 27               58              85
# 36               59              95
 
# how many times have we met?(1-8): 8
# mom born me at   my age          mon's age
# 18               79              97
 
# mom born me at   my age          mon's age
# 18               2               20
# 18               13              31
# 18               24              42
# 18               35              53
# 18               46              64
# 18               57              75
# 18               68              86
# 18               79              97
# 27               3               30
# 27               14              41
# 27               25              52
# 27               36              63
# 27               47              74
# 27               58              85
# 27               69              96
# 36               4               40
# 36               15              51
# 36               26              62
# 36               37              73
# 36               48              84
# 36               59              95
# 45               5               50
# 45               16              61
# 45               27              72
# 45               38              83
# 45               49              94
# 54               6               60
# 54               17              71
# 54               28              82
# 54               39              93
# 63               7               70
# 63               18              81
# 63               29              92
# 72               8               80
# 72               19              91
2020-04
15

反正这是我的答案

By xrspook @ 19:44:55 归类于: 扮IT

题目摆在这里,没有确切的答案,下面是我的解答,对不对不知道。words.txt资源在这里。

There are solutions to these exercises in the next section. You should at least attempt each one before you read the solutions.

Exercise 1: Write a program that reads words.txt and prints only the words with more than 20 characters (not counting whitespace).

Exercise 2: In 1939 Ernest Vincent Wright published a 50,000 word novel called Gadsby that does not contain the letter “e”. Since “e” is the most common letter in English, that’s not easy to do. In fact, it is difficult to construct a solitary thought without using that most common symbol. It is slow going at first, but with caution and hours of training you can gradually gain facility. All right, I’ll stop now. Write a function called has_no_e that returns True if the given word doesn’t have the letter “e” in it. Write a program that reads words.txt and prints only the words that have no “e”. Compute the percentage of words in the list that have no “e”.

Exercise 3: Write a function named avoids that takes a word and a string of forbidden letters, and that returns True if the word doesn’t use any of the forbidden letters. Write a program that prompts the user to enter a string of forbidden letters and then prints the number of words that don’t contain any of them. Can you find a combination of 5 forbidden letters that excludes the smallest number of words?

Exercise 4: Write a function named uses_only that takes a word and a string of letters, and that returns True if the word contains only letters in the list. Can you make a sentence using only the letters acefhlo? Other than “Hoe alfalfa”?

Exercise 5: Write a function named uses_all that takes a word and a string of required letters, and that returns True if the word uses all the required letters at least once. How many words are there that use all the vowels aeiou? How about aeiouy?

Exercise 6: Write a function called is_abecedarian that returns True if the letters in a word appear in alphabetical order (double letters are ok). How many abecedarian words are there?

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
fin = open('words.txt') # 第1小问
for line in fin:
    if len(line) >= (20+2):
        word = line.strip()
        print(word)
# counterdemonstrations
# hyperaggressivenesses
# microminiaturizations
 
def has_no_e(word): # 第2小问
    for letter in word:
        if letter == 'e':
            return False
    return True
fin = open('words.txt')
all = 0
count = 0
for line in fin:
    word = line.strip()
    all = all + 1
    if has_no_e(word):
        print(word)
        count = count + 1
print(count, 'words without e')
print('{:.0%}'.format(count/all), 'words without e')
# ...
# zymosis
# zymotic
# zymurgy
# 37641 words without e
# 33% words without e
 
def avoids(word, x): # 第3小问,最后一个问题举手投降
    for letterw in word:
        for letterx in x:
            if letterw == letterx:
                return False
    return True
fin = open('words.txt')
x = input('withtout: ')
num = 0
# word = 'jwrojgre' # input('word is ')
# print(avoids(word, x))
for line in fin:
    word = line.strip()
    if avoids(word, x):
        num = num + 1
print(num, 'words without', x)
# withtout: aeiou
# 107 words without aeiou
# count = 0
# import itertools
# for i in itertools.combinations('abcdefghijklmnopqrstuvwxyz', 5):
#     print(''.join(i))
#     count = count + 1
# print(count) # 65780个排列组合的可能性啊啊啊啊啊啊
 
 
def uses_only(word, x): # 第4小问
    for letter in word:
        if letter not in x:
            return False
    return True
word = input('word is ')
x = input('uses is ')
print(uses_only(word, x))
# word is abc
# uses is efg
# False
 
def uses_all(word, x): # 第5小问
    for letter in x:
        if letter not in word:
            return False
    return True
fin = open('words.txt')
x = input('must use: ' )
num = 0
for line in fin:
    word = line.strip()
    if uses_all(word, x):
        num = num + 1
print(num, 'words with', x)
# must use: aeiou
# 598 words with aeiou
# must use: aeiouy
# 42 words with aeiouy
 
def is_abecedarian(word): # 第6小问
    index = 1
    while index < len(word) - 1:
        if ord(word[index-1]) > ord(word[index]):
            return False
        index = index + 1
    return True
fin = open('words.txt')
num = 0
for line in fin:
    word = line.strip()
    if is_abecedarian(word):
        num = num + 1
print(num, 'words is abecedarian')
# 1573 words is abecedarian
© 2004 - 2024 我的天 | Theme by xrspook | Power by WordPress