rubiks cube

rubiks_cube.py

# Pseudo code. mix of python, lisp, and haskell syntax
# Wrote for fun after skimming https://en.wikipedia.org/wiki/Rubik%27s_Cube_group 
# and http://www.math.harvard.edu/~jjchen/docs/Group%20Theory%20and%20the%20Rubik%27s%20Cube.pdf

# Solve a rubik's cube:
def RC-pre-solve (init-state, operations)
    let solutions = {}, todo = [ (init-state, []) ]
    
    # Algorithm is simple:
    #   solutions is a set / mapping of explored states to optimal / approaching optimal paths
    #   todo is just a queue of states so we can explore recursively
    #
    # So long as solutions is bounded (it is, see group theory) we will terminate so long as we
    # de-duplicate searches.
    #
    # This algorithm is NOT optimal though as it'd be better to store a set of states w/ *mutatable*,
    # self-referential step lists (ie. so you can update / reduce the graph in place w/out re-iterating
    # when a better solution is found), though the general gist is more or less the same. 
    while size(todo) != 0
        # Could be breadth-first or depth-first depending on implementation of remove-1
        # and/or our "todo" list. Can be trivially parallelized, though would need to handle
        # de-duplication in a clever way for good performance
        let (state, chain) = remove-1(todo)

        # Skip / exit early if we've already explored this solution or if this solution is worse
        if state not in solutions or (solutions[state'] != chain and size(chain) <= size(solutions[state]))
            for op in operations
                # Solution is a pair of 2 values: current state + list of steps taken to get there
                # the "cost" that we're attempting to minimize is simple, just the # of steps
                let state' = op(state)
                let chain' = op : chain

                # Add / update solution, and recursively paths from there
                if state' not in solutions or size(chain') < size(solutions[state'])
                    solutions[state'] = chain'
                    todo += [ (state', chain') ]
    return solutions

# Usage:
let solved-states = RC-pre-solve(init-state, [ operations... ])
def RC-solve (state)
    return solved-states[state]

# Or (if you want to solve for any state):
let solved-states = {}, ops = [ operations... ]
def RC-solve (target, current-state)
    if target not in solved-states  # Cache value
        solved-states[target] = RC-pre-solve(target, ops)
    return solved-states[target][current-state]

todo: build an iphone app that does this, use ARKit to read in the rubiks cube face values and display solution steps

Has been done before (but not with ARKit?), but would def be an interesting and not too complicated project
Bonus points: outperform existing apps, should be able to evaluate this near instantaneously on modern hardware