Python 2.7: 544 bytes -50% = 272 bytes**
import sys;o=''.join;r=range;a=sys.argv[1];a=o([(' ',x)[x in a[12]+a[19]+a[22]] for x in a]);v={a:''};w={' '*4+(a[12]*2+' '*4+a[19]*2)*2+a[22]*4:''}
m=lambda a,k:o([a[([0x55a5498531bb9ac58d10a98a4788e0,0xbdab49ca307b9ac2916a4a0e608c02,0xbd9109ca233beac5a92233a842b420][k]>>5*i)%32] for i in r(24)])
def z(d,h):
t={}
for s in d[0]:
if s in d[1]:print d[h][s]+d[1-h][s];exit()
n=[d[0][s],'']
for k in r(3):
for j in r(3):s=m(s,k);t[s]=n[h]+'RUF'[k]+" 2'"[(j,2-j)[h]]+n[1-h]
s=m(s,k)
d[0]=t;return d
while 1:v,w=z([v,w],0);w,v=z([w,v],1)
Stackexchange replaces tabs with multiple whitespaces. So technical this version has 549 bytes. Just replace the first two spaces in the lines 6-10 with a tabulator.
Idea behind my program:
My first idea was a breath first search. But this took too long. Around 2 minutes for a hard (11 move optimal) scramble.
So I decided to approach the problem from both sides. I use two sets. I generate sequentially all states with distance 1,2,3,... to the scramble and save them in set1, and at the same time all states with distance 1,2,3,... to the solved state and save them in set2.
The first time a state is in both sets, we found the solution.
For this I need the colors of the solved cube, which are not known. The characters 13, 20 and 23 define the left, back and down color. But these 3 colors are sufficient to represent the cube. I simply replace the other 3 colors with whitespaces and I can represent my solved state as '____ll____bbll____dddd'.
Oh, and for shortening the permutations I used an idea from https://codegolf.stackexchange.com/a/34651/29577
Ungolfed version:
import sys
#define permutations for R,U,F
permutation = [[0,7,2,15,4,5,6,21,16,8,3,11,12,13,14,23,17,9,1,19,20,18,22,10],
[2,0,3,1,6,7,8,9,10,11,4,5,12,13,14,15,16,17,18,19,20,21,22,23],
[0,1,13,5,4,20,14,6,2,9,10,11,12,21,15,7,3,17,18,19,16,8,22,23]]
def applyMove(state, move):
return ''.join([state[i] for i in permutation[move]])
scramble = sys.argv[1]
#remove up,front,rigth colors
scramble = ''.join([(' ', x)[x in scramble[12]+scramble[19]+scramble[22]] for x in scramble])
solved = ' '*4+scramble[12]*2+' '*4+scramble[19]*2+scramble[12]*2+' '*4+scramble[19]*2+scramble[22]*4
dict1 = {scramble: ''} #stores states with dist 0,1,2,... from the scramble
dict2 = {solved: ''} #stores states with dist 0,1,2,... from the solved state
moveName = 'RUF'
turnName = " 2'"
for i in range(6):
tmp = {}
for state in dict1:
if state in dict2:
#solution found
print dict1[state] + dict2[state]
exit()
moveString = dict1[state]
#do all 9 moves
for move in range(3):
for turn in range(3):
state = applyMove(state, move)
tmp[state] = moveString + moveName[move] + turnName[turn]
state = applyMove(state, move)
dict1 = tmp
tmp = {}
for state in dict2:
if state in dict1:
#solution found
print dict1[state] + dict2[state]
exit()
moveString = dict2[state]
#do all 9 moves
for move in range(3):
for turn in range(3):
state = applyMove(state, move)
tmp[state] = moveName[move] + turnName[2 - turn] + moveString
state = applyMove(state, move)
dict2 = tmp
I'm pretty happy with the result, because I'm quite new to Python. This is one of my first python programs.
edit: half a year later: 427 - 50% = 213.5
Got a little bit more experience in Python and in golfing. So I revised my original code and could save more than 100 character.
import sys;o=''.join;a=sys.argv[1];d=[{o((' ',x)[x in a[12]+a[19]+a[22]]for x in a):[]},{' '*4+(a[12]*2+' '*4+a[19]*2)*2+a[22]*4:[]}]
for h in[0,1]*6:
for s,x in d[h].items():
for y in range(12):
d[h][s]=x+[y-[1,-1,1,3][h*y%4]];
if s in d[1-h]:print o('RUF'[x/4]+" 2'"[x%4]for x in d[0][s]+d[1][s][::-1]);exit()
s=o(s[ord(c)-97]for c in'acahabcdnpbfegefhugiovjgqkciljdeklflmmmnnvoopxphrqdjrrbsstttuuqsviwwwkxx'[y/4::3])
I basically use the exact same approach. The biggest change is, that I don't define a function anymore. Instead of
def z(d,h):
for s in d[0]:
if s in d[1]:...
while 1:v,w=z([v,w],0);w,v=z([w,v],1)
I can do
for h in[0,1]*6:
for s in d[h]:
if s in d[1-h]:...
Also I changed the move lamda a little bit. First shortend, and then integrated the code directly, since the function call only appears once.
I keep for each state a list of numbers between 0 and 11, to represent the moves, instead of a string containing the moves. The numbers are converted at the very end.
Also I combined the two for-loops 'for k in r(3):for j in r(3): into one for y in r(12). Therefore I also have to do the moves U4, R4, F4. Of course such a move doesn't appear in the shortest solution, so " 2'"[x%4] works. (If x % 4 == 3, there would be a index out of range exception)
It's also a little bit faster, since I look for the entry in the second set earlier. About 0.5 second for a 11 move solution.
