(New page: Most people who have competed against our GPA4 solution have wondered - how do you do it? For Group 4, this project ended up being more of a resource-utilization exercise than an algorithm...) |
|||
| Line 1: | Line 1: | ||
| − | + | Solving the Cube, Group 4 Style = | |
| − | + | Most people who have competed against our GPA4 solution have wondered - how do you do it? For Group 4, this project ended up being more of a resource-utilization exercise than an algorithmic development application. I will now explain why! | |
| + | <br> | ||
| + | After doing initial research on optimized cube solving algorithms and the A* search (courtesy Prof. Kulkarni), we came across [http://kociemba.org/cube.htm Kociemba's Algorithm]. As some of you have likely already discovered, this algorithm is guaranteed to solve the cube in the minimum number of moves. We downloaded the available source code (already written in C, makefile included) and took the software on a test run. It did exactly what it promised - it solved even the most scrambled cubes in 20 steps or less! The next challenge was implementing the program and conforming it to our program's needs, and vice versa. We labored for a few days trying to convert it to C++, but eventually came to the realization that the best way to implement this solution was *gasp* via shell. (In case anyone is wondering - we did ask for and receive permission from Prof. Lu to implement the available source of Kociemba's algorithm.) | ||
| − | + | <br> | |
| + | Thus the core operation of our program: It takes the 54-character string given by the user/server, converts it to the format used by Kociemba's program, runs the executable with that file, and reads the list of commands that were saved to a file by the executable. We then check this list and edit for disallowed commands, further edit the list to remove any groups of four consecutive commands which might have been added by the previous edit, and then send each command in two different directions. First, the command is sent through a C++ version of GPA1 to retrieve the current cube state. The command is then also sent to the server using the appropriate formatting. In the end, we end up with a cube solved in the minimum possible number of steps. | ||
| + | <br> | ||
| − | As you can see, we did very little algorithmic development. Our solution to GPA4 ended up being more of a systems engineering project in which we tied together all existing, correctly functioning pieces for one correct solution. The challenge was making sure all parts could communicate with each other. | + | As you can see, we did very little algorithmic development. Our solution to GPA4 ended up being more of a systems engineering project in which we tied together all existing, correctly functioning pieces for one correct solution. The challenge was making sure all parts could communicate with each other. |
| + | <br> | ||
| + | Best, | ||
| − | + | Group 4 | |
| − | + | Alex Glenn | |
| − | + | Ryan McLean | |
| − | + | ||
| − | Ryan McLean | + | |
Julien Neidballa | Julien Neidballa | ||
Revision as of 05:40, 6 December 2010
Solving the Cube, Group 4 Style =
Most people who have competed against our GPA4 solution have wondered - how do you do it? For Group 4, this project ended up being more of a resource-utilization exercise than an algorithmic development application. I will now explain why!
After doing initial research on optimized cube solving algorithms and the A* search (courtesy Prof. Kulkarni), we came across Kociemba's Algorithm. As some of you have likely already discovered, this algorithm is guaranteed to solve the cube in the minimum number of moves. We downloaded the available source code (already written in C, makefile included) and took the software on a test run. It did exactly what it promised - it solved even the most scrambled cubes in 20 steps or less! The next challenge was implementing the program and conforming it to our program's needs, and vice versa. We labored for a few days trying to convert it to C++, but eventually came to the realization that the best way to implement this solution was *gasp* via shell. (In case anyone is wondering - we did ask for and receive permission from Prof. Lu to implement the available source of Kociemba's algorithm.)
Thus the core operation of our program: It takes the 54-character string given by the user/server, converts it to the format used by Kociemba's program, runs the executable with that file, and reads the list of commands that were saved to a file by the executable. We then check this list and edit for disallowed commands, further edit the list to remove any groups of four consecutive commands which might have been added by the previous edit, and then send each command in two different directions. First, the command is sent through a C++ version of GPA1 to retrieve the current cube state. The command is then also sent to the server using the appropriate formatting. In the end, we end up with a cube solved in the minimum possible number of steps.
As you can see, we did very little algorithmic development. Our solution to GPA4 ended up being more of a systems engineering project in which we tied together all existing, correctly functioning pieces for one correct solution. The challenge was making sure all parts could communicate with each other.
Best,
Group 4
Alex Glenn
Ryan McLean
Julien Neidballa
