Happy 40th anniversary Rubik's Cube!

Computer Science Level 5

Today the Rubik's cube celebrates $40$ years of bringing joy to children and adults alike.Besides the pleasure of solving it,it also has a lot of mathematics to it too.

Consider a solved $3 \times 3$ Rubik's cube. The six faces of the cube are named $FRONT$ , $BACK$ , $UP$ , $DOWN$ , $LEFT$ and $RIGHT$ respectively. An elementary move of the Rubik's cube is rotating a face by $90°$ clockwise or $90°$ anticlockwise. Any valid state of the Rubik's cube can be reached by applying these elementary operations one after the other.

An elementary move is denoted in the following fashion. If a given face is rotated by $90°$ clockwise about the axis passing from the center of the face to the center of the cube, the move is denoted by the first letter of the name of the face. If the rotation is anticlockwise by $90°$ , the letter is followed by an apostrophe (').These are all the elementary moves: $R R' U U' L L' D D' B B' F F'$

Given a single string of elementary moves $S$ let $F(s)$ denote the number of times the sequence should be applied repeatedly to the solved cube to get back the original cube.

Consider the following ten strings $D F'$ $B R' U' F' D'$ $B' F' B'$ $F L' U B$ $F B U L'$ $D U F$ $F F'$ $U' B' L$ $B' R' R' U' F'$ $B L' B L'$

Find $\sum F(S)$ for the ten strings above.

Explicit examples

$F(LB')=63$

$F(RR')=1$

$F(FUB)=90$

The answer is 1151.

1 solution

Thaddeus Abiy
May 25, 2014

I was inspired to make this problem because me and a friend had coded a Rubik's cube solver program a while back. I had the cube implementation lying around for a while. It was made using object oriented programming. We have many versions, this one is long but it is the most readable.

import copy
CONVENTION = {'Y':('Top',0),'R':('Front',1),'B':('Left',2),
              'G':('Right',3),'W':('Bottom',4),'O':('Back',5)}

Solved = [[[i,i,i]]*3 for i in CONVENTION]

class Cube:    
    ''' A quick and dirty implementation of a Rubiks cube '''
    def __init__(self , Cube_Array , Faces = None ):
        '''Takes an array of faces and sorts them out and assigns a conventional reference point '''
        self.History = []
        if Faces == None:

            self.Faces  = {}
            for face in Cube_Array:
                Key = CONVENTION[ face[1][1] ][0]
                self.Faces[ Key ] = face        

        else:
            self.Faces = Faces

    def __repr__( self ):
        '''Output for printing the cube object'''
        for f in ['Front','Right','Back','Left','Top','Bottom']:
            for i in self.Faces[f]:print i
            print (f+'^=^')*12
        return ''

    def __getitem__(self,indice):
        return self.Faces[indice]

    def __iter__( self ):
        return iter( self.Faces.values() )

    def get_face( self , position ):
        '''Returns a face given the position of the'''
        return self.Faces[ position ]

    def get_row( self , position , row , Input = None):
        '''Returns a row of a given face'''
        if Input != None:return Input[ position ][ row ]
        return self.Faces[ position ][ row ]

    def get_column( self , position , column , Input = None):
        '''Return a column of a given face'''
        if Input != None:return [ Input[ position ][ row ][ column ] for row in range(3) ]
        column = [ self.Faces[ position ][ row ][ column ] for row in range(3) ]
        return column

    def is_solved(self):
        ''' Checks wheather the cube has been solved or not '''
        for face in self.Faces:
            All=self.Faces[face]
            if len(set(map(tuple,All))) != 1:
                return False
            for i in All:
                if len(set(i))!=1:
                    return False

        return True

    def F( self , clockwise = True ):
        faces = {i:[] for i in self.Faces}
        faces['Back'] = self.Faces['Back']
        for i in range(3):
            if clockwise:
                faces['Front'].append(self.get_column('Front',i)[::-1])
                faces['Right'].append([self.get_row('Top',2)[i]]+self.get_row('Right',i)[1::])
                faces['Left'].append(self.get_row('Left',i)[0:2]+[self.get_row('Bottom',0)[i]] )
                faces['Top'] = self.Faces['Top'][0:2] + [self.get_column('Left',2)[::-1]]
                faces['Bottom'] = [self.get_column('Right',0)[::-1]] + self.Faces['Bottom'][1::]
            else:
                faces['Front'].append(self.get_column('Front',2-i))
                faces['Right'].append([self.get_row('Bottom',0)[2-i]]+self.get_row('Right',i)[1::])
                faces['Left'].append(self.get_row('Left',i)[0:2]+[self.get_row('Top',2)[2-i]])
                faces['Top']=self.Faces['Top'][0:2] + [self.get_column('Right',0)]
                faces['Bottom']=[self.get_column('Left',2)]+self.Faces['Bottom'][1::]

        self.Faces = faces

    def Rotate_Up(self):
        ''' Rotate the whole cube 90 degrees up'''
        Faces = {i:[] for i in self.Faces}
        Faces['Top'] = self.Faces['Front']
        Faces['Front'] = self.Faces['Bottom']
        Faces['Back']=[ i[::-1] for i in self.Faces['Top'] ][::-1]
        Faces['Bottom'] =[ i[::-1] for i in self.Faces['Back']][::-1]
        for r in range(3):
            Faces['Right'].append( self.get_column('Right',r)[::-1] )
            Faces['Left'].append( self.get_column('Left',2-r))
        self.Faces = Faces

    def Rotate_Down(self):
        ''' Rotate the whole cube 90 degrees down'''
        for i in range(3):self.Rotate_Up()

    def Rotate_Right(self):
        ''' Rotate the whole cube 90 degrees to the right'''
        Faces = {i:[] for i in self.Faces}
        Faces['Right']=self.Faces['Front']
        Faces['Back']=self.Faces['Right']
        Faces['Left']=self.Faces['Back']
        Faces['Front']=self.Faces['Left']
        for r in range(3):
            Faces['Top'].append(self.get_column('Top',2-r))
            Faces['Bottom'].append(self.get_column('Bottom',r)[::-1])
        self.Faces=Faces

    def Rotate_Left(self):
        ''' Rotate the whole cube 90 degrees to the left'''
        self.Rotate_Right()
        self.Rotate_Right()
        self.Rotate_Right()

    def U(self,clockwise=True):
        ''' Rotate the upper face of the cube clockwise or anticlockwise'''
        TempCube = Cube( self.Faces.values() )      
        TempCube.Rotate_Down()
        TempCube.F(clockwise)
        TempCube.Rotate_Up()
        self.Faces = TempCube.Faces


    def D(self,clockwise=True):
        '''Rotate the bottom face of the cube clock/anti wise'''
        TempCube = Cube( self.Faces.values() )      
        TempCube.Rotate_Up()
        TempCube.F(clockwise)
        TempCube.Rotate_Down()
        self.Faces = copy.copy(TempCube.Faces)


    def B(self,clockwise=True):
        '''Rotate the back face of the cube clock/anti wise'''
        TempCube = Cube( self.Faces.values() )      
        TempCube.Rotate_Right()
        TempCube.Rotate_Right()
        TempCube.F(clockwise)
        TempCube.Rotate_Right()
        TempCube.Rotate_Right()
        self.Faces = TempCube.Faces


    def L(self,clockwise=True):
        ''' Rotate the left face of the cube clockwise or anticlockwise'''
        TempCube = Cube( self.Faces.values() )      
        TempCube.Rotate_Right()
        TempCube.F(clockwise)
        TempCube.Rotate_Left()
        self.Faces = TempCube.Faces


    def R(self,clockwise=True):
        ''' Rotate the right face of the cube clockwise or anticlockwise'''
        TempCube = Cube(  self.Faces.values() )     
        TempCube.Rotate_Left()
        TempCube.F(clockwise)
        TempCube.Rotate_Right()
        self.Faces = TempCube.Faces


    def Eval(self,moves):
        for move in moves:
            move += ' '
            Dir,Orientation = move[0],move[1]!="'"
            eval('self.%s(%s)' % (Dir,Orientation) )

A=Cube(Solved)
def F(S):
    New_Cube = copy.copy(A)
    count = 0
    while True:
        count += 1
        New_Cube.Eval(S)
        if New_Cube.is_solved():
            return count

Move_List = [["D","F'"],
             ['B',"R'","U'","F'","D'"],
             ["B","F'","B'"],
             ["F","L'","U","B"],
             ["F","B","U","L'"],
             ["D","U","F"],
             ["F","F'"],
             ["U'","B'","L"],
             ["B'","R'","R'","U'","F'"],
             ["B","L'","B","L'"]]

print sum(map(F,Move_List))

Nice solution! Thanks for adding it here

Agnishom Chattopadhyay - 7 years ago

wow, much easier solution. Thanks :)

Vedabit Saha - 6 years, 10 months ago

Happy 40th anniversary Rubik's Cube!

The answer is 1151.

1 solution

0 pending reports