The trick that solves Rubik’s Cubes and breaks ciphers

2024 ж. 27 Нау.
2 645 355 Рет қаралды

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

Пікірлер
  • 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.

    @Thesnakerox@Thesnakerox Жыл бұрын
    • In theory, I love FMC, but in practice, i am so bad at it it's not even funny.

      @Quazex@Quazex Жыл бұрын
    • Ah yes, WCA FMC TAS

      @teamcyeborg@teamcyeborg Жыл бұрын
    • Small nit-pick: it's just called "Fewest Moves" 😉

      @FakeDane@FakeDane Жыл бұрын
    • @@FakeDane But it's also called FMC

      @FreddieStarWars@FreddieStarWars Жыл бұрын
    • @@FreddieStarWars if you find a WCA document where it's called FMC let me know so I can get it corrected!

      @FakeDane@FakeDane Жыл бұрын
  • 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

    @marc-andreservant201@marc-andreservant201 Жыл бұрын
    • The problem is that there is a large number of check mate positions,and probably most of then are unreachable.

      @tatoute1@tatoute1 Жыл бұрын
    • @@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)

      @animowany111@animowany111 Жыл бұрын
    • @@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.)

      @attilatorok5767@attilatorok5767 Жыл бұрын
    • @@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 ;)

      @PolylogCS@PolylogCS Жыл бұрын
    • 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 KZhead chess strategy content creator.

      @DarkVoidIII@DarkVoidIII Жыл бұрын
  • 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.

    @deidara_8598@deidara_8598 Жыл бұрын
    • 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!

      @PolylogCS@PolylogCS Жыл бұрын
    • 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. :/

      @HunterHerbst@HunterHerbst Жыл бұрын
    • 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.

      @peterkoch3777@peterkoch3777 Жыл бұрын
    • 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@Reth_Hard Жыл бұрын
    • @@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.

      @stephenJpollei@stephenJpollei Жыл бұрын
  • 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).

    @MechMK1@MechMK1 Жыл бұрын
    • I'm now trying to invisage the most computationally intensive way to 'reasonably' implement this. Nested loops anyone?

      @roxannemoore9694@roxannemoore9694 Жыл бұрын
    • Using recursion would save memory, you are using memory dynamically not statically.

      @toriless@toriless Жыл бұрын
    • @@toriless today i learned stack memory is free

      @Ricardo-C@Ricardo-C9 ай бұрын
  • 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)

    @codenamelambda@codenamelambda2 жыл бұрын
    • 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

      @PolylogCS@PolylogCS2 жыл бұрын
    • 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@TechSY730 Жыл бұрын
    • @@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.

      @Joe_Payne@Joe_Payne Жыл бұрын
    • @@PolylogCS my motto. "If it works, don't touch it"

      @mz00956@mz00956 Жыл бұрын
    • 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.)

      @attilatorok5767@attilatorok5767 Жыл бұрын
  • 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

    @midasredblade236@midasredblade236 Жыл бұрын
  • The visualizations and sound effects are done so well. Nice work!

    @alien5589@alien5589 Жыл бұрын
  • Criminally underrated KZhead 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 :(

    @InOtherNews1@InOtherNews1 Жыл бұрын
    • Absolutely correct

      @ganiti_314@ganiti_314 Жыл бұрын
    • wow a week ago he had only 300 subs now it it almost 2k

      @maximhoeve2087@maximhoeve2087 Жыл бұрын
    • the animations an explanations are of incredible quality. better than some channels with millions of subscribers

      @milkjug7800@milkjug7800 Жыл бұрын
    • @@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.

      @toasteduranium@toasteduranium Жыл бұрын
    • Yes! This is insane!

      @louisdalibard818@louisdalibard818 Жыл бұрын
  • 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!

    @xXx-un3ie@xXx-un3ie Жыл бұрын
    • Me too!

      @ismailalim8308@ismailalim8308 Жыл бұрын
  • This is fascinating! Your explanations and visualisations are wonderful. Thank you.

    @JackFoz454@JackFoz454 Жыл бұрын
  • Instant subscribe. The visualizations and explanations have a rare flavor that deliver flawless pedagogy.

    @bentpen2805@bentpen2805 Жыл бұрын
  • I love the sound design on this video too. It’s a very under appreciated touch that adds to the polish of the video.

    @urbandefinition@urbandefinition Жыл бұрын
  • 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.

    @rubixtheslime@rubixtheslime Жыл бұрын
    • 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...

      @PolylogCS@PolylogCS Жыл бұрын
    • Not only is it valid, it's the starting position of Feliks's cube and you can it being solved at 1:26.

      @Gameboygenius@Gameboygenius Жыл бұрын
    • Yeah, matrix math in interesting concept and how they really calculate the best navigational course.

      @toriless@toriless Жыл бұрын
  • 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 :))

    @LiamTolentino@LiamTolentino Жыл бұрын
  • The visuals on this channel are just amazing. Helps so much the explain the concept.

    @153ridzzzz@153ridzzzz Жыл бұрын
  • This video has insane quality for the channel's size. Great job explaining the meet in the middle approach.

    @bujin5455@bujin5455 Жыл бұрын
  • Meet in the middle is a very common CTF target. It's always fun to implement.

    @somebodystealsmyname@somebodystealsmyname Жыл бұрын
  • Absolutely stunning video! You did a great job explaining it!

    @GeorgAubele@GeorgAubele Жыл бұрын
  • Wow this was fascinating. I’m going to start watching more of your videos. You animate these so amazingly. Great job!

    @dixztube@dixztube Жыл бұрын
  • Amazing quality video. Such an underrated channel , those animations were on point!

    @picklypt@picklypt Жыл бұрын
  • 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.

    @spinospinellibass@spinospinellibass9 ай бұрын
  • This is so cool, thanks for making it easy to understand. This is an epic code challenge!

    @russelljazzbeck@russelljazzbeck Жыл бұрын
  • Beautifully animated and explained, I can't wait to see where this channel goes! You're very skilled!

    @Infinityand1@Infinityand1 Жыл бұрын
  • Incredible, loved the visuals and the content. Keep up the great work!

    @CyrusK@CyrusK Жыл бұрын
  • My guy, get yourself more of a social media presence or something- I was expecting you to be one of those math and logic KZheadrs 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.

    @Groudon466@Groudon466 Жыл бұрын
    • Thanks, we hope the some competition will help with that :) Though we are more computer scientists than mathematicians.

      @PolylogCS@PolylogCS Жыл бұрын
    • @@PolylogCS sorry you have to become mathematicians now

      @xXx-un3ie@xXx-un3ie Жыл бұрын
    • @@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. KZhead 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 KZhead. KZhead 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!

      @jamespond3668@jamespond3668 Жыл бұрын
    • @polylog I agree 100% with them. Wow!

      @henrivanderriet3895@henrivanderriet3895 Жыл бұрын
    • 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.

      @elissitdesign@elissitdesign Жыл бұрын
  • 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.

    @wChris_@wChris_ Жыл бұрын
    • kzhead.infoXeNFkzqGsMc?feature=share

      @bboobbee1965@bboobbee19659 ай бұрын
  • 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 :-)

    @norasalocin@norasalocin Жыл бұрын
  • 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!

    @KeyError@KeyError Жыл бұрын
  • 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

    @suurion1@suurion1 Жыл бұрын
    • Nice examples! How do you view hash collision as an instance of MITM?

      @PolylogCS@PolylogCS Жыл бұрын
  • 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.

    @lior9156@lior9156 Жыл бұрын
    • 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@gloverelaxis Жыл бұрын
    • Thanks, good points. :)

      @PolylogCS@PolylogCS Жыл бұрын
    • @@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. KZhead being KZhead just recommended this video to me and I was wondering if I could make my old code faster

      @gerardoberlangaiii@gerardoberlangaiii11 ай бұрын
    • ⁠@@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

      @clarkeelke2805@clarkeelke28059 ай бұрын
  • Greatly explained and beautifully animated ! GG for the work !

    @Oxey405@Oxey405 Жыл бұрын
  • This really is outstanding STEM communication, well done! First video I've watched, and already Subscribed

    @scottwilliams895@scottwilliams895 Жыл бұрын
  • 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.)

    @cubest817@cubest817 Жыл бұрын
    • Thanks! It is also good to know that the algorithms that are actually used are actually a bit more complicated but also faster

      @PolylogCS@PolylogCS Жыл бұрын
  • 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.

    @jpdemer5@jpdemer5 Жыл бұрын
  • Really appreciate the effort you have gone to in explaining this and the attention to detail. I learnt a great deal. Thank you!

    @JNighty@JNighty Жыл бұрын
    • Did it teach you how to solve a cube in 20 moves or less? I completely missed that part.

      @ollieox9181@ollieox9181 Жыл бұрын
  • Insanely great video. Walked up to the idea of MiM in a way where it just makes sense as the solution.

    @aiden_3c@aiden_3c Жыл бұрын
  • "The number of possible Rubik's cube configurations is 43." Oh, that's not as much as I tho-- "Quintillion."

    @AndiFels@AndiFels Жыл бұрын
  • 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 !

    @freedom_aint_free@freedom_aint_free Жыл бұрын
  • I like the "dark side" concept and animation to put the viewer into a different setting and refresh attention. 👍🏽

    @SerenityReceiver@SerenityReceiver8 ай бұрын
  • Came here by accident, stayed for the beautiful and insightful animation and overall design and even learned something. Great content!

    @peitz.design@peitz.design Жыл бұрын
  • 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.

    @DeclanMBrennan@DeclanMBrennan Жыл бұрын
    • Thanks for bringing this up!

      @PolylogCS@PolylogCS Жыл бұрын
  • 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.

    @greatbriton8425@greatbriton8425 Жыл бұрын
    • 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@AutPen38 Жыл бұрын
    • @@AutPen38 :) No, because the (1) is the seed :) You have to give it a fresh seed for a new set of random numbers.

      @greatbriton8425@greatbriton8425 Жыл бұрын
  • I love this channel!!! Thank you! So happy to find it and very grateful for your work! 🙏

    @ejejej9200@ejejej9200 Жыл бұрын
  • 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.

    @xcoder1122@xcoder1122 Жыл бұрын
  • 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

    @m4rt_@m4rt_ Жыл бұрын
  • 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.

    @christianstonecipher1547@christianstonecipher1547 Жыл бұрын
    • You are totally right! We performed the ancient theoretical-computer-science ritual of sweeping the constant factors under the rug :)

      @PolylogCS@PolylogCS Жыл бұрын
    • Yeah, well double key encryption pretty much killed it.

      @toriless@toriless Жыл бұрын
    • @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_noob@irrelevant_noob9 ай бұрын
    • @@irrelevant_noobis this true? Wouldn’t that mean you need 57 times more computing power? Don’t you mean 2^57+57?

      @MrWedge21@MrWedge219 ай бұрын
    • @@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. :-)

      @irrelevant_noob@irrelevant_noob9 ай бұрын
  • holy shit the animations and sound design in your videos are absolutely incredible!!

    @baksoboy@baksoboy Жыл бұрын
  • 4:30 the sound of those cubes turning is AWESOME!

    @SamundraDarion@SamundraDarion Жыл бұрын
  • 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

    @KanjiasDev@KanjiasDev Жыл бұрын
    • 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

      @andyelgrand0@andyelgrand0 Жыл бұрын
    • Interesting! 7-zip allows for encrypting file names as well, I imagine that helps prevent the issue with known plaintext?

      @BrainwashingDetectiv@BrainwashingDetectiv Жыл бұрын
  • Your video is so well made. How did you make the visuals for it? The animations I mean

    @sabari50312@sabari5031210 ай бұрын
  • Always nice to meet a fellow connoisseur of the solarized light theme. We are a rare breed indeed 🙂

    @ANDSENS@ANDSENS9 ай бұрын
  • Amazing graphics and a simple explanation, underrated channel for sure...

    @martinsimons7710@martinsimons7710 Жыл бұрын
  • Thank you for the nice video!

    @LukasZav@LukasZav2 жыл бұрын
  • 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.

    @afriedrich1452@afriedrich1452 Жыл бұрын
    • 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@david2039 ай бұрын
    • @@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.

      @afriedrich1452@afriedrich14529 ай бұрын
  • 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!

    @brianarsuaga5008@brianarsuaga500811 ай бұрын
    • kzhead.infoXeNFkzqGsMc?feature=share

      @bboobbee1965@bboobbee19659 ай бұрын
  • Beautiful graphics and explanation. Love it!

    @xoctor@xoctor Жыл бұрын
  • 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.

    @LunchThyme@LunchThyme Жыл бұрын
    • pretty sure chess engines dont, but yeah

      @aphraxiaojun1145@aphraxiaojun1145 Жыл бұрын
    • 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@AutPen38 Жыл бұрын
    • @@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.

      @LunchThyme@LunchThyme Жыл бұрын
    • kzhead.infoXeNFkzqGsMc?feature=share

      @bboobbee1965@bboobbee19659 ай бұрын
  • Excellent video. Really enjoyed it!

    @LeeDeVilleMath@LeeDeVilleMath2 жыл бұрын
  • LOVE the use of Solarized, incredible video! Noticed it when you said "into the dark side" at 10:47

    @micalobia1515@micalobia1515 Жыл бұрын
    • Oh yes, somebody noticed. :D

      @PolylogCS@PolylogCS Жыл бұрын
  • This is an excellent video and channel. KZhead only suggested this because I am a cuber looking for cubing videos. Keep up the good work, I am definitely subscribing.

    @hsinhinlim8762@hsinhinlim8762 Жыл бұрын
  • 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?

    @tatoute1@tatoute1 Жыл бұрын
    • 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

      @Temari_Virus@Temari_Virus Жыл бұрын
  • In Triple DES, the inner "encryption" actually applies the decryption algorithm.

    @PvblivsAelivs@PvblivsAelivs Жыл бұрын
    • Interesting. So it encrypts, decrypts with the wrong key, then re-encrypts the corrupted "plaintext"?

      @alexholker1309@alexholker1309 Жыл бұрын
    • @@alexholker1309 That's about it, yes.

      @PvblivsAelivs@PvblivsAelivs Жыл бұрын
    • 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@Melds Жыл бұрын
    • @@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@alexholker1309 Жыл бұрын
    • @@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.

      @Melds@Melds Жыл бұрын
  • I love the edit at 10:48 it is really funny. Also I love all the sounds in these videos too. Really good editing! :) Consider me a new subscriber!

    @SheepStar8@SheepStar8 Жыл бұрын
  • absolutely insane graphics and excellent presentation otherwise! the attention paid to sound design was also awesome to see :)

    @chakra6666@chakra6666 Жыл бұрын
  • 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).

    @user-kc2gi7eq1y@user-kc2gi7eq1y Жыл бұрын
    • 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.

      @gregmark1688@gregmark1688 Жыл бұрын
    • 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%).

      @coolcat23@coolcat2311 ай бұрын
    • 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 (

      @romanlinnik7441@romanlinnik744111 ай бұрын
    • @Roman Linnik Honestly, I don't mind when non cubers think we can plan the entire cube, makes us look more impressive lol!

      @taggamer335@taggamer33511 ай бұрын
    • @@taggamer335 i WISH i could be a pauseless lookahead chad, you are very much correct lol

      @romanlinnik7441@romanlinnik744111 ай бұрын
  • 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.

    @derherrdirektor9686@derherrdirektor9686 Жыл бұрын
  • Very understandable explanation. Really clever trick using properties of exponents and large numbers

    @brandonmtb3767@brandonmtb3767 Жыл бұрын
  • really good video / editing / content. WELL DONE

    @Ma-pz5kl@Ma-pz5kl10 ай бұрын
  • 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

    @SatisfyingWhirlpools@SatisfyingWhirlpools9 ай бұрын
    • 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…

      @chaddaifouche536@chaddaifouche5369 ай бұрын
  • 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@simonharris4873 Жыл бұрын
    • Yes, every little optimisation was needed here :)

      @PolylogCS@PolylogCS Жыл бұрын
    • You could optimise your first sentence by omitting the superfluous word, "glaringly".

      @JohnPreston888@JohnPreston88811 ай бұрын
    • @@JohnPreston888 You could optimise your entire post by deleting it. 😁

      @simonharris4873@simonharris487311 ай бұрын
    • @@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@JohnPreston88810 ай бұрын
    • @@JohnPreston888 You need more things to fill out your day.

      @simonharris4873@simonharris487310 ай бұрын
  • 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.

    @LiamDennehy@LiamDennehy Жыл бұрын
  • 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.

    @HypocriticalElitist@HypocriticalElitist5 ай бұрын
  • Hamburgers also use the meat in the middle technique.

    @davemarm@davemarm Жыл бұрын
  • I can't believe it took me this long, but as soon as 10:48 happened, I realized "wait, that's Solarized!" Love it!

    @GammaFn.@GammaFn.9 ай бұрын
  • I watched every second of this video. Very well explained.

    @pedromonteiro1556@pedromonteiro1556 Жыл бұрын
  • 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.

    @mcb187@mcb187 Жыл бұрын
    • If you want to know the equation here: (12! * 2^12 * 8! * 3^8) / 12

      @droganjake2802@droganjake2802 Жыл бұрын
    • 43 quintillion already takes into account that you cannot move only 1 edge or only 1 corner

      @motherlove8366@motherlove8366 Жыл бұрын
    • 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!

      @bannah6400@bannah6400 Жыл бұрын
    • 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.

      @justinsmith2363@justinsmith2363 Жыл бұрын
  • Spoiler: this video will not make you better at solving a Rubik's cube

    @chrispysaid@chrispysaid Жыл бұрын
    • 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@atlantic_love Жыл бұрын
    • @@atlantic_love Young people have this little thing (you might have heard of it) called KZhead, 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@chrispysaid Жыл бұрын
    • @@chrispysaid How did the kids learn to do this back when there wasn't internet for the masses?

      @atlantic_love@atlantic_love Жыл бұрын
  • I'm 2:21 in and I'm already blown away by the quality of this video. So good. Edit: Done. Amazing.

    @felixmerz6229@felixmerz6229 Жыл бұрын
  • 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!

    @Wonders_of_Reality@Wonders_of_Reality10 ай бұрын
    • 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@david2039 ай бұрын
    • @@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.

      @Wonders_of_Reality@Wonders_of_Reality9 ай бұрын
  • 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.

    @sebbes333@sebbes333 Жыл бұрын
    • 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.

      @poproporpo@poproporpo Жыл бұрын
    • The problem would be the time taken to generate that directed graph, and the memory required to store it.

      @Aquillyne@Aquillyne Жыл бұрын
    • Try generating that 10^20 node graph and see how fast you run out of storage space.

      @ddichny@ddichny Жыл бұрын
    • 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!

      @bannah6400@bannah6400 Жыл бұрын
    • @Sion but all directions within the graph are "towards" the solved cube, just how all roads lead to Rome...

      @irrelevant_noob@irrelevant_noob9 ай бұрын
  • 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.

    @ruemeese@ruemeese Жыл бұрын
    • One could argue that Feliks spent years looking at cubes to get there. But I get your point.

      @petros_adamopoulos@petros_adamopoulos Жыл бұрын
    • @@petros_adamopoulos You could! But wouldn't that be the equivalent of spending years developing the software.

      @ruemeese@ruemeese Жыл бұрын
    • 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.

      @ddichny@ddichny Жыл бұрын
    • 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!

      @bannah6400@bannah6400 Жыл бұрын
    • @@ddichny "unscramble" is certainly a word, I like it.

      @romanlinnik7441@romanlinnik744111 ай бұрын
  • This video is how all algorithm teaching should be done

    @mamborambo@mamborambo Жыл бұрын
  • First time that I encounter this trick, and I really like it 🤩, please share more tricks like this

    @yassinesafraoui@yassinesafraoui9 ай бұрын
  • 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.

    @ryzenforce@ryzenforce Жыл бұрын
  • AMAZING CAN'T WAIT FOR YOU TO EXPLODE

    @prathameshsundaram7509@prathameshsundaram7509 Жыл бұрын
  • Wow the video production is crazy. Perfect

    @jeepkd@jeepkd Жыл бұрын
  • Excellent clear explanation!

    @8180634@8180634 Жыл бұрын
  • An excellent video turned out, everything is well thought out, a very clear instruction turned out)))

    @hemantahembram7601@hemantahembram7601 Жыл бұрын
  • I came here for the information. I was blown away by the presentation.

    @nosekills@nosekills Жыл бұрын
    • You are an amazing person.

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

    @gregrice1354@gregrice1354 Жыл бұрын
  • Your visualizations are incredible

    @isaacgreen9495@isaacgreen9495 Жыл бұрын
  • Next level quality ... n terms of content and art direction ..

    @uprobo4670@uprobo4670 Жыл бұрын
  • Very informative and great video overall!

    @So0fer@So0fer Жыл бұрын
  • So beautiful, ironic und understandable! GREAT WORK!

    @Funzelwicht@Funzelwicht Жыл бұрын
  • Krása! A tolik českých jmen pokupy. Wow, pěkná práce!

    @sarahsleamanova2072@sarahsleamanova207210 ай бұрын
    • Dekujeme za podporu!

      @PolylogCS@PolylogCS10 ай бұрын
  • 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.

    @emessar@emessar Жыл бұрын
  • I was never this fast in the 80s, but I certainly managed to solve the cube within 20 seconds. Great fun.

    @zerobeat2020@zerobeat2020 Жыл бұрын
    • kzhead.infoXeNFkzqGsMc?feature=share

      @bboobbee1965@bboobbee19659 ай бұрын
  • This video was excellent. Liked and subscribed!

    @hackercop@hackercop11 ай бұрын
  • Very clever! The meet-in-the-middle is so obvious - AFTER - you exposited it, that is.`😄

    @rgarlinyc@rgarlinyc10 ай бұрын
  • 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.

    @janparkki5704@janparkki5704 Жыл бұрын
    • So happy you shared your ordinary thought process.

      @david203@david2039 ай бұрын
KZhead