> My initial implementation worked at a whopping 200 permutations per second. That’s incredibly slow, and meant that it would take well over a century (in the worst case) for my program to finish. Now, it works at about 190,000 permutations per second, with an estimated worst-case search time of 2 months. (I haven’t encountered a scrambled cube position which has taken more than 10 hours.)
> Instead of 10^20 moves to find connecting path(s) towards Solved in a Rubik's cube, this algorithm solves in
2*10^10 from each side (and IIUC the solution side (1*10^10) can be cached?)
Interesting video. The approach in it is also inspired by meet-in-the-middle, but suffers from a significant deficiency: It requires a lot of memory—90 GiB—enough that the author had to borrow their university's compute cluster to conduct a solve, even when written and optimized in C++. Likewise, their "triple DES" presentation discussed another way that would require a database that's terabytes in size (specifically, memory that's O(N^0.5)). Nonetheless, I think it's a good exposition of meet-in-the-middle.
What's neat about the method in the post is that it requires O(N^0.5) time and O(N^0.25) memory, which allows running it on an entry-level consumer laptop (hours of time and a few GiB of memory) when implemented even in a dynamically typed, garbage-collected language.
> It requires a lot of memory—90 GiB—enough that the author had to borrow their university's compute cluster to conduct a solve
I remember something like fifteen years ago we needed a 128GB computer to solve IC modelling (timing closure) problems. While this was reasonably available, the only supplier we could find was gaming-oriented, so we had a blinky light tower PC in the corner of the server cupboard.
Anyway, never underestimate the power of a single computer, especially with a GPU.
It's also not hard these days to fire up an instance on AWS or other cloud service which will have up to a few terabytes of RAM.
Plus, you can always just bite the bullet and do it all out of swap - might not be as bad as you fear, and often can optimize whatever you're doing to be more online. There are countless tricks left over from the old days for doing out-of-core operations efficiently, whether disk or tape.
If you're firing up anything on AWS with that kind of RAM, you want to make sure you understand how much that's going to cost. The per second cost is always going to look really low and you will tend not to worry about it. However, once you do the math, you could find that you're easily and quickly spending more money than it would cost to buy a machine to run locally with that much RAM.
It's been fine when I've used terabyte instances for dynamic programming stuff similar to OP. You are babysitting it and waiting for a specific answer, not running a permanent service which will hemorrhage $$$ when you forget to turn it off. At dollars an hour, hard to forget...
"The algorithmic trick that solves Rubik’s Cubes and breaks ciphers" (2022) https://youtu.be/wL3uWO-KLUE :
> Instead of 10^20 moves to find connecting path(s) towards Solved in a Rubik's cube, this algorithm solves in 2*10^10 from each side (and IIUC the solution side (1*10^10) can be cached?)
The manim code for the video and the c++ solution code are open source: https://github.com/polylog-cs/rubiks-cube-video/blob/main/co...