-
Notifications
You must be signed in to change notification settings - Fork 0
/
solver.py
103 lines (92 loc) · 3.49 KB
/
solver.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
class Solver:
def __init__(
self,
field,
height,
width
):
self.field = field
self.height = height
self.width = width
self.prob_dict = dict()
def Run(self):
self.MakeProbDict()
self.CorrectProbDict()
self.CorrectTotalProb()
prev = [element[0] for element in self.prob_dict]
eps = 0.01
while True:
self.CorrectTotalProb()
cur = [element[0] for element in self.prob_dict]
if self.AccuracyCheck(prev, cur, eps):
break
prev = cur
return len(self.prob_dict) > 0
def OutBorder(self, x, y):
return x < 0 or y < 0 or x >= self.height or y >= self.width
def NearCellList(self, x, y):
ans = []
for offset_x in range(-1, 2):
for offset_y in range(-1, 2):
if not self.OutBorder(x + offset_x, y + offset_y):
if self.field[x + offset_x][y + offset_y] == '-':
ans.append((x + offset_x, y + offset_y))
return ans
def MakeProbDict(self):
for x in range(self.height):
for y in range(self.width):
if (self.field[x][y] != '-' and
self.field[x][y] != 'F' and
self.field[x][y] != '*'):
if int(self.field[x][y]) > 0:
g = self.NearProb(x, y)
for element in g:
if element[0] not in self.prob_dict:
self.prob_dict[element[0]] = []
self.prob_dict[element[0]].append(element[1])
def NearProb(self, x, y):
s = []
n = len(self.NearCellList(x, y))
for offset_x in range(-1, 2):
for offset_y in range(-1, 2):
if not self.OutBorder(x + offset_x, y + offset_y):
if self.field[x + offset_x][y + offset_y] == '-':
prob = int(self.field[x][y]) / n
s.append([(x + offset_x, y + offset_y), prob])
return s
def CorrectProbDict(self):
for element in self.prob_dict:
p = 1
for i in self.prob_dict[element]:
p *= (1 - i)
p = 1 - p
self.prob_dict[element] = [p]
def CorrectTotalProb(self):
for x in range(self.height):
for y in range(self.width):
if (self.field[x][y] != '-' and
self.field[x][y] != 'F' and
self.field[x][y] != '*'):
if int(self.field[x][y]) > 0:
s = 0
for element in self.NearCellList(x, y):
s += self.prob_dict[element][0]
if s != 0:
s = int(self.field[x][y]) / s
for element in self.NearCellList(x, y):
r = self.prob_dict[element][0]
self.prob_dict[element] = [r * s]
@staticmethod
def AccuracyCheck(l1, l2, eps):
for i in range(len(l1)):
if l2[i] - l1[i] > eps:
return False
return True
def MakePrediction(self):
minimum = 1.0
cords = (0, 0)
for key in self.prob_dict:
if self.prob_dict[key][0] <= minimum:
minimum = self.prob_dict[key][0]
cords = key
return cords