• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Dec 14th, 2019 97 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. tree = {}
2.
3.
4. def is_winner(state):
5.     if state[:3] == '111' or state[3:6] == '111' or state[6:9] == '111' or state[:7:3] == '111' or state[1:8:3] == '111' or state[2:9:3] == '111' or state[:9:4] == '111' or state[2:7:2] == '111':
6.         return -1
7.     if state[:3] == '222' or state[3:6] == '222' or state[6:9] == '222' or state[:7:3] == '222' or state[1:8:3] == '222' or state[2:9:3] == '222' or state[:9:4] == '222' or state[2:7:2] == '222':
8.         return 1
9.     return 0
10.
11.
12. def fill_tree(state, num, step):
13.     global tree
14.     winner = is_winner(state)
15.     if winner == -1 or winner == 1 or step == 0:
16.         tree[state] = [winner]
17.         return
18.     tree[state] = []
19.     for i in range(9):
20.         if state[i] == '0':
21.             newstate = state[:i]+num+state[i+1:]
22.             tree[state].append([newstate, 0])
23.             if num == '1':
24.                 fill_tree(newstate, '2', step-1)
25.             else:
26.                 fill_tree(newstate, '1', step-1)
27.
28.
29. def count_tree(state, step):
30.     global tree
31.     if len(tree[state]) == 1 and tree[state][0] in [-1, 1, 0]:
32.         if step == 9:
33.             return tree[state][0]
34.         sum = 9-step
35.         cstep = 9-step
36.         while cstep > 1:
37.             cstep-=1
38.             sum*=cstep
39.         sum*=tree[state][0]
40.         return sum
41.     for v in tree[state]:
42.         res = count_tree(v[0], step+1)
43.         v[1] = res
44.     sum = 0
45.     if step % 2 == 1:
46.         flag = 0
47.         for v in tree[state]:
48.             if v[1] < 0:
49.                 continue
50.             sum += v[1]
51.             flag = 1
52.         if flag == 0:
53.             sum = -1
54.     else:
55.         for v in tree[state]:
56.             if v[1] < 0:
57.                 sum = -1
58.                 break
59.             sum += v[1]
60.     return sum
61.
62.
63. ans = {}
64. def build_json(state):
65.     global ans
66.     ans[state] = []
67.     try:
68.         if len(tree[state]) == 1 and type(tree[state][0]) is int:
69.             if tree[state][0] == 1:
70.                 ans[state].append(('smth','smth'))                 # бот победил
71.             else:
72.                 ans[state].append(('smth', 'smth'))                # бот дошел до ничьи
73.             return
74.     except KeyError:
75.         pass
76.     for c in tree[state]:
77.         if type(tree[c[0]][0]) is int:
78.             ans[state].append((c[0],'draw'))           # ничья, c[0] - ход человека, привел к ничье
79.         else:
80.             maxvalue = -1000000000
81.             maxstate = ''
82.             for pc in tree[c[0]]:
83.                 try:
84.                     if len(tree[pc[0]]) == 1 and type(tree[pc[0]][0]) is int and tree[pc[0]][0] > 0:
85.                         maxstate = pc[0]
86.                         break
87.                     if pc[1] > maxvalue:
88.                         maxvalue = pc[1]
89.                         maxstate = pc[0]
90.                 except IndexError:
91.                     pass
92.             if maxstate == '':
93.                 pass
94.             ans[state].append((c[0], maxstate))
95.             build_json(maxstate)
96.
97.
98. fill_tree('000000000', '1', 9)
99. count_tree('000000000', 0)
100. build_json('000000000')
101. # print(ans)
102. print(tree)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top