rubik.py

r"""

Interface to two Rubik's cube solvers. 

The first is by Michael Reid, and tries to find an optimal solution given 
the cube's state, and may take a long time. 
See http://www.math.ucf.edu/~reid/Rubik/optimal_solver.html

The second is by Eric Dietz, and uses a standard (?) algorithm to 
solve the cube one level at a time. It is extremely fast, but often
returns a far from optimal solution. 
See http://wrongway.org/?rubiksource

The third is by Dik Winter and implements Kociemba's algorithm which 
finds reasonable solutions relatively quickly, and if it is kept running
will eventually find the optimal solution. 



AUTHOR:
   -- Optimal was written by Michael Reid <[email protected]> (2004)
   -- Cubex was written by Eric Dietz <[email protected]> (2003)
   -- Kociemba was written by Dik T. Winter <[email protected]> (1993)
   -- Initial interface by Robert Bradshaw (2007-08)
"""

########################################################################
#   Copyright (C) 2007 Robert Bradshaw <[email protected]>
#
#  Distributed under the terms of the GNU General Public License (GPL)
#
#  The full text of the GPL is available at:
#
#                  http://www.gnu.org/licenses/
########################################################################

import pexpect, time
import cleaner

from sage.groups.perm_gps.cubegroup import *



# Can't seem to find consistency in letter ordering
# between us and them... These are copied from the source. 
optimal_solver_tokens = ["UF", "UR", "UB", "UL", \
                        "DF", "DR", "DB", "DL", \
                        "FR", "FL", "BR", "BL", \
                        "FU", "RU", "BU", "LU", \
                        "FD", "RD", "BD", "LD", \
                        "RF", "LF", "RB", "LB", \
                        "UFR", "URB", "UBL", "ULF", \
                        "DRF", "DFL", "DLB", "DBR", \
                        "FRU", "RBU", "BLU", "LFU", \
                        "RFD", "FLD", "LBD", "BRD", \
                        "RUF", "BUR", "LUB", "FUL", \
                        "FDR", "LDF", "BDL", "RDB"]
                        
# The input format. 
optimal_solver_format = "UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR"

class SingNot:
    """
    This class is to resolve difference between various Singmaster notation. 
    Case is ignored, and the second and third letters may be swapped. 
    
    EXAMPLE: 
        sage: from sage.interfaces.rubik import SingNot
        sage: SingNot("acb") == SingNot("ACB")
        True
        sage: SingNot("acb") == SingNot("bca")
        False
    """
    def __init__(self, s):
        self.rep = s
        self.canonical = (s[0] + "".join(sorted(list(s[1:])))).lower()
    def __eq__(self, other):
        return isinstance(other, SingNot) and other.canonical == self.canonical
    def __repr__(self):
        return self.rep
    def __hash__(self):
        return hash(self.canonical)

# This is our list
singmaster_list = [''] + [SingNot(index2singmaster(i+1)) for i in range(48)]; singmaster_list                        

class OptimalSolver:
    """
    Interface to Michael Reid's optimal Rubik's Cube solver.
    """
    __cmd = "optimal"
    
    def __init__(self, verbose=False, wait=True):
        self.verbose = verbose
        self.start()
        if wait:
            print "Initializing tables..."
            self.ready()
            print "Done."
          
    def start(self):
        child = pexpect.spawn(self.__cmd)        
        cleaner.cleaner(child.pid, self.__cmd)
        child.timeout = None
        self.child = child
        self._ready = False
        
    def stop(self):
        if child:
            self.child.sendline(chr(3)) # send ctrl-c 
            self.child.sendline(chr(4)) # send ctrl-d 
            self.child.close(True)
            self.child = None
    
    def ready(self):
        if not self._ready:
            self.child.expect('enter cube')
            self._ready = True
    
    def __call__(self, facets):
        return self.solve(facets)
    
    def solve(self, facets):
        """
        The initial startup and precomputation are substantial...
        
        TODO: Let it keep searching once it found a solution?
        
        EXAMPLES: 
            sage: from sage.interfaces.rubik import *
            sage: solver = DikSolver()
            sage: solver = OptimalSolver() # long time
            Initializing tables...
            Done.
            sage: C = RubiksCube("R U")
            sage: solver.solve(C.facets())
            'R  U'
            sage: C = RubiksCube("R U F L B D")
            sage: solver.solve(C.facets())
            'R  U  F  L  B  D'
            sage: C = RubiksCube("R2 D2")
            sage: solver.solve(C.facets())
            'R2 D2'
        """
        self.ready()
        self.child.sendline(self.format_cube(facets))
        self.child.expect(r"([LRUDBF'2 ]+)\s+\((\d+)q\*?, (\d+)f\*?\)")
        self.child.sendline(chr(3)) # send ctrl-c 
        return self.child.match.groups()[0].strip()

    def format_cube(self, facets):
        L = []
        optimal_solver_list = [SingNot(x) for x in optimal_solver_tokens]
        for f in optimal_solver_format.split(" "):
            ix = facets[singmaster_list.index(SingNot(f))-1]
            facet = singmaster_list[ix]
            L.append(optimal_solver_list[optimal_solver_list.index(facet)])
        return " ".join([str(f) for f in L])        
        


move_map = {
    "LD":"L'",
    "LU":"L",
    "RD":"R",
    "RU":"R'",
    "FA":"F",
    "FC":"F'",
    "BA":"B'",
    "BC":"B",
    "UR":"U",
    "UL":"U'",
    "DR":"D'",
    "DL":"D"
}

class CubexSolver:
    
    __cmd = "cubex"
    
    def __call__(self, facets):
        return self.solve(facets)
        
    def solve(self, facets):
        """
        EXAMPLES: 
            sage: from sage.interfaces.rubik import *
            sage: C = RubiksCube("R U")
            sage: CubexSolver().solve(C.facets())
            'R U'
            sage: C = RubiksCube("R U F L B D")
            sage: sol = CubexSolver().solve(C.facets()); sol
            "U' L' L' U L U' L U D L L D' L' D L' D' L D L' U' L D' L' U L' B' U' L' U B L D L D' U' L' U L B L B' L' U L U' L' F' L' F L' F L F' L' D' L' D D L D' B L B' L B' L B F' L F F B' L F' B D' D' L D B' B' L' D' B U' U' L' B' D' F' F' L D F'"
            sage: RubiksCube(sol) == C
            True
            sage: C = RubiksCube("R2 F'")
            sage: CubexSolver().solve(C.facets())
            "R' R' F'"
            sage: C = RubiksCube().scramble()
            sage: sol = CubexSolver().solve(C.facets())
            sage: C == RubiksCube(sol)
            True
        """
        s = self.format_cube(facets)
        child = pexpect.spawn(self.__cmd+" "+s)
        ix = child.expect(['210.*?:', '^5\d+(.*)'])
        if ix == 0:
            child.expect(['211', pexpect.EOF])
            moves = child.before.strip().replace(',','').split(' ')
            return " ".join([move_map[m] for m in reversed(moves)])
        else:
            s = child.after
            while child.expect(['^5\d+', pexpect.EOF]) == 0:
                s += child.after
            raise ValueError, s
            
    def format_cube(self, facets):
        colors = sum([[i]*8 for i in range(1,7)], [])
        facet_colors = [0] * 54
        for i in range(48):
            f = facets[i]-1
            f += (f+4) // 8 # to compensate for the centers
            facet_colors[f] = colors[i]
        for i in range(6):
            facet_colors[i*9+4] = i+1
        return "".join(str(c) for c in facet_colors)




class DikSolver:
    
    __cmd = "dikcube"
    
    def __call__(self, facets):
        return self.solve(facets)
        
    def solve(self, facets, timeout=10, extra_time=2):
        """
        EXAMPLES: 
            sage: from sage.interfaces.rubik import *
            sage: C = RubiksCube().move("R U")
            sage: DikSolver().solve(C.facets())
            'R U'
            sage: C = RubiksCube().move("R U F L B D")
            sage: DikSolver().solve(C.facets())
            'R U F L B D'
            sage: C = RubiksCube().move("R2 F'")
            sage: DikSolver().solve(C.facets())
            "R2 F'"
        """
        cube_str = self.format_cube(facets)
        child = pexpect.spawn(self.__cmd+" -p")
        child.expect('Initialization done!')
        child.sendline(cube_str)

        # We use send(chr(4)) instead of sendeof in this case, since
        # child.sendoef() when run in the background with the Dik solver
        # sends a SIGTTOU which suspends the process -- this is very bad.
        # This is only a temporary workaround, and does not fix the problem
        # on OS X.  The Dik C program itself will need to be fixed.
        # See trac #1683. (TODO)      -- willem jp, wstein, mabshoff
        child.send(chr(4))          
        #child.sendeof()
        
        ix = child.expect(['Solution[^\n]*:', pexpect.EOF, pexpect.TIMEOUT], timeout=timeout)
        if ix == 0:
            child.expect(['[^\n]+'])
            sol = child.after.strip()
            start_time = time.time()
            while extra_time > time.time() - start_time:
                ix = child.expect(['Solution[^\n]*:', pexpect.EOF, pexpect.TIMEOUT], timeout=extra_time - int(time.time() - start_time))
                if ix == 0:
                    child.expect(['[^\n]+'])
                    sol = child.after.strip()
                else:
                    extra_time = 0
            # format the string into our notation
            child.close(True)
            return ' '.join([self.rot_map[m[0]]+str(4-int(m[1])) for m in reversed(sol.split(' '))]).replace('1', '').replace('3',"'")                   
        elif ix == 1:
            # invalid format
            child.close(True)
            raise ValueError, child.before
        else:
            child.close(True)
            raise RuntimeError, "timeout"
            
    def format_cube(self, facets):
        colors = sum([[i]*8 for i in range(1,7)], [])
        facet_colors = [0] * 54
        for i in range(48):
            f = self.facet_map.index(facets[i])
            facet_colors[f] = colors[i]
        # now do the centers
        facet_colors[4] = 1
        facet_colors[49] = 6
        for i in range(2,6):
            facet_colors[16+i*3] = i
        return "".join(str(c) for c in facet_colors)
        
    facet_map = [      1,  2,  3,                                \
                       4,  0,  5,                                \
                       6,  7,  8,                                \
           9, 10, 11, 17, 18, 19, 25, 26, 27, 33, 34, 35,        \
          12,  0, 13, 20,  0, 21, 28,  0, 29, 36,  0, 37,        \
          14, 15, 16, 22, 23, 24, 30, 31, 32, 38, 39, 40,        \
                      41, 42, 43,                                \
                      44,  0, 45,                                \
                      46, 47, 48,                                \
            ]
            
    
    # to compensate for different face naming
    rot_map = dict(zip("BLURDF", "ULFRBD"))

        
#    facet_map = [
#                      1,  2,  3, 
#                      4,      6, 
#                      7,  8,  9,
#          10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
#          23,     25, 26,     28,     29, 30, 31,     33,
#          34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45,
#                      46, 47, 48,
#                      49,     51, 
#                      52, 53, 54,
#    ]