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
| import re
letters = {1051081353: 'a', 66849241: 'a', 53342583: 'n', 213493562: 'd', 4385267: 'i', 261138725: 'o', 51574206: 't', 565468867: 'e', 647082638: 'r', 177014844: 'd', 894978618: 'e', 948544779: 'n', 572570465: 'n', 582531406: 'r', 264939475: 'a', 415170621: 's', 532012257: 't', 151901859: 'v', 346347468: 'g', 148496047: 'g', 125615053: 's', 723039811: 'e', 962878065: 'i', 112993293: 'w', 748275487: 'n', 120330115: 's', 76544105: 'c', 186790608: 'h'}
edge_list =[(53342583, 565468867), (582531406, 76544105), (125615053, 120330115), (264939475, 572570465), (53342583, 565468867), (532012257, 264939475), (346347468, 532012257), (125615053, 582531406), (177014844, 120330115), (264939475, 962878065), (647082638, 1051081353), (346347468, 112993293), (120330115, 151901859), (647082638, 125615053), (532012257, 66849241), (582531406, 894978618), (582531406, 572570465), (125615053, 532012257), (948544779, 261138725), (748275487, 894978618), (112993293, 177014844), (532012257, 4385267), (415170621, 962878065), (723039811, 962878065), (120330115, 151901859), (51574206, 76544105), (415170621, 532012257), (53342583, 120330115), (723039811, 582531406), (186790608, 112993293), (148496047, 582531406), (4385267, 125615053), (151901859, 962878065), (582531406, 894978618), (76544105, 748275487), (261138725, 186790608), (948544779, 346347468), (565468867, 213493562), (213493562, 261138725), (565468867, 894978618), (572570465, 264939475), (415170621, 151901859), (582531406, 962878065), (112993293, 346347468), (66849241, 1051081353), (894978618, 264939475), (647082638, 66849241), (894978618, 148496047), (213493562, 748275487), (572570465, 120330115), (565468867, 264939475), (148496047, 948544779), (186790608, 76544105), (177014844, 647082638), (125615053, 186790608), (112993293, 76544105), (582531406, 415170621), (151901859, 177014844), (346347468, 565468867), (148496047, 151901859), (723039811, 415170621), (1051081353, 415170621), (261138725, 76544105), (894978618, 723039811), (66849241, 112993293), (264939475, 112993293), (346347468, 748275487), (647082638, 948544779), (962878065, 647082638), (948544779, 962878065), (723039811, 120330115), (572570465, 51574206), (565468867, 151901859), (213493562, 76544105), (1051081353, 213493562), (962878065, 151901859), (112993293, 948544779), (186790608, 948544779), (346347468, 4385267), (565468867, 66849241), (1051081353, 177014844), (962878065, 148496047), (748275487, 264939475), (4385267, 565468867), (565468867, 1051081353), (51574206, 76544105), (532012257, 213493562), (532012257, 894978618), (723039811, 415170621), (264939475, 51574206), (572570465, 723039811), (894978618, 532012257), (66849241, 186790608), (213493562, 261138725), (415170621, 261138725), (125615053, 177014844), (186790608, 53342583), (565468867, 120330115), (51574206, 120330115), (186790608, 748275487), (213493562, 1051081353), (76544105, 53342583), (148496047, 565468867)]
ans = set()
adj = {}
for edge in edge_list:
try:
adj[edge[1]].append(edge[0])
except:
adj[edge[1]] = [edge[0]]
# print(len(adj['4385267']))
# exit(0)
def get_word_list():
with open('USACONST.TXT', encoding='ISO8859') as f:
text = f.read()
return list(set(re.sub('[^a-z]', ' ', text.lower()).split()))
word_list = get_word_list()
ma = 0
for x in word_list:
if ma < len(x):
ma = len(x)
concat_word = ' ' + ' '.join(word_list) + ' '
def backtrack(u, list_node, w, last):
# print(w, last, len(list_node), len(letters), sep='|')
global concat_word, word_list, ma
if (len(list_node) == len(letters)):
# with open('ans', 'a') as f:
# f.write(w + '\n')
ans.add(w.replace(' ',''))
return
for v in adj[u]:
old_last = last
if v not in list_node:
if ' ' + last + letters[v] in concat_word and len(last) < ma:
last += letters[v]
w += letters[v]
list_node.append(v)
backtrack(v, list_node, w, last)
list_node.pop()
last = old_last
w = w[:-1]
if ' ' + letters[v] not in concat_word or ' ' + old_last + ' ' not in concat_word:
continue
last = letters[v]
list_node.append(v)
w += ' ' + letters[v]
backtrack(v, list_node, w, last)
list_node.pop()
last = old_last
w = w[:-2]
for i in letters:
backtrack(i, [i], letters[i], letters[i])
with open('ans','w') as w:
for i in ans:
w.writelines(i+'\n')
|