Rubik's Cube Solver

Time limit1sMemory limit128 MB

Summary

Apply the listed face rotations to the unfolded cube layout and report whether each face ends up a single color.

Level: Medium5 of 10
Topics: Simulation, Implementation
Solved: No attempts yet

Problem

The Rubik's Cube was invented by Ernő Rubik in 1974. It is a three-dimensional puzzle built from 26 smaller cubes. Each smaller cube has between one and three sides exposed, for a total of 54 exposed sides. Every exposed side carries one of six colors, and every color covers exactly nine exposed sides. You manipulate the cube by rotating any side of it 90 degrees. The cube is solved when each of its six sides is covered entirely by a single color.

You are a researcher at Rubik's University working on an algorithm that solves a cube in the fewest possible moves from any starting position. That research needs a program that reads cube configurations, performs operations on them, and decides whether the resulting cube is solved.

Input

The input holds a starting configuration of the cube followed by one or more operations to perform on it.

A configuration occupies nine lines and is laid out like this:

      G W O
      G R R
      G B R
B R B R G Y W W W Y G O
G W B O G B Y B O W Y O
W R Y O Y B R Y R G O O
      B R Y
      B O W
      G Y W

Those nine lines follow the layout below.

Each character in the grid is the color of one exposed side of the cube. Characters on the same line are separated by a single space, and a line may begin with several spaces before its first character. The grid shows the cube unfolded and flattened out, and each group of 9 characters (a 3 × 3 array) is one side of the cube. The first 3 lines are the top of the cube. The next 3 lines hold the left, front, right, and back sides in that order. The last 3 lines are the bottom.

The configuration is followed by one or more operations, each on its own line. There are 12 possible operations, each a 90 degree rotation of one of the cube's faces of 9 smaller cubes. One rotation moves 20 colored squares: 8 on the face being rotated and 12 on the sides of the smaller cubes that make up that face. The table below lists all 12 operations with a description of how to perform each one.

The input is a non-empty series of at most 100 data sets, and no blank line separates one data set from the next. A single data set has four parts.

Start line, a single line reading START.
An initial configuration of the cube, 9 lines in total.
One or more operations, each on a separate line.
End line, a single line reading END.

A single line reading ENDOFINPUT follows the final data set.

Operation	Description
`front left`	Rotate the front side counter-clockwise when viewing from the front
`front right`	Rotate the front side clockwise when viewing from the front
`left left`	Rotate the left side counter-clockwise when viewing from the left
`left right`	Rotate the left side clockwise when viewing from the left
`right left`	Rotate the right side counter-clockwise when viewing from the right
`right right`	Rotate the right side clockwise when viewing from the right
`back left`	Rotate the back side counter-clockwise when viewing from the back
`back right`	Rotate the back side clockwise when viewing from the back
`top left`	Rotate the top side counter-clockwise when viewing from the top
`top right`	Rotate the top side clockwise when viewing from the top
`bottom left`	Rotate the bottom side counter-clockwise when viewing from the bottom
`bottom right`	Rotate the bottom side clockwise when viewing from the bottom

Output

Print exactly one line for each data set. Print Yes if the cube is solved, and No if it remains unsolved.

Examples1

Example 1

Input

START
      O O O
      O O O
      O G W
W W W Y B G R B B G G G
B Y W Y B G R G G W W R
B Y Y B O O B W W Y Y R
      R Y Y
      B R R
      G R R
front right
top right
left left
bottom right
END
START
      Y B B
      O G B
      G R B
W W B R Y Y R G G O O O
R O O G B R G R O Y W W
Y G Y O R G W B G O Y W
      B B R
      W Y Y
      R W W
back left
top right
left right
right right
front left
bottom right
right left
END
ENDOFINPUT

Expected output

Yes
No