Timeline for How to represent a Rubik's Cube in a data structure
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 19 at 2:47 | comment | added | Wyck | This doesn't describe the orientation of the middle face of each side. Some variations of cubes have pictures on the sides instead of just solid colours and the orientation matters. An official cube has a logo on the center of the white side whose orientation relative to the other faces may change. | |
| Dec 17, 2018 at 15:05 | comment | added | alexander | and what datatype should the array be? Integer, Color or a complex type? | |
| Apr 4, 2012 at 16:22 | vote | accept | Mel | ||
| Apr 4, 2012 at 11:34 | comment | added | MaR | [6][X][X] will probably yield the most convenient solution. Imho forget lists - those just obfuscate need for convenient model of cube surface. | |
| Apr 4, 2012 at 11:03 | comment | added | Sergey Kalinichenko |
@JamesAnderson I wouldn't call it "a problem", just a point of complexity: edges and corners move as one, but they still have two and three faces, each of which is represented in the 6*X*X array. I agree that these cases do require special attention - that's why I called methods to manipulate the array "ugly".
|
|
| Apr 4, 2012 at 10:35 | comment | added | prusswan | @PeterAllenWebb the argument on perspective is spot on. Some perspectives that actually represent an identical problem, can be radically different but are suited for their respective unique situations (tic-tac-toe vs sum-to-15) | |
| Apr 4, 2012 at 8:28 | comment | added | James Anderson | Problem here is that the "edge" cubes exist on two "planes" and the "corner" cube exits on "three" planes. The 6 x 6 x 6 model assumes that each face is separate. | |
| Apr 3, 2012 at 16:05 | comment | added | PeterAllenWebb | As someone who has actually written programs to manipulate a Rubik's Cube, I took the simple approach of using six two-dimensional arrays, one per face. It's true that you have to implement some fundamental operations on the cube that are a little annoying, but after that you are free to forget about the representation. It was never a problem for me. I often wondered how other representations would work from a performance perspective, but never felt burdened from a coding perspective. | |
| Apr 3, 2012 at 15:16 | comment | added | Sergey Kalinichenko |
@Simon The two options that you suggest are equally valid. As long as the number of items is 6*X^2, their organization does not particularly matter (after the discussion in the comments I like the [6][X][X] more and more, though).
|
|
| Apr 3, 2012 at 15:13 | comment | added | Simon Bergot | in any case, shouldn't your answer be [6][X*X] or [6][X][X] ? | |
| Apr 3, 2012 at 15:08 | comment | added | maple_shaft♦ | @dasblinkenlight I see your point, but not entirely sure how much more complex a "read" will be. If the individual block knows certain properties about its given state then I can ask all manner of complex queries and get an answer quickly without a complex algorithm. (Eg. How many edge pieces are in the correct position? A. Loop through all edge type blocks and look where the adjacent centers have the same color as the edge piece on that side) Dead simple algorithm. | |
| Apr 3, 2012 at 15:02 | comment | added | Sergey Kalinichenko | @maple_shaft "Which is exactly what a more robust data structure will give you." I don't know about that: a data structure with more "structure" to it would necessarily bring about additional incidental complexity related to setting up, maintaining, and accessing individual parts of that structure. It is hard to say what would be more complex - implementing ugly shifts on a plain array with some corner cases plus a "free ride" on accessing individual cells, or a structure with a somewhat less complex shifts and somewhat more complex reads. | |
| Apr 3, 2012 at 14:42 | comment | added | maple_shaft♦ |
As long as you know how the six surfaces are "threaded" together Which is exactly what a more robust data structure will give you. I think we are arguing for the same thing. An array sides, and a side being an array of blocks, however there is a lot of interesting properties about sides and blocks that help figure out that "threading" Don't really like that term because it can be confused with multi-threading ;)
|
|
| Apr 3, 2012 at 14:38 | comment | added | Sergey Kalinichenko | @maple_shaft The idea is to hide the simple structure behind a convenient interface. As long as you know how the six surfaces are "threaded" together in groups of four in each of the three cardinal dimensions, the algorithms shouldn't be too complex either, all you need to do is to pay attention to corner (literally!) cases. | |
| Apr 3, 2012 at 14:19 | comment | added | maple_shaft♦ | This will work but your algorithm will probably be inordinately complex to accomodate such a simple data structure. | |
| Apr 3, 2012 at 12:17 | comment | added | jk. | even a real Rubik's cube doesn't have any inner mini-cubes | |
| Apr 3, 2012 at 12:15 | comment | added | Mel |
nothing is wrong with it. I just wanted to know how other people would tackle this problem. honestly I thought of the minicube[][][] approach first and I know its far from the best answer! I like the idea: unit test it to death. lol
|
|
| Apr 3, 2012 at 12:09 | history | answered | Sergey Kalinichenko | CC BY-SA 3.0 |