21
\$\begingroup\$

Your task is to create a random sequence of moves, which can be used to scramble a Rubik's Cube. Such a scramble is made up of exactly 25 moves. Each move consist of of the letters UDRLFB optionally followed by one of the suffixes '2.

This notation is called the Singmaster notation. UDRLFB represents one of the 6 faces and the optional suffix '2 represents the turning angle. This information is in no way necessary to solve the task.

To assure, that the scrambles are of 'good quality', the following two rules have to apply:

  • Two consecutive moves must not have the same letter. This bans the consecutive moves UU, DD, RR, LL, FF and BB and all their combinations using the optional suffixes like U2U or U'U'.

    These move pairs are banned, because they can easily reduced to 1 or 0 moves. U2U has the same effect as U', R'R the same effect as .

  • Three consecutive moves must not be of the same letter group. The letter groups are UD, RL and FB. This rule additionally bans the consecutive moves UDU, DUD, RLR, LRL, FBF, BFB and all their combinations using the optional suffixes like U2DU, RL'R or B2FB'.

    The groups sort the faces by their move axis. U and D are in the same group, because both turn around the same axis. Therefore an U move doesn't influence the pieces of the D face, and a D move doesn't influence pieces of the U face. Therefore the two moves can be exchanged, UDU has the same effect as UUD, and this can be reduced to U2D.

Challenge

Write a script or a function, that generates one random scramble. There is no input. The script / function has to print the 25 moves without separation or separated by one space or return the correspondent string.

Your program has to be able to create every single scramble, which satisfies the rules above. Of course assuming, that the random number generator is true random, and not pseudo random.

This is code-golf. The shortest code (counted in bytes) wins.

Examples outputs:

Calling the script / function 3 times should print / return something like:

R'B2R2F2R2FB'R2DR2ULFB2RB'U2B'FL'BR'U'RB'
U'DBR'B2U'B'U'RUF'B'RDR2U'B'LR'B'F2D2UF2L'
BR2F'B'R'D'R'U2B'F2D2R'F2D'F'D2R2B'L2R'UB'R2L'D

If you separate the moves by a space each:

R2 L' F2 U2 D' R2 L2 F L' D2 U R B D' U2 L B2 L U B2 D U2 R' D2 U'
B R D2 F U2 B' R2 F2 B' U' L' R2 B U2 R' D B' F' U2 R' B' L R D2 R2
B2 R2 U D' B R D' R L2 D2 L2 R B2 F U' F2 B2 U' F U' D F R2 U2 B'

Notice, that all these outputs consists of 25 moves, but have different lengths, because of the optional suffixes. It's not allowed to print a space, when either 2 or ' are uses as suffix. You have to print L2UR2F'R'U2 or L2 U R2 F' R' U2. L2U R2F'R'U2 is not allowed.

\$\endgroup\$
  • \$\begingroup\$ Did you mean UR 2 is not allowed? U R2 should be allowed, I think, since spaces between moves makes sense. \$\endgroup\$ – mbomb007 Mar 5 '15 at 19:19
  • \$\begingroup\$ @mbomb007 I mean stuff like L2U R2F'R'U2. U has no optional suffix and therefore shouldn't have a space. A space should not be a replacement for the optional suffix. \$\endgroup\$ – Jakube Mar 5 '15 at 19:35
  • \$\begingroup\$ What if there are spaces between every move? Could we output U F2 L D2 R'..., for example? In this case, there isn't an extra space, which I think should be okay according to your rule. \$\endgroup\$ – mbomb007 Mar 5 '15 at 19:37
  • \$\begingroup\$ @mbomb007 Yes, I will put it into the description. \$\endgroup\$ – Jakube Mar 5 '15 at 19:39
  • \$\begingroup\$ Isn't the 2 before the letter? o.O \$\endgroup\$ – Oliver Ni Jul 8 '17 at 18:00
6
\$\begingroup\$

CJam, 47 45 bytes

This solution uses an approach that's different from any other posted so far. It takes advantage of CJam's concise list operations to generate the available move list and select one at random each iteraton. Modifiers are simply generated independently.

Try it online.

{BA^2/6,_B-?A:B-mr0=:A"UDRLFB"=3mr[L2'']=}25*

Explanation

{               "Loop...";
  BA^2/           "If the two previous moves were not from the same group, ...";
  6,              "... then produce the available move list [0 1 2 3 4 5], ...";
  _B-             "... else produce the available move list [0 1 2 3 4 5] with
                   the second previous move removed";
  ?
  A:B             "Save the previous move as the second previous move";
  -               "Remove the previous move from the available move list";
  mr0=            "Randomly select an available move";
  :A              "Save this move as the previous move";
  "UDRLFB"=       "Map this move to its character (implicitly printed)";
  3mr[L2'']=      "Randomly select a modifier (implicitly printed)";
}25*            "... 25 times";
\$\endgroup\$
9
\$\begingroup\$

C,129

f(){int i,n,m,r,s,t;for(i=26;i--;i<25&&printf("%c%c","URFDLB"[s%6],"'2"[r%3])){for(n=m,t=1;t;t=m*n==9)m=(r=rand()%15)/3+1;s+=m;}}

The inner loop generates a value of m in the range 1..5 which when added to s and taken modulo 6, ensures that no two consecutive moves are on the same side of the cube. The old value of m is stored in n and the test m*n==9 ensures that the value m=3 is never generated twice in a row (so opposite faces cannot be picked twice in a row; note the order of faces in the string.)

The least significant part of r is used to decide which suffix (', 2 or null) to use, taking advantage of the null character at the end of "'2".

The outer loop runs 26 times. The first time, U can never be picked, so printf is suppressed for the first iteration.

Ungolfed code in test program

The ungolfed code puts a space between each move for clarity (the golfed code does not, in order to save one byte.) Additionally the golfed code saves a semicolon by relocating the printf within the for bracket.

f(){
  int i,n,m,r,s,t;
  for(i=26;i--;){
    for(n=m,t=1;t;t=m*n==9)m=(r=rand()%15)/3+1;
    s+=m;
    i<25&&printf("%c%c ","URFDLB"[s%6],"'2"[r%3]);
  }
}

main(){
  int j;
  srand(time(0));
  for(j=0;j<5;j++)f(), puts("");
}

Typical output

U' B D2 B' R' L F' D2 B D2 B2 R' B2 U D2 F' R U R' L B' L R2 B2 F'
U B U B F L2 D2 B' U' L B L R' D B U' D R D' B' F2 D' B D R
L D F2 B2 R' U F B' D2 L U R' L' U2 F' R F D U2 B L' B' U L2 F'
R2 B' F2 R2 L2 F' U2 L U' B' F R' D' F2 D F' L2 U2 R' D' B2 D F R2 L'
U2 F2 B2 D' F D F R L2 U' B D2 L' R D R F2 R' F2 U2 D R' D2 L F2
\$\endgroup\$
  • \$\begingroup\$ 124 bytes \$\endgroup\$ – MD XF Dec 25 '17 at 18:08
4
\$\begingroup\$

Pyth, 65 66

I've never really golfed in Pyth, maybe written a program or two. This is basically @steveverrill's solution translated to Pyth. Improvement suggestions are welcome.

Update: added 1 byte to make scrambles also start with U. Maybe the C solution is relying on undefined behavior to make it work...

=YO6V25JZK1WK=GO15=Z/+3G3=Kq9*ZJ)~YZpd+@"URFDLB"%Y6?@"'2"%G3>2%G3k

I believe this should be done with less assignments, but that would require me to modify the algorithm a lot. (Well, might try.)

Here's an explanation based on the C code:

=YO6           s = random.choice(range(6))
V25            for i in range(25):
  JZ               n = m
  K1               t = 1
  WK               while t:
    =GO15              r = random.choice(range(15))
    =Z/+3G3            m = (r + 3) / 3
    =Kq9*ZJ            t = 9 == m * n
  )
  ~YZ              s += m
  pd               print(..., end = " ")
  +                ... + ...
  @"URFDLB"%Y6     "URFDLB"[s % 6]
  ?@"'2"%G3>2%G3k  "'2"[G % 3] if 2 > G % 3 else ""
\$\endgroup\$
  • \$\begingroup\$ Switch the variables Y and Z. Z is preinitialized with 0, so you save the first 3 chars. \$\endgroup\$ – Jakube Mar 6 '15 at 9:54
  • \$\begingroup\$ @Jakube But then I need to set n = m (3rd explanation line), which must mean n = 0 the first time, which in turn would require Y to be 0. \$\endgroup\$ – PurkkaKoodari Mar 6 '15 at 10:09
  • \$\begingroup\$ Y is preinitialized with an empty list []. And I don't think the value of n matters in the first iteration. \$\endgroup\$ – Jakube Mar 6 '15 at 10:12
  • \$\begingroup\$ Btw, your code doesn't produce scrambles that start with U. \$\endgroup\$ – Jakube Mar 6 '15 at 10:12
  • \$\begingroup\$ @Jakube thanks, fixed. \$\endgroup\$ – PurkkaKoodari Mar 6 '15 at 10:37
4
\$\begingroup\$

JavaScript (ES6) 175 178 204

Edit 3 bytes less, 1 by changing the code and 2 by changing the way bytes are counted (not counting F=)

The code to avoid repetitons is taken from @stevemiller. His way of managing the letter groups is even better, but i'm not going to steal it.

Bonus: you can optionally specify the number of moves.

(n=25,R=n=>Math.random()*n|0)=>(r=>{for(N=_=>'UDRLFB'[(r-=~R(5))%6],b=N(a=N(s=''));n;~(a+b+c).search('^([UD]*|[RL]*|[FB]*)$')?0:s+=(--n,a=b,b=c)+["","'",2][R(3)])c=N()})(0)||s

Less golfed

(n = 25) => 
{
  R = n => Math.random()*n | 0;
  N = _ => 'UDRLFB'[(r += 1+R(5)) % 6];
  r = 0;
  b = N();
  a = N();
  for(s = '' ; n; )
     c = N(),
     ~(a+b+c).search('^([UD]*|[RL]*|[FB]*)$')
       ? 0
       : s += (--n, a=b, b=c) + ["","'",2][R(3)];
  return s
}

Test

var F=
(n=25,R=n=>Math.random()*n|0)=>(r=>{for(N=_=>'UDRLFB'[(r-=~R(5))%6],b=N(a=N(s=''));n;~(a+b+c).search('^([UD]*|[RL]*|[FB]*)$')?0:s+=(--n,a=b,b=c)+["","'",2][R(3)])c=N()})(0)||s

function go() {
  console.log(F(+M.value))
}

go()
Moves <input type=number min=1 id=M value=25 max=999>
<button onclick='go()'>Test</button>

\$\endgroup\$
2
\$\begingroup\$

Javascript - 112

for(c=b=j=25,r=Math.random;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
\$\endgroup\$
2
\$\begingroup\$

Java 8, 189 183 bytes

v->{for(int i=26,n,m=0,r=0,s=0,t;i-->0;){for(n=m,t=1;t>0;t=m*n==9?1:0)m=(r=(int)(Math.random()*15))/3+1;s+=m;if(i<25)System.out.print("URFDLB".charAt(s%6)+(r%3<1?"'":r%3<2?"2":""));}}

Port of @LevelRiverSt's C answer. I tried some things myself, but this was shorter than what I had..

Try it online.

\$\endgroup\$
2
\$\begingroup\$

Ruby, 116 107 105 95 bytes

->{(0..r=l=m=24).map{m=rand 6while l==m||r/2==l/2&&l/2==m/2;r=l;l=m;'RLFBUD'[m]+" '2"[rand 3]}}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Clojure, 223 bytes

(let[R(range)F(fn[f p c](apply concat(filter f(partition-by p c))))](apply str(map str(take 25(F(fn[p](<(count p)3))(zipmap"UDLF""1122")(F(fn[p](=(count p)1))int(for[_ R](rand-nth"UDRLFB")))))(for[_ R](rand-nth[""\'\2])))))

This relies heavily on the "sequence -> partition-by -> filter -> concat" pattern, it is used to filter out "illegal" sequences of faces. This seq is then mapped to string together with a random postfix (including the empty string).

Ungolfed starting point:

(->> (for[_(range)](rand-nth"UDRLFB"))
     (partition-by int)           ; "identity" would be the correct fn to use here
     (filter(fn[p](=(count p)1))) ; Only one identical value in partition
     (apply concat)
     (partition-by(zipmap"UDLF""1122")) ; R & B are in the implicit nil group
     (filter(fn[p](<(count p)3)))       ; Only 1 or 2 consecutive faces from a group
     (apply concat)
     (take 25))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.