19
\$\begingroup\$

Whenever you make a move on a Rubik's Cube, there is a reverse move which undoes the first move. Because of this, every algorithm (set of moves) has a reverse algorithm which undoes the first algorithm.

The goal of this challenge is to find the reverse of a given algorithm.

Specification:

The input consists of an array of individual moves. Each move is a string of length 1 or 2. Of course, you can use whatever input format makes the most sense in your language. Each move consists of the structure X or X' or X2, where X is an uppercase or lowercase letter.

To reverse X, simply replace it with X'. Likewise, X' becomes X. X2 on the other hand does not get changed.

To create the output, reverse each move, and then reverse the array.

Examples (strings separated by spaces):

R => R'

D U' => U D'

S T A C K => K' C' A' T' S'

A2 B2 => B2 A2

Scoring:

This is code-golf, so the fewest amount of bytes win. Standard loopholes are not allowed.

\$\endgroup\$
  • \$\begingroup\$ Is R2 -> R2' or B -> B3 allowed? \$\endgroup\$ – CalculatorFeline Jul 6 '17 at 18:01
  • 2
    \$\begingroup\$ Having to handle X3 or X1 would have been a nice addition to the challenge. \$\endgroup\$ – Shaggy Jul 6 '17 at 18:32
  • 1
    \$\begingroup\$ "Because of this, every algorithm (set of moves) has a reverse algorithm which undoes the first algorithm" is this true for every algorithms?? Cause I think the hashing algorithms are one way. Means it doesn't have any reverse algorithms, right? please let me know \$\endgroup\$ – Avishek Saha Jul 7 '17 at 4:21
  • 4
    \$\begingroup\$ @AvishekSaha : For Rubik's Cube problems, "algorithm" is restricted to the meaning "a sequence of moves you can do on the Cube". In this sense, there is no such thing as a one-way hashing algorithm on the Cube. \$\endgroup\$ – Ross Presser Jul 7 '17 at 4:35
  • 5
    \$\begingroup\$ Should have had D2R2 as a test case... \$\endgroup\$ – Neil Jul 29 '17 at 15:49

15 Answers 15

7
\$\begingroup\$

Python 2, 71 57 54 53 bytes

-15 bytes thanks to ovs! -3 bytes thanks to Rod.

lambda l:[i.strip("'")+" '"[len(i):]for i in l[::-1]]

Try it online!

String I/O, 70 bytes

lambda s:' '.join(i.strip("'")+"'"*(len(i)<2)for i in s.split()[::-1])

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ 53 bytes \$\endgroup\$ – ovs Jul 6 '17 at 18:11
7
\$\begingroup\$

V, 13 10 bytes

æGÇä/á'Ó''

Try it online!

3 bytes saved thanks to @nmjmcman pointing out my favorite feature. Explanation:

æG          " Revere the order of every line
  Ç         " On every line not containing...
   ä/       " a digit:
     á'     "   Append an '
       Ó    "   Remove every instance on this line
        ''  "     Of two single quotes
\$\endgroup\$
  • \$\begingroup\$ Does ä like represent a regex when compiled to vim? \$\endgroup\$ – Downgoat Jul 6 '17 at 21:14
  • \$\begingroup\$ @Downgoat Yes! It does. Translated into vim, this solution is :g!/\d/norm A'<CR>:%s/''//g<CR>gg:g/^/m0<CR> More information on how V compresses regular expressions can be found here \$\endgroup\$ – DJMcMayhem Jul 6 '17 at 21:18
  • \$\begingroup\$ @DJMcMayhem Aren't implicit endings like your favorite feature? Try it online! \$\endgroup\$ – nmjcman101 Jul 7 '17 at 16:43
  • 3
    \$\begingroup\$ I know this is quite late, but this doesn't work for me. It turns an R2 into a 2R, which isn't valid \$\endgroup\$ – Jamie Sanborn Jul 30 '17 at 3:15
7
\$\begingroup\$

Retina 0.8.2, 27 26 bytes

\w
$&'
''

'2'
2
O$^`.'?2?

Try it online! Link includes test cases. Explanation: The first stage adds an apostrophe after every alphanumeric. This results in double apostrophes (with or without an inclusive 2) which need to be removed. The final stage reverses the moves.

\$\endgroup\$
  • \$\begingroup\$ Could this be improved with the release of Retina 1.0? \$\endgroup\$ – MD XF Jan 24 '18 at 5:41
  • \$\begingroup\$ @MDXF It seems that O$^ is in fact still the best way of reversing a list of matches, so the byte count is actually unchanged in Retina 1. \$\endgroup\$ – Neil Jan 24 '18 at 10:56
5
\$\begingroup\$

JavaScript (ES6), 45 bytes

s=>s.map(([a,b])=>b?+b?a+b:a:a+"'").reverse()

Shortest solution is to take Array IO. Simple and appropriate use of argument destruction.

String output is +8 bytes for .join` `.

String input, Array output: 69 bytes

(s,k=[])=>s.replace(/\S\S?/g,([a,b])=>k.unshift(b?+b?a+b:a:a+"'"))&&k

f=

(s,k=[])=>s.replace(/\S\S?/g,([a,b])=>k.unshift(b?+b?a+b:a:a+"'"))&&k

;

console.log(["R", "D U'", "S T A C K", "A2 B2"].map(e => `${e} => ${f(e)}`));
<textarea oninput="out.value=(f(this.value)||[]).join` `" placeholder="input here"></textarea>
<textarea id="out" readonly></textarea>

\$\endgroup\$
  • \$\begingroup\$ Nice one. Why do I never think to destructure function parameters?! :( \$\endgroup\$ – Shaggy Jul 6 '17 at 18:31
  • \$\begingroup\$ You should be able to replace .reverse() with ::reverse saving 1 byte but making ES7 \$\endgroup\$ – Downgoat Jul 6 '17 at 21:13
  • \$\begingroup\$ @Downgoat Any place where I can test ES7? \$\endgroup\$ – Conor O'Brien Jul 7 '17 at 2:03
  • \$\begingroup\$ @ConorO'Brien you can use babel online REPL (tick execute and all the preset boxes for all feature): babeljs.io/repl \$\endgroup\$ – Downgoat Jul 7 '17 at 2:35
4
\$\begingroup\$

Jelly, 11 bytes

ḟ;ċ?”'ḣ2µ€Ṛ

A monadic link taking an returning a list of lists of characters (an "array" of "strings").

Try it online! (The footer avoids smashing the output, displaying the list split with spaces.)

How?

ḟ;ċ?”'ḣ2µ€Ṛ - Link: list of lists of characters             e.g. ["F'", "D2" , "R"]
        µ€  - perform the chain to the left for €ach turn instruction:
    ”'      -   literal "'" character
   ?        -   if:
  ċ         -     count (number of "'" in the instruction) i.e.:  1   , 0    , 0
ḟ           -   then: filter out                                  "F"
 ;          -   else: concatenate                                       "D2'", "R'"
      ḣ2    -   head to index 2                                   "F" , "D2" , "R'"
          Ṛ - reverse                                            ["R'", "D2" , "F"]
\$\endgroup\$
  • \$\begingroup\$ 10 bytes with new Jelly. \$\endgroup\$ – user202729 Jun 8 '18 at 9:49
4
\$\begingroup\$

JavaScript (ES6), 46 bytes

Takes input as an array of moves.

a=>a.map(m=>m[1]?+m[1]?m:m[0]:m+"'").reverse()

Test it

Enter a comma separated list of moves.

o.innerText=(f=
a=>a.map(m=>m[1]?+m[1]?m:m[0]:m+"'").reverse()
)((i.value="S,T,A,C,K").split`,`);oninput=_=>o.innerText=f(i.value.split`,`)
<input id=i><pre id=o>


Explanation

a=>

Anonymous function taking the array of moves as an argument via parameter a.

a.map(m=>                       )

Map over the array, passing each string through a function, where m is the current string.

 m[1]?

Check if the string contains a second second character ("'" or "2").

+m[1]?

If it does try to cast that character string to an integer. If the string is "2", it becomes 2, which is truthy. If the string is "'", it becomes NaN, which is falsey.

m

If the previous test is truthy, simply return m.

:m[0]

Otherwise, return the first character of m.

:m+"'"

If the string does not contain a second character then return m appended with a '.

.reverse()

Reverse the modified array.

\$\endgroup\$
  • \$\begingroup\$ Sorry, I just saw this. My own answer is similar to yours :P \$\endgroup\$ – Conor O'Brien Jul 6 '17 at 18:13
2
\$\begingroup\$

Python,  51  48 bytes

lambda a:[(v+"'")[:2-("'"in v)]for v in a[::-1]]

An unnamed function taking and returning lists of strings.

Try it online!

Reverses the input list with a[::-1]; appends a ' to every entry with v+"'"; heads each one to 1 or 2 characters depending on whether the original had a ' in or not with [:2-("'"in v)].

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

Python 3, 91 89 72 70 69 65 bytes

lambda s:[i[0]+(len(i)-2and"'"or"2"*("2"==i[1]))for i in s[::-1]]

Try it online! (With testcases)

Apparantly you don't need to take input and output as strings, so a 69 byte solution is possible

\$\endgroup\$
  • \$\begingroup\$ AFAIK you can delete the space after len(i)==1 \$\endgroup\$ – Stephen Jul 6 '17 at 17:50
  • \$\begingroup\$ @StepHen Huh, didn't know that was allowed (Knew that some interpreters allowed it, just didn't know it's allowed in codegolf) \$\endgroup\$ – sagiksp Jul 6 '17 at 17:54
  • 2
    \$\begingroup\$ Languages are defined by their interpreters here so, if it works in any one interpreter, it's valid. \$\endgroup\$ – Shaggy Jul 6 '17 at 17:55
  • \$\begingroup\$ If the interpreter allows it, you can do it. That's all code-golf cares about ;) \$\endgroup\$ – Stephen Jul 6 '17 at 17:55
  • \$\begingroup\$ len(i)-2 is shorter than len(i)==1 (remember 0 is falsey) \$\endgroup\$ – Stephen Jul 6 '17 at 17:56
1
\$\begingroup\$

Haskell, 43 bytes

map f.reverse
f[x]=x:"'"
f[x,c]=x:[c|c>'1']

Try it online! Declares an anonymous function map f.reverse. Bind to g and use as g["S","T","A","C","K"].

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

PHP, 81 bytes

<?foreach(array_reverse($_GET)as$v)$r[]=$v[1]?$v[1]<2?$v[0]:$v:"$v'";print_r($r);

Try it online!

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

05AB1E, 13 bytes

RεÐ1èQ''si«ëK

Try it online!

Explanation

RεÐ1èQ''si«ëK
R             # Reverse input array
 ε            # Map over each element...
  Ð1èQ         # Is the second char in the element the first one? (Uses the fact that in python indexing loops)
      ''       # Push '
        s      # Swap top items of stack
         i     # If the question above is true...
          «     # Concatenate
           ë   # Else
            K   # Push element without '  
\$\endgroup\$
1
\$\begingroup\$

J, 25 bytes

J handles this one well, other than the unfortunate escape sequence needed to represent a single quote:

|.,&''''`}:@.(''''={:)&.>

We need to represent the list using boxed data, since it's a mix of one and two character items, hence:

  • &.> - "under unbox", which means unbox each element, perform the operation that follows (ie, the symbols explained below) and then rebox when done
  • (''''={:) "if the 2nd character is a single quote"....
  • @. (J's agenda verb, a kind of generalized ternary statement, or a case statement) "then perform the 2nd item on the agenda list, otherwise perform the first"
  • }: (the 2nd item on the agenda list), "remove the last character", ie, the single quote
  • ` (J's tie verb) You can think of this as the agenda item separator
  • ,&'''' (first item on agenda list) "add a single quote to the end"
  • |. "reverse"

Try it online!

\$\endgroup\$
0
\$\begingroup\$

R, 51 bytes

function(u)sub("((2)|')'","\\2",paste0(rev(u),"'"))

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Ruby, 44 bytes

->a{a.reverse.map{|i|i[1]?i.tr(?',''):i+?'}}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Java 8, 141 128 126 bytes

a->new StringBuffer(a.replaceAll("(.)","$1'").replace("'''","").replaceAll("(.)'","'$1").replaceAll("'(.)'2","2$1")).reverse()

Takes input as single String without spaces (i.e. RUR'URU2R'U).

Explanation:

Try it online.

a->new StringBuffer(           // Method with String parameter and StringBuffer return-type
  a.replaceAll("(.)","$1'")    //1  Add an apostrophe after every character
   .replace("'''","")          //2  Remove all occurrences of three adjacent apostrophes
   .replaceAll("(.)'","'$1")   //3  Reverse letter+apostrophe to apostrophe+letter
   .replaceAll("'(.)'2","2$1") //4  Reverse letter+2 to 2+letter and remove aphostrophes
  ).reverse()                  //5 Reverse everything

Example of the steps above, with as given input: RUR'URU2R'U

  1. RUR'URU2R'UR'U'R'''U'R'U'2'R'''U'
  2. R'U'R'''U'R'U'2'R'''U'R'U'RU'R'U'2'RU'
  3. R'U'RU'R'U'2'RU''R'UR'U'R'U'2R'U
  4. 'R'UR'U'R'U'2R'U'R'UR'U'R2UR'U
  5. 'R'UR'U'R2UR'UU'RU2R'U'RU'R'
\$\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.