The trick that solves Rubik’s Cubes and breaks ciphers

What do the Rubik's cube and a cipher from the 70s have in common? Let's find out.
Our Patreon: / polylog
0:00 Rubik's cube
9:40 DES
------------------------
Links:
Feliks setting the 4.73 record
• Rubik's Cube World Rec...
webpage "God's number is 20"
www.cube20.org/
The fact it was verified computationally that every cube can be solved in at most 20 moves is super impressive and much more complicated than the problem of solving just one cube that we covered in this video!
Four degrees of separation on Facebook
arxiv.org/pdf/1111.4570.pdf
Code:
github.com/polylog-cs/rubiks-...
------------------------
Fill in the gaps:
Convince yourself that the meet in the middle algorithm finds the shortest path!
Convince yourself that the meet in the middle algorithm for Rubik's cube does not need to know that every cube can be solved in 20 steps.
------------------------
Real Algorithms:
The first algorithms solving a random scramble like Korf's algorithm
www.cs.princeton.edu/courses/...
work roughly as follows:
First, although there are around 10^20 possible cube configurations, if you focus on just the possible configurations of 8 corner cubies, the number of possibilities drops to around 10^8. Using breadth first search, you can precompute for each such configuration of corner cubies how many steps you need to put them into the correct position. You need at least that many steps to solve the full cube configuration, probably even more as you need to solve not just the corners but also the edges.
You can now iterate a breadth first search from your scrambled cube, each time looking into further distance from it. For each cube you look up in your table of size 10^8 to find how many steps, at least, are needed to finish the search. If it is more than the current maximum distance you are looking at, you stop searching, as you can be sure you will not find the solved cube in this branch of the breadth first search.
This approach is similar to the meet in the middle algorithm in that we first precompute some information from the solved cube and then run breadth first search from the scrambled cube. However, now you need much less memory.
The actual state of the art algorithms are more complicated than that. You can read more about it e.g. here.
en.wikipedia.org/wiki/Optimal...
------------------------
More Connections:
The meet in the middle trick is also called "bidirectional search" in the context of searching graphs.
en.wikipedia.org/wiki/Bidirec...
Computing the exact number of states of a Rubik's cube (we used it is around 10^20) is not so hard.
• Why Are There 43,252,0...
The graphs where the number of nodes in your distance grows exponentially are pretty important in computer science. For example, there are scale-free networks and expander graphs.
en.wikipedia.org/wiki/Scale-f...
en.wikipedia.org/wiki/Expande...
Triple DES is kind of a hack made to prolong the life of the DES cipher when it became apparent that it is not strong enough. However, because of the meet in the middle attack, its "security level" is only 2*56 bits and not 3*56 bits as one would naively expect. But you still need to apply DES three times. So you can guess it is not the most efficient way of doing the encryption; it is now superseded by the so-called AES standard.
en.wikipedia.org/wiki/Advance...
------------------------
Riddles:
If you like to solve algorithmic puzzles, here you can find more algorithmic problems that can be solved with this technique:
• Meet in the Middle | T...
wiki.algo.is/Meet-in-the-middle
Try to prove, just with pen, paper and calculator that there is a cube for which at least 16 moves are needed to solve it.
Try to convince yourself that by blind search of the cube graph you cannot beat the sqrt(N) time, at least if you do not use anything else than that the graph "looks random". Hint: Birthday paradox
------------------------
Attributions:
To make this video, we used manim, a Python library:
docs.manim.community/en/stable/
The color palette we use:
ethanschoonover.com/solarized/
Photo of Grant Sanderson:
/ grantsanderson
Thumbnail: Alžběta Volhejnová

[@Thesnakerox]

Fun fact: The WCA (World Cubing Association, basically the governing body for competitive cubing) actually has an event called FMC (Fewest Moves Challenge), in which you are given a scramble, three cubes, some paper and a pen, and a set amount of time, and your goal is to find the shortest solution you can. However in that event, they check your solution against those of other competitors rather than a computer.

[@Quazex]

In theory, I love FMC, but in practice, i am so bad at it it's not even funny.

[@teamcyeborg]

Ah yes, WCA FMC TAS

[@FakeDane]

Small nit-pick: it's just called "Fewest Moves" 😉

[@FreddieStarWars]

@@FakeDane But it's also called FMC

[@FakeDane]

@@FreddieStarWars if you find a WCA document where it's called FMC let me know so I can get it corrected!

[@marc-andreservant201]

This is kind of the point of endgame tables in computer chess. Instead of evaluating every position fully, you start from the checkmate and work backwards, building up a database of positions that are won/lost. Then you select a move that will take you from your current position to a winning position

[@tatoute1]

The problem is that there is a large number of check mate positions,and probably most of then are unreachable.

[@animowany111]

@@tatoute1 Actually, with tablebases you are only concerned with game states with a small number of pieces on the board (to make it viable to solve), and I'm fairly certain all 7men game states in the tablebases are reachable by legal games (it does some fairly fancy filtering to not calculate positions with illegal pawn structures, and all other positions are likely reachable by pawn (under)promotion and a bunch of moves)

[@attilatorok5767]

@@tatoute1 Oh you can do some stuff with chess things. A suprising amount of work went into chess engines. The hard thing in chess is that there are a lot of peices making calculations go very big very fast. In the engame the peice count means a lower amouont of variation and thus a significant drop in possible positions. Considering how fast exponentials grow you still cant calclate all possible positions, there is also moves that become circular in 1 or more moves, a lot of difficulty with a bruteforce aproach. The possible number of positions is something like (just coming up with it on the spot): normal peices: 64 bishops: 32 pawns: 8*(rank_of_pawn - 1) + * 4 * 64 (this ignores pawns only being able to go sideways with a diagonal) multiply all the these together for each peice. Like a quasi-exponentitation based on the number of peices ignore positions where the king is in check and its the opposite-colored sides turn and it is not a checkmate as this is impossibe (you also dont have to store them) ignore positions where the king is attacking the other king (also impossible but technically escapes the previous criteria becouse you also cant attack the king with the king for checkmate) (you also dont have to store them) And then you would have to calculate all the legal moves from all these positions wich would be a lot in and of itself. And then you have to select from all these favorable roots the one that you consider the best by whatever mechanism. Using heuristics tough you can select for only the most likely wich is what not-ai-based engines do (its also possible to use the ai as a heuristic). When you dont need an exact answer but something that is the best lets say 90% of the time and good-enough in the other 10% wich is the case in chess engines and many other applications (GPS, city logistics, friend networks, etc.)

[@PolylogCS]

@@tatoute1 good point, in practice the chess tables are not built starting from checkmate as suggested by André, but starting from all positions with at most ~5 (or some other number) pieces on board. So the principle is kind of meet-in-the-middle-ish, also in that you need to store these huge tables so you trade time/performance with memory. EDIT: missed that animowany111 already said the same thing ;)

[@DarkVoidIII]

The thing about chess is that there's an opening strategy that is pretty hard to defeat and practically guarantees a win. It's to do with which pawn is moved at the start of the game, and it makes for a very short game, if the opponent uses it. I'm not going to mention it since it is already known to at least one KZbin chess strategy content creator.

[@deidara_8598]

Unfortunately for DES it's also a Feistel network, which means the decryption function is the same as the encryption function just with the key reversed. This means that certain keys in Triple DES only have security equivalent of Double DES or even just DES, these are known as "weak keys" and is a huge problem for DES. This is why DES is no longer used, and other ciphers like the AES family and ChaCha20 are preferred. These ciphers have their own unique challenges though.

[@PolylogCS]

We considered mentioning that triple DES is outdated and then it did not get in the final version of the video.Thanks for bringing this up!

[@HunterHerbst]

This is the information I wish I'd learned in my Security in Computing course in uni. Instead I had a lazy professor that seemed so uninterested in the course that we pretty much learned about the Cuckoo's Egg and took a final in surface level information. Man gave the final halfway through the semester and called it a day. :/

[@peterkoch3777]

Nah, its not. The bad keys are only a few and you simply avoid them. Second, Triple DES usually is used with the first and third Key being the same. This has been proven to be as secure as three different Keys. Therefore the "difficulty" to break Triple DES is usually given as 2^112 only. Another thing: Rainbow Tables are used in cracking for speed gains by using huge amounts of memory with precomputed intermediate results. Comparable to meet in the middle.

[@Reth_Hard]

About 20 years ago, when I was young, I made my own algorithm and program (in Visual Basic) to encrypt files and I was very proud of it! Basically, for making an encryption key I was using 2 random files (usually two mp3), then, if I remember correctly, I had a loop that was using modulo on every byte in a sequence like this: Source -> Key-1 -> Key-2 -> Encrypted (And backward for decryption) What seemed to be "ingenious" about this method is that since your 2 key files (Ex: random Mp3s) were of different sizes, the resulting "Encrypting Key" was very big without having any obvious repeating sequence, unless you get in the Terabyte territory. I always been curious to know how difficult it would be to crack this algorithm compared to DES or triple DES. One weakness that I knew about this algorithm is that since I was encrypting the file names and directories using this method, if you knew just one file name that was encrypted in this archive, you could probably scan every files on the computer and try to find the matching keys, and also, encrypting a file filled with zeros would be spitting out directly a portion of the encryption key, so, not very good... If I added a password that would've been a lot more secure but the main purpose of this project was to encrypt files without having to remember any passwords. BTW, I am just an amateur, so I really don't have any advanced notion about programing, mathematics or cryptography, it is just a hobby that I have.

[@stephenJpollei]

@@Reth_Hard Sounds like you are very close to reinventing the OTP(One Time Pad). OTP is unbreakable in theory as long as you never reuse pad and pad was random etc. In practice people misuse it.

[@codenamelambda]

You could definitely cut down the memory consumption by a lot by not actually storing the full result, but only what would essentially be a hashmap from the precomputed results to the move sequences, that doesn't actually store the results (as they are implied by the move sequences), and not even the full move sequences - if you only store the first half of the move sequence (since you can always reexplore those missing five moves pretty quickly in comparison to how long the initial exploration took in the first place anyway) that would put this (if I didn't make a mistake calculating it) at about 30GiB, which *is* in range for normal PCs. This *does* come with a lot of recomputation though, by trading memory requirements for computation time again. Another solution is to just use persistent storage media of course though (even if it is much slower, though if you try and optimize for data locality there it *should* not be too much of an issue I *think*. I might be horribly wrong there though)

[@PolylogCS]

Thanks! We were experimenting a bit with some "bloom filters" where we had a huge binary array indexed by hashes of the cubes. These kind of tricks would, as you say, trade some more time for decreased memory, but in the end we decided for the simplest version of the code that kind of worked. :D

[@TechSY730]

You would need to generate a pretty good hashing algorithm that you can prove will have no conflicts. Or at least no conflicts for moves and states that are not isomorphic to each other Since exactly what states and moves they represent is kind of important to solve things.

[@Joe_Payne]

@@TechSY730 you could just check all solutions that conflict after finding the matching hashes. As that will reduce the number of states you have to store for a bit more time.

[@mz00956]

@@PolylogCS my motto. "If it works, don't touch it"

[@attilatorok5767]

I think using persistant memory with big write buckets would be fine. Say you have a 16 GiB pc and you make buckets of 10 GiB. For 90 GiB you would need to do 9 writes and than 9 reads (worst case) wich would not take longer than say 10 minutes combined with an SSD. For a workload that takes 4 hours this time is only a small increase. You could probably speed this up even more if you used a GPU instead. GPUs are very good at graph stuff. (You could possibly use the VRAM too? Idk, not very good at GPU programming.)

[@MechMK1]

In case you want to learn more about this, the generic term is "Time-Memory Tradeoff Attack", where either you sacrifice memory to speed up computation, or do the reverse, where you calculate values on-the-fly instead of storing them (thus increasing computation time, but saving memory).

[@roxannemoore9694]

I'm now trying to invisage the most computationally intensive way to 'reasonably' implement this. Nested loops anyone?

[@toriless]

Using recursion would save memory, you are using memory dynamically not statically.

[@Ricardo-C]

@@toriless today i learned stack memory is free

[@AndiFels]

"The number of possible Rubik's cube configurations is 43." Oh, that's not as much as I tho-- "Quintillion."

[@alien5589]

The visualizations and sound effects are done so well. Nice work!

[@midasredblade236]

Your videos are the epitome of quality over quantity.... IDC if it takes 4 months for the next video, please never lose this beautiful quality you have

[@JackFoz454]

This is fascinating! Your explanations and visualisations are wonderful. Thank you.

[@InOtherNews1]

Criminally underrated KZbin channel. Was absolutely shocked to see that you only had around 300 subscribers! Keep it up! Edit: Fixed my spelling error and didn't realize that wipes the channel hearts :(

[@ganiti_314]

Absolutely correct

[@maximhoeve2087]

wow a week ago he had only 300 subs now it it almost 2k

[@milkjug7800]

the animations an explanations are of incredible quality. better than some channels with millions of subscribers

[@toasteduranium]

@@ganiti_314 is your name in Gujarati? And is that the name of the script? I’ve never seen that script before. I find it interesting that you have a detailed list of expectations for your channel without any videos yet. I’ve stumbled on the future. Good luck.

[@louisdalibard818]

Yes! This is insane!

[@dixztube]

Wow this was fascinating. I’m going to start watching more of your videos. You animate these so amazingly. Great job!

[@bentpen2805]

Instant subscribe. The visualizations and explanations have a rare flavor that deliver flawless pedagogy.

[@GeorgAubele]

Absolutely stunning video! You did a great job explaining it!

[@LiamTolentino]

I'd love to see more videos like this that connect cubing to mathematical concepts. Most math videos I see that talk about the Rubik's cube either explain things purely from the context of cubing or just use the Rubik's cube as a simple example for a certain math concept. I love that this video bridges the gap a bit and actually shows a more direct way that the Rubik's cube relates to mathematics rather than just using it as an example for permutations or something. I also love the visuals you used and how you explained things so well. Keep up the great work; I look forward to learning more from this channel! :D (As for the question at the beginning, I can usually solve it around 23-25 seconds, with my fastest being 18.279 seconds. Nowhere near the likes of Feliks Zemdegs, but I do my best :))

[@CyrusK]

Incredible, loved the visuals and the content. Keep up the great work!

[@153ridzzzz]

The visuals on this channel are just amazing. Helps so much the explain the concept.

[@russelljazzbeck]

This is so cool, thanks for making it easy to understand. This is an epic code challenge!

[@xXx-un3ie]

I learned something new as a programmer of 15 years. Nice work, keep it up! All you need is to have good quality animations like that and some time for people to recognize you and you will be at the top of the youtube game!

[@ismailalim8308]

Me too!

[@Infinityand1]

Beautifully animated and explained, I can't wait to see where this channel goes! You're very skilled!

[@bujin5455]

This video has insane quality for the channel's size. Great job explaining the meet in the middle approach.

[@somebodystealsmyname]

Meet in the middle is a very common CTF target. It's always fun to implement.

[@spinospinellibass]

Great video. I would add that the right part of meet-in-the-middle is fixed through all instances of the problem (all solved cubes are identical), so you could pre-compute it and store it. You would obtain half time at the expense of large memory use. In chess the analogous are the well-known endgames.

[@urbandefinition]

I love the sound design on this video too. It’s a very under appreciated touch that adds to the polish of the video.

[@picklypt]

Amazing quality video. Such an underrated channel , those animations were on point!

[@wChris_]

there is a technique used in the FMC challenge called NISS. This basically allows you to work towards a solved cube, both forward and in reverse. Not only that, but you can switch between the inverse and normal state multiple times when trying to come up with a solve.

[@bboobbee1965]

kzbin.infoXeNFkzqGsMc?feature=share

[@afriedrich1452]

I once said to an Intel interviewer that "top down" design doesn't always work. I explained that you need to do "top down" and "bottom up" at the same time to get a good design. Of course, I didn't get the job. This was when "top down" design was all the rage. Nobody talks about it anymore.

[@david203]

In my experience, you are correct. Various parts of a design, in general, may be more suitable for top-down or bottom-up design. And, in some cases, neither works and you need to implement a finite-state machine, a pattern matcher, an implication solver, a neural net, or some other type of design to get a understandable, maintainable, or natural problem solution.

[@afriedrich1452]

@@david203 Your comment suggests that you probably don't work for Intel, and instead you probably work for a smart Israeli company. I am now glad I didn't get hired at Intel because the ratio of stupid employees is over 50% now.

[@Oxey405]

Greatly explained and beautifully animated ! GG for the work !

[@norasalocin]

Incredible work on research, details in the description, and of course animation ans sound design!! It's amazing how it's easy to recognize Manim-made videos, yet still see the creators' touch for each of them. Anyway, subscribed and bell ready for the next video :-)

[@rubixtheslime]

I give my deepest thanks for putting the cube in the thumbnail in a (theoretically) valid state. Interestingly enough, the Kociemba algorithm (the main computer algorithm used for solving 3x3) is quite similar to what you showed here, at least in the sense that it breaks it up into two halves that more or less meet.

[@PolylogCS]

That is a very interesting observation! If I remember correctly, we actually also lied a bit in the video because we said something like "there is nothing smarter than blindly exploring the configuration space" to motivate meet in the middle. This is not true as Kociemba algorithm or just some A* search rely on the specific properties of the graph...

[@Gameboygenius]

Not only is it valid, it's the starting position of Feliks's cube and you can it being solved at 1:26.

[@toriless]

Yeah, matrix math in interesting concept and how they really calculate the best navigational course.

[@jpdemer5]

I think symmetry could play a big role in optimization: many states are mathematically identical, differing only in which colors are where. You only need to analyze one of them to know how the whole set of states maps out. I think this is what enables human solvers to whip through the problem in seconds: patterns, not colors, are analyzed.

[@scottwilliams895]

This really is outstanding STEM communication, well done! First video I've watched, and already Subscribed

[@ejejej9200]

I love this channel!!! Thank you! So happy to find it and very grateful for your work! 🙏

[@LukasZav]

Thank you for the nice video!

[@Groudon466]

My guy, get yourself more of a social media presence or something- I was expecting you to be one of those math and logic KZbinrs with like a million views per video, and you absolutely can be one. Reddit, Twitter, who knows what else- start posting everywhere, or get a buddy to do so for you. You have all the video quality you need, and I expect you'll explode as soon as the algorithm notices an influx of viewers.

[@PolylogCS]

Thanks, we hope the some competition will help with that :) Though we are more computer scientists than mathematicians.

[@xXx-un3ie]

@@PolylogCS sorry you have to become mathematicians now

[@jamespond3668]

@@PolylogCS this is certainly a good start! I’m not trying to dox myself, but I will say I’m a Data Scientist, and I have family/friends in the social media influencer world that I help on occasion. KZbin has pretty bad discoverability, it’s really hard to build an audience on this platform. The best platform I’ve seen for building an audience is Tik-Tok, and then converting the audience to KZbin. KZbin shorts also have much better discoverability than normal videos, but it’s still not as good as tik-tok. Maybe this information helps you, maybe not. Regardless, your content is extremely well made, and I hope you find success producing these videos!

[@henrivanderriet3895]

@polylog I agree 100% with them. Wow!

[@elissitdesign]

Do highlight shorts of each video on that hellhole called TikTok. He should be blowing up but I find the algorithms like self-absorbed me me me content.

[@AcademiaCS1]

Very interesting. Amazingly built up work. This piece of art is collectable. Thank you so much.

[@JNighty]

Really appreciate the effort you have gone to in explaining this and the attention to detail. I learnt a great deal. Thank you!

[@ollieox9181]

Did it teach you how to solve a cube in 20 moves or less? I completely missed that part.

[@cubest817]

As a cuber, it's interesting and first time I know how computer find the fewest moves count of the 3×3's scramble! Great video👍 (BTW, I'm quite surprised to see Feliks here haha.)

[@PolylogCS]

Thanks! It is also good to know that the algorithms that are actually used are actually a bit more complicated but also faster

[@m4rt_]

6:30 actually, on norwegian tv, they had a gamified version of it where 2 norwegian celebrities were sent so some place like vietnam, then find a random person who is not someone in a gigant city, and then get to a celebrity, for example some hollywood star. And they actually managed to do it, I think it was like 1 or 2 episodes out of like 4 seasons where they failed, and needed 7 people instead of 6

[@xoctor]

Beautiful graphics and explanation. Love it!

[@KeyError]

7:27 as soon as you said that, and gave that visualisation, my mind was like “oooooooooooh!” That’s some awesome teaching right there! Subscribed!

[@lior9156]

This was a very interesting video but I have two things to note. Meet in the Middle (MM) is an algorithm, not necessarily a name for biderctional search - "Bidirectional search that is guaranteed to meet in the middle" published in AAAI 2016. Also, heuristics can cut down the number of explored nodes significantly instead of running two BFSs.

[@gloverelaxis]

yeah while watching this I kept waiting for A* to be mentioned - surely you can use the current sorted-ness / entropy of the cube as a heuristic to massively increase the chances of iterating along the correct path, right?

[@PolylogCS]

Thanks, good points. :)

[@gerardoberlangaiii]

@@gloverelaxis hello, do you have any pointers on how to calculate the entropy of the cube to use as a heuristic? I implemented this myself a couple of weeks ago. KZbin being KZbin just recommended this video to me and I was wondering if I could make my old code faster

[@clarkeelke2805]

⁠@@gerardoberlangaiii you could probably figure out the least number of moves to get any one piece to its correct spot (ignoring all other pieces). the h cost could be the sum of how many moves it takes each piece to get to its correct spot. the only issue would be that this heuristic sometimes (probably pretty often) overestimates so it wouldn’t guarantee to find you the shortest path using a*, but it might find a pretty good path, idk (ik it overestimates because for example if a cube is 1 rotation off, the heuristic would be 8) edit: you could also train a neural net to predict move count based on cube state (trained on precalculated examples of scrambled cubes and the number of moves to solve them) and use that has a heuristic

[@suurion1]

The other use of MITM approach is Shanks Baby-step Giant-step algorithm which solves discrete logarithm problem (DLP), this problem is also a basis for assymetric types of ciphers. The MITM is also a reason why finding a collision between hashes (two different values that have same hash but we dont choose any of them) is "square root easier" than finding value that gives certain hash being given that hash value. In a nutshell... MITM and birthday paradox is a quite a pain in the bottom in some areas concerning cryptography

[@PolylogCS]

Nice examples! How do you view hash collision as an instance of MITM?

[@aiden_3c]

Insanely great video. Walked up to the idea of MiM in a way where it just makes sense as the solution.

[@peitz.design]

Came here by accident, stayed for the beautiful and insightful animation and overall design and even learned something. Great content!

[@LeeDeVilleMath]

Excellent video. Really enjoyed it!

[@freedom_aint_free]

I remember trying to use undergraduate level math in the early 2000's to solve this, at the time I was obliged to "choose" some extra credits in other disciplines than in my course, and as I'd enjoyed linear algebra, I've deiced to study something in that area but more advanced, and as I've always have been a computer enthusiast I was set for Rings, Categories, group theory and etc., I didn't find a general algorithm to solve the Rubik cube but I've discovered many many more math fields and applications of theories in computer science and chase was much better than the catch !

[@hsinhinlim8762]

This is an excellent video and channel. KZbin only suggested this because I am a cuber looking for cubing videos. Keep up the good work, I am definitely subscribing.

[@baksoBoy]

holy shit the animations and sound design in your videos are absolutely incredible!!

[@Wasaby50312]

Your video is so well made. How did you make the visuals for it? The animations I mean

[@user-kc2gi7eq1y]

It's really useful to go through it frame by frame (it starts at around the 00:00:14 mark). You can use "," and "." to step back or forward by one frame, while the video is paused. Unfortunately, there's a lot of blur; but you still get the general idea of what's going on. There's a point (in the 00:00:14.XX range) where he's holding the (vertical) center faces, while rotating both the bottom and top simultaneously (i.e. executing two discrete changes in parallel). Even with an extremely loose mechanism, that can't be easy; although you can definitely tell that the mechanism is super loose-sometimes there are huge wedge shaped gaps between adjacent sides. Also, check out the facial expression of the guy sitting next to him, when he drops the cube after solving it (in the 00:00:18:XX range). It's worth pointing out, as an aside, that that guy himself is clearly no amateur. But unlike the main character, he doesn't visualize the solution and memorize the steps in advance. By comparison, the MC first observes the cube's current state, then figures out in his head the sequence of changes necessary, and finally executes this predetermined sequence all at once, without pause or backtracking, and in fact even eliminates one of the steps in the process (by carrying it out in parallel with the previous step). It's almost as impressive as observing the Red Bull Formula One Pit Crew change all four tires in 1.82 seconds-and that's only because of the perfect choreography of 20 individuals working in perfect sync, literally with 100% trust in each other, which is ultimately what makes the seamless transition between the different stages of the process (and in fact some parallelism in stages: if you frame step through that video, you can clearly see that the center-locking nut is already in the process of being removed, before the car has stopped moving and before it's lifted up at the front and rear; so by the time it's lifted and kept balanced on either side, the four crew members with the pneumatic guns have made way for the next four who remove the wheels, making way for the subsequent four who put the new wheels on; and finally the tool guys tighten the nuts, even while the car is being dropped to the ground-in fact, that video absolutely has to be watched frame by frame, which is really the only way to fully appreciate every little detail as it's happening. Once you think about how perfectly in sync it is, without a single mistake, it becomes quite breathtaking).

[@gregmark1688]

Holy cow, I have spent so much time rapidly tapping my spacebar to try to see things frame by frame. After 10 years, I thought I knew everything about YT, but thank you SO MUCH for sharing those hotkeys!! I wonder when then were introduced, and how I missed it. I'm seriously grateful.

[@coolcat23]

The "guy sitting next to him" is Mats Valk, a former world record holder (4.74s) and in the clip you see Feliks "stealing" his world record by a hundredth of a second (~0.2%).

[@romanlinnik7441]

Very thorough explanation, but you're wrong here. You can't figure out a full solution in your head during 15 seconds of inspection. Feliks here has planned his cross and 2, maybe 3 F2L pairs. He then pauselessly executes what he saw in inspection while looking ahead and tracking his last F2L pieces and then quickly recognizes LL. Solves like this one (

[@taggamer335]

@Roman Linnik Honestly, I don't mind when non cubers think we can plan the entire cube, makes us look more impressive lol!

[@romanlinnik7441]

@@taggamer335 i WISH i could be a pauseless lookahead chad, you are very much correct lol

[@8180634]

Excellent clear explanation!

[@chakra6666]

absolutely insane graphics and excellent presentation otherwise! the attention paid to sound design was also awesome to see :)

[@christianstonecipher1547]

In the double DES scenario I am pretty sure it should be 2^57 instead of 2^56 as in the worst case you go through 2^56 cases for computing the first half list and then go through up to 2^56 more cases when trying to find the match, thus the work is 2^56+2^56=2^57. And similarly 2sqrt(n) instead of sqrt(n) for the general case.

[@PolylogCS]

You are totally right! We performed the ancient theoretical-computer-science ritual of sweeping the constant factors under the rug :)

[@toriless]

Yeah, well double key encryption pretty much killed it.

[@irrelevant_noob]

@Christian Stonecipher well if you're going to dig into the operations like that, it should be 57*2^56 since each of the latter 2^56 cases will have to be checked against the existing set of middle-point states, and a binary search is log(size). 🤓

[@MrWedge21]

@@irrelevant_noobis this true? Wouldn’t that mean you need 57 times more computing power? Don’t you mean 2^57+57?

[@irrelevant_noob]

@@MrWedge21 it should be true, or i wouldn't have said it. And since you seem to have missed out on the shortcuts i used, here's the breakdown: * [A] 2^56 for generating the initial list of potential keys + resulting code-text; * [B] for each of the other 2^56 secondary keys... oh oops i was off by one here, forgot to factor in the "1" for generating the backwards step, but after you have that, you look it up against the list from step A; this look-up would take at most 56 = log(2^56) steps. So cost of B was 56*2^56, plus the cost of A of 2^56, that's how i got that earlier 57*2^56. Now, with the corrected info, it should be 58*2^56, so i was arguably close enough. Also, not sure why you say "times" but use a "+" sign in there. :-)

[@LunchThyme]

Would love to see a follow up video on the fastest method for finding the shortest solution for a cube (I remember I had an app on my ipod touch 10 years ago that could do it in a few seconds). I imagine it involves determining whether the current path being checked is improving the situation or not, and not exploring bad paths needlessly, the way chess engines do.

[@aphraxiaojun1145]

pretty sure chess engines dont, but yeah

[@AutPen38]

I'm not sure if they call it something different in chess or Rubik engines, but the machine-learning neural nets that made great strides in solving poker used something called "regret minimisation". Essentially, they used look-up tables that effectively said "pursuing that line in the past was mostly bad, so let's pursue a line that is less likely to be a waste of processing time". I presume that modern chess engines do a lot of pruning of the game tree. GPUs are cheap these days, but not cheap enough to look at trillions of branches of the game tree. There also isn't enough time to explore *every* possibility through brute force. Leela et al simulated a LOT of games though!

[@LunchThyme]

@@AutPen38 I watched a bit of the TCEC a couple years ago, and one thing I noticed was Leela was checking far fewer lines than Stockfish, like 400k vs 10M; she must've been far better at pruning bad lines. The tradeoff I guess is that Leela was only capable of checking 400k lines/S. She won that year though.

[@bboobbee1965]

kzbin.infoXeNFkzqGsMc?feature=share

[@Ma-pz5kl]

really good video / editing / content. WELL DONE

[@brandonmtb3767]

Very understandable explanation. Really clever trick using properties of exponents and large numbers

[@DeclanMBrennan]

Neat trick neatly explained. Loved the graphics and the Rubik cube configuration graph construction with actual animated cubes was a tour-de-force. One way around memory usage for the double DES attack could be to keep just a checksum of the output text rather than the text itself. Run the algorithm from one side to generate effectively a very large multii-map from checksum to key. (This may still be too big to be memory based but will use a lot less disk space). Run the algorithm from the other side and look up checksums. to get keys if any For each candidate match, recalculate the text and compare. Candidate matches should be rare if the checksum or signature algorithm is chosen well.

[@PolylogCS]

Thanks for bringing this up!

[@greatbriton8425]

This reminds me of the time when I was trying to program an AI to play bridge with a ZX Spectrum 48K. The speed was really slow and right off the bat I hit a problem: shuffling the cards, dealing them, and sorting the hands took ages... But at the start we have a sorted deck and at the finish sorted hands, so really the problem is just how to DEAL randomly. I tried dealing the cards in sorted order to random players, but the last player always got the K and A of Spades. Suddenly it hit me: I needed to shuffle the PLAYERS instead of the cards. So I put 1234 repeated into 52 slots, shuffled them, and then dealt out the sorted cards according to the player numbers in the 52 slots. I guess I was reminded because it's that same kind of mind leap to redefine the PROBLEM in a new way, rather than looking for a better SOLUTION to the old problem.

[@AutPen38]

That reminds of how - in the 8-bit days, the pseudo random number generator wasn't very random at all. If you switched on a Vic-20 (I think) and typed RND(1) it would always give you the same number, presumably because it just used a list of numbers, and it just reloaded that list every time you booted it up.

[@greatbriton8425]

@@AutPen38 :) No, because the (1) is the seed :) You have to give it a fresh seed for a new set of random numbers.

[@ANDSENS]

Always nice to meet a fellow connoisseur of the solarized light theme. We are a rare breed indeed 🙂

[@SheepStar8]

I love the edit at 10:48 it is really funny. Also I love all the sounds in these videos too. Really good editing! :) Consider me a new subscriber!

[@KanjiasDev]

Hi, known plaintext is a common problem for cipher encryption. Especially in ZIP Files containing multiple files you often find a "LICENSE" File, which of in best case you know the Name and Version... For example if a user has Notepad++ in path you know it's most likely GLP-3.0-or-later (as it's used since 2021) and if not GPL-2.0-or-later, so you just need to check that. Here comes double ZIP encryption into play, which is way more useful then Double-DES. Why? Because you can't run Meet in the middle anymore as you don't know the source code anymore. For this we have to understand how ZIP encryption works: It keeps the directorys and files (as well as their names) available unencrypted, which enables attackers to find things that might be known plain text. When you encrypt this ZIP File again you mitigate this issue - sure you still would have small amounts of known plaintext like the file header of .zip, but tbh this is way to small to be really helpful :D

[@andyelgrand0]

you are making the biggest assumption mistake known to man... you assume humans are perfect. users are leaky. so someone WILL see the plaintext whether you like it or not at some point

[@BrainwashingDetectiv]

Interesting! 7-zip allows for encrypting file names as well, I imagine that helps prevent the issue with known plaintext?

[@tatoute1]

assuming there is 10^20 configurations, it is equivalent to 2^67 , so you need in theory 67 bits to store a combination. With your algo "meet in the middle" you need to store 10^10 configurations, so 10 billions times 67 bits, aka 80GB of memory. But the "sphere" of configurations from the solved cube is always the same, so you can store it in a permanent memory in a so call rainbow table. But I think a major improvement may be to find "quasi instantaneously" a non optimal solution, and to transform it to become optimal. starting from each intermediate configuration we can build mini spheres and detect shortcuts. But I fail to find a way to prove it will be the shortest path at the end. Another way may be to try to find an calculable order equivalent to the number of movements to go back to the solution. Why not to train a neural network over the rainbow of 10 moves and let it predict the path?

[@Temari_Virus]

I think the mini spheres can reduce the "hot" memory (not including the rainbow table) needed to ~2 * 10^5 configurations. To ensure we find the shortest path, we first do meet in the middle normally, but only up to 5 steps away from each side. If no solution is found, we know that the distance is >10. Then we do the same thing, but start with a configuration that is distance 10 away from being solved instead of the solved cube. We do this for all the configurations, keeping track of the shortest path found so far. This is ~10^5 times more memory efficient but also ~10^5 times slower

[@martinsimons7710]

Amazing graphics and a simple explanation, underrated channel for sure...

[@xcoder1122]

Not only a great explanation for meet in the middle but also once again showing the classical trade off between CPU time and memory. A lot of problems can be solved with almost no memory at all but then you will need a lot of computation power or they can be solved with very little computation power as long as you have huge amounts of memory or storage space available. In reality you always try to find a compromise between memory and computation time as in reality both are limited resources and you need to make the best out of what you have available.

[@PvblivsAelivs]

In Triple DES, the inner "encryption" actually applies the decryption algorithm.

[@alexholker1309]

Interesting. So it encrypts, decrypts with the wrong key, then re-encrypts the corrupted "plaintext"?

[@PvblivsAelivs]

@@alexholker1309 That's about it, yes.

[@Melds]

I was just going to ask about this. I know this is how 3des works, but does that help reduce the meet in the middle between rounds? I've never understood why they swap the algorithms.

[@alexholker1309]

@@Melds Reading the Wikipedia page, one consequence of this decision is that 3DES is backwards-compatible with DES - just give it the same key for all three stages and it will correctly output a regular DES-encrypted cyphertext.

[@Melds]

@@alexholker1309 It looks like my response wasn't accepted. Anyhow, I found some Stack Exchange posts that confirmed what you've said. One answer also said there's a slightly higher overhead to EDE (encrypt-decrypt-encrypt) since the set-up for EEE could reuse information from the previous round, so it would be slightly more expensive to brute force.

[@mcb187]

Slight correction: that 43 quintillion number is the number of permutations based on putting 6 colors on 9 squares for each side of a cube. The number of physically possible permutations is actually much smaller, due to how the cube actually works. Also, there is a very widely known position that will stress test any program. It is called the “superflip”. All edges are flipped, but all corners are still in a solved state. If your program can solve the cube from that position in 20 moves, your program almost certainly works.

[@droganjake2802]

If you want to know the equation here: (12! * 2^12 * 8! * 3^8) / 12

[@motherlove8366]

43 quintillion already takes into account that you cannot move only 1 edge or only 1 corner

[@bannah6400]

This world is rapidly passing away and I hope that you repent and take time to change before all out disaster occurs! Belief in messiah alone is not enough to grant you salvation - Matthew 7:21-23, John 3:3, John 3:36 (ESV is the best translation for John 3:36) if you believed in Messiah you would be following His commands as best as you could. If you are not a follower of Messiah I would highly recommend becoming one. Call on the name of Jesus and pray for Him to intervene in your life - Revelation 3:20. Contemplate how the Roman Empire fulfilled the role of the beast from the sea in Revelation 13 over the course of 1260+ years. Revelation 17 confirms that the beast is in fact Rome. From this we can conclude that A) Jesus is the Son of God and can predict the future or make it happen, B) The world leaders/nations/governments etc have been conspiring together for the last 3000+ years going back to Babylon and before, C) History as we know it is fake. You don't really need to speculate once you start a relationship with God. Can't get a response from God? Fasting can help increase your perception and prayer can help initiate events. God will ignore you if your prayer does not align with His purpose (James 4:3) or if you are approaching Him when "unclean" (Isaiah 1:15, Isaiah 59:2, Micah 3:4). Stop eating food sacrificed to idols (McDonald's, Wendy's etc) stop glorifying yourself on social media or making other images of yourself (Second Commandment), stop gossiping about other people, stop watching obscene content etc. Have a blessed day!

[@justinsmith2363]

It would be eight squares per side, not nine, giving 6^48, a much bigger number. As the other replies point out, 43 quintillion IS the physically possible number.

[@So0fer]

Very informative and great video overall!

[@pedromonteiro1556]

I watched every second of this video. Very well explained.

[@SatisfyingWhirlpools]

A way to cut down on the graph a little: avoid doing the opposite of the move you just did, and also, if you just did right, don’t do right a second time after, since one of the options you already explored was R2

[@chaddaifouche536]

The use of a graph automatically takes care of all of these : when you do a breadth first search, you only visit nodes that haven't been visited in the past, which of course means you won't do the opposite of your last move (you already visited your parent) and won't do moves that get you to a past state of the cube. Of course this imply that you keep a set of visited nodes, which in this case may be prohibitive in terms of memory usage… Your tricks (and some more) may then be useful to implement a BFS without memory that avoid repeating too many visits, but then you would only get the minimum number of moves, not the exact sequence (because you need to keep track of the parent of each visited node to find this) so…

[@derherrdirektor9686]

Hallo Polylog. I have an proposal for an even better algorithm. If you know there is a strategy to solve the cube in a good way, but not ideal way, let's say by divide and conquer of the lanes, then you could use varying elements of this path for waypoints and explore their surroundings. A long as no step is orthogonal to the direct connection, this must result in an optimization.

[@SerenityReceiver]

I like the "dark side" concept and animation to put the viewer into a different setting and refresh attention. 👍🏽

[@SamundraDarion]

4:30 the sound of those cubes turning is AWESOME!

[@davemarm]

Hamburgers also use the meat in the middle technique.

[@simonharris4873]

One more optimisation that is glaringly obvious... After the first move, you only need to check 15 paths, not 18. If the first move is say, on the top face, then you don't need to check any of the top face moves on the second move. That would increase the efficiency by almost 17 per cent. EDIT: Just saw line 163 in you code which seems to do precisely that. :)

[@PolylogCS]

Yes, every little optimisation was needed here :)

[@JohnPreston888]

You could optimise your first sentence by omitting the superfluous word, "glaringly".

[@simonharris4873]

@@JohnPreston888 You could optimise your entire post by deleting it. 😁

[@JohnPreston888]

@@simonharris4873 That's really your best comeback? You don't seem to understand that "optimise" is not a synonym for "kill". You used imprecise, inefficient English in an attempt to make your point about efficiency...

[@simonharris4873]

@@JohnPreston888 You need more things to fill out your day.

[@hemantahembram7601]

An excellent video turned out, everything is well thought out, a very clear instruction turned out)))

[@micalobia1515]

LOVE the use of Solarized, incredible video! Noticed it when you said "into the dark side" at 10:47

[@PolylogCS]

Oh yes, somebody noticed. :D

[@chrispysaid]

Spoiler: this video will not make you better at solving a Rubik's cube

[@atlantic_love]

I'd like to know how all these young people learned to solve a Rubik's cube. It's obviously not trial-and-error. They were taught by someone, and taught some technique. What technique is it?

[@chrispysaid]

@@atlantic_love Young people have this little thing (you might have heard of it) called KZbin, where there are an abundance of explanations and tutorials on how to solve a Rubik's cube or do literally anything else. This video is a bad example of one of those aforementioned tutorials and is more of a showcase on computer algorithms, but if you take the time to watch a couple videos and spend a few hours practicing what you learned, you'll get it.

[@atlantic_love]

@@chrispysaid How did the kids learn to do this back when there wasn't internet for the masses?

[@yassinesafraoui]

First time that I encounter this trick, and I really like it 🤩, please share more tricks like this

[@pentachronic]

Very well presented ! Thanks.

[@sebbes333]

1:58 *_Here is a better solution:_* *Encode the direction towards the solved cube into the graph itself.* Then for ANY scrambled cube, you INSTANTLY KNOW the path to the solved cube. The problem is to find whichever 10^20 nodes the scrambled cube corresponds to, but since that never was a problem in any of the examples in this video, I'm also just going to ignore that.

[@poproporpo]

Mhm, but the encoding process requires iterating through every point in the graph in some sequential order, and that is a lot of overhead (as well as memory consumption), which is quadratic in relation to the complexity of the meet-in-the-middle algorithm. Granted, if you don't count overhead, then this would run in constant time.

[@Aquillyne]

The problem would be the time taken to generate that directed graph, and the memory required to store it.

[@ddichny]

Try generating that 10^20 node graph and see how fast you run out of storage space.

[@bannah6400]

This world is rapidly passing away and I hope that you repent and take time to change before all out disaster occurs! Belief in messiah alone is not enough to grant you salvation - Matthew 7:21-23, John 3:3, John 3:36 (ESV is the best translation for John 3:36) if you believed in Messiah you would be following His commands as best as you could. If you are not a follower of Messiah I would highly recommend becoming one. Call on the name of Jesus and pray for Him to intervene in your life - Revelation 3:20. Contemplate how the Roman Empire fulfilled the role of the beast from the sea in Revelation 13 over the course of 1260+ years. Revelation 17 confirms that the beast is in fact Rome. From this we can conclude that A) Jesus is the Son of God and can predict the future or make it happen, B) The world leaders/nations/governments etc have been conspiring together for the last 3000+ years going back to Babylon and before, C) History as we know it is fake. You don't really need to speculate once you start a relationship with God. Can't get a response from God? Fasting can help increase your perception and prayer can help initiate events. God will ignore you if your prayer does not align with His purpose (James 4:3) or if you are approaching Him when "unclean" (Isaiah 1:15, Isaiah 59:2, Micah 3:4). Stop eating food sacrificed to idols (McDonald's, Wendy's etc) stop glorifying yourself on social media or making other images of yourself (Second Commandment), stop gossiping about other people, stop watching obscene content etc. Have a blessed day!

[@irrelevant_noob]

@Sion but all directions within the graph are "towards" the solved cube, just how all roads lead to Rome...

[@ruemeese]

Great. There's no way you beat Feliks though. He spent a few seconds looking at the initial cube and your algorithm spent four hours on it.

[@petros_adamopoulos]

One could argue that Feliks spent years looking at cubes to get there. But I get your point.

[@ruemeese]

@@petros_adamopoulos You could! But wouldn't that be the equivalent of spending years developing the software.

[@ddichny]

They're solving different problems. Feliks wants to unscramble a cube quickly and doesn't care how many moves that takes. Polylog wants to determine with certainty the solution that takes the absolutely minimum number of moves. The latter is actually the more challenging problem.

[@bannah6400]

This world is rapidly passing away and I hope that you repent and take time to change before all out disaster occurs! Belief in messiah alone is not enough to grant you salvation - Matthew 7:21-23, John 3:3, John 3:36 (ESV is the best translation for John 3:36) if you believed in Messiah you would be following His commands as best as you could. If you are not a follower of Messiah I would highly recommend becoming one. Call on the name of Jesus and pray for Him to intervene in your life - Revelation 3:20. Contemplate how the Roman Empire fulfilled the role of the beast from the sea in Revelation 13 over the course of 1260+ years. Revelation 17 confirms that the beast is in fact Rome. From this we can conclude that A) Jesus is the Son of God and can predict the future or make it happen, B) The world leaders/nations/governments etc have been conspiring together for the last 3000+ years going back to Babylon and before, C) History as we know it is fake. You don't really need to speculate once you start a relationship with God. Can't get a response from God? Fasting can help increase your perception and prayer can help initiate events. God will ignore you if your prayer does not align with His purpose (James 4:3) or if you are approaching Him when "unclean" (Isaiah 1:15, Isaiah 59:2, Micah 3:4). Stop eating food sacrificed to idols (McDonald's, Wendy's etc) stop glorifying yourself on social media or making other images of yourself (Second Commandment), stop gossiping about other people, stop watching obscene content etc. Have a blessed day!

[@romanlinnik7441]

@@ddichny "unscramble" is certainly a word, I like it.

[@prathameshsundaram7509]

AMAZING CAN'T WAIT FOR YOU TO EXPLODE

[@hackercop]

This video was excellent. Liked and subscribed!

[@Funzelwicht]

So beautiful, ironic und understandable! GREAT WORK!

[@brianarsuaga5008]

I once used this for a pathfinding algorithm across a stable known graph. I didn't know which nodes might be requested by the user for a path, but I did know both endpoints, so I'd explore from both with a* until I found a midway. I'd then add both paths of that as a virtual link with the appropriate weights, so that later pathfinds could recycle that. I didn't do any random walks to train it or anything, letting user input shape the "trodden trail" caching, but it did seem to help, though I seem to recall that it wasn't always most efficient, and might even have been unsound as a strategy!

[@bboobbee1965]

kzbin.infoXeNFkzqGsMc?feature=share

[@jimday666]

Amazing animations! Keep it up!

[@isaacgreen9495]

Your visualizations are incredible

[@jantalipun8529]

Oh my God this video looks great! And explained just as good :)

[@jeepkd]

Wow the video production is crazy. Perfect

[@uprobo4670]

Next level quality ... n terms of content and art direction ..

[@gregrice1354]

Thanks for beautifully explained, mathematics problem or challenge that kids can enjoy and learn a great deal from! Your animation is beautiful. Did you use a 3D modeling program, or was it rendered by manual generation of the cube and layer rotation images. Fantastically smooth, and edited for comprehension, not to dazzle and avoid close, critical examination of the cube movements. Personally, I think this video jumps to to the top 100 of all web videos on explaining complex math concepts. Maybe higher on the chart, since, as you indicate, the proof took over 30 years of avid use by millions of people before the solutions were found to be 20 moves!

[@jamesrichardson8151]

Fantastic video - really interesting, clear and informative. I tried creating a Python script to solve the Rubik's cube using the brute force method you described initially, but failed due to the size issues you describe. With a bit of recoding it did work perfectly for the 2x2x2 cube though, with my answers for each distance from the starting cube matching those in the online encyclopaedia of integer sequences. I'm now pondering how I'll get my hands on enough storage to implement the "meet in the middle" method for the 3x3x3 cube 🤣

[@HiManLOL]

Man this is really superb content

[@felixmerz6229]

I'm 2:21 in and I'm already blown away by the quality of this video. So good. Edit: Done. Amazing.

[@zerobeat2020]

I was never this fast in the 80s, but I certainly managed to solve the cube within 20 seconds. Great fun.

[@bboobbee1965]

kzbin.infoXeNFkzqGsMc?feature=share

[@emessar]

This is so cool. I had the idea for a meet in the middle algorythm when I was taking discrete mathematics several years ago. It's cool to finally find out that's a legit thing.

[@fromdil6470]

Great job on the explanation! I appreciate the use of visually stunning graphics to enhance my understanding. I was wondering if you could kindly share some insights on how you created the animation, particularly the different situations captured in the cube at the [14:16] mark? Thank you.

[@user-jj1bb3kk9y]

I just adore your videos

[@rgarlinyc]

Very clever! The meet-in-the-middle is so obvious - AFTER - you exposited it, that is.`😄

[@mamborambo]

This video is how all algorithm teaching should be done