0
On a Rubik's Cube, performing a particular sequence of moves repeatedly will always return it to its original state. Your job is to figure out the "order" of a particular sequence of moves, that is, the number of times it must be repeated before the original state is restored.
There have been other questions about this in the past:
Order of Elements of the Rubik's Cube
But most of the answers are trivial solutions which simply perform the algorithm on a simulated cube repeatedly and count the repetitions needed to restore it to its original state.
But this question is different because I'm specifically disallowing such trivial solutions. Performing the turns repeatedly on a simulated cube and counting the repetitions that were needed to reach the original state is not allowed. There should be no loop nor recursive call in your program that runs the same or a greater number of times as the order or the sequence unless its purpose is somehow strictly related to golfing and not a functionally necessary part of the calculation of the order itself.
Edit: if you have trouble understanding what “no trivial solutions” or “don’t repeatedly execute the sequence on a simulated cube, and return the number of repetitions that were required to restore it to its original state” means, then you can follow this additional criterion to help: if you choose to execute the sequence on a simulated cube, you may do so no more than 4 times.
The moves are defined in Singmaster Notation. The linked questions explain this quiet well. You're not required to support double moves formatted as "F2", "U2" ect. as input, "FF" and "UU" are acceptable, but the former are also allowed.
Example output (taken from other question):
Move Order
(empty) 1
F 4
FF 2
FFFF 1
U'L' 105
LLUU 6
L'L'U' 30
RUUD'BD' 1260
U'L'U'LU'L'U'U'L 4
R'LFRL'U' 5
Or alternatively:
Move Order
(empty) 1
F 4
F2 2
F2F2 1
U'L' 105
L2U2 6
L2 U' 30
RU2D'BD' 1260
U'L'U'LU'L'U2L 4
R'LFRL'U' 5
This is code golf. The winning answer will be the one with the smallest code.
Conor Henry
Posted 2019-04-05T06:07:55.197
Reputation: 31
5I get what you're going for with the complexity limit, but if you get technical, because the maximum possible cycle size is a constant (1260), the basic turn-the-cube strategy is constant-time. I don't have a good fix offhand. – xnor – 2019-04-05T06:15:06.250
2
The thing which differentiates this question from the earlier ones is unobservable, but if it could be observed then I'm pretty sure some of the previous answers would be permitted anyway. (I'd be astonished if the Gap one was disqualified).
– Peter Taylor – 2019-04-05T06:54:11.857In general, for variations which simply narrow an existing answer the best thing to do is add a bounty with a custom text explaining what you want. Obviously you'd need to get some more rep first. – Peter Taylor – 2019-04-05T06:57:15.777
@xnor I made an edit to try to be more specific about about the requirements. – Conor Henry – 2019-04-05T07:04:34.297
@PeterTaylor per my edit, would you say the difference between preforming moves repeatedly on a simulated cube and reducing sequences to equivalent shorter sequences is unobservable? – Conor Henry – 2019-04-05T07:05:58.973
I'm still inclined to believe this is unobservable. I also don't think it really does what you want. An algorithm that seems to fit the requirements is "Do 1260 iterations, then find the first member that was the identity", which will pretty much always take the exact same amount of time, but does actually perform the moves. – Post Rock Garf Hunter – 2019-04-05T13:49:16.830
Adding a slight requirement change doesn't make this question significantly different from the existing challenge.
– mbomb007 – 2019-04-05T14:12:12.713@SriotchilismO'Zaic I’ve made additional changes that should make it very clear that such approaches are not allowed. Personally I feel there’s very little subjectivity in whether a solution works by repeatedly executing the sequence and counting repetitions or not, and that introducing additional constraints just to make the fact that this type of solution is not allowed clear enough to not be marked as duplicate I’m only limiting people’s ability to come up with creative solutions that don’t violate this rule. – Conor Henry – 2019-04-05T16:47:20.287
@mbomb007 It does if nearly every single answer to the other question relied significantly on such a requirement not being imposed. It’s not like I said “this question but you’re not allowed to use any numbers in your code” or something. The constraint I’m adding doesn’t just make the code harder to golf, make it more difficult for certain languages, or require your code look a certain way. The constraint is central to the logic of the algorithm itself, not just the code. It’s simple: “this problem has a trivial solution, you solution must preform significantly better”. – Conor Henry – 2019-04-05T17:07:39.577
But it still won't be clear. The performance will likely vary based on the interpreter and the computer. It's far better to create a challenge that's not the same as something else with a single added restriction. Make something unique. – mbomb007 – 2019-04-05T18:44:53.077
@mbomb007 I've removed all references to performance and runtime from the question entirely, so this is no longer an issue. And I disagree. The same problem with one interesting constraint can often be an entirely different and much more interesting challenge, like it is for this one. I found the previous version boring since all the responses were just the trivial approach. I'm trying to spark creativity here. But can we at least agree that this is not a duplicate as it stands? – Conor Henry – 2019-04-05T21:23:47.333
1I linked to the meta post about unobservable requirements in part because it explains what they are. Implementing a specific algorithm is explicitly mentioned: avoiding a specific algorithm is equally problematic. – Peter Taylor – 2019-04-06T12:49:11.393
@PeterTaylor Yes and I read that post and other related discussions. My understanding was that saying “use this algorithm” was problematic because it’s very subjective as to how much you can modify a specific algorithm and still say you’re using that specific algorithm. I don’t see how that problem exists in this case. The approach I’m disallowing shouldn’t be very subjective, and the runtime specifications were simply to make this more explicit. With my current edits it should still be completely unambiguous, so I’m not sure what the problem is and I definitely don’t think it’s a duplicate. – Conor Henry – 2019-04-07T01:54:05.600
the correct spelling is perform, not preform – Jo King – 2019-04-08T02:29:24.723
@JoKing Fixed. I would appreciate a vote to reopen since the question is not a duplicate. Thank you. – Conor Henry – 2019-04-08T02:44:29.907
Mmm, sorry I'm on @PeterTaylor's side with this. If you were restricting the complexity to avoid brute-force solutions, I'd be okay with it, but in this case the brute force method is still constant time, which means it is indistinguishable from other methods – Jo King – 2019-04-08T06:11:22.197