namin / spots

various code snippets in various languages

This URL has Read+Write access

spots / lunarLockout / lunarLockout.py
raw normal view history
122ce564 » namin 2008-12-24 Lunar Lockout Simple Solver 1 center = (2,2)
2 ex_board = [(2,4),(0,4),(1,2),(1,0),(4,2)]
83ae30c8 » namin 2009-01-04 refactored for python 2.6 3
122ce564 » namin 2008-12-24 Lunar Lockout Simple Solver 4 def moves(board):
5 for (a,b) in board:
2465915e » namin 2008-12-25 replaced tabs with spaces 6 for (c,d) in board:
83ae30c8 » namin 2009-01-04 refactored for python 2.6 7 if a==c and abs(b-d)>=1 and not any([e==a and min(b,d)<f<max(b,d) for (e,f) in board]):
8 yield (a,b), (a,d+(1 if b>d else -1))
9 elif b==d and abs(a-c)>=1 and not any([f==b and min(a,c)<e<max(a,c) for (e,f) in board]):
10 yield (a,b), (c+(1 if a>c else -1),b)
122ce564 » namin 2008-12-24 Lunar Lockout Simple Solver 11
12 ## [m for m in moves(ex_board)]
13 #. [((2, 4), (1, 4)), ((0, 4), (1, 4)), ((1, 2), (1, 1)), ((1, 2), (3, 2)), ((1, 0), (1, 1)), ((4, 2), (2, 2))]
14
15 def copy(board):
16 return [piece for piece in board]
17
18 def apply_move(move, board):
19 new_board = copy(board)
20 (before,after) = move
21 i = new_board.index(before)
22 new_board[i] = after
23 return new_board
24
25 ## apply_move(((2,4),(1,4)),ex_board)
26 #. [(1, 4), (0, 4), (1, 2), (1, 0), (4, 2)]
27
28 def is_solution(board):
29 return board[0] == center
30
31 ## is_solution(ex_board)
32 #. False
33
34 def bfs(cs,seen=None):
35 seen = seen or []
36 next_cs = []
37 for (path,board) in cs:
96e345ca » namin 2009-01-04 tabs/space 38 if is_solution(board):
39 return path
40 for move in moves(board):
41 new_board = apply_move(move,board)
42 if new_board not in seen:
43 next_cs.append((path+[move],new_board))
44 seen.append(new_board)
122ce564 » namin 2008-12-24 Lunar Lockout Simple Solver 45 if next_cs == []:
96e345ca » namin 2009-01-04 tabs/space 46 return None
122ce564 » namin 2008-12-24 Lunar Lockout Simple Solver 47 return bfs(next_cs, seen)
48
49 def solve(board):
50 return bfs([([],board)])
51
52 ## solve(ex_board)
16cc5097 » namin 2008-12-25 restricted legal moves to t... 53 #. [((2, 4), (1, 4)), ((1, 0), (1, 1)), ((1, 2), (3, 2)), ((1, 4), (1, 2)), ((1, 2), (2, 2))]
122ce564 » namin 2008-12-24 Lunar Lockout Simple Solver 54
55 ## solve([(3,1), (0,4), (0,2), (1,0), (2,4), (4,3)])
56 #. [((0, 4), (0, 3)), ((4, 3), (1, 3)), ((1, 3), (1, 1)), ((1, 1), (2, 1)), ((2, 1), (2, 3)), ((0, 3), (1, 3)), ((1, 3), (1, 1)), ((3, 1), (2, 1)), ((2, 1), (2, 2))]
57
58 ## solve([(2,4),(0,4),(0,0),(4,4),(4,0)])
59 #. [((0, 4), (1, 4)), ((4, 4), (4, 1)), ((4, 0), (1, 0)), ((1, 4), (1, 1)), ((4, 1), (2, 1)), ((2, 4), (2, 2))]
16cc5097 » namin 2008-12-25 restricted legal moves to t... 60
61 ## solve([(1,0),(0,4),(2,4),(4,4),(4,1)])
62 #. [((2, 4), (1, 4)), ((4, 4), (2, 4)), ((1, 4), (1, 1)), ((0, 4), (1, 4)), ((1, 4), (1, 2)), ((1, 1), (3, 1)), ((1, 0), (1, 1)), ((3, 1), (2, 1)), ((4, 1), (3, 1)), ((2, 1), (2, 3)), ((1, 1), (2, 1)), ((2, 1), (2, 2))]