source: sage/interfaces/rubik.py @ 7701:957524edbf46

Revision 7701:957524edbf46, 8.8 KB checked in by Robert Bradshaw <robertwb@…>, 6 years ago (diff)

cleanup cube call (wasn't getting killed before)
Line 
1r"""nodoctest
2
3Interface to two Rubik's cube solvers.
4
5The first is by Michael Reid, and tries to find an optimal solution given
6the cube's state, and may take a long time.
7See http://www.math.ucf.edu/~reid/Rubik/optimal_solver.html
8
9The second is by Eric Dietz, and uses a standard (?) algorithm to
10solve the cube one level at a time. It is extremly fast, but often
11returns a far from optimal solution.
12See http://wrongway.org/?rubiksource
13
14
15TODO:
16    I'm sure there's algorithms and/or implementations that provide
17    a happy medium between the above two. Find or implement and interface.
18
19
20AUTHOR:
21   -- Optimal was written by Michael Reid <reid@math.ucf.edu> (2004)
22   -- Cubex was written by Eric Dietz <root@wrongway.org> (2003)
23   -- Initial interface by Robert Bradshaw (2007-08)
24"""
25
26########################################################################
27#   Copyright (C) 2007 Robert Bradshaw <robertwb@math.washington.edu>
28#
29#  Distributed under the terms of the GNU General Public License (GPL)
30#
31#  The full text of the GPL is available at:
32#
33#                  http://www.gnu.org/licenses/
34########################################################################
35
36import os, pexpect, time
37import cleaner
38
39from sage.groups.perm_gps.cubegroup import *
40
41
42
43# Can't seem to find consistancy in letter ordering
44# between us and them... These are copied from the source.
45optimal_solver_tokens = ["UF", "UR", "UB", "UL", \
46                        "DF", "DR", "DB", "DL", \
47                        "FR", "FL", "BR", "BL", \
48                        "FU", "RU", "BU", "LU", \
49                        "FD", "RD", "BD", "LD", \
50                        "RF", "LF", "RB", "LB", \
51                        "UFR", "URB", "UBL", "ULF", \
52                        "DRF", "DFL", "DLB", "DBR", \
53                        "FRU", "RBU", "BLU", "LFU", \
54                        "RFD", "FLD", "LBD", "BRD", \
55                        "RUF", "BUR", "LUB", "FUL", \
56                        "FDR", "LDF", "BDL", "RDB"]
57                       
58# The imput format.
59optimal_solver_format = "UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR"
60
61class SingNot:
62    """
63    This class is to resolve difference between various Singmaster notation.
64    Case is ignored, and the second and third letters may be swapped.
65   
66    EXAMPLE:
67        sage: SingNot("acb") == SingNot("ACB")
68        True
69        sage: SingNot("acb") == SingNot("bca")
70        False
71    """
72    def __init__(self, s):
73        self.rep = s
74        self.cannonical = (s[0] + "".join(sorted(list(s[1:])))).lower()
75    def __eq__(self, other):
76        return isinstance(other, SingNot) and other.cannonical == self.cannonical
77    def __repr__(self):
78        return self.rep
79    def __hash__(self):
80        return hash(self.cannonical)
81
82# This is our list
83singmaster_list = [''] + [SingNot(index2singmaster(i+1)) for i in range(48)]; singmaster_list                       
84
85class OptimalSolver:
86    """
87    Interface to Michael Reid's optimal Rubik's Cube solver.
88    """
89    __cmd = "optimal"
90   
91    def __init__(self, verbose=False, wait=True):
92        self.verbose = verbose
93        self.start()
94        if wait:
95            print "Initializing tables..."
96            self.ready()
97            print "Done."
98         
99    def start(self):
100        child = pexpect.spawn(self.__cmd)       
101        cleaner.cleaner(child.pid, self.__cmd)
102        child.timeout = None
103        self.child = child
104        self._ready = False
105       
106    def stop(self):
107        if child:
108            self.child.sendline(chr(3)) # send ctrl-c
109            self.child.sendline(chr(4)) # send ctrl-d
110            self.child.close(True)
111            self.child = None
112   
113    def ready(self):
114        if not self._ready:
115            self.child.expect('enter cube')
116            self._ready = True
117   
118    def __call__(self, facets):
119        return self.solve(facets)
120   
121    def solve(self, facets):
122        """
123        TODO: Let it keep searching once it found a solution?
124        """
125        self.ready()
126        self.child.sendline(self.format_cube(facets))
127        self.child.expect(r"([LRUDBF' ]+)\s+\((\d+)q\*?, (\d+)f\*?\)")
128        self.child.sendline(chr(3)) # send ctrl-c
129        return self.child.match.groups()[0].strip()
130
131    def format_cube(self, facets):
132        L = []
133        optimal_solver_list = [SingNot(x) for x in optimal_solver_tokens]
134        for f in optimal_solver_format.split(" "):
135            ix = facets[singmaster_list.index(SingNot(f))-1]
136            facet = singmaster_list[ix]
137            L.append(optimal_solver_list[optimal_solver_list.index(facet)])
138        return " ".join([str(f) for f in L])       
139       
140
141
142move_map = {
143    "LD":"L'",
144    "LU":"L",
145    "RD":"R",
146    "RU":"R'",
147    "FA":"F",
148    "FC":"F'",
149    "BA":"B'",
150    "BC":"B",
151    "UR":"U",
152    "UL":"U'",
153    "DR":"D'",
154    "DL":"D"
155}
156
157class CubexSolver:
158   
159    __cmd = "cubex"
160   
161    def __call__(self, facets):
162        return self.solve(facets)
163       
164    def solve(self, facets):
165        s = self.format_cube(facets)
166        child = pexpect.spawn(self.__cmd+" "+s)
167        ix = child.expect(['210.*?:', '^5\d+(.*)'])
168        if ix == 0:
169            child.expect(['211', pexpect.EOF])
170            moves = child.before.strip().replace(',','').split(' ')
171            return " ".join([move_map[m] for m in reversed(moves)])
172        else:
173            s = child.after
174            while child.expect(['^5\d+', pexpect.EOF]) == 0:
175                s += child.after
176            raise ValueError, s
177           
178    def format_cube(self, facets):
179        colors = sum([[i]*8 for i in range(1,7)], [])
180        facet_colors = [0] * 54
181        for i in range(48):
182            f = facets[i]-1
183            f += (f+4) // 8 # to compensate for the centers
184            facet_colors[f] = colors[i]
185        for i in range(6):
186            facet_colors[i*9+4] = i+1
187        return "".join(str(c) for c in facet_colors)
188
189
190
191
192class DikSolver:
193   
194    __cmd = "cube"
195   
196    def __call__(self, facets):
197        return self.solve(facets)
198       
199    def solve(self, facets, timeout=10, extra_time=2):
200        cube_str = self.format_cube(facets)
201        child = pexpect.spawn(self.__cmd+" -p")
202        child.expect('Initialization done!')
203        child.sendline(cube_str)
204        child.sendeof()
205        ix = child.expect(['Solution[^\n]*:', pexpect.EOF, pexpect.TIMEOUT], timeout=timeout)
206        if ix == 0:
207            child.expect(['[^\n]+'])
208            sol = child.after.strip()
209            start_time = time.time()
210            while extra_time > time.time() - start_time:
211                ix = child.expect(['Solution[^\n]*:', pexpect.EOF, pexpect.TIMEOUT], timeout=extra_time - int(time.time() - start_time))
212                if ix == 0:
213                    child.expect(['[^\n]+'])
214                    sol = child.after.strip()
215                else:
216                    extra_time = 0
217            # format the string into our notation
218            child.close(True)
219            return ' '.join([self.rot_map[m[0]]+str(4-int(m[1])) for m in reversed(sol.split(' '))]).replace('1', '').replace('3',"'")                   
220        elif ix == 1:
221            # invalid format
222            child.close(True)
223            raise ValueError, child.before
224        else:
225            child.close(True)
226            raise RuntimeError, "timeout"
227           
228    def format_cube(self, facets):
229        colors = sum([[i]*8 for i in range(1,7)], [])
230        facet_colors = [0] * 54
231        for i in range(48):
232            f = self.facet_map.index(facets[i])
233            facet_colors[f] = colors[i]
234        # now do the centers
235        facet_colors[4] = 1
236        facet_colors[49] = 6
237        for i in range(2,6):
238            facet_colors[16+i*3] = i
239        return "".join(str(c) for c in facet_colors)
240       
241    facet_map = [      1,  2,  3,                                \
242                       4,  0,  5,                                \
243                       6,  7,  8,                                \
244           9, 10, 11, 17, 18, 19, 25, 26, 27, 33, 34, 35,        \
245          12,  0, 13, 20,  0, 21, 28,  0, 29, 36,  0, 37,        \
246          14, 15, 16, 22, 23, 24, 30, 31, 32, 38, 39, 40,        \
247                      41, 42, 43,                                \
248                      44,  0, 45,                                \
249                      46, 47, 48,                                \
250            ]
251           
252   
253    # to compensate for different face naming
254    rot_map = dict(zip("BLURDF", "ULFRBD"))
255
256       
257#    facet_map = [
258#                      1,  2,  3,
259#                      4,      6,
260#                      7,  8,  9,
261#          10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
262#          23,     25, 26,     28,     29, 30, 31,     33,
263#          34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45,
264#                      46, 47, 48,
265#                      49,     51,
266#                      52, 53, 54,
267#    ]
268       
Note: See TracBrowser for help on using the repository browser.