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.
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 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)
@@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.)
@@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 ;)
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 TH-cam chess strategy content creator.
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).
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.
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. :/
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.
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.
@@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.
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)
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
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.
@@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.
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.)
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
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.
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
Criminally underrated TH-cam 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 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.
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.
My guy, get yourself more of a social media presence or something- I was expecting you to be one of those math and logic TH-camrs 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 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. TH-cam 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 TH-cam. TH-cam 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!
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.
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.
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...
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.
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!
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.
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?
@@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. TH-cam being TH-cam just recommended this video to me and I was wondering if I could make my old code faster
@@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
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
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 :))
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.
@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 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. :-)
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.
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.
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).
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.
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%).
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 (
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
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
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.
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.
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!
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.)
Another consideration for why Double-DES was skipped is that Triple-DES is not plaintext encrypted three times with three keys. It is plaintext encrypted with one key, decrypted with a second, and encrypted with a third - to give a so-called "E-D-E" pattern. This means that if the same key was used in all three steps, it would encrypt, decrypt and encrypt again with a single 56-bit key, resulting in the same output as if it was just DES. This allowed Triple-DES to handle both Triple-DES encryption with three 56-bit keys as one long 168-bit key, and regular DES with a a 56-bit key repeated three times to make a 168-bit key, simplifying implementation.
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 !
I once read a paper on a technique called "dissection". You split the cube up and only look at how moves transform one piece of the cube without caring about the rest, i.e. represent pieces of the cube in ways that make each piece independent of the other. Then you can brute force all states for one piece of the cube, and for each state do a meet-in-the-middle between it and the initial state and again between it and the end-state. This gives you a set of candidate paths from the initial state, through the chosen state, and all the way to the end state. You then union together the candidates for all the brute forces middle states and finally check which among those also happened to solve the rest of the cube whose state you up until now ignored. Basically, it's meet in there middle with half the exponent (quarter of overall bfs), with extra cost of enumerating all possible states for one piece of the problem.
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
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…
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.
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!
@@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.
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.
@@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.
@@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.
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?
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
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.
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. :)
@@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...
I want to thank you for staying on the light side! It was a pleasure to watch a video! Light backgrounds are calm and even uplifting! I’m so tired of this fashion of pitch-black backgrounds and scorching white. Thank you very much!
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.
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!
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.
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.
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.
@@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.
On a computer it can help to embed the distant states in the near nodes in the graph. If you can afford to store this, this can go in a sparse matrix. Also, you can virtualize the graph, rather than actually constructing it, by defining a canonical order of state discovery, and computing the edges while searching.
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.
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.
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!
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?
@@atlantic_love Young people have this little thing (you might have heard of it) called TH-cam, 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.
Many modern solvers use algorithms that move the middle slices (Roux solvers for example). Adding the slice moves (S, E, M) would increase your 18 configurations to 27 configurations. This doesn't change anything other than increasing the number of nodes in your graph.
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.
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!
We used to solve it by looking for specific patterns and each pattern told you to make a specific series of moves. It wasn't hard to learn it and it was fast.
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 :-)
I used to struggle solving my Rubik's cube but then after I washed this video I just started writing complex algorithms in my own head and now I can solve it in seconds thanks video on TH-cam
This is an excellent video and channel. TH-cam only suggested this because I am a cuber looking for cubing videos. Keep up the good work, I am definitely subscribing.
I am still looking for the old (1980s era) formulas to solve the cube. Those are the one I still remember today except the few ones to finish the top layer after the cross is made. I was able to solve the cube in around 25s back then as a 12 yo with a hard to turn cheap plastic cube immitation and without being able to see the cube before hand. With the cubes we have today, I think I would have been able to do it in 20s. It is impressive to see how things changed with the help of computers.
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.
I remember using "meet in the middle" trick in route finding algorithm for personal navigation device I was developing back in 2007. But it wasn't nearly enough to sped things up enough, many other tricks were needed.
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.
In theory, I love FMC, but in practice, i am so bad at it it's not even funny.
Ah yes, WCA FMC TAS
Small nit-pick: it's just called "Fewest Moves" 😉
@@FakeDane But it's also called FMC
@@FreddieStarWars if you find a WCA document where it's called FMC let me know so I can get it corrected!
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
The problem is that there is a large number of check mate positions,and probably most of then are unreachable.
@@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)
@@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.)
@@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 ;)
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 TH-cam chess strategy content creator.
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).
I'm now trying to invisage the most computationally intensive way to 'reasonably' implement this. Nested loops anyone?
Using recursion would save memory, you are using memory dynamically not statically.
@@toriless today i learned stack memory is free
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.
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!
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. :/
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.
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.
@@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.
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)
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
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.
@@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.
@@PolylogCS my motto. "If it works, don't touch it"
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.)
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
The visualizations and sound effects are done so well. Nice work!
Always nice to meet a fellow connoisseur of the solarized light theme. We are a rare breed indeed 🙂
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.
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
Nice examples! How do you view hash collision as an instance of MITM?
Meet in the middle is a very common CTF target. It's always fun to implement.
Criminally underrated TH-cam 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 :(
Absolutely correct
wow a week ago he had only 300 subs now it it almost 2k
the animations an explanations are of incredible quality. better than some channels with millions of subscribers
@@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.
Yes! This is insane!
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.
th-cam.com/users/shortsXeNFkzqGsMc?feature=share
My guy, get yourself more of a social media presence or something- I was expecting you to be one of those math and logic TH-camrs 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.
Thanks, we hope the some competition will help with that :) Though we are more computer scientists than mathematicians.
@@PolylogCS sorry you have to become mathematicians now
@@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.
TH-cam 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 TH-cam. TH-cam 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!
@polylog I agree 100% with them. Wow!
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.
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.
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...
Not only is it valid, it's the starting position of Feliks's cube and you can it being solved at 1:26.
Yeah, matrix math in interesting concept and how they really calculate the best navigational course.
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.
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!
Me too!
I love the sound design on this video too. It’s a very under appreciated touch that adds to the polish of the video.
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.
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?
Thanks, good points. :)
@@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. TH-cam being TH-cam just recommended this video to me and I was wondering if I could make my old code faster
@@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
I like the "dark side" concept and animation to put the viewer into a different setting and refresh attention. 👍🏽
"The number of possible Rubik's cube configurations is 43."
Oh, that's not as much as I tho--
"Quintillion."
😂
Yeah it is alot
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!
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
The visuals on this channel are just amazing. Helps so much the explain the concept.
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 :))
This video has insane quality for the channel's size. Great job explaining the meet in the middle approach.
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.
You are totally right! We performed the ancient theoretical-computer-science ritual of sweeping the constant factors under the rug :)
Yeah, well double key encryption pretty much killed it.
@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). 🤓
@@irrelevant_noobis this true? Wouldn’t that mean you need 57 times more computing power? Don’t you mean 2^57+57?
@@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. :-)
Came here by accident, stayed for the beautiful and insightful animation and overall design and even learned something. Great content!
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.
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.
@@AutPen38 :) No, because the (1) is the seed :) You have to give it a fresh seed for a new set of random numbers.
Instant subscribe. The visualizations and explanations have a rare flavor that deliver flawless pedagogy.
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).
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.
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%).
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 (
@Roman Linnik Honestly, I don't mind when non cubers think we can plan the entire cube, makes us look more impressive lol!
@@taggamer335 i WISH i could be a pauseless lookahead chad, you are very much correct lol
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
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
Interesting! 7-zip allows for encrypting file names as well, I imagine that helps prevent the issue with known plaintext?
This is so cool, thanks for making it easy to understand. This is an epic code challenge!
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.
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.
Thanks for bringing this up!
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!
th-cam.com/users/shortsXeNFkzqGsMc?feature=share
This is fascinating! Your explanations and visualisations are wonderful. Thank you.
"... that the number of Rubik's cube configurations is about 43 ... quintillions" you got me so good I had to pause to sub lmao. Amazing video.
Absolutely stunning video! You did a great job explaining it!
I can't believe it took me this long, but as soon as 10:48 happened, I realized "wait, that's Solarized!" Love it!
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.)
Thanks! It is also good to know that the algorithms that are actually used are actually a bit more complicated but also faster
Another consideration for why Double-DES was skipped is that Triple-DES is not plaintext encrypted three times with three keys. It is plaintext encrypted with one key, decrypted with a second, and encrypted with a third - to give a so-called "E-D-E" pattern. This means that if the same key was used in all three steps, it would encrypt, decrypt and encrypt again with a single 56-bit key, resulting in the same output as if it was just DES. This allowed Triple-DES to handle both Triple-DES encryption with three 56-bit keys as one long 168-bit key, and regular DES with a a 56-bit key repeated three times to make a 168-bit key, simplifying implementation.
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 !
I once read a paper on a technique called "dissection". You split the cube up and only look at how moves transform one piece of the cube without caring about the rest, i.e. represent pieces of the cube in ways that make each piece independent of the other. Then you can brute force all states for one piece of the cube, and for each state do a meet-in-the-middle between it and the initial state and again between it and the end-state. This gives you a set of candidate paths from the initial state, through the chosen state, and all the way to the end state. You then union together the candidates for all the brute forces middle states and finally check which among those also happened to solve the rest of the cube whose state you up until now ignored.
Basically, it's meet in there middle with half the exponent (quarter of overall bfs), with extra cost of enumerating all possible states for one piece of the problem.
Your video is so well made. How did you make the visuals for it? The animations I mean
Amazing quality video. Such an underrated channel , those animations were on point!
Hamburgers also use the meat in the middle technique.
Insanely great video. Walked up to the idea of MiM in a way where it just makes sense as the solution.
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
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…
I'm 2:21 in and I'm already blown away by the quality of this video. So good. Edit: Done. Amazing.
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.
pretty sure chess engines dont, but yeah
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!
@@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.
th-cam.com/users/shortsXeNFkzqGsMc?feature=share
This video is how all algorithm teaching should be done
In Triple DES, the inner "encryption" actually applies the decryption algorithm.
Interesting. So it encrypts, decrypts with the wrong key, then re-encrypts the corrupted "plaintext"?
@@alexholker1309
That's about it, yes.
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.
@@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.
@@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.
Beautifully animated and explained, I can't wait to see where this channel goes! You're very skilled!
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?
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
4:30 the sound of those cubes turning is AWESOME!
Thank you for the nice video!
Amazing graphics and a simple explanation, underrated channel for sure...
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.
Wow this was fascinating. I’m going to start watching more of your videos. You animate these so amazingly. Great job!
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. :)
Yes, every little optimisation was needed here :)
You could optimise your first sentence by omitting the superfluous word, "glaringly".
@@JohnPreston888 You could optimise your entire post by deleting it. 😁
@@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...
@@JohnPreston888 You need more things to fill out your day.
I was never this fast in the 80s, but I certainly managed to solve the cube within 20 seconds. Great fun.
th-cam.com/users/shortsXeNFkzqGsMc?feature=share
Excellent video. Really enjoyed it!
I want to thank you for staying on the light side! It was a pleasure to watch a video! Light backgrounds are calm and even uplifting! I’m so tired of this fashion of pitch-black backgrounds and scorching white. Thank you very much!
My eyes prefer a black background; pure white almost hurts. That is why it is good for us to have a choice. Not everyone is the same.
@@david203 You know, even better would be to have a brightness slider, like in Moho. Too bad that’s not an option for videos, at least for now.
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.
If you want to know the equation here:
(12! * 2^12 * 8! * 3^8) / 12
43 quintillion already takes into account that you cannot move only 1 edge or only 1 corner
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!
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.
What is this production/cgi quality. It’s insane!
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.
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.
@@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.
On a computer it can help to embed the distant states in the near nodes in the graph. If you can afford to store this, this can go in a sparse matrix.
Also, you can virtualize the graph, rather than actually constructing it, by defining a canonical order of state discovery, and computing the edges while searching.
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.
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.
The problem would be the time taken to generate that directed graph, and the memory required to store it.
Try generating that 10^20 node graph and see how fast you run out of storage space.
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!
@Sion but all directions within the graph are "towards" the solved cube, just how all roads lead to Rome...
Although I still don't know how to solve Rubik's cube myself, this was very interesting and educational. I think I'll watch some more videos here.
So happy you shared your ordinary thought process.
Spoiler: this video will not make you better at solving a Rubik's cube
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?
@@atlantic_love Young people have this little thing (you might have heard of it) called TH-cam, 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.
@@chrispysaid How did the kids learn to do this back when there wasn't internet for the masses?
They bought a book
Very interesting. Amazingly built up work. This piece of art is collectable. Thank you so much.
Many modern solvers use algorithms that move the middle slices (Roux solvers for example). Adding the slice moves (S, E, M) would increase your 18 configurations to 27 configurations. This doesn't change anything other than increasing the number of nodes in your graph.
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.
One could argue that Feliks spent years looking at cubes to get there.
But I get your point.
@@petros_adamopoulos You could! But wouldn't that be the equivalent of spending years developing the software.
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.
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!
@@ddichny "unscramble" is certainly a word, I like it.
I Don’t Have An Application For This Algorithm. Good Work. Thanks For Sharing
We used to solve it by looking for specific patterns and each pattern told you to make a specific series of moves. It wasn't hard to learn it and it was fast.
Wow the video production is crazy. Perfect
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 :-)
LOVE the use of Solarized, incredible video! Noticed it when you said "into the dark side" at 10:47
Oh yes, somebody noticed. :D
holy shit the animations and sound design in your videos are absolutely incredible!!
I used to struggle solving my Rubik's cube but then after I washed this video I just started writing complex algorithms in my own head and now I can solve it in seconds thanks video on TH-cam
That is quite an accomplishment.
I watched every second of this video. Very well explained.
Very clever! The meet-in-the-middle is so obvious - AFTER - you exposited it, that is.`😄
This is an excellent video and channel. TH-cam only suggested this because I am a cuber looking for cubing videos. Keep up the good work, I am definitely subscribing.
Incredible, loved the visuals and the content. Keep up the great work!
Beautiful graphics and explanation. Love it!
This really is outstanding STEM communication, well done!
First video I've watched, and already Subscribed
Very understandable explanation. Really clever trick using properties of exponents and large numbers
Greatly explained and beautifully animated ! GG for the work !
Next level quality ... n terms of content and art direction ..
I am still looking for the old (1980s era) formulas to solve the cube. Those are the one I still remember today except the few ones to finish the top layer after the cross is made. I was able to solve the cube in around 25s back then as a 12 yo with a hard to turn cheap plastic cube immitation and without being able to see the cube before hand. With the cubes we have today, I think I would have been able to do it in 20s. It is impressive to see how things changed with the help of computers.
First time that I encounter this trick, and I really like it 🤩, please share more tricks like this
Your visualizations are incredible
Nice video, content is extremely interesting. May I ask which tool/software you used to create the animated graphics?
Now I'm interested to know how it can be solved with the least compute and / or memory!
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.
really good video / editing / content. WELL DONE
I remember using "meet in the middle" trick in route finding algorithm for personal navigation device I was developing back in 2007. But it wasn't nearly enough to sped things up enough, many other tricks were needed.
This was a very well done explanation . However, you did not mention the 'trap door' technique.
Loved the surprise 3Blue1Brown. Great video