My python one-liner scramble generator

guzman said:
You're right, thanks, I'll update it.

Edit: same goes for javascript, php, python.
I think we should set b=c=j=6 and j<31.
Click to expand...
Good point. I forgot about this effect when I changed the JS code. (Previously I had all the variables initialized to 4 for a similar reason.)

Using Portponky's idea of for(j=25;j;j--) I think we can save some moves in other ones too, like this for javascript:
Code: 
r=Math.random;for(c=b=j=25;j;c+b-5|c-m&&b-m?document.write("URFBLD"[j--,c=b,b=m]+" 2'"[0|r()*3]+" "):0)m=0|r()*6
 
qqwref said:
I'd say you cheated a lot :| The permutations U,F,R,D,L,B take a significant amount of space to define. If you don't count variable initializations then I claim the following JS code:

Code: 
for(;j<k;c+b-5|c-m&&b-m?w(x[j++,c=b,b=m]+y[s()]+z):0)m=t()
Click to expand...

OK, I cheated a lot. I also note that the generated scrambles are quite long (on the order of 100 moves typically) and it doesn't necessarily obey the rule forbidding 3 consecutive turns on the same axis.

I hadn't worked on trying to optimize my initialization for U,D,L,R,F, and B yet when I posted previously. I've now come up with this (268 characters) for initializing these variables (although used like constants):

U:=(1,3,8,6)(2,5,7,4)(9,33,25,17)(10,34,26,18)(11,35,27,19);;L:=(9,11,16,14)(10,13,15,12)(1,17,41,40)(4,20,44,37)(6,22,46,35);;R:=(25,27,32,30)(26,29,31,28)(3,38,43,19)(5,36,45,21)(8,33,48,24);;x:=R*(2,39,42,18)(7,34,47,23)*L^-1;;D:=x^2*U*x^2;;F:=x*U*x^3;;B:=x*D*x^3;;

So yes, it's even longer than the rest of the code (posted earlier). Together it's 169 (corrected number for the earlier post) + 268 = 437. I note that the count includes the extra semicolon characters that avoids extraneous stuff from being output prior to the scramble being output.

The entire GAP code (and a sample output) is:
Code: 
U:=(1,3,8,6)(2,5,7,4)(9,33,25,17)(10,34,26,18)(11,35,27,19);;L:=(9,11,16,14)(10,13,15,12)(1,17,41,40)(4,20,44,37)(6,22,46,35);;R:=(25,27,32,30)(26,29,31,28)(3,38,43,19)(5,36,45,21)(8,33,48,24);;x:=R*(2,39,42,18)(7,34,47,23)*L^-1;;D:=x^2*U*x^2;;F:=x*U*x^3;;B:=x*D*x^3;;G:=Group(U,D,L,R,F,B);;P:=FreeGroup("U","D","L","R","F","B");;h:=GroupHomomorphismByImages(P,G,GeneratorsOfGroup(P),[noparse][U,D,L,R,F,B]);;[/noparse]PreImagesRepresentative(h,Random(G));
U*R*B^-1*L*U*R*U^-1*B^-1*R*B*F*U^2*D^-1*B^-1*D*U^-1*F^2*D*F*D^-1*L^-1*R^-1*F^
-1*R*U^2*F*L*F^-1*L^-1*F^-1*B*L^-1*B^-1*U*B^-1*U*B*U^-1*L^-1*F^-1*L*F*L*U^
-1*L^-1*B^-1*U^-1*B*U^-1*L*U^-1*L^-1*U*L*U*F*U^-1*F^-1*U^2*L^-1*U^-1*L*U*L*F^
-1*L^-1*F*L*U^2*L^-1*U^-1*L*U^-1*L^-1*U*F*U*F^-1*L*U*L^-1*F*L*U^-1*L^-1*U^
-1*F^-1*U
Given that the shortest solution in Rokicki's cube solver contest was over 500 characters, this is probably still not too bad for a random state scramble generator.

(Since this scramble generator is non-conforming and is a different type of scramble generator, I suggest it should not be added to recaps.)

In addition to main(){...}, doesn't the C++ version (in order to use cout) need a #include line and possibly a "using namespace std;" declaration to make it valid? Of course, a #include would necessarily make it no longer a 1-liner.
 
Last edited:
170 in visual basic

Code: 
For s = 1 To 25
c = b
b = a
Do While a = b Or a + b = 7 And a = c
a = Int(Rnd * 6 + 1)
Loop
t.Text = t.Text & Mid("URFBLD", a, 1) & Mid(" '2", Int(Rnd * 3 + 1), 1)
Next s

I'm a noob in VB so this can be improved.
 
Recap 3

Recap 0.
Recap 1.
Recap 2.
Recap 3:

perl: 98 (Patrick, Johannes91, Stefan, qqwref)
This one doesn't give scrambles that start with U.
Which one was the last one correct ?
Code: 
map{$m=0|rand 6until$c+$b-5|$c-$m&&$m-$b;$c=$b;print" ".(U,R,F,B,L,D)[$b=$m].qw(' 2)[rand 3]}1..25

perl: 102 (edit: solves above problem) (Patrick, Johannes91, Stefan, qqwref)
Code: 
map{$m=0|rand 6until$c+$b-5|$c ne$m&&$m ne$b;$c=$b;print" ".(U,R,F,B,L,D)[$b=$m].qw(' 2)[rand 3]}1..25


C++: 102 (110 with main(){} ) (keemy, Marcell, guzman, Portponky, Stefan)
Code: 
for(int c=0,b=6,j=25,m;j;m-c|c+b-5&&b-m&&cout<<"URFBLD"[j--,c=b,b=m]<<" 2'"[rand()%3]<<" ")m=rand()%6;

perl: 111 (Stefan)
Code: 
$_.=chr rand 99,/[^URFBLD]|(.)\1|LRL|RLR|UDU|DUD|FBF|BFB/&&chop until/.{25}/;s/./" $&".qw(' 2)[rand 3]/ge;print

javascript: 112 (qqwref, Devin, guzman, Johannes91, Patrick, Stefan)
Code: 
r=Math.random;for(c=b=j=25;j;c+b-5|c-m&&b-m?document.write("URFBLD"[j--,c=b,b=m]+" 2'"[0|r()*3]+" "):0)m=0|r()*6

perl: 114 (Edit) (Patrick, Stefan, Johannes91)
Code: 
$_=join'',map{(U,R,F,B,L,D)[rand 6]}1..25while/^$|(.)\1|LRL|RLR|UDU|DUD|FBF|BFB/;print" $_".qw(' 2)[rand 3]for/./g

Ruby: 115 (joey)
Code: 
p (x=y=0..25).map{z=x;x=(w=[%(UD),%(FB),%(RL)][rand 3])[rand 2] until x!=y||z!=x&&w[y];(y=x)+"2'"[rand 3].to_s}*" "

php: 114 (Marcell, guzman)
Code: 
for($i=$b=$c=25;$i;$M="URFBLD 2'")if(($b-$m=rand()%6)&($c+$b-5|$c-$m))echo$M[$b=$m+0*$i--*$c=$b].$M[rand(6,8)].' '

python: 149 (masterofthebass)
Code: 
from random import randint as r;c=b=0
for i in range(25):
 m=r(0,5)
 while (c+b-4 or c==m)and m==b:m=r(0,5)
 print "URFBLD"[m]+" '2"[r(0,2)],;c=b;b=m

mathematica: 166 (Lucas)
Code: 
StringJoin[ToString[#]<>(c=RandomChoice)[{" ","' ","2 "}]&/@(Flatten[RandomSample[#,Ceiling[Random[]*5/4]]&/@c[{{U,R},{F,B},{L,D}},25]]//.{a___,b_,b_,c___}:>{a,b,c})]

Visual Basic: 170 (mr. giggums)
Code: 
For s = 1 To 25
c = b
b = a
Do While a = b Or a + b = 7 And a = c
a = Int(Rnd * 6 + 1)
Loop
t.Text = t.Text & Mid("URFBLD", a, 1) & Mid(" '2", Int(Rnd * 3 + 1), 1)
Next s
 
Last edited:
guzman said:
perl: 98 (Patrick, Johannes91, Stefan, qqwref)
This one doesn't give scrambles that start with U.
Which one was the last one correct ?
Click to expand...

Not sure it ever was. But here's one with 100 that fixes that:
map{$m=0|rand 6until$c+$b-5|$c-$m&&$m ne$b;$c=$b;print" ".(U,R,F,B,L,D)[$b=$m].qw(' 2)[rand 3]}1..25

We might need to fix $c-$m as well, though... not sure.

Edit: I thought this would prevent starting with DU, but I tested it and that does work. Why? I thought it would be:
$c is undefined
$b is 5
$m is 0
So $c+$b-5|$c-$m would be 0 and thus false and thus prevent a DU start...

Edit2: Embarrassing... I tested it inside a loop and forgot to undef the variables...
 
Last edited:
I thought the same but I dont know perl ...
I thought $c+$b-5|$c-$m was undefined and therefore not true ...

Anyway, I edited the recap.

Edit:
I think that c+b-5 is not undef
it is actually evaluated as 0+b-5 since c is treated as zero and this solves the problem.
I found a doc that says: "Perl treats undef as either zero or the empty string"
therefore I think it is consider false in boolean operations
but it is considered as 0 in arithmetical operations.
 
Last edited:
guzman said:
I think that c+b-5 is not undef
it is actually evaluated as 0+b-5 since c is treated as zero and this solves the problem.
Click to expand...

Yes, undef is treated as zero in such numerical context, but then c+b+5 is 0 and c-m is 0 as well, so or-ing them is again 0 and we have the problem.
 
qqwref said:
I'm not actually sure the normal scrambling algorithm does this. Consider 3-move scrambles, ignoring suffixes. The probability of the first two moves being R B and R L are exactly the same (1/30). However, R B can be followed by 5 moves (so each 3-move scramble starting with R B has probability 1/150) but R L can be followed by only 4 moves (so each 3-move scramble starting with R L has probability 1/120). The same thing should happen with more moves.
Click to expand...

Hmm. Good point.

Removing do{} and adding ^$| to the regex saves on character:

$_=join'',map{(U,R,F,B,L,D)[rand 6]}1..25while/^$|(.)\1|LRL|RLR|UDU|DUD|FBF|BFB/;print" $_".qw(' 2)[rand 3]for/./g
 
Probability of moves on the same axis ...

May I repost this to ask for further considerations ....
I edited it a bit.

guzman said:
Consider a scramble.
What is the probability of having two consecutive letters on the same axis (such as R and L).

Say we begin with an R, the following letter is any letter chosen randomly among UFLBD, so the probability of having L is 1/5.

We may therefore think of a scrambler with the following structure:

  • 1 - choose a random axis (say we choose the RL axis),
  • 2 - choose randomly between two moves on that axis (with probability 1/5) or one move (with probability 4/5) on that axis:
  • 2a - if we need two moves: choose randomly between RL and LR
  • 2b - if we need one move: choose randomly between R and L
  • 3 - apply random suffixes to each letter
  • 4 - repeat process changing axis.

So, the idea is to decompose a scramble as follows, here's an example:
B - R' - DU - B2 - U' - BF - D2 - R2 - D2 - LR' - B - L2R' - D' - F - R2L' - B - R' - D'U2 - R'
where moves on the same axis are coupled together.
The probability of having a couple should be 1/5.

Does that make sense ?
I think it gives each scramble the same probability
that we get by choosing random moves at each turn (and checking for validity).

Dunno if it can be implemented more efficiently than what we have.
Click to expand...
 
Last edited:
guzman: I'm not sure that would provide a uniform scramble setup - so far the only thing I'm sure will work is do{generate scramble}until(valid). And it's definitely more complex than the current approach.

I tried a few things to fix the Perl code but the only way I could see to do it was to plunk in a $b=7; before the map statement. :fp
 
qqwref said:
I tried a few things to fix the Perl code but the only way I could see to do it was to plunk in a $b=7; before the map statement. :fp
Click to expand...

Have you seen mine? I replaced $m-$b with $m ne$b, the ne-operator creates a string context which fixes that problem (because undefined is treated as '', which differs from '0'). But we both still have the problem that $c also starts undefined, preventing a DU start...
 
Last edited:
Stefan said:
Have you seen mine? I replaced $m-$b with $m ne$b, the ne-operator creates a string context which fixes that problem (because undefined is treated as '', which differs from '0'). But we both still have the problem that $c also starts undefined, preventing a DU start...
Click to expand...

I did see yours, yes. But your post made it sound like it didn't work, so I assumed your fix did nothing useful.

Why wouldn't this work?:
Code: 
map{$m=0|rand 6until$c+$b-5|$c ne$m&&$m ne$b;$c=$b;print" ".(U,R,F,B,L,D)[$b=$m].qw(' 2)[rand 3]}1..25
 
qqwref said:
Why wouldn't this work?:
Code: 
map{$m=0|rand 6until$c+$b-5|$c ne$m&&$m ne$b;$c=$b;print" ".(U,R,F,B,L,D)[$b=$m].qw(' 2)[rand 3]}1..25
Click to expand...

Seems (*) to work, maybe I dismissed it when my testing was flawed.

(*) as in "it passes my test, but I'm unsure about it and too tired to think it through" :)
 
mr. giggums said:
170 in visual basic

Code: 
For s = 1 To 25
c = b
b = a
Do While a = b Or a + b = 7 And a = c
a = Int(Rnd * 6 + 1)
Loop
t.Text = t.Text & Mid("URFBLD", a, 1) & Mid(" '2", Int(Rnd * 3 + 1), 1)
Next s

I'm a noob in VB so this can be improved.
Click to expand...

I don't know much VB, but I think this can be applied:
Code: 
t.Text += Mid("URFBLD", a, 1) & Mid(" '2", Int(Rnd * 3 + 1), 1)
saving 7 chars


EDIT:

The python one didn't work( AT ALL!!! Couldn't start with U, could do the same move twice and so on...)... so I fixed it and saved some chars :)

Code: 
from random import randint as r;c=b=m=9
for i in range(25):
 while c+b-4 and m==c or m==b:m=r(0,5)
 print "URFBLD"[m]+" '2"[r(0,2)],;c=b;b=m

instead of calling m=r(0,5) inside the loop, I called it as 9 (because everything that is 5 or below will restrict a beginning move) together with the c and b...
I also fixed an 'and/or' confusion, and I deleting unecessary paranthesis :)

this makes it 140 chars... and working ;)

EDIT2:
with my little neat b=9, I fixed the perl, making it a 103 chars ... EDIT3: it can only start with U now :S
Code: 
$b=9;map{$m=0|rand 6until$c+$b-5|$c-$m&&$m-$b;$c=$b;print" ".(U,R,F,B,L,D)[$b=$m].qw(' 2)[rand 3]}1..25
 
Last edited:
Alright, I think the normal 3x3 scrambler is getting too easy. Time to make it a little trickier. Here is a *pyraminx optimal scrambler* to try to code-golf. (Written in JavaScript of course.) It's kinda long, you might wanna copy it to Notepad or something before editing.

Code: 
var j=1,b,mn=11,g=[],f=[],d=[],e=[],k=[],h=[],i=[];function u(){var c,p,q,l,m;for(p=0;p<720;p++){g[p]=-1;d[p]=[];for(m=0;m<4;m++)d[p][m]=w(p,m)}g[0]=0;for(l=0;l<=6;l++)for(p=0;p<720;p++)if(g[p]==l)for(m=0;m<4;m++){q=p;for(c=0;c<2;c++){q=d[q][m];if(g[q]==-1)g[q]=l+1}}for(p=0;p<2592;p++){f[p]=-1;e[p]=[];for(m=0;m<4;m++)e[p][m]=x(p,m)}f[0]=0;for(l=0;l<=5;l++)for(p=0;p<2592;p++)if(f[p]==l)for(m=0;m<4;m++){q=p;for(c=0;c<2;c++){q=e[q][m];if(f[q]==-1)f[q]=l+1}}for(c=0;c<j;c++){k=[];var t=0,s=0;q=0;h=[0,1,2,3,4,5];for(m=0;m<4;m++){p=m+n(6-m);l=h[m];h[m]=h[p];h[p]=l;if(m!=p)s++}if(s%2==1){l=h[4];h[4]=h[5];h[5]=l}s=0;i=[];for(m=0;m<5;m++){i[m]=n(2);s+=i[m]}i[5]=s%2;for(m=6;m<10;m++){i[m]=n(3)}for(m=0;m<6;m++){l=0;for(p=0;p<6;p++){if(h[p]==m)break;if(h[p]>m)l++}q=q*(6-m)+l}for(m=9;m>=6;m--)t=t*3+i[m];for(m=4;m>=0;m--)t=t*2+i[m];if(q!=0||t!=0)for(m=mn;m<99;m++)if(v(q,t,m,-1))break;b="";for(p=0;p<k.length;p++)b+="ULRB"[k[p]&7]+["","'"][(k[p]&8)/8]+" ";var a="lrbu";for(p=0;p<4;p++){q=n(3);if(q<2)b+=a[p]+["","'"][q]+" "}}}function v(q,t,l,c){if(l==0){if(q==0&&t==0)return true}else{if(g[q]>l||f[t]>l)return false;var p,s,a,m;for(m=0;m<4;m++)if(m!=c){p=q;s=t;for(a=0;a<2;a++){p=d[p][m];s=e[s][m];k[k.length]=m+8*a;if(v(p,s,l-1,m))return true;k.length--}}}return false}function w(p,m){var a,l,c,s=[],q=p;for(a=1;a<=6;a++){c=0|(q/a);l=q-a*c;q=c;for(c=a-1;c>=l;c--)s[c+1]=s[c];s[l]=6-a}if(m==0)y(s,0,3,1);if(m==1)y(s,1,5,2);if(m==2)y(s,0,2,4);if(m==3)y(s,3,4,5);q=0;for(a=0;a<6;a++){l=0;for(c=0;c<6;c++){if(s[c]==a)break;if(s[c]>a)l++}q=q*(6-a)+l}return q}function x(p,m){var a,l,c,t=0,s=[],q=p;for(a=0;a<=4;a++){s[a]=q&1;q>>=1;t^=s[a]}s[5]=t;for(a=6;a<=9;a++){c=0|(q/3);l=q-3*c;q=c;s[a]=l}if(m==0){s[6]++;if(s[6]==3)s[6]=0;y(s,0,3,1);s[1]^=1;s[3]^=1}if(m==1){s[7]++;if(s[7]==3)s[7]=0;y(s,1,5,2);s[2]^=1;s[5]^=1}if(m==2){s[8]++;if(s[8]==3)s[8]=0;y(s,0,2,4);s[0]^=1;s[2]^=1}if(m==3){s[9]++;if(s[9]==3)s[9]=0;y(s,3,4,5);s[3]^=1;s[4]^=1}q=0;for(a=9;a>=6;a--)q=q*3+s[a];for(a=4;a>=0;a--)q=q*2+s[a];return q}function y(p,a,c,t){var s=p[a];p[a]=p[c];p[c]=p[t];p[t]=s}function n(c){return 0|Math.random()*c}u();document.write(b);
 
You must log in or register to reply here.

Similar threads

Xflighenjoyer
what is wrong with my python code
Replies
3
Views
408
SpeedCubingLord
SpeedCubingLord
I
Cube Solver Python Package
Replies
7
Views
5,978
Exmestify
Exmestify
TheDuckCuber
"Singmaster" to "Cubestring" conversion
Replies
4
Views
2,971
Bruce MacKenzie
Bruce MacKenzie
Etotheipi
  • Poll Poll
Finding the best 2-look ZBLL method
2
Replies
32
Views
5,769
Caleb Raphael
C
Etotheipi
Python Cube Project
4 5 6
Replies
114
Views
14,700
Etotheipi
Etotheipi
Back
Top