001 #coding: utf-8
002
003 from itertools import chain
004
005 # 用来加速python程序的。在我的机器上，不用psyco是每秒780个结点，用psyco是913个结点，17%的性能提升。
006 import psyco
007 psyco.full()
008
009
010 class Item(object):
011     u''' 棋盘上的对象，注，棋盘的左上角坐标为(1, 1)，右下角坐标为(4, 5) '''
012
013     # 以下4个函数是对象向上下左右移动，如果移动后出界，返回False
014
015     def left(self):
016         self.x -= 1
017         for x, y in self.pixels():
018             if not x > 0:
019                 return False
020         return True
021
022     def right(self):
023         self.x += 1
024         for x, y in self.pixels():
025             if not x < 5:
026                 return False
027         return True
028
029     def up(self):
030         self.y -= 1
031         for x, y in self.pixels():
032             if not y > 0:
033                 return False
034         return True
035
036     def down(self):
037         self.y += 1
038         for x, y in self.pixels():
039             if not y < 6:
040                 return False
041         return True
042
043     def clone(self):
044         u''' 复制一份对象 '''
045         return self.__class__(self.x, self.y)
046
047     def __lt__(self, other):
048         u''' 对象的坐标比较 '''
049         return self.x < other.x or self.x == other.x and self.y < other.y
050
051     def __str__(self):
052         u''' 对象的输出 '''
053         return '%s at (%d, %d)' % (self.__class__.__name__, self.x, self.y)
054     __repr__ = __str__
055
056
057 class Dot(Item):
058     u''' 用来表示一个小方格的对象，对应游戏里的'兵'和'卒' '''
059     C = ord('D')
060
061     def __init__(self, x, y):
062         if not 1<= x <= 4 or not 1 <= y <= 5:
063             self.valid = False
064
065         self.x = x
066         self.y = y
067
068     def pixels(self):
069         yield (self.x, self.y)
070
071
072 class VerticalBar(Item):
073     u''' 用来表示一个竖条的对象，对应游戏里的'黄忠'和'马超'等 '''
074     C = ord('V')
075
076     def __init__(self, x, y):
077         if not 1<= x <= 4 or not 1 <= y <= 4:
078             self.valid = False
079
080         self.x = x
081         self.y = y
082
083     def pixels(self):
084         yield (self.x, self.y)
085         yield (self.x, self.y+1)
086
087
088 class HorizontalBar(Item):
089     u''' 用来表示一个横条的对象，对应游戏里的'关羽' '''
090     C = ord('H')
091
092     def __init__(self, x, y):
093         if not 1<= x <= 3 or not 1 <= y <= 5:
094             self.valid = False
095
096         self.x = x
097         self.y = y
098
099     def pixels(self):
100         yield (self.x, self.y)
101         yield (self.x+1, self.y)
102
103
104 class Box(Item):
105     u''' 用来表示一个正方形的对象，对应游戏里的'曹操' '''
106     C = ord('B')
107
108     def __init__(self, x, y):
109         if not 1<= x <= 3 or not 1 <= y <= 4:
110             self.valid = False
111
112         self.x = x
113         self.y = y
114
115     def pixels(self):
116         yield (self.x, self.y)
117         yield (self.x+1, self.y)
118         yield (self.x, self.y+1)
119         yield (self.x+1, self.y+1)
120
121
122 class Board(Item):
123     u''' 整个棋盘 '''
124
125     def check_validity(self):
126         pixels = set()
127         for item in self.items():
128             for x, y in item.pixels():
129                 if (x, y) in pixels:
130                     return False
131                 pixels.add((x, y))
132
133         return len(pixels) == 18
134
135     def __init__(self, box, dots, vbs, hbs):
136         self.box = box
137         self.dots = dots
138         self.vbs = vbs
139         self.hbs = hbs
140
141         self.dots.sort()
142         self.vbs.sort()
143         self.hbs.sort()
144
145
146         if not self.check_validity():
147             self.valid = False
148             return
149
150         # 用一个Long型的变量来唯一地表示一个棋盘的状态。
151         self.statuscode = reduce(lambda code, item: (code<<5) + ((item.x-1)<<3)+item.y-1, self.items(), 0L)
152
153     def __str__(self):
154         result = [[ord(' ')]*4 for i in xrange(5)]
155         for item in self.items():
156             for x, y in item.pixels():
157                 result[y-1][x-1] = item.C
158         return '\n'.join(''.join(chr(c) for c in line) for line in result)
159
160     def items(self):
161         u''' 按顺序返回棋盘里的所有对象 '''
162         return chain([self.box], self.dots, self.vbs, self.hbs)
163
164
165     OP = ['up', 'down', 'left', 'right']
166
167     def permutate_items(self):
168         u''' 枚举棋盘上可能的移动方案，返回新的棋盘 '''
169
170         # 试着往4个方向移动box
171         for op in Board.OP:
172             newbox = self.box.clone()
173             if not getattr(newbox, op)():
174                 continue
175
176             newboard = Board(newbox, self.dots, self.vbs, self.hbs)
177             if not hasattr(newboard, 'valid'):
178                 yield newboard
179
180         # 试着往4个方向移动dot
181         for i in xrange(len(self.dots)):
182             origindot = self.dots[i]
183             for op in Board.OP:
184                 newdot = origindot.clone()
185                 if not getattr(newdot, op)():
186                     continue
187
188                 newdots = self.dots[:]
189                 newdots[i] = newdot
190                 newboard = Board(self.box, newdots, self.vbs, self.hbs)
191                 if not hasattr(newboard, 'valid'):
192                     yield newboard
193                     for op2 in Board.OP:
194                         newdot2 = newdot.clone()
195                         if not getattr(newdot2, op2)() or newdot2.x == origindot.x and newdot2.y == origindot.y:
196                             continue
197
198                         newdots = self.dots[:]
199                         newdots[i] = newdot2
200                         newboard = Board(self.box, newdots, self.vbs, self.hbs)
201                         if not hasattr(newboard, 'valid'):
202                             yield newboard
203
204
205         # 试着往4个方向移动vertical bar
206         for i in xrange(len(self.vbs)):
207             for op in Board.OP:
208                 newvb = self.vbs[i].clone()
209                 if not getattr(newvb, op)():
210                     continue
211
212                 newvbs = self.vbs[:]
213                 newvbs[i] = newvb
214                 newboard = Board(self.box, self.dots, newvbs, self.hbs)
215                 if not hasattr(newboard, 'valid'):
216                     yield newboard
217                     newvb = newvb.clone()
218                     if not getattr(newvb, op)():
219                         continue
220
221                     newvbs = self.vbs[:]
222                     newvbs[i] = newvb
223                     newboard = Board(self.box, self.dots, newvbs, self.hbs)
224                     if not hasattr(newboard, 'valid'):
225                         yield newboard
226
227
228
229         # 试着往4个方向移动horizontal bar
230         for i in xrange(len(self.hbs)):
231             for op in Board.OP:
232                 newhb = self.hbs[i].clone()
233                 if not getattr(newhb, op)():
234                     continue
235
236                 newhbs = self.hbs[:]
237                 newhbs[i] = newhb
238                 newboard = Board(self.box, self.dots, self.vbs, newhbs)
239                 if not hasattr(newboard, 'valid'):
240                     yield newboard
241                     newhb = newhb.clone()
242                     if not getattr(newhb, op)():
243                         continue
244
245                     newhbs = self.hbs[:]
246                     newhbs[i] = newhb
247                     newboard = Board(self.box, self.dots, self.vbs, newhbs)
248                     if not hasattr(newboard, 'valid'):
249                         yield newboard
250
251     def worked_out(self):
252         u''' 返回当前棋盘是否是获胜的棋盘，即box是否走到了坐标(2, 4) '''
253         return self.box.x == 2 and self.box.y == 4
254
255
256 def solve_the_board(board):
257     u''' 求指定的棋盘的解 '''
258     from datetime import datetime
259
260     if hasattr(board, 'valid'):
261         print 'original data error!'
262         return
263
264     print 'original status: %x' % (board.statuscode)
265
266     searched = {}       # 一个dict，保留了statuscode到board的映射
267     bfs = []            # 记录我们广度优先搜索的节点
268     board.previous_status = None
269     bfs.append(board)
270     searched[board.statuscode] = board
271     board.step = 0
272
273     # 开始做广度优先搜索（BFS）
274     start = datetime.now()
275     i = 0
276     current_step = 0
277     while i < len(bfs):
278         board = bfs[i]      # 取第i个结点做推演
279
280         if board.step != current_step:
281             current_step = board.step
282             print 'current step: %d, i = %d' % (current_step, i)
283
284         i += 1
285         if i % 1000 == 0:   # 每处理1k个结点，输出一些信息
286             print i
287             delta = datetime.now() - start
288             dt = delta.days * 24 * 60 * 60.0 + delta.seconds
289             if dt:
290                 print 'len(bfs) = %d, len(searched) = %d, %.2f nodes / sec' % (len(bfs), len(searched), i / dt)
291
292         # 找这个结点棋盘所有可能的下一步
293         for nb in board.permutate_items():
294             # 如果这一步曾经到过，就不再处理了。
295             if nb.statuscode in searched:
296                 continue
297
298             nb.step = board.step + 1
299
300             # 如果已经找到解了，输出然后退出
301             if nb.worked_out():
302                 result = [nb]
303
304                 # 由每一个结点棋盘的previous_status属性，计算出走的过程
305                 previous_status = board.statuscode
306                 while previous_status:
307                     pre = searched[previous_status]
308                     result.append(pre)
309                     previous_status = pre.previous_status
310
311                 for board in reversed(result):
312                     print board
313                     print '-' * 20
314
315                 print 'total steps:', nb.step
316                 return
317
318             # 计录下新的节点是由当前节点而来的，方便后面的输出。
319             nb.previous_status = board.statuscode
320
321             # 把新计算出来的结点，放到bfs的后面
322             searched[nb.statuscode] = nb
323             bfs.append(nb)
324
325     # 如果所有的结点都找完了，说明无解。
326     print 'not solution!'
327
328
329 def main():
330     # 第1关 横刀立马
331     #board = Board(Box(2, 1),        # 曹操的位置
332     #          [Dot(1, 5), Dot(2, 4), Dot(3, 4), Dot(4, 5)],     # 所有点点的位置
333     #          [VerticalBar(1, 1), VerticalBar(1, 3), VerticalBar(4, 1), VerticalBar(4, 3)], # 竖条的位置
334     #          [HorizontalBar(2, 3)],     # 横条的位置
335     #          )
336
337     # 第53关 四将连关
338     board = Board(Box(1, 1),        # 曹操的位置
339               [Dot(1, 5), Dot(3, 4), Dot(4, 4), Dot(4, 5)],     # 所有点点的位置
340               [VerticalBar(1, 3), VerticalBar(2, 3)],           # 竖条的位置
341               [HorizontalBar(3, 1), HorizontalBar(3, 2), HorizontalBar(3, 3)],     # 横条的位置
342               )
343
344     solve_the_board(board)
345
346 main()
347
348
349 # 下面两个函数是用来做性能分析的
350
351
352 def runhotshot():
353     import hotshot
354     prof = hotshot.Profile('/home/leojay/my/test.log')
355     prof.runcall(main)
356     prof.close()
357 #runhotshot()
358
359
360 def printhotshot():
361     import hotshot.stats
362     stats = hotshot.stats.load('/home/leojay/my/test.log')
363     stats.strip_dirs()
364     stats.sort_stats('time', 'calls')
365     stats.print_stats(20)
366 #printhotshot()