How I solved Mega Cube — Part 3 (Optimize Memory Consumption)
After I implemented the initial code and won some initial victories, I faced some performance issues which have been solved by profiling and using the proper data structure. I have ended up running out of memory on my laptop and the rented virtual machine.
Profiling the memory usage seems the solution in this case (this is a wage indication as getsizeof is only indicating the size of the memory in heap, not the actual size. However that indication showed me which direction I needed to move). The size of explored seems to be the most between other variables from the measuring.
And that makes complete sense as the explored set will always grow and nothing will be removed from it. On the other hand, I used a string of 54 char to store that. That string representation is very easy to work with and track the changes of the moves for the cube but it’s not memory-friendly when it comes to storing a huge amount of state in a variable like explored which always grows.
The fact is that each cube has 54 pieces and each piece can get only 6 different values (as 6 different colors of each side of the cube). However, I used string in the current implementation. Each string is a list of char and each char can store up to 256 different states/values. Much more than what I needed in this case. If I can reduce this amount of memory consumption, (let say by half), the existing memory (even on my laptop) will be sufficient to solve this problem. So, I have added a new function to be passed as an argument to A* which is supposed to compress the status of each state and then store it in explored. You can follow the code here.
To implement the efficient compress function for this cube representation, I decided to convert each piece’s color to be represented in base 6, and store each side of the cube separately. Each color has a number between 0 to 5 and each position is a digit in that numeric base. To compact it more, I have changed the representation one more time into base 90 and use a 4 digit/char string for each side. To exclude all unfamiliar characters in ASCII code, I have applied some offset change mapping. By using this technique, the representation of each state of a cube was reduced to 24 characters instead of 54.
By applying this technique the last technical issue has been resolved and I could solve my Modified Cube version. Shortly after that, I solved my Siamese Mirror Blocks tower cube.
I know that the solution of this cube was explained in this youtube video, but I wanted to achieve it by implementing a solution that can be used in other situations as well and try some functional programming on real-world puzzles. During this implementation, I found out that Python is not meant for functional programming. There are a lot of hacks here and there to overcome the missing functional aspects of python. That’s why I have decided to learn a purely functional programming language, Clojure, and try to re-implement this solution with Clojure and compare them. Will write a post when I achieve that goal. That might take a while. Until then, see you!!
