Get smart curated videos delivered to your inbox.   SUBSCRIBE

# What algorithmic trick solves Rubik’s Cubes and breaks ciphers?

Watch more with these video collections:

How fast can you solve the Rubik’s cube? In 2016, Feliks Zemdegs set a world record for solving a 3×3 Rubik’s cube in just 4.73 seconds. “I can’t compete with that,” explains the narrator of the Polylog YouTube channel, “but maybe my computer could if we redefine ‘fast’ a little bit.”

“Instead of time, let’s measure the number of moves it takes to solve a cube and let’s find an algorithm that will help us solve any cube the fastest, thereby, in a way, beating Feliks Zemdegs.”

“You’ll see that the algorithm will lead us to a surprisingly general technique that can also be used for completely different things such as breaking ciphers.”

That technique is called Meet in the Middle.

Much like Six Degrees of Separation—the premise that any two people in the world are connected to each other by no more than six intermediate relationships or acquaintances—Meet in the Middle looks to connect two states via the shortest path, and starts at both states to get there instead of starting at one and ending at the other.

“Now, we could run this algorithm for other graphs, not just the Rubik’s cube graph, but for it to work, it’s really crucial that the number of explored nodes grows exponentially in the number of steps. That ensures that if we walk half the distance we only see a tiny fraction of the nodes.”

The last third of the video, starting around 9m40s, focuses on the DES (Data Encryption Standard) algorithm and how this Meet in the Middle approach can break ciphers.

via Kottke.

This Webby award-winning video collection exists to help teachers, librarians, and families spark kid wonder and curiosity. TKSST features smarter, more meaningful content than what's usually served up by YouTube's algorithms, and amplifies the creators who make that content.

Curated, kid-friendly, independently-published. Support this mission by becoming a sustaining member today.

This video was posted 6 months ago.