=================Instructions============================================================
The data structure itself is not runnable, it is a class that defines each faces and rotation methods for them. The randomizer class will have a driver, that's where the data structure is being executed.
If you are using IDEA Intellij, simply point the project of Intellij to this folder pyraminx_Qiu.
If not, you can find 3 Java file under src/com/pyraminx. Compile all 3 files, Pyraminx.java, Pyraminx_randomizer.java, Pyraminx_const.java. Then run the Pyraminx_randomizer.java. Then a command list should be displayed, enter the command the run specific tasks.
=================Description of the data structure=======================================
The data structure I used is 2D Java Array defined by char[][] pyraminx = new char[4][16]. The 4 stands for 4 faces, and the 16 stands for the number of blocks on each face. I rearranged the index in the array so it will represent the faces in the order I want. To have a better view, here is a layout, each number on the face i represent their order in the array char[face][i].
I call these faces respect to the tip. The four tips are U(up), B(bottom), L(left), R(right) The index 0 in the face will always point at the tip they are representing.
This idea of modeling the pyraminx with respect to their tips, is inspired by this website when I was browsing for the human method to solve the pyraminx: https://www.speedsolving.com/wiki/index.php/Pyraminx_notation
Layout:
L: 9 U: 0 R: 15
11 10 4 1 2 3 8 14 13
13 12 6 5 1 4 5 6 7 8 3 7 6 12 11
15 14 8 7 3 2 0 9 10 11 12 13 14 15 0 2 1 5 4 10 9
B: 15 14 13 12 11 10 9
8 7 6 5 4
3 2 1
0
The good thing is, if I design the array to be this way, when I do the swap for their values, all the faces can be treated same, just the Pyraminx is being held differently.
I have defined 4 main types of rotation, each respect to rotate about their tip. And I have levels from 1-3 for each rotation, represents how many levels you want to rotate with the tip. Every other ways of rotation can be achieved from the rotation I defined.
===================Example Output============================================================
Command List:
"d" for display pyraminx
"s" for scramble pyraminx
"r" for reset pyraminx
"q" to quit
Enter a command:
d
L: Y U: G R: R
YYY GGG RRR
YYYYY GGGGG RRRRR
YYYYYYY GGGGGGG RRRRRRR
B: BBBBBBB
BBBBB
BBB
B
Enter a command:
s
How many moves:
5
Scrambled!
Enter a command:
d
L: Y U: G R: R
YYY GGG RRR
BYYYG BGGGR BRRRY
RBBYGGG BBBGRRB GBBRYYB
B: YYYBGGR
YBBBG
RRR
Y
Enter a command: q
Process finished with exit code 0
==================Description of the Randomizer==================================================
My randomizer is pretty simple since I only defined 4 types of rotations, each with 3 different levels. So, in the randomizer, I'll create two random numbers in the range of [0->3] and [0->2] respectively, generated by Java Random class to randomize the rotation method and the levels. There is a loop that is going to run x times where x is the user specified number of moves. At each iteration, the pyraminx is rotated in one of the 12 rotation methods.
The default setting for my scramble method is to rotate counter-clockwise. I plan to rotate clockwise only when writing my solver. This idea is brought to me by Dr. Goldsmith.
===================Heuristics=====================================================================
For the heuristic, I came up with two simple heuristics. They might not be accurate when being applied to the next program, but they are admissible. I definitely need to refine my heuristic for the next program.
Admissible heuristic 1:
Each face has 3 tips and one center, I simply count the number of tips and centers that are not on its original faces. I added one to each of the misplaced tips/centers, and divide that value by 4, since I'm counting 4 pieces for each face.
The best case for this heuristic would be everything is in its correct position. That would give me a zero.
The worst case for this heuristic would be all tips/centers are out of order, that would give me 4*4/4 = 4. So the upper bound would be 4.
Admissible heuristic 2:
Each face has 3 tips and 3 sub-centers, which are the pieces surrounding the center. I add one for each misplaced tips/sub-centers, and divide that value by 6, since I'm counting 6 pieces for each face.
The best case for this heuristic would be everything is in its correct position. That would give me a zero.
The worst case for this heuristic would be all tips/sub-centers are out of order, that would give me 6*4/6 = 4. So the upper bound would be 4.
====================Learning Outcome================================================================
From this program, I learned that it's difficult to model a real life problem in a real life way. I wanted to model the pyraminx as 3 classes: the face class, the block class which contains different faces, and the frame class where the block goes into. Then I would have a "real" physical pyraminx stored in my computer. Eventually I failed doing it, because things get too complicated. But, I definitely believe that it is achievable.
I also learned this when I was thinking about heuristic: heuristic is an educated guess applied on an algorithm, in order to let the algorithm solve some really time-consuming tasks faster, but taking educated guesses.
One last learning outcome. I started working on this program 5 days before it's due. I thought I should've had plenty of time, but I'm not. Next time I will start as soon as the program is posted.