2020-04
20
更爽
战胜参考答案从昨晚开始貌似就成了我最大的快乐。互锁词的生成要比昨天的回文词复杂一些，因为这意味着搜索的次数更多了。虽然都是用二分法搜索的思路，但我就是要比参考答案快接近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 # 三次互锁 参考答案 |
还没有评论