My python one-liner scramble generator

[guzman]

I see the error in mine:

c=b; // then
b=m;

not the inverse.

 

[Marcell]

Oh that's right. But that's easily solvable by applying the trick eariler:

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

116 characters. Up for testing at http://kerulo.uw.hu/miniscr/miniscr2.php


Edit: Ech... still invalid. Opposite letter error.

 

[guzman]

Oh that's right. But that's easily solvable by applying the trick eariler

Edit: shoudln't it be: $b=$m+0*$i++*$c=$b ?
'cause the righthand side is evaluated first.

 

[Marcell]

Oh that's right. Thanks.

for($i=$b=$c=0;$i<25;$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)].' '

116 chars, still longer then your javascript code with all that crazy evaluation stuff.

Unfortunately I know squad about perl, but I think the perl code could be shortened with some of these tricks too.
Also, php let me use & and | instead of && and ||, maybe perl would do so as well.

 

[guzman]

116 chars, still longer then your javascript code with all that crazy evaluation stuff.

Yeah, the if part in php and all those () are cumbersome, and of course all the $'s

The comma (,) is also helpful in javascript

 

[Marcell]

Yeah. But as for javascript, "math.random" and "document.write" are just painful.

 

[guzman]

Yeah. But as for javascript, "math.random" and "document.write" are just painful.

Yeah, I thought we could reach shorter versions with php,
I dont know perl either, I would like to.

Edit: That was fun. Thanks.

 

[Marcell]

It really was.
But I don't think it's finished yet

 

[guzman]

So far. Various authors and contributions:

perl: 107

map{$m=int rand 6until($c+$b-5||$c-$m)&&$m-$b;print+(U,R,F,B,L,D)[$m].qw(' 2)[rand 3]." ";$c=$b;$b=$m}1..25

javascript: 115

r=Math.random;for(c=b=j=0;j<25;c+b==5&c==m|b==m||document.write("URFBLD"[j++,c=b,b=m]+" 2'"[0|r()*3]+" "))m=0|r()*6

php: 116

for($i=$b=$c=0;$i<25;$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)].' '

mathematica: 166

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})]

pyton: 273

c,a,l,f,g=__import__('random').choice,['FB','UD','RL'],[],lambda y:lambda x:x in y,lambda y:lambda x:x not in y;h=[l.append(c(filter(g(l[-1:]),c(filter(g(filter(f(a),[''.join(l[-2:][::x]) for x in [-1,1]])),a))))) for u in range(25)];print ' '.join([h+c(" '2") for h in l])

(it's nice that horizontal scroll bars look as indicators in a graph, at least with my browser and screen)

EDIT:
I removed the Ruby program since it wasn't able to give all kind of valid scrambles:

 

[qqwref]

- the program has to give a sequence of 25 letters chosen randomly amogn RFULBD,
- each letter appears with an "exponent" chosen ramdomly among 1,2,3: that is, for instance R may appear as R, R2 or R',
- consecutive letters cannot be the same
- if R follows L, the next letter cannot be L again (and similarly for the other opposite letters in whatever form they appear).

More specifically:
- A scramble is a 25-move sequence, where each move is one of the 6 letters URFBLD with one of the 3 suffixes "", "2", "'". The moves should have a single space between them (but I wouldn't say this is required.)
- In a valid scramble, two consecutive moves may not have the same letter, and three consecutive moves may not have the letters X Y X (for X and Y being any two opposite sides, i.e. R/L, U/D, or F/B).
- A scrambling program must be able to print out ALL valid scrambles (assuming of course that the RNG can output all possible sequences of sufficient length), and must not print any non-valid scrambles.


EDIT: By the way, although the above Perl scrambler works (same mechanism as the JS one), the Ruby one does not. Because it switches axis every move, it cannot ever print scrambles containing sequences like R L or F2 B'.

 

[joey]

Lame, I didn't know that. I'll try write a Ruby one sometime.

 

[Stefan]

perl: 107

map{$m=int rand 6until($c+$b-5||$c-$m)&&$m-$b;print+(U,R,F,B,L,D)[$m].qw(' 2)[rand 3]." ";$c=$b;$b=$m}1..25

I think you can replace "int " with "0|" there as well.

And here's a longer (currently 111 bytes) but quite simple and straightforward approach very close to Michael's definition:

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

The following (with 107 bytes) also works, but I'm unsure about the randomness:

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

 

[Johannes91]

The following (with 107 bytes) also works, but I'm unsure about the randomness:

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

Sweet! I thought of using regexes but couldn't come up with something so short.

However, if we include in the requirements that every valid scramble must be generated with equal probability - and I think we should* - that code doesn't pass. It discriminates against sequences containing UD or FB or RL.

* Problems with a language implementation's implementation of rand() can be ignored, of course.

 

[qqwref]

However, if we include in the requirements that every valid scramble must be generated with equal probability

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.

Can anyone write an efficient adaptation of this algorithm (here in pseudocode)?:

do {
 generate random sequence of 25 faces
} until the sequence contains no duplicates or sequences such as RLR
randomly add a suffix after each face

 

[PatrickJameson]

Can anyone write an efficient adaptation of this algorithm (here in pseudocode)?:

do {
 generate random sequence of 25 faces
} until the sequence contains no duplicates or sequences such as RLR
randomly add a suffix after each face

Here's my implementation at 122 chars(stealing Stefan's RLR etc part of the regex). There must be a better way to do the regex.

do{@a=map{(U,R,F,B,L,D)[rand 6]}1..25}while(join'',@a)=~/((.)\2|LRL|RLR|UDU|DUD|FBF|BFB)/;print$_.qw(' 2)[rand 3]." "for@a

Edit: And another, mixing around a few things. Still 122.

do{$_=join'',map{(U,R,F,B,L,D)[rand 6]}1..25}while/((.)\2|LRL|RLR|UDU|DUD|FBF|BFB)/;print$_.qw(' 2)[rand 3]." "for split//

 

[keemy]

C++ 115 (111 w/o needing spaces between)

for(int c=0,b=0,j=0;j<25;){int m=rand()%18;c+b==5&c==m%6|b==m%6||(cout<<"URFBLD"[j++,c=b,b=m%6]<<" 2'"[m/6]<<" ");}

Basically the same as the JS one with few modifications(to make it work), also I don't really program so changes are probably nub. Though I liked my idea of only using 1 random number a loop and just *6 and /6 for the choices(and it was the first way I got it to work lol).

 

[guzman]

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:

choose a random axis (say we choose the RL axis),
choose randomly if there's gonna be two moves (with probability 1/5) or one move (with probability 4/5) on that axis:
if we need two moves: choose randomly between R L and L R
if we need one move: choose randomly between R and L,
apply random suffixes to each letter (none, 2, or ')
repeat process changing axis.

Does that make sense ?
I think it gives each scramble the same probability
that we get by choosing random moves at each turn.

So, the idea is to decompose a scramble as follows:
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.

Dunno if it can be implemented more efficiently than what we have.
__________________

I'll update the list of algs later
(and I'll remove the wrong Ruby program).

 

[PatrickJameson]

Edit: And another, mixing around a few things. Still 122.

do{$_=join'',map{(U,R,F,B,L,D)[rand 6]}1..25}while/((.)\2|LRL|RLR|UDU|DUD|FBF|BFB)/;print$_.qw(' 2)[rand 3]." "for split//

Using /./g instead of split// and removing the outer parentheses in the regex we get 116 chars.

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

 

[joey]

115 my first attempt with ruby.

(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}*" "

edit:

115 again, but this time it prints. (I was working in IRB so it printed automatically)

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}*" "

 

[Stefan]

Using /./g instead of split// and removing the outer parentheses in the regex we get 116 chars.

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

115 with spaces before turns instead of after:

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