The algorithmic trick that solves Rubik’s Cubes and breaks ciphers

Рет қаралды 2,026,967

Күн бұрын

What do the Rubik's cube and a cipher from the 70s have in common? Let's find out.
Our Patreon: www.patreon.com/Polylog
0:00 Rubik's cube
9:40 DES
------------------------
Links:
Feliks setting the 4.73 record
• Rubik's Cube Worl...
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,...
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 Middl...
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á

Пікірлер: 1 084

Thesnakerox 9 ай бұрын

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

Quazex 8 ай бұрын

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

Team Cyborg 8 ай бұрын

Ah yes, WCA FMC TAS

FakeDane 8 ай бұрын

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

FreddieStarWars 8 ай бұрын

@FakeDane But it's also called FMC

FakeDane 8 ай бұрын

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

Marc-André Servant 9 ай бұрын

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

Michel Tatoute 8 ай бұрын

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

animowany111 8 ай бұрын

@Michel Tatoute 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)

Attila Török 8 ай бұрын

@Michel Tatoute 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.)

polylog 8 ай бұрын

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

DarkVoidIII 8 ай бұрын

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 KZhome chess strategy content creator.

deidara _ 8 ай бұрын

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.

polylog 8 ай бұрын

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!

Hunter Herbst 8 ай бұрын

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. :/

Peter Koch 8 ай бұрын

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

Reth Hard 8 ай бұрын

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.

Stephen Pollei 8 ай бұрын

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

CodenameLambda Жыл бұрын

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

polylog Жыл бұрын

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

TechSY730 8 ай бұрын

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

Joe Payne ◢ ◤ 8 ай бұрын

@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.

mz 00956 8 ай бұрын

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

Attila Török 8 ай бұрын

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

MechMK1 8 ай бұрын

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).

Roxanne Moore 8 ай бұрын

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

toriless 2 ай бұрын

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

MIDAS redblade 3 ай бұрын

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

Groudon466 9 ай бұрын

My guy, get yourself more of a social media presence or something- I was expecting you to be one of those math and logic KZhomers 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.

polylog 9 ай бұрын

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

xXx 8 ай бұрын

@polylog sorry you have to become mathematicians now

James Pond 8 ай бұрын

@polylog 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. KZhome 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 KZhome. KZhome 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!

Henri van der Riet 8 ай бұрын

@polylog I agree 100% with them. Wow!

Designed Audio 8 ай бұрын

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.

Z 2 ай бұрын

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).

Greg Mark 2 ай бұрын

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.

CoolCat Ай бұрын

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%).

Roman Linnik Ай бұрын

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 (

TagGamer Ай бұрын

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

Roman Linnik Ай бұрын

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

Chris 4 ай бұрын

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.

baianoise 3 ай бұрын

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 !

Lior 9 ай бұрын

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

gloverelaxis 8 ай бұрын

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?

polylog 8 ай бұрын

Thanks, good points. :)

Gerardo Berlanga Ай бұрын

@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. KZhome being KZhome just recommended this video to me and I was wondering if I could make my old code faster

Liam Tolentino 8 ай бұрын

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 :))

xXx 8 ай бұрын

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!

Ismail Alim 3 ай бұрын

Me too!

Brian Arsuaga Ай бұрын

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!

RubixTheSlime 9 ай бұрын

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.

polylog 9 ай бұрын

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

Gameboygenius 8 ай бұрын

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

toriless 2 ай бұрын

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

z3r0t3n 9 ай бұрын

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

Christian Stonecipher 8 ай бұрын

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.

polylog 8 ай бұрын

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

toriless 2 ай бұрын

Yeah, well double key encryption pretty much killed it.

Rich 3 ай бұрын

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

JackFoz454 8 ай бұрын

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

from Dil 2 ай бұрын

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

Ron C 3 күн бұрын

I can't imagine how long it took to make this video. Very interesting and thank you very much.

Greg Rice 2 ай бұрын

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!

Jason Harris 8 ай бұрын

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

Ollie Ox 8 ай бұрын

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

Public CBel 8 ай бұрын

This concept can be even more generalized as a standard computer science rule, which is memory vs computation. In the example of the rubics cube, you can find the shortest path in 1 move : you just have to get a full list of all moves. (so, you transform a problem too difficult on computation side to a problem too difficult on memory side) The idea of a pure symmetrical cut is theorical. In practical, you have to start one side, and store all the results, and then, go the other side and crawl in depth until you get one known position. As a solution, they cut the problem in half, but it could have been 20% computation side, 80% memory side (so going 16 steps from the solved status instead of 10), or the opposite.

Taurus Fan 8 ай бұрын

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

Jade Detective 3 ай бұрын

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

Michael Sanft 8 ай бұрын

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.

Aphra Xiaojun 3 ай бұрын

pretty sure chess engines dont, but yeah

AutPen38 2 ай бұрын

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!

Michael Sanft 2 ай бұрын

@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.

InOtherNews1 9 ай бұрын

Criminally underrated KZhome 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 :(

ગણિતી 9 ай бұрын

Absolutely correct

Maxim hoeve 9 ай бұрын

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

Milk Jug 9 ай бұрын

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

Toasted Uranium 8 ай бұрын

@ગણિતી 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.

Louis Dalibard 8 ай бұрын

Yes! This is insane!

Xcoder112 2 ай бұрын

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.

Liam Dennehy 6 ай бұрын

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.

Declan Brennan 8 ай бұрын

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.

polylog 8 ай бұрын

Thanks for bringing this up!

Georg Aubele 3 ай бұрын

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

Oxey405 8 ай бұрын

Greatly explained and beautifully animated ! GG for the work !

Infinity 2 ай бұрын

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

alien5589 8 ай бұрын

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

Russell Jazzbeck 3 ай бұрын

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

WagonLoads 8 ай бұрын

I really love this video, because I am trying to develop a cipher. My first attempt was a simple letter substitution (like a secret decoder ring) type code. I used a C64 and wrote it in basic, then later in machine lang. I put the scrambled text in data statements, then ran each letter in the message through the decode process. This is the simplified PHP version $message = "PZoOMFeMUXVxpuQ"; Decode strings: $secret = "eariotnslcudpmhgbfywkvxzjq"; $solved = "abcdefghijklmnopqrstuvwxyz"; This would convert each letter in the secret message from secret to solved. If the result wasn't correct, I would just type 2 letters to be swapped in the $secret string until the message was solved...

cubest 8 ай бұрын

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.)

polylog 8 ай бұрын

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

R Lanning 8 ай бұрын

What if - instead of calculating/storing ALL of the possibilities after 1 move, you found a way to quantify how close a cube is from a certain state, and only continued searching using the top 50 moves that get the cube closer to its desired state. Then using a meet-in-the-middle strategy would be even more efficient, as you’d only be searching through a fraction of the possibilities. For example, you could i this value based on each how close each individual piece is to its desired position and orientation, and consider all of them.

Kodfk Dleepd 8 ай бұрын

Is there a "conjugate" configuration that is sort of the "inverse" of some configuration? Maximally distant and easy to get to such as "flipping" all colors in some sense. If so then this should be able to be used to reduce the search moves list down to 4*10^5. Also does there exist a unique min path between a configuration and its conjugate configuration?

Emessar Games 3 ай бұрын

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.

microcolonel 8 ай бұрын

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.

DVSS 8 ай бұрын

As a computer Science student and a cuber, I absolutely enjoyed this video. Subbed! The information is presented so neatly and understandable, and the animations are amazing! It reminded me of 3Blue1Brown's animation!! edit: 14:02 it is !! Can you suggest some tutorials on how to use manim?

gloverelaxis 8 ай бұрын

whenever you see that awful* animation of newly-drawn text, you know people are using the graphics library 3B1B created for exactly this purpose * it's bad because there's no semantic connection between the animated states of "no text" and "text" to require that line-by-line drawing animation. it makes the mistake of "animating because it looks pretty" in a context where you also, crucially, use "animating to clearly visualise meaningful connections between states" -- i.e. it makes the visual explanation more confusing by muddying the waters of what all animations *mean*

Adam Jagielski 8 ай бұрын

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

polylog 8 ай бұрын

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

Brian Mahoney 2 ай бұрын

I've been using a similar dual point analysis to solve puzzle mazes since back in the 60's I think. I don't remember for certain when I came up with the idea it's been so long. The automotive diagnostic troubleshooting industry uses dual point analysis in their higher-end equipment.

Nora Salocin 3 ай бұрын

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 :-)

FFVison 2 ай бұрын

That issue with the having the plain text and the cypher text is also used in password hacking. There are lists of leaked passwords (known text) which may be compared to a list of hashed passwords to determine their hashing algorithm and try to bust the rest of the list open to figure out new passwords. Generally logins will take whatever password you enter and then pass it through a hashing algorithm and then compare the result to the hash it generated before.

cmonkey63 3 ай бұрын

I hold a PhD in applied mathematics (optimisation) with a special interest in cryptography, and so even though it is midnight, I watched this video with much interest. Combinatoric problems are notoriously difficult. This meet-in-the-middle approach got my interest. Thanks for this video.

peitz.design 2 ай бұрын

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

GreatBriton 8 ай бұрын

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

AutPen38 2 ай бұрын

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.

GreatBriton 2 ай бұрын

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

Bu Jin 8 ай бұрын

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

alexthebold 3 ай бұрын

For the purposes of simply solving, as most people can solve one face, could you discuss the numbers involved in solving a 2-layer scrambled cube?

Der HerrDirektor 8 ай бұрын

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.

spineO 3 ай бұрын

If you use this kind of approach for a weighted graph instead, then you get "bidirectional dijkstra" (and related variants). However, now when you meet in the middle you are not guaranteed to have the ideal solution, there will often be "shortcuts" that your algorithm thought looked longer, so you have to go through a little more searching to see if you missed anything better. Edit: i will just never remember the correct order of letters in dijkstra...

Ryzen 8 ай бұрын

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.

Michel Tatoute 8 ай бұрын

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

TEMARI VÍRUS 8 ай бұрын

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

TrailDude 2 ай бұрын

Wow. Best I ever did was 35 seconds, and I took about two moves per second. My younger brother liked to show off; he'd hand someone a Rubik's Cube and say "Make seven turns or less", and when they handed it back to him he'd ask how many turns they'd made, then he'd study it for maybe ten seconds and solve it in the same number of moves. Just once someone watched carefully enough to say, "Those weren't all the same moves I used".

Cyrus 9 ай бұрын

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

EJ EJ EJ 8 ай бұрын

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

cat22 3 ай бұрын

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.

jpdemer5 2 ай бұрын

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.

Rob Schmidt 3 ай бұрын

If you have a copy of both an unencrypted letter and the encrypted letter that are both 10,000 bytes long in this example. Wouldn't it make it faster to possibly solve the key if you solve for a subset of the 10,000 like 2,000 bytes. You might get a few possible solution, but you could then use those possible keys with a smaller set working on the entire 10,000 byte ones. Would that work?

Jan Parkki 8 ай бұрын

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.

MIMIK 8 ай бұрын

Wow! I learned about meet in the middle, why symmetric cyphers are symmetric, and why double DES is secure as single DES (if you don't count memory restraint). And a general solution to Rubik's cube, be it on a 90GB RAM machine... I wonder if there is a way to access memory on 8GB RAM with swapping to swap only every 1GB or so, but the graph is probably too dense to do that... No zkrátka parádní video ;)

polylog 8 ай бұрын

dík :)

Timothy & J 2 ай бұрын

For the meet in the middle, you only need to computing power (on hand) for getting to the middle, not the middle to the solution. For the solution to the middle that can be pre-computed and stored

Simon Harris 3 ай бұрын

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. :)

polylog 3 ай бұрын

Yes, every little optimisation was needed here :)

John Preston 27 күн бұрын

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

Simon Harris 27 күн бұрын

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

John Preston 27 күн бұрын

@Simon Harris 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...

Simon Harris 27 күн бұрын

@John Preston You need more things to fill out your day.

chakra 8 ай бұрын

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

Cat22 8 ай бұрын

When i was a kid we used a method called pattern identification. If you saw a certain pattern, and there were only a few of them, you made a specific series of moves, then the process was repeated until the cube was solved. The cube could be solved very quickly using this method.

spangle1980 2 ай бұрын

Nice video, content is extremely interesting. May I ask which tool/software you used to create the animated graphics?

Afonso Franco 8 ай бұрын

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

Twotone Ай бұрын

Knowing very little about this, could you reduce the memory required by using a similar technique that is used to reduce bandwidth required on transmission lines by only storing the differences from one outcome to the next? As an aside, when about 10 years old I tried solving an Evol, created by Edward De Bono, where you transition from one word to another with the least number of moves changing only one letter at a time to form a new real word. I used the meet in the middle technique, refining the list after finding a solution. Of course I had no idea I was doing something sensible I just was trying from both ends and realised it worked. I'm not really that clever.

Lee DeVille Жыл бұрын

Excellent video. Really enjoyed it!

William Graham 7 ай бұрын

I thought of this Meet in the Middle algorithm myself, about 30 years ago. I was just waiting for computers to get fast enough and with enough memory before implementing it. I see I've been beaten to the punch. I tend to consider quarter turns as the elementary moves, though. I learned of the Bűvös Kocka in 1979. It took a couple of years before I could buy one, after the deal with Ideal Toys and after the stores in North America had them. I like your animated explanation. It's very clear.

Rid Z 3 ай бұрын

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

Andariel Drachen Ай бұрын

That's funny.. I proposed this tactic be used as a potential solution for the queens puzzle as a SERIES of "reflections" as I noticed any given position of 4 squares only had a specific number of positions (1 but with 2 reflections) and that each grouping of 4 x 4 the same.... Unfortunately, i'm not gifted enough to program it but I thought it was an interesting way to solve for it quickly as the number of reflections was an issue of stored memory instead of having to brute force it.

Daniel Mondot 3 ай бұрын

You said that to store in memory all configurations up to 10 moves, you need ~10^10 bytes... That's a little simplified. To uniquely describe a cube you need about 90 bits of memory or about 12 bytes per configuration. Although technically if you compress the information to the minimum, you can do it in 8 bytes. Plus you need to store a tree structure to know from which configuration each configuration was made from, and what move was made. So that's probably over 120 GB of memory (assume the 10^n rule holds).

Zerøbeat 2 ай бұрын

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

John Undefined 8 ай бұрын

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

Alex Holker 8 ай бұрын

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

John Undefined 8 ай бұрын

@Alex Holker That's about it, yes.

Melds 8 ай бұрын

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.

Alex Holker 8 ай бұрын

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

Melds 8 ай бұрын

@Alex Holker 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.

Brandon MTB 8 ай бұрын

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

Scott Williams 8 ай бұрын

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

AnythingGodamnit 6 күн бұрын

Loved this, thank you! I wonder whether there's any specific animation tooling you use, or maybe it's home-grown?

polylog 4 күн бұрын

Thanks! We use Manim: www.manim.community/

John Ellison 8 ай бұрын

I'm glad to see that the Rubik's Cube is still fascinating kids today. I got mine when they first came out in Australia back in the 1980s. But I could never seem to get the last four corners to go back to the original positions. I should never have pulled it apart. 🤔

Luaan 8 ай бұрын

You have to put it together in a solved configuration; if you just put it together at random, it's rather unlikely it's going to be solvable. Most often, you're left with one corner rotated wrong and no way to fix it :)

So0fer 8 ай бұрын

Very informative and great video overall!

Sion 9 ай бұрын

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.

Darren Zhu 9 ай бұрын

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.

Virgil Ierubino 8 ай бұрын

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

ddichny 8 ай бұрын

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

MrVegas Ай бұрын

I was so engrossed in one of the many pivots with the discussion of Double and Tripple DES, I lost interest, for a quick minute, in what conclusions Meet In The Middle was attempting to explain the "solve" of a Rubik's Cube. lol. I can't believe I was able to follow all of that. to be honest. It was very enlightening and easy to understand. Thank you.

Wojciech Wiśniewski 3 ай бұрын

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.

Funzelwicht 2 ай бұрын

So beautiful, ironic und understandable! GREAT WORK!

Vlastimil Fürst 2 ай бұрын

It is kinda weird that I figured this trick it on my own some time ago, when trying to figure out a good solution for the old number scramble game. Seems that it is somewhat intuitive idea, even if proving it might be a bit harder than figuring out that it might actually work. By the way, zdar jak Brno :)

Mike Blackford 3 ай бұрын

I definitely learned a lot and it opened up my perception to a whole new reality thanks a lot definitely subscribing to the channel thanks

Lukáš Жыл бұрын

Thank you for the nice video!

Aiden 9 ай бұрын

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

John Długosz 2 ай бұрын

Another reason Double DES is not a thing is because applying two consecutive keys *might* form a group, where that is equivilent to another (single) key. It is not known whether DES has that property. But, 3DES uses Encode,Decode,Encode (not 3 encodes) to prevent this. Second, it provides for backward compatibility: a DES key, repeated 3 times, works as a 3DES key.

flojipo 3 ай бұрын

Double DES was also never used as it had a security issue with users using the same key twice, which in turn would mean it is sent in plain text. If a user would use the same keys in Triple DES it would still have DES safty - not really great, but better than plain text.

Ligaff The Indifferent 3 ай бұрын

Damn. I understood the whole thing. I could probably program something to do this simply based on this discussion, though I suspect some of the optimizations he did not explain would make a very big difference.

Jesse Helton 8 ай бұрын

There are many move sequences which are circular. In the solving steps I know there are about half a dozen of these that would be 10-20 moves. It seems to me that you could make sub-man-in-the-middle branches of the search graph sequences using known circular sequences and you could optimize both cpu and memory.

MCB18 8 ай бұрын

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.

ImADragonRawr 8 ай бұрын

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

motherlove 8 ай бұрын

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

Justin Smith 7 ай бұрын

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.

Old Starchy 8 ай бұрын

This reminds me of two things. One is that my housemate has a folder full of images he uses as desktop backgrounds, he's got about 4000 of them. The problem is that there are duplicates, we wrote a program to find the duplicates. Initially we talked about writing a program to compare each file to each other file but 4000*3999 comparisons would take too long. Instead we just stored the content of each file in memory and only compared each image to the previously loaded images. This is still n^2 but it ran in about 10 minutes. It was fun watching the ram usage graph increase as it was running. Using a hash would make this much more efficient, and we're going to have a look at resizing the images and reducing the colours used to find similar images, not just exact matches. The other thing is a pathfinder I wrote for ComputerCraft. Even with heuristic searching the number of possible paths was huge when entering buildings. Finding it's way out of a maze was efficient as there's only one way to go, but from the outside it would take forever to get back in the maze since it would only know about obstacles it had bumped into already. It had no concept of the ground and would constantly try to go around the floor. Searching from both ends at once would potentially make the pathfinder much more efficient in these asymmetric situations.

ddichny 8 ай бұрын

Were you comparing for "close but not exact", or simply "the exact same image"? If the latter, there are much faster methods involving sorting the images (either by full content or by their hashcode), at which point any identical images will necessarily be adjacent to each other in the sorted list. Sorting a list of 4000 items and then doing a linear search for adjacent matches will take a trivial amount of time.

Old Starchy 8 ай бұрын

@ddichny the latter, keeping a sorted list would have been faster but I didn't think of it at the time. We did consider using content hashes, which led us on to discuss reducing the resolution and colour palette to find similar images.

Luke Newmeyer 3 ай бұрын

Somehow I expected there to be a less "brute force" solution to the fewest moves. Fascinating approach to simplifying the problem though!

Sarah Sleamanová 17 күн бұрын

Krása! A tolik českých jmen pokupy. Wow, pěkná práce!

polylog 4 күн бұрын

Dekujeme za podporu!

CTLanni 3 ай бұрын

When the Rubik's cube came out I was absolutely fascinated with the engineering of the puzzle. How did they hold all those pieces in place so that you could move them in each layer of 9 cubes? Needless to say I never solved that frikkin puzzle! Nor did I take a hammer to it to see how it was constructed. LOL! But I was impressed by some of the world's record solvers over the years and I think the algorithm solution here is remarkable too. Good job!

Eli Chapin 3 ай бұрын

don't wanna be, that guy, but the middle layer only has 8 cubes cause there isn't a center one

Izzi-Vee Morse 2 ай бұрын

It's actually really neat to look at the way that it all holds together. Highly recommend opening one up when you get a chance, you can actually just kind of force/twist a corner piece off and that helps you take it apart quite cleanly

John Preston 27 күн бұрын

@Eli Chapin There is only one "cube", and that exists only when none of the sides are twisted in such a way that it is no longer is a geometric cube. The little bits that make it a cube, are not themselves "cubes". Fascinating design, though. As Izzi-Vee Morse suggests (below), prise/twist (gently) off a corner piece, then the rest can easily be separated from the core.

Eli Chapin 27 күн бұрын

@John Preston they are tho, at least mostly cubes, the centers are the least cube like, but on my cube they are still cubes, the edges and corners have bits sticking off of them, but the main body is a cube

John Preston 27 күн бұрын

@Eli Chapin Agreed, the whole thing is a very close approximation of a geometric cube, but the components are cube-like. In the same way as an incomplete circle is not truly a circle.