forked from KenMercusLai/checkio
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Robot Sort.py
144 lines (119 loc) · 4.44 KB
/
Robot Sort.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
from copy import deepcopy
class AStar(object):
def __init__(self, Goal):
self.Goal = Goal
def Heuristic(self, Node):
raise NotImplementedError
def GetResult(self, Node):
raise NotImplementedError
def Search(self, StartNode):
OpenSet = set()
ClosedSet = set()
StartNode.H = self.Heuristic(StartNode)
OpenSet.add(StartNode)
while OpenSet:
Current = min(OpenSet, key=lambda o: o.G + o.H)
if Current.Status == self.Goal:
return self.GetResult(Current)
OpenSet.remove(Current)
ClosedSet.add(Current)
for Node in Current.PossibleNextNodes():
if Node.Status in [i.Status for i in ClosedSet]:
continue
if Node.Status in [i.Status for i in OpenSet]:
index = [i.Status for i in OpenSet].index(Node.Status)
if Node.G < list(OpenSet)[index].G:
list(OpenSet)[index].G = Node.G
list(OpenSet)[index].Parent = Node.Parent
else:
Node.H = self.Heuristic(Node)
if Node.SelfCheck:
OpenSet.add(Node)
return None
class AStarNode(object):
def __init__(self, Status, G, Parent):
self.G = G
self.H = None
self.Parent = Parent
self.Status = Status
self.Comment = None
def SelfCheck(self):
if self.G and self.H and self.Status:
return True
else:
print self.G
print self.H
print self.Parent
print self.Status
print self.Comment
assert 1 == 0
def PossibleNextNodes(self):
raise NotImplementedError
class RobotSortPuzzle(AStar):
def __init__(self, Goal):
super(RobotSortPuzzle, self).__init__(Goal)
def Heuristic(self, Node):
return sum([10 for i, j in enumerate(self.Goal)
if Node.Status[i] != j])
def GetResult(self, Node):
Result = []
while Node.Parent:
Result.insert(0, Node.Status)
Node = Node.Parent
Result.insert(0, Node.Status)
Moves = []
for i, j in zip(Result, Result[1:]):
for k in range(len(i)):
if i[k] != j[k]:
Moves.append(str(k) + str(k + 1))
break
return ','.join(Moves)
class RobotSortPuzzleNode(AStarNode):
def __init__(self, Status, G, Parent):
super(RobotSortPuzzleNode, self).__init__(Status, G, Parent)
def PossibleNextNodes(self):
result = []
for i in range(len(self.Status) - 1):
temp = deepcopy(self.Status)
temp[i], temp[i + 1] = temp[i + 1], temp[i]
newNode = RobotSortPuzzleNode(temp, self.G + 1, self)
result.append(newNode)
return result
def swapsort(array):
Puzzle = RobotSortPuzzle(sorted(array))
startNode = RobotSortPuzzleNode(list(array), 0, None)
return Puzzle.Search(startNode)
if __name__ == '__main__':
# These "asserts" using only for self-checking and not necessary for
# auto-testing
def check_solution(f, indata):
result = f(indata)
array = list(indata[:])
la = len(array)
if not isinstance(result, str):
print("The result should be a string")
return False
actions = result.split(",") if result else []
for act in actions:
if len(act) != 2 or not act.isdigit():
print("The wrong action: {}".format(act))
return False
i, j = int(act[0]), int(act[1])
if i >= la or j >= la:
print("Index error: {}".format(act))
return False
if abs(i - j) != 1:
print("The wrong action: {}".format(act))
return False
array[i], array[j] = array[j], array[i]
if len(actions) > (la * (la - 1)) // 2:
print("Too many actions. BOOM!")
return False
if array != sorted(indata):
print("The array is not sorted. BOOM!")
return False
return True
assert check_solution(swapsort, (6, 4, 2)), "Reverse simple"
assert check_solution(swapsort, (1, 2, 3, 4, 5)), "All right!"
assert check_solution(swapsort, (1, 2, 3, 5, 3)), "One move"
swapsort((1, 2, 3, 4, 5, 6, 7, 8, 9, 1,))