21
\$\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\$
9
  • \$\begingroup\$ Is R2 -> R2' or B -> B3 allowed? \$\endgroup\$ Jul 6, 2017 at 18:01
  • 2
    \$\begingroup\$ Having to handle X3 or X1 would have been a nice addition to the challenge. \$\endgroup\$
    – Shaggy
    Jul 6, 2017 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\$ Jul 7, 2017 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\$ Jul 7, 2017 at 4:35
  • 5
    \$\begingroup\$ Should have had D2R2 as a test case... \$\endgroup\$
    – Neil
    Jul 29, 2017 at 15:49

17 Answers 17

8
\$\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
  • 1
    \$\begingroup\$ 53 bytes \$\endgroup\$
    – ovs
    Jul 6, 2017 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\$
4
  • \$\begingroup\$ Does ä like represent a regex when compiled to vim? \$\endgroup\$
    – Downgoat
    Jul 6, 2017 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, 2017 at 21:18
  • \$\begingroup\$ @DJMcMayhem Aren't implicit endings like your favorite feature? Try it online! \$\endgroup\$
    – nmjcman101
    Jul 7, 2017 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\$
    – ZTqvhI5vpo
    Jul 30, 2017 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\$
2
  • \$\begingroup\$ Could this be improved with the release of Retina 1.0? \$\endgroup\$
    – MD XF
    Jan 24, 2018 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, 2018 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\$
4
  • \$\begingroup\$ Nice one. Why do I never think to destructure function parameters?! :( \$\endgroup\$
    – Shaggy
    Jul 6, 2017 at 18:31
  • \$\begingroup\$ You should be able to replace .reverse() with ::reverse saving 1 byte but making ES7 \$\endgroup\$
    – Downgoat
    Jul 6, 2017 at 21:13
  • \$\begingroup\$ @Downgoat Any place where I can test ES7? \$\endgroup\$ Jul 7, 2017 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, 2017 at 2:35
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\$
1
  • \$\begingroup\$ Sorry, I just saw this. My own answer is similar to yours :P \$\endgroup\$ Jul 6, 2017 at 18:13
4
\$\begingroup\$

Jelly, 10 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"]
        )  - for each 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\$
1
  • \$\begingroup\$ 10 bytes with new Jelly. \$\endgroup\$
    – DELETE_ME
    Jun 8, 2018 at 9:49
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\$
5
  • \$\begingroup\$ AFAIK you can delete the space after len(i)==1 \$\endgroup\$
    – Stephen
    Jul 6, 2017 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, 2017 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, 2017 at 17:55
  • \$\begingroup\$ If the interpreter allows it, you can do it. That's all code-golf cares about ;) \$\endgroup\$
    – Stephen
    Jul 6, 2017 at 17:55
  • \$\begingroup\$ len(i)-2 is shorter than len(i)==1 (remember 0 is falsey) \$\endgroup\$
    – Stephen
    Jul 6, 2017 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\$
1
\$\begingroup\$

05AB1E, 10 bytes

Rε''«¤ºK2£

I/O as a list of moves.

This is a subset of my answer for the Expand a Rubik's Cube Commutator challenge.

Try it online or verify all test cases.

Explanation:

R           # Reverse the (implicit) input-list
 ε          # Map over its strings:
  ''«       #  Append a "'" to each string
     ¤      #  Push the last character (the "'") without popping the string
      º     #  Mirror it to "''"
       K    #  Remove all "''" from the string
        2£  #  Only keep the first two characters of the string
            # (after which the result is output implicitly)
\$\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 115 bytes

a->(new StringBuffer(a).reverse()+"").replaceAll(".","'$0").replace("'''","").replaceAll("('(2)'|('))(.)","$4$2$3")

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

Try it online.

Explanation:

a->                      // Method with String as both parameter and return-type
  (new StringBuffer(a).reverse()+"")
                         //1  Reverse the input
  .replaceAll(".","'$0") //2  Prepend an apostrophe before each character
  .replace("'''","")     //3  Remove all occurrences of three adjacent apostrophes
  .replaceAll("('(2)'|('))(.)","$4$2$3")
                         //4  Replace '2'C with C2 OR 'C with C' (C is any character)

Example of the result after each step, with RUR'URU2R'U as given input:

  1. U'R2URU'RUR
  2. 'U'''R'2'U'R'U'''R'U'R
  3. 'UR'2'U'R'UR'U'R
  4. U'RU2R'U'RU'R'
\$\endgroup\$
0
\$\begingroup\$

Scala, 47 bytes

Golfed version. Try it online!

_.reverse.map(i=>if(i.last=='\'')i else i+" '")

Ungolfed version. Try it online!

object Main {
  def f(l: List[String]): List[String] = {
    l.reverse.map(i => if (i.last == '\'') i else i + " '")
  }

  val tests: List[List[String]] = List(
    List("R"),
    List("D", "U'"),
    List("S", "T", "A", "C", "K"),
    List("A2", "B2")
  )

  def main(args: Array[String]): Unit = {
    tests.foreach(test => println(f(test)))
  }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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