Login or Sign Up to become a member!
LessThanDot Site Logo

LessThanDot

A Technical Community for IT Professionals

Less Than Dot is a community of passionate IT professionals and enthusiasts dedicated to sharing technical knowledge, experience, and assistance. Inside you will find reference materials, interesting technical discussions, and expert tips and commentary. Once you register for an account you will have immediate access to the forums and all past articles and commentaries.

LTD Social Sitings

Lessthandot twitter Lessthandot Linkedin Lessthandot facebook Lessthandot rss

Note: Watch for social icons on posts by your favorite authors to follow their postings on these and other social sites.

Highly Rated Users

Forum
No Posts Rated

Top 50
Given
Received

Forum Statistics

Users
Members:
1875
Members Online:
3
Guests Online:
75

Total Post History
Posts:
81446
Topics:
18714

7-Day Post History
New Posts:
0
New Topics:
0
Active Topics:
0

Our newest member
konam534As

Other

FAQ
All times are UTC [ DST ]

Google Ads

Rubik's cube mixture

Mind Boggling Puzzles, to keep that grey matter in shape...
Forum rules
Always post answers in a "Hidecode" tag, so that others have a chance to answer the question too.
Please wait...

Rubik's cube mixture

Postby Thirster42 on Thu Nov 11, 2010 5:50 pm

A Rubik's cube is a 3x3 cube, with each face having a different color. The point of a Rubik's cube is to scramble the cube, and then solve it so that the cube is back to it's original position.

In the cubing world, God's Algorithim (the supposed algorithim to solve any cube pattern in the least moves) was 25 moves. This number was recently recude to 20. However, competitions still use 25 moves to scramble a cube.

There are a total of 18 non-redundent ways to move the faces on a cube to solve/scramble it. Here's a variable table witht he moves:

Code is hidden, SHOW


Here's the puzzle: produce a list of 25 random, non-redudent moves to scramble a solved cube.

The issue, however, is that a random list of 25 moves might have some redundancies. Such as:

R' R' L D2 D'

The two R' could be simplified to R2, the D2 D' could be simplified to D. The final result to your solution should have 25 moves that can't be simplified.

edit- updated info

edit 2- check here for visuals on cube notation


when holding a cube directly in front of you with one face directly at you the notation goes like this:

face facing you: F
face opposite face facing you: B
Left Face: L
Right Face: R
Top Face: U
Bottom Face: B

when you see a letter corresponding to a face, it means rotate that face clock-wise as if it was facing you. A ' means rotate it counter-clock-wise as if it was facing you. A 2 means rotate that face twice.
Ask three DBAs a question, and you’ll get four different answers.

-Brent Ozar
User avatar
Thirster42
Guru
Guru
LTD Silver - Rating: 517LTD Silver - Rating: 517LTD Silver - Rating: 517LTD Silver - Rating: 517LTD Silver - Rating: 517
LTD Silver - Rating: 517LTD Silver - Rating: 517LTD Silver - Rating: 517
 
Posts: 4646
Joined: Tue Nov 11, 2008 5:49 pm
Location: Jefferson City, Mo
Unrated

Re: Rubik's cube mixture

Postby kaht on Thu Nov 11, 2010 9:22 pm

Thirster42 wrote:In the cubing world, God's Algorithim (the supposed algorithim to solve any cube pattern in the least moves) was 25 moves. This number was recently recude to 22. However, competitions still use 25 moves to scramble a cube.


Actually, just about 4 months ago "God's Number" was changed to 20:

http://www.cube20.org/
#8
AlexCuse is n better than me.
User avatar
kaht
LTD Admin
LTD Admin
LTD Silver - Rating: 252LTD Silver - Rating: 252LTD Silver - Rating: 252LTD Silver - Rating: 252LTD Silver - Rating: 252
LTD Silver - Rating: 252
 
Posts: 1383
Joined: Wed Oct 10, 2007 6:49 pm
Location: STL
Unrated

Re: Rubik's cube mixture

Postby Thirster42 on Thu Nov 11, 2010 9:29 pm

kaht wrote:
Thirster42 wrote:In the cubing world, God's Algorithim (the supposed algorithim to solve any cube pattern in the least moves) was 25 moves. This number was recently recude to 22. However, competitions still use 25 moves to scramble a cube.


Actually, just about 4 months ago "God's Number" was changed to 20:

http://www.cube20.org/


yup, you're right.
Ask three DBAs a question, and you’ll get four different answers.

-Brent Ozar
User avatar
Thirster42
Guru
Guru
LTD Silver - Rating: 517LTD Silver - Rating: 517LTD Silver - Rating: 517LTD Silver - Rating: 517LTD Silver - Rating: 517
LTD Silver - Rating: 517LTD Silver - Rating: 517LTD Silver - Rating: 517
 
Posts: 4646
Joined: Tue Nov 11, 2008 5:49 pm
Location: Jefferson City, Mo
Unrated

Re: Rubik's cube mixture

Postby ThatRickGuy on Thu Nov 11, 2010 9:40 pm

I'm not all up to snuff on the leet Cube lingo, can we get a bit of meaning on the "R" "R'" "R2" etc... meanings and operations? For instance why does R' + R' = R2 and D2 + D' = D?

-Rick
O_o \__o- \__o- \__o- \__o-
User avatar
ThatRickGuy
LTD Admin
LTD Admin
LTD Silver - Rating: 311LTD Silver - Rating: 311LTD Silver - Rating: 311LTD Silver - Rating: 311LTD Silver - Rating: 311
LTD Silver - Rating: 311
 
Posts: 1598
Joined: Thu Oct 11, 2007 3:21 pm
Location: Madison, WI
Unrated

Re: Rubik's cube mixture

Postby kaht on Thu Nov 11, 2010 11:10 pm

Ok, played mr. procrastinator and took a stab at this instead of doing stuff I should be working on... :blush:

Code is hidden, SHOW


I was able to do it all in one query, but due to the nature of rand() I didn't really see a way to do it completely set-based. In other words, I don't really know if this is possible w/o a loop of some sort.
#8
AlexCuse is n better than me.
User avatar
kaht
LTD Admin
LTD Admin
LTD Silver - Rating: 252LTD Silver - Rating: 252LTD Silver - Rating: 252LTD Silver - Rating: 252LTD Silver - Rating: 252
LTD Silver - Rating: 252
 
Posts: 1383
Joined: Wed Oct 10, 2007 6:49 pm
Location: STL

Re: Rubik's cube mixture

Postby kaht on Thu Nov 11, 2010 11:20 pm

ThatRickGuy wrote:I'm not all up to snuff on the leet Cube lingo, can we get a bit of meaning on the "R" "R'" "R2" etc... meanings and operations? For instance why does R' + R' = R2 and D2 + D' = D?

-Rick


Assuming you're looking straight at a cube, each of the 6 faces will be named as follows:
Image

The cube is turned in the picture so that you can see more faces. But, assuming you were holding the pictured cube with the yellow face toward you, it would be the F face (front). The blue face would be the R face (right). Green (not pictured) would be the L face (left) and so on.

Now that each face is identified, the turning notation is as follows:

R - turn the right face clockwise (with respect to that face)
R' - turn the right face counter-clockwise (with respect to that face)
R2 - turn the right face 2 times (a.k.a. 180 degrees)

The prime & 2 notation applies to all faces. For example, L' means turn the left face counter-clockwise and B2 means turn the back face 2 times.

With all that said, answering your specific questions from above:

R' + R' means to turn the right face counter-clockwise twice. Which is equivalent to an R2 move.

D2 + D' means to turn the down face twice, and then an additional 1 more time counter-clockwise. This would be equivalent to one clockwise turn of the down face.
#8
AlexCuse is n better than me.
User avatar
kaht
LTD Admin
LTD Admin
LTD Silver - Rating: 252LTD Silver - Rating: 252LTD Silver - Rating: 252LTD Silver - Rating: 252LTD Silver - Rating: 252
LTD Silver - Rating: 252
 
Posts: 1383
Joined: Wed Oct 10, 2007 6:49 pm
Location: STL
Unrated

Re: Rubik's cube mixture

Postby ThatRickGuy on Thu Nov 11, 2010 11:46 pm

Excellent! Now if my laptop will stop blue screening on me, I might get some work done so I can toy with that later :)

-Rick
O_o \__o- \__o- \__o- \__o-
User avatar
ThatRickGuy
LTD Admin
LTD Admin
LTD Silver - Rating: 311LTD Silver - Rating: 311LTD Silver - Rating: 311LTD Silver - Rating: 311LTD Silver - Rating: 311
LTD Silver - Rating: 311
 
Posts: 1598
Joined: Thu Oct 11, 2007 3:21 pm
Location: Madison, WI
Unrated

Re: Rubik's cube mixture

Postby Naomi on Fri Nov 12, 2010 4:00 am

Check if this may be close to your problem
http://en.community.dell.com/support-fo ... ageIndex=5
Premature optimization is the root of all evil in programming.
Donald Knuth, repeating C. A. R. Hoare
Naomi
Senior Sage
Senior Sage
LTD Bronze - Rating: 234LTD Bronze - Rating: 234LTD Bronze - Rating: 234LTD Bronze - Rating: 234LTD Bronze - Rating: 234
 
Posts: 1754
Joined: Thu Mar 26, 2009 5:46 am
Location: WI
Unrated

Re: Rubik's cube mixture

Postby ThatRickGuy on Fri Nov 12, 2010 3:56 pm

Code is hidden, SHOW


Not optimized at all, but should do the trick in VB.Net.

-Rick
O_o \__o- \__o- \__o- \__o-
User avatar
ThatRickGuy
LTD Admin
LTD Admin
LTD Silver - Rating: 311LTD Silver - Rating: 311LTD Silver - Rating: 311LTD Silver - Rating: 311LTD Silver - Rating: 311
LTD Silver - Rating: 311
 
Posts: 1598
Joined: Thu Oct 11, 2007 3:21 pm
Location: Madison, WI

Re: Rubik's cube mixture

Postby vongrunt on Fri Nov 12, 2010 11:50 pm

Single query, recursive logic, RAND() hack, no joins and no CASE/WHEN statements ;):
Code is hidden, SHOW
How many SEO experts do you need to change a lightbulb lightbulbs buy light bulbs neon lights sex p0rn
User avatar
vongrunt
Senior Apprentice
Senior Apprentice
LTD Bronze - Rating: 103LTD Bronze - Rating: 103LTD Bronze - Rating: 103
 
Posts: 151
Joined: Thu Mar 27, 2008 3:21 pm
Location: Space sector 2814

Re: Rubik's cube mixture

Postby ThatRickGuy on Sat Nov 13, 2010 12:31 am

Even more simplified, still VB.Net. Since the array contains all possible moves, there is no need to combin. Just ensure that the last move was not on the same axis as the new random move:

Code is hidden, SHOW


-Rick
O_o \__o- \__o- \__o- \__o-
User avatar
ThatRickGuy
LTD Admin
LTD Admin
LTD Silver - Rating: 311LTD Silver - Rating: 311LTD Silver - Rating: 311LTD Silver - Rating: 311LTD Silver - Rating: 311
LTD Silver - Rating: 311
 
Posts: 1598
Joined: Thu Oct 11, 2007 3:21 pm
Location: Madison, WI
Unrated

Re: Rubik's cube mixture

Postby vongrunt on Sat Nov 13, 2010 1:11 am

Without running VS it looks like code is checking only last move. Is it enough to prevent sandwich cases like L R L?

Also: if you "block" axis for next move (e.g deny both L or R after L) this will reduce randomness a bit.
How many SEO experts do you need to change a lightbulb lightbulbs buy light bulbs neon lights sex p0rn
User avatar
vongrunt
Senior Apprentice
Senior Apprentice
LTD Bronze - Rating: 103LTD Bronze - Rating: 103LTD Bronze - Rating: 103
 
Posts: 151
Joined: Thu Mar 27, 2008 3:21 pm
Location: Space sector 2814
Unrated

Re: Rubik's cube mixture

Postby Thirster42 on Mon Nov 15, 2010 3:42 pm

Alright grunt, i like your solution, but i don't understand how it works. could you explain it please?
Ask three DBAs a question, and you’ll get four different answers.

-Brent Ozar
User avatar
Thirster42
Guru
Guru
LTD Silver - Rating: 517LTD Silver - Rating: 517LTD Silver - Rating: 517LTD Silver - Rating: 517LTD Silver - Rating: 517
LTD Silver - Rating: 517LTD Silver - Rating: 517LTD Silver - Rating: 517
 
Posts: 4646
Joined: Tue Nov 11, 2008 5:49 pm
Location: Jefferson City, Mo
Unrated

Re: Rubik's cube mixture

Postby ThatRickGuy on Mon Nov 15, 2010 6:03 pm

Bah, I hadn't considered an L R L combination.

I can account for it though.

-Rick
O_o \__o- \__o- \__o- \__o-
User avatar
ThatRickGuy
LTD Admin
LTD Admin
LTD Silver - Rating: 311LTD Silver - Rating: 311LTD Silver - Rating: 311LTD Silver - Rating: 311LTD Silver - Rating: 311
LTD Silver - Rating: 311
 
Posts: 1598
Joined: Thu Oct 11, 2007 3:21 pm
Location: Madison, WI
Unrated

Re: Rubik's cube mixture

Postby vongrunt on Mon Nov 15, 2010 9:33 pm

Thirster42 wrote:Alright grunt, i like your solution, but i don't understand how it works. could you explain it please?

A recursive CTE generates sequence in range [0, 25]. Anchor part sets initial values. That row (seq=0) must be removed from results later. Each CTE row has sequence number and historical data (last two moves - curr, prev). Derived table [currentMove] in recursive part of CTE increments sequence, calculates valid moves by removing invalid ones from '123456' and shifts historical data. This thingy:
Code is hidden, SHOW

... checks whether last two moves were on the same axis (12, 21, 34, 43, 56, 65) and returns either former, 2-rounds old move or '0' which has no effect on REPLACE. Basically this bunch of hacks avoids CASE/WHEN and makes everything look cryptic :).

The rest of recursive part simply picks one of valid moves. As kaht indirectly mentioned, RAND() alone is not enough. It returns a single, constant random value per-query. Fortunately NEWID() returns random value per-row so it can be used as base for RAND() seed. To illustrate:
Code is hidden, SHOW

Finally, once outta CTE code translates 1 to F, 2 to B etc... and adds random rotation (0 - clockwise , 1 - double, 2 - ccw).
How many SEO experts do you need to change a lightbulb lightbulbs buy light bulbs neon lights sex p0rn
User avatar
vongrunt
Senior Apprentice
Senior Apprentice
LTD Bronze - Rating: 103LTD Bronze - Rating: 103LTD Bronze - Rating: 103
 
Posts: 151
Joined: Thu Mar 27, 2008 3:21 pm
Location: Space sector 2814
Unrated

Re: Rubik's cube mixture

Postby ThatRickGuy on Mon Nov 15, 2010 10:45 pm

Not really pretty, but it should take care of the issue of "L R L" in VB.Net:
Code is hidden, SHOW


-Rick
O_o \__o- \__o- \__o- \__o-
User avatar
ThatRickGuy
LTD Admin
LTD Admin
LTD Silver - Rating: 311LTD Silver - Rating: 311LTD Silver - Rating: 311LTD Silver - Rating: 311LTD Silver - Rating: 311
LTD Silver - Rating: 311
 
Posts: 1598
Joined: Thu Oct 11, 2007 3:21 pm
Location: Madison, WI
Unrated

Re: Rubik's cube mixture

Postby Thirster42 on Mon Mar 07, 2011 10:37 pm

Well, i finally circled back around to this, and came up with this:

Code is hidden, SHOW



i was actually quite surprised that the logic in the last select worked. i've ran it quite a few times to see if i can produce any erroneous issues, and i haven't seen any.
Ask three DBAs a question, and you’ll get four different answers.

-Brent Ozar
User avatar
Thirster42
Guru
Guru
LTD Silver - Rating: 517LTD Silver - Rating: 517LTD Silver - Rating: 517LTD Silver - Rating: 517LTD Silver - Rating: 517
LTD Silver - Rating: 517LTD Silver - Rating: 517LTD Silver - Rating: 517
 
Posts: 4646
Joined: Tue Nov 11, 2008 5:49 pm
Location: Jefferson City, Mo
Unrated