My somewhat botched method of solving the Rubik’s cube

The Rubik’s cube is a pretty cool and amazing toy, one that I’ve been spending a considerable amount of time playing with recently.

Methods for solving the cube vary. Beginner methods are easy to learn, but the downside is that they’re inefficient, usually taking a hundred moves or more to solve the cube. On the other hand, speedcubing methods often enable the cube to be assembled in fifty or sixty moves, but requires memorization of up to hundreds of move sequences, or algorithms.

The most common speedcubing method, usually called the CFOP or Fridrich method, requires memorization of about 70 different algorithms. Naturally, I didn’t want to do so much memorizing.

I learned to solve the Rubik’s cube from this site, which I think is a very good beginner tutorial. For the rest of this article, I will assume that the reader already solves the cube using this method, and furthermore I will use their notation and conventions. That is, this article would be a sort of extension to the tutorial.

The method provided is basically as follows:

1. Solve the first two layers
2. Orient the edges
3. Permute the corners
4. Orient the corners
5. Permute the edges

The site gives 7 algorithms to solve the last layer (5 algorithms plus 2 mirror ones). As a result, any of steps 2-5 may require two sub-steps to do.

Here I provide 9 additional algorithms, making it possible to solve each of steps 2-5 in a single step. This makes a 4-step last layer with a total of 16 algorithms.

I will not be listing the original 7 algorithms: they are already available on the linked site.

Orienting the edges

In this step we want to form a yellow cross, that is, all four yellow edges are oriented so that yellow is facing up.

In addition to the three cases already covered, here’s a special algorithm for the fourth case:

R U2 R2 F R F’ U2 R’ F R F’

Permuting the corners

Next we make it so the corners are in the right place (although not necessarily the right orientation). The usual method for this is switching two corner pieces. However, in one case both corner pieces have to be swapped.

You can apply the algorithm twice, or you can use this algorithm:

L U2 R’ U L’ U’ R L U2 L’

Orienting the corners

Now we want the corners to all be oriented, that is: have yellow facing up on all of them. The only algorithm here that’s really needed is the one that rotates groups of 3 pieces clockwise (or counterclockwise) 120 degrees all at once. Any case can be solved with at most a combination of two of these.

The first two cases are when exactly three of the corners are facing incorrectly. The two algorithms needed are already covered.

Next, there are two similar looking cases where all four pieces are facing incorrectly:

R U R’ U R U’ R’ U R U2 R’

The other case is similar, but a little bit different:

R U2 R2 U’ R2 U’ R2 U2 R U2

There is one case where two diagonal corners are oriented incorrectly:

L B’ D2 B L’ U2 L B’ D2 B L’ U2

Finally there are two cases where the two adjacent corners are oriented incorrectly. Here’s one:

R’ U’ R U’ R’ U2 R2 U R’ U R U2 R’

The other one, which is basically the reverse:

R U2 R’ U’ R U’ R2 U2 R U R’ U R

Permuting the edges

The final step now is permuting the edges. There are two algorithms already, to rotate a group of three edges clockwise (or counterclockwise). The other two cases can be done in a combination of two substeps.

The first one, where edges need to be swapped oppositely:

R2 L2 D R2 L2 U2 R2 L2 D R2 L2

Or the other case where edges need to be swapped adjacently:

R’ U’ R U’ R U R U’ R’ U R U R2 U’ R’ U2

And this is it. We’re done!

Facebook: Simon Says – How to set up Thrift on Windows

I’ve been doing some of the Facebook Engineering Puzzles recently, and in a previous blog post I described how to solve the problem User Bin Crash.

The problem User Bin Crash would be considered a batch problem. Such problem requires a program that takes some input, and produces some output. All the judge does is feed your program the input and check its output.

Thrift problems are a bit different. Such a problem would be an interactive problem, where the judge program has to interact with your program.

In the facebook puzzles, Simon Says, Rush Hour, Battleship, and Dinosaur island are interactive problems. All of the rest of the problems are batch.

Interactive problems are submitted in a different way from regular problems, as well. You, the programmer, are required to make a Thrift program, and instead of sending it to run on their server, you run your program on your own computer. The program connects to the facebook servers via Thrift. A successful program will return a special code which can be used to claim credit for a problem.

Because of the nature of interactive problems, they are somewhat difficult to set up. Thrift itself is rather new and its documentation lacking. When making my first Thrift submission, I found a few difficulties. No adequate tutorial exists on this topic, so this post may be of some use to future puzzlers.

Prerequisites

Simon Says is, after all, a simple test problem to help you get set up with Thrift.

This tutorial is relevant most if you are using the Java programming language, and are using Windows with Cygwin. If you’re using a different language, or a different platform, parts of this document may not apply to you.

Cygwin is required because the thrift compiler itself does not run natively on windows. Only the base cygwin is necessary to run the thrift compiler.

Step 1: Setting up the Thrift compiler

The official Thrift package comes only with the source code, and no linux nor cygwin binaries. As building anything from source is a tricky and error-prone process, we’re not going to compile Thrift from source (even though the official documentation recommends us to do so).

I wasn’t able to compile Thrift from source, but I found someone else’s cygwin Thrift binaries. I’ll put a link to it:

thrift.zip (2.5 mb)

To run this in Cygwin, extract thrift.exe to /cygwin/bin/.

This Thrift binary is of version 0.20, which is not backwards compatible with 0.10. The Thrift wiki provides cygwin binaries to 0.10, which isn’t very useful for us since the code generated by 0.10 can’t be used to solve Facebook problems.

Anyways, this compiler will likely be obsolete soon, and 0.3x will likely break backwards compatability again.

The Thrift compiler compiles your thrift source into source code into a language of your choice. The outputted source code contains much of the code handling networking, protocols, etc.

To run the thrift compiler, navigate to the directory containing simonsays.thrift (while in cygwin), and run,

thrift --gen java simonsays.thrift

You should now have a directory called gen-java. At this point we just need the stuff in gen-java, and we don’t need the thrift compiler anymore. We can also switch back from the cygwin shell.

Part 2: Setting up the Java libraries

To build and run a Thrift Java program, we need to link a few libraries. The first library is the Java thrift library, which I’ve named thrift.jar.

Another dependency is SLF4J, a logging framework required by the Thrift libraries. I’m not sure why it really needs this library, but we need this to compile the code. I’ve named this library slf4j.jar.

Here’s a download link to the two jar files:

javathrift.zip (189 kb)

Now we’re ready to begin coding. In a new directory, place the two jar files and the gen-java folder; create your source file in this folder as well.

Part 3: Coding the problem

The problem itself is very simple. On each round, you receive a list of colors via startTurn(), and send the colors back one by one in order using chooseTurn(). When you’re done, call endTurn() (which also tells you if there’s more rounds).

In the beginning, call registerClient() with your facebook email address; at the end, call winGame() to receive the special password.

Here’s my implementation (simonsays.java):

import org.apache.thrift.*;
import org.apache.thrift.transport.*;
import org.apache.thrift.protocol.*;
import java.util.*;

public class simonsays{
    public static void main(String[] args) throws Throwable {

        // Set up the thrift connection to the Facebook servers
        TTransport transport =
            new TSocket("thriftpuzzle.facebook.com", 9030);
        TProtocol protocol = new TBinaryProtocol(transport);
        SimonSays.Client client = new SimonSays.Client(protocol);
        transport.open();

        // Register client
        client.registerClient("your.email@gmail.com");

        boolean done = false;

        while(!done){

            // Retrieve color list
            List<Color> listColors = client.startTurn();

            // Some debug information
            System.out.println(listColors.size());

            // Play back colors list
            for(Color color : listColors){
                client.chooseColor(color);
            }

            // If we're done, endTurn() will return true.
            done = client.endTurn();
        }

        String pwd = client.winGame();
        System.out.println(pwd);
    }
}

Compiling the code:

javac -cp .;./thrift.jar;./slf4j.jar;./gen-java simonsays.java

Running the code:

java -cp .;./thrift.jar;./slf4j.jar;./gen-java simonsays

If you did everything correctly, the program should output the numbers 1 to 31 and finally a line like this:

simonsays(8d96b611989c0d38b0c47703a37466c5)

Part 4: Submitting the code

Be sure to replace my email with your own email if you wish to receive credit for the problem.

From the email you provided in registerClient(), send an email to puzzles@facebook.com, with the subject as the line outputted by the program.

If you want, you can also attach your source code, but that’s not needed. We’re done!

Yet another Quine tutorial

A quine is a program that prints its own source code. For example, this would be a quine (save as quine.hs):

main = putStr =<< readFile "quine.hs"

When the program is run, the following output is produced:

main = putStr =<< readFile "quine.hs"

Although this program technically prints its own source code, this wouldn’t be considered a real quine. A real quine cannot read its own source code from a file.

A first approach

Usually the most obvious way to approach this problem is to print a program, something like this:

main = putStr "main = putStr \"Hello\""

Of course, this isn’t really a quine, because the output of this program is main = putStr "Hello". Although the program prints another program, a quine must reproduce itself.

It’s clear that this approach isn’t going to work.

The structure of a Quine

One distinguishing feature of a quine is part of the program’s code encoded as a string. We’ll make this the structure of attention:

Usually there are code before and after this string. We’ll call them A and B:

Now the important thing is the code inside the quotes is a character for character representation of everything after the ending quotation:

Perhaps this would be a better representation of the structure:

Up to this point we haven’t mentioned what the code should contain. Here is a rough guideline:

You can see here that the code is printed twice. The first time, we print it the way it appears in the string, handling the quotations, and escapes (if any). The second time we print it normally.

Here’s a quine in Haskell:

s = "\nmain = putStr (\"s = \" ++ show s ++ s)"
main = putStr ("s = " ++ show s ++ s)

A major problem faced when writing quines is how to print the quoted code exactly as it appears in the source code.

Fortunately for us, we don’t have this problem in Haskell because the show function does exactly this.