Scale By The Bay 2021 : Stewart Stewart, Solving the Rubik's Cube with Group Theory

Scale By The Bay 2021 : Stewart Stewart, Solving the Rubik's Cube with Group Theory

Recording: Scale By The Bay 2021 : Stewart Stewart, Solving the Rubik's Cube with Group Theory

thank you for coming my talk we have a lot of interesting stuff to talk about uh so we're gonna get into it so we don't know why we're here we are here to solve the rubik's cube using group theory and functional programming in particular on our agenda so we're going to learn a little bit about the the group type class and and permutations so the group type class actually already exists in your functional programming library so uh cats for example has a group implementation um notably it doesn't have a dedicated documentation page so perhaps you can bridge some of that gap here um we're going to use a permutation a simple permutation class that i've written up for this and we can see how how theory in informs the the modeling and design of a dsl and solution um and finally we're gonna um we're gonna combine all this theory to solve the rubik's cube and we're going to solve it live on screen with this uh this bluetooth rubik's cube so i have it enabled here where it'll track all the moves i do here and they'll be that'll be useful throughout the presentation for demonstrations and we'll we'll get back to that okay so um let's start with the definition of a group and in fact as as a recap you you've heard of what a monoi is uh probably um the monoi just has an empty and a combining observation so the empty is your identity element um and here's a monologue for for ins uh it's a typical example you have zero and you have addition so you can you can add into the with the monoid now here is a definition of a group this to the abstract definition the group is just like a monoid except that it has here the inverse so for ants that means negation so now we have negative numbers and you can combine negative numbers to get back the identity now this is an example using using the integers but i actually don't like this example this is a common example i don't like it it doesn't tell you the full story of what a group actually is and what you can what you can do with it so for example with a monod you know that that tells you that this is full foldable you know we can do mapreduce we can optimize in various ways by doing like parallel computation and removing intermediate data structures and you can imagine with the group like perhaps you can also take the inverses and collapse them and avoid those computations but there's a lot more to it which is why we're going to show you a particular kind of group called a permutation so this is this is a perm and we're going to um go into a demo here let's bring up a worksheet in fact actually we'll bring up we'll bring up a rebel so we know what permutations are they're they're scramblings right so if we take abc uh permutations in scala then we can do like for each print line and we get all these scramblings of abc similarly you know we can do that with one two three and there's a similarity here i want to point out is that okay the first line of these two is is the same it's just an order the second line here is a swapping of the second two elements so what what a perm does what a perm does is it encodes that so this is that swapping of the second two elements you swap three with two um swap and you know this a here just swapping one with two okay so what can you do with these permutations um these problems are not just data structures they are they are functions so we can we can apply these to two numbers so a applied to 2 that gets us 1 b applied to 3 that gets us 2. okay so these are com these are functions and as with your regular functions you can compose them so if we compose a times b and we apply that to three um you know we get one and i'm going to do just a few examples here of some multiplication of two terms so we have a times b and notably normally the functions you don't get a data structure back right but since these are represented as data we do actually have a physical thing so we can we can compare that we can we can compare that with um equals perm 1 3. okay so a few more of these b times a we can do b times b and we have uh we have many more permutations and now um what i what i want to point out here is that just by multiplying a and b we have all these permutations 1 2 1 3 2 1 3 three two three one two three these are all these are exactly these numbers here so we have all six of those um so so uh yes terms form a group they are there there's a composition i i should show you the inverse so if we multiply a by itself uh we get the identity right so um a is actually its own inverse a di inverse and then you know b dot inverse is uh it's just like b times b so this this fits the definition of a group but one reason i want to point that out um is because oh one second here okay so these six elements here these are the actual um these are the actual group it's a group of six elements and you can generate completely by multiplying just two elements of a group so just like how with a rubik's cube you have you have these six operations which are face turns when you when you start combining those operations you get the full list of 43 quintillion possible states of the rubik's cube um but there's more to it than that so so we have yes this is a group and in particular i i want to note so so this is a group definition i i want to note that because all these elements are actually functions um well all all these all of these are are actually by jackson show bijection is exactly the same thing as a as a scramble as a as a permutation right and it turns out that for any any kind of group you get so you have you have you have a you can define a function using a's operation like this and you can define an inverse function g so not just for permutations but for any permutation for any group you you all the elements are bijections uh so if all the elements are bijections all the elements are also permutations and this is essentially what what kaylie's theorem is and we can do a more formal proof later but the point is that any group you can define can also be defined in terms of permutations and with permutations we have all these um all these useful operations we can [Music] for example we can we can compose one two two three three four and this gets us the um the the four cycle one two three four we could also take one two three four and we could decompose it into into individual um transpositions so that would be true for anything with a group structure right you can represent as permutations you can build your uh you can build up your actions you can um and you can decompose them and if it's if it's easier you can represent in terms of permutations which are a familiar object okay how are we on time 10 minutes cool okay and this just a recap of everything i've said we can represent our functions of data we can leverage entries of group theory knowledge and theorems have come out and permutations are computationally useful so that's why we're using permutations in fact any group is a permutation okay so now we'll look into um into the rubik's cube so the rubik's cube naively you can think of this as a permutation of the sticker so it sort of makes sense to represent as a permutation but there is more to it than that um let me pull this up it has some structure uh some rules that we can encode in into group theory um so for one there are let me let me pull up an image for you here there are two types of pieces here so we have um we have corner pieces and edge pieces so these three stickers on like that red green white corner they can't ever be moved away from each other and since these piece types are distinct a single corner can only ever be moved to the location of another corner so so demonstrating that with the cube say this is red green and white if i did a clockwise turn of the red face it is now in the in the back position right so we can think of this as having two permutations within it a permutation of eight corners and a permutation of of the twelve edge pieces right so if we ignore just the edge pieces then we have a smaller puzzle it would be the two by two rubik's cube and it turns out this is something called um a subgroup right so so this is composed of at least two subgroups where you have the corner the the corners only puzzle on the edges only puzzle and then um it also has orientation so this red green white piece i could do i could do a transformation here and now we have the same piece in the same location so that's that's its orientations and the orientations also form a subgroup and these are these are particular particular kinds of subgroups these are um normal subgroups which which means we can it's easy to work on them individually so you can we can solve these individual puzzles first uh when we're trying to solve the larger puzzle okay um a note about this so this face turn it is a pairing of two four cycles you have four cyclone edges four cycle on the corners uh now i i mentioned earlier that you can deco decompose a cycle into into pairs right so the the a four cycle is composed of three pairs which is an odd number of pairs and it turns out every permutation can only be composed of either an even number or an odd number of pairs um so that that's relevant for solving this rubik's cube because we'll only we'll always have the same parity on both our corner puzzle and the edge puzzle and we'll get back to the idea of parody later but you should just you should just know about it for now okay so here's here's my model another rubik's cube like naively you might have just made this like an array of 54 elements uh but here we're going to model it in in pieces so that so the whole cube state is composed of both the corners and the edges um the corner state is composed of its permutation and the orientation of those corners similarly for the edges and in fact the um the orientations can also be represented as groups or that each corn each corner orientation for example is just a the group generated by like a three cycle and this is what our group definition looks for like for cube state so when we're combining two cube states which is which is to say you know doing a set of moves that creates one state and then following that with another set of moves then we combine it by just multiplying the states of of both groups so we multiply the corners of both groups and then the the edges of both groups similarly the inverse is just the inverse of both groups pairwise and this this type of group composition is called a direct product so you could generally take any any two groups and concatenate them in the same way this could be part of the the group um the group type class interface that allows you to combine uh two groups into a larger group and that's called the group product and there are technicalities i'm hiding there but we can say that for q a the corner group is similarly it's just you combine the corners and you combine the um you can run the orientation it's actually a little bit more complicated here because in this case we are taking this is what's called the subdirect product and uh you could come to that intuitively or you could use theory uh in this case i'm sort of just giving it to you because there's not much time to go over that and then similarly even even corners are are groups that you combine so um so yeah our our definition of a group for a cube is just composed of definitions of groups um all the way down all the way down to the orientation of a single piece it's just subgroups all the way down um so how might we start using all this information and develop a solution um we are 15 minutes and oh this is great we'll have plenty of time okay so um the first concept i want to teach you about is commutators so i'm going to bring up a bring up a ripple here and i'm going to bring up two particular permutations here this cycle is the first five elements and this cycle is five through nine so these two permutations intersect at only a single point now where a commutator gets useful is that um if you were to do p so a commutator is a as a form as a an expression of the form a b and then a inverse and then b inverse so if we were to do that with this times uh p dot inverse times q dot inverse what we get is a three cycle a three cycle of elements 165 which is to say that because these two perms hardly overlap most of these operations in in pq you know in in the commutator get cancelled out um and that's something i neglected to point out earlier uh groups aren't necessarily commutative right so with the integers you can um you can add and subtract in any order you want and you can you can swap those around but it's not always true that p q p inverse q inverse is is back to the identity so um with a group like the rubik's cube or permutations in in general um you have to do your operations in in in terms of of operations like this here uh okay so those are those commutators all right um let's talk a little bit more about parity so all all these perms let's take um all these sperms are either even or odd right so it turns out when we have an even permutation we can take each of those uh we can take those transmission positions and we can take them in pairs and when you multiply two transpositions you you can get a uh you can get a three cycle so that that means um you know a a problem like p which uh this is an even permutation we can do uh we can decompose that as three cycles so p can be decomposed into one four five one two three uh and that helps us manage these these larger um permutations we're getting on the cube we can decompose it into three cycles and since a commutator can help us solve these three cycles that helps to solve the the problem in general and a final note we the other tool in our box here is conjugates so this is um an expression of the form a b a inverse um and conjugates are useful when you have something when you have like a a normal subgroup excuse me so let's say our our operations so back back in the slide this b is one of our commutators it's a three cycle so those three cycles form um form a a normal subgroup which is to say you know the permutations of the cube are a normal subgroup and we can use um and that's the case uh a conjugate of that operation is also the same type of it also stays within the same uh sub subgroup so a conjugate of a three cycle is or of you know and any corner permutation is still going to be a corner permutation and just to demonstrate that so here we have on screen um let's say we had you know a useful element uh i'm what i'm going to do here is uh well before we get into that let's just show an example of a of a useful operation so we can do um we'll do a commutator so here we've swapped uh we swapped this front right corner and this is this back right corner uh we've left the front intact but the the back has been messed up somewhat so we can do a b move which intersects at only that one point so this only affects the front face and that one corner that was affected as part of the previous algorithm then we can undo the first move and then undo that front move and and now we have a three cycle right but while we didn't want to cycle those three then we could take um we could take another element altogether and put it in the place of one of those so where that move i just did swaps these top three if i were to do a half turn on the back i can swap these three instead and that's essentially what a conjugate is right it lets you get more more mileage out of that single um commutator you invented all right um and now we get kind of into a demonstration of solving some of these so we'll pull up the worksheet um okay here here i've encoded a scramble uh and we can print it states here you know we see we see the corner state the edge state the permutations and orientations um but in particular we don't have time for kind of a full full-on solution so we're gonna we're gonna look at just the the corner permutation and when we do this scramble the permutations of the corner that this is what we're doing to the corners um is we we don't need to and we can solve this independent independently of everything else um so remember that com actually i showed you a different commutator but here's another commutator for cycling um for cycling corners right it gives us some algorithm we can print that in a nice way so we can do simple com that turns okay so this is the algorithm for for that commutator that that generates um but like like i said earlier we can we can conjugate that uh to invent new new algorithms new commutators so this this one here that we just did corresponds to the permutation 187 right but if we were to change something let's say um uh conjugate by um conjugate by u which is a turn on the upper face now we get 487 right we can we can create many different variations of that let's say this d became a d two uh d2 we get yet another algorithm so we can take our commutator and and kind of break it down and we could insert variations here so instead of u i could have done u2 or i could have done you know u3 instead of r2 you know i could have done l2 but you'll note here this this list oh maybe i can't do all of those okay we'll just do conjugates here so we have a list of one possible algorithm but if we start to do u and u2 and u3 down here then now we have four uh you know we can do d d2 d3 and we're getting more and more more algorithms and this is growing fairly quickly but remember we only need we only need 56 different cycles so it doesn't take much modification before we get uh you know 56 distinct cycles um so going back to our our our scramble it was that that one permutation one four eight six three two five right so we can take that we can take that um scramble uh that state that we can take the corners uh and then we can do we can get just the three cycles from that um so um we're just going to get like a a pretty print that and we'll print that actually this is this is not exactly honest here um because what we want is kind of the what we what we want is the inverse of the of the scrambling permutation so we take solution cycles that inverse and then well actually we take the scramble and then we invert that so we can take the the corner permutations and and get the inverse i'll just print that as so and this tells us that in order to solve this scramble for the f for the corners we first have to do 184 then one three six and then one five two okay so i don't have time to to code up like the full um full generation of all possible commutators but you get the point you can you can you can search for these commutators essentially by looking for algorithms that intersect at only one point and then you can make variations of any commutator you you discover by just doing conjugations um okay so i've actually already coded this up here so if we if we run this here is an example scramble and let me pull that up next to oh ok we're going to pull that up and we're going to pull up our code our worksheet we actually want our terminal okay here okay so i'm gonna uh we have three minutes that's plenty of time to solve rubik's cube okay so here we have we have a scramble this is a permutation that generates this is the part the orientation it generates the scramble is actually just a corners-only scramble we're going to ignore edges for now but you solve them in basically the same way so we're going to the scramble uh d2 u r 2 d 2 prime p 2 r 2 b 2 r d prime b 2 d b 2 r p b2 and it looks like it didn't mess that up okay so what we have here now uh this here describes that permutation and this here is our solution so if we first did 163 and then we did 1557 we'd solve the the permutation now i i didn't i didn't show the generation of like a orientation commutators but i can i can just solve that um independently here okay so we'll fix the orientation um okay so the orientation is fixed and oddly huh interesting so so the the bluetooth web app is out of sync with my um with my rubik's cube so i can't just put this right now okay what i'm gonna do basically i'm going to execute these two algorithms and now we have to use my my camera because that's that's out of sync but we can do this one here so it's like a ldd prime l2 uh u2 and oh whoops um okay so we have um l2d primal to r2 area b2 altitude prime ltv too um and as you as you can see on on my cube here there's only a three cycle left everything else is solved um so now i can i can just uh solve the second cycle and now we have um what do we have and there we go so the rubik's cube is solved and if everything had gone according to plan this this cube here would also be solved but they're out of sync for whatever reason and i can debug that later um but it works and i'm happy about that you could be happy about it too if you want but the key takeaways here are that groups aren't just a monolith inverse they are about space transformations um they allow us to turn our functions into data which we can then manipulate so we can manipulate functions in that way so so they're great for computation and when when our intuition fails we can rely on the centuries of group theory that that you know of all the theorems have been developed and look into the literature and use that and leverage all of that knowledge uh so groups are um groups are useful they're not just fun and interesting and and perhaps you know next time you reach from onenote you should also look at hey is my thing a group okay so that's my presentation thanks for watching um if you want to see more of this i'll be streaming live with this with this um library doing more development interesting stuff with it at twitch.tv.2 squared you can see my group my my code at this link of course you can contact me on twitter or email or you can just dm me on discord that works too but that's it thanks everyone