Mike's Cube Code - Computerphile

Key Takeaways

today I thought we could talk about something just for fun that I was coding at home right so a quite a while ago now I did a video on maze solving and the only reason I did that really was I just thought that might be quite fun to do right so I wrote some maze code and quite a lot of people looked at the GitHub and had a go at the code themselves and so we're doing something a bit like that today now this actually came about because my son came home my son my son is 10 came home from a math class and what they were doing was they were trying to find all the different shapes you could make with different cubes so kind of like Tetris shapes how many of those are there right and they just had to basically try and Brute Force find them all and then there's a question of like well you know if you can now add one more Cube how many new shapes are there and you've got to add more one more cue to all of those how many new shapes are there and you know my son's teacher sort of absent-mindedly said well I know your dad does some coding maybe you can look into this and one thing led to another I lost hours of evening and and you know it's a red flag to a ball when you ask me like could you just do this you know coding thing like well obviously yes um so anyway long story short uh that's what we're talking about today or how do I generate all the possible combinations of Cubes just for fun right and is there a formula here or is it there's no there's no scene there doesn't seem to be any kind of formula but you can imagine that if you have sort of a straight one and then you add a cube on this side or you add a cube down here that's the same shape right because if you rotate it it's the same it just makes an L so there is a little bit of thought behind this it's actually quite why it's quite an interesting programming problem I think is this in a 2d plane no so this is in 3D right I'm going to draw 2D on the page because I think if I try and draw 3D we're all going to have a bad time uh but but actually it's the same exact problem it's just that there's now an extra Dimension so my code is all 3D but it's exactly the same problem in 2D you can find a few people that had a go at this before and in fact it turned out on Wikipedia about the most ever combinations of shapes are for 16 cubes right no one's ever documented Computing more than that now I have not managed to get to 16 cubes yet but when I do you can be sure I'll be editing the Wikipedia page and saying I did it like 17 cubes what I thought was interesting about this was I started programming it thinking this is going to be quite trivial right and it wasn't desperately difficult but actually there some thought has to go into this especially if you want to make it fast right so I thought we'd just talked through what I did and I'm not saying it's the right way to do it and then maybe people want to have a mess around see if they can improve my code recode it in a different language which is way faster and and so on and so forth and let's see you know how far we get what did you do it in uh C sharp I did it in Python using numpy which is essentially a lot a large array it lets me do operations on arrays the reason I did this was because it was the quickest way to getting this running right python is much much slower even with numpy you you could speed this up a huge amount by using you know C or Java or something like this the first thing that was on my mind was how do I represent one of these shapes in memory so one option was that I read online was you could just have a list of coordinates so you could say Okay a three long would be not not one not not two not naught or something like this right and you could have a coordinate system that did this but you then got to write a load of code that transforms some coordinate systems to you know rotations and things and I thought well that sounds difficult so what I'll do is I'll just have a byte array that is let's say three by three by three or two by two or whatever and there's ones if there's a cube in that position and it's not if there's not a cube in that position right that's very easy for me to visualize in my head so that's what I'm doing so suppose I wanted to do an L shape a Tetris L you know then you might have a two by three array we're talking about n equals four so you know and in 2D and you might have a one here a one here a one here and a one here and actually that's quite easy to do in in numpy you can create a two-dimensional array if you want to do this in 3D you can create a three-dimensional array which would obviously have something going back here which may or may not have ones and zeros in other channels now how do you then generate all of the possible combinations of this well one one option would be just to have a blank array and just randomly populate this with ones and see if you've ever seen that shape before that's not a desperately efficient way of doing it because for example that is not a valid shape right because these have to be connected diagonal's not allowed so it has to be you know that or that or some you know some combination of ones that can actually connect together one of the ideas that I was reading about and I'll put all the links to all the resources I use as well in the in the description but one of the ideas was why don't you build all the next set of shapes off the previous set of shapes right if you've got all the possible threes you can just put some blocks on it and then create all the possible fours and then you can create all the possible fives and so on now it takes a little bit longer to do this because you always have to generate the previous set of shapes but actually in practice generating the next set is always so much slower that it doesn't really make any difference so suppose you were generating these this four here and you wanted to know what are the next set of shapes I could build from this what I do is I pad this array out I haven't really thought this through this drawing but sort of worked very nice numpy functions to do just this right you'd have to do it by hand this would be populated with zeros and then I can say well okay where are the possible places I could extend this to right well one of them is here here here here here here here here here here and here now sometimes depending on the shape this will produce you a new shape that you've never seen before so if I put one in here you get a kind of Zed or whatever that is if you put one here you get a kind of upside down tee so you can go through each of these and you can add one in and say okay have I seen that shape before it gets a little bit more complicated because then you realize well hang on a minute half of these shapes are always the same as the ones I've seen before so suppose you had this shape here which is let's say one one one and you put one in here right now you've got a kind of t-shape whatever that shape is in Tetris I don't know I'm sure there's a name right but if you put one there you've made the exact same shape just rotated 180 degrees right now you could include those are two different shapes but actually you shouldn't really right if you want to know all the possible shapes you have to be able to weed out all the repetitions what counts as a rotation and what counts as a flip I think you have to just try and visualize in your head but obviously if you can rotate around any axis and it aligns up exactly it's the same shape that's the idea so when I was coding this up it was quite easy to write something that represented a queue a polyq is what these are called as ones within a sea of zeros and it was quite easy to write some code that said okay these are the next shapes and let's Loop through each of those it becomes a bit more difficult when you want to say have I ever seen this shape before given that I don't know what rotation it was in last time I saw it right that's when it becomes a real headache and it's just it's just the kind of thing where you think oh I can't be too difficult and it's going to be really really quick and efficient and then you realize actually this it isn't very easy to write really fast code that does that because ultimately there are 24 possible rotations in 3D of this and that's not not so good so I I did I thought the first thing I did was a super lazy version so what I did was I just had a huge list of all the shapes I'd seen when a new shape came along I rotated it in all possible directions and then looked through the whole list right and those of you watching and wincing a little bit at the at the efficiency of that you'll be absolutely right to do so right it was shockingly slow I managed to produce I think up to all the eights and nines before my laptop said no I'm not not going to go any further than that unless you want to wait half a year Savannah had another thought but think about this and I thought well one of the ways that you can improve the speed of lookup is to use something back like a hash table right or in Python a set which allows you to find very very quickly whether something is already in there as I mentioned one way in 2D if you've got a new possible shape which is let's say this shape here and you want to know if this shape has already been seen before and you've got a huge long list of all the other shapes one of which might be that or that you know and some other rotation then in 2D what you would have to do is rotate this four times and then for each of those four look for all your shapes and that's really really slow right in 3D it's 24 times it's even worse is it is there any benefit in sort of storing each unique one you've found in those 24 ways and then when you're looking something up you're just looking through 24 times the data or is that just the same problem reversed it yeah you end up at some point you have to calculate all 24 rotations and then what you're doing is you're trading off the lookups fee for the memory you've used and so on I think you know this is what I quite like about this problem actually is that you think oh this can't be that hard and then you realize this is a bit of a memory mess and this is taking quite a long time to solve and apparently the world record for this is number is n equals 16 and I'm not even close to N equals 16. my my laptop's maxing out n equals nine this is an embarrassment right I need to do something about this so what what I did was I I decided okay so the first thing to do is what is the fastest way we can compare this at each rotation to all others now one nice thing is that in numpy when you rotate an array you don't actually have to rotate it in memory you just look it up in a different way right so depending if these are all pixels you could imagine that if you looked in this order or you looked in this order or in this order that's equivalent to rotating that shape and so actually you can do this quite elegantly so in some sense the rotations isn't actually such a big deal it's the lookup if you're looking through a list then the problem you have is to find this element you have to compare it to every single element in the list that's going to get very slow very quickly if you've got one element in the list it's one check if you've got 10 000 elements in the list it's going to be 10 000 checks right you don't want to do this essentially what we're going to do is we're going to find somewhere converting this shape into a simple hash numerical code and we can just look up if the code's in there and that can be done much more quickly because often you avoid any collisions you just jump straight to the right place and you say nope not not been seen before now hash functions don't work well with objects that can change right mutable objects where this can change and change shape and be different shapes that's hard to Hash so what I was trying to do was find a way of representing this in memory in a really concise way that also didn't change and so I could hash it really quickly so I came up with my kind of Mike pound special run length encoding scheme which is never going to be used again and it's terrible but I thought it would work so what I do is I store a list of integers that represent this so first of all I flatten it and that means basically take this and just lay it all out in one row and then I store the X the Y and the Z size or X and Y if it's 2D XYZ if it's 3D and then for any string of zero so this would be one two three four five zeros before you get to the next one I'm going to restore a minus five and then for any string of ones I'm going to store a positive number so that would be one then it'll be one two three minus three then another uh that's two actually right it's kind of worked I can't believe it uh and then one two three four five minus five now is this the perfect way of storing these shapes probably not right this is what I came up with while I was sitting in front of a TV if anyone can beat me then please do what were you watching there were no helpful programs on how to do this that was disappointing so now that I've got this I can fix this in memory and then I can hash it and that can be stored in offset and that allows our lookup to be much faster right so now essentially we're not having to look through 10 000 objects every time we have to convert it into this one length encoding format then we hash that which is automatic in Python I I like when it does things for me you know I have to do it myself and then we can quickly look it up in a set and say is it in there if not we can store a new one and then and that's really what my code does right so if you download my code on GitHub you can see what it does it essentially takes as a command line parameter a number of poly cubes to use right so n equals 10 would mean you're generating all the combinations of 10. so what it first does is generate all the combinations of one two three four five six seven eight nine if it's already seen them before and saved them to a file it will just load that file nice and quickly and then um and then it starts generating each 10 and actually I think I've generated up to 11 or 12 now right and and it's getting a bit slow and I got a bit bored so I stopped right and I thought you know I've got to give someone else some work to do um but there are lots of ways you can improve it so first of all python is quite slow right I mean python is fine and and I've tried to use numpy libraries to do this most of the time partly because it's easier for me to program and partly because that drops down into C quite quickly and it's much faster than if you're doing lots of Loops in Python but multi-threading this doing it in a language which is Fast By Design would be better right and it might be more memory efficient because I've made use of some sort of slightly lazy numpy libraries to find the bounds of objects and rotate all the objects and stuff there might be better ways of doing this um the key if you really wanted to produce many many of these is that you would need to find some way of encoding this which accounts for rotation and I haven't thought of one yet right and everyone else I've asked has gone well that must be easy and they've wandered it off and come back with a bit of a headache and not work to how to do it part of my code crops them down to the minimum bounds first because that's not the true shape of the object that's also slow and also annoying that I had to do that but you know there are loads of efficiency savings you could make I kind of gave up and thought well this is good enough what I'll do is I'll put it on the internet and let someone else fix it for me um but it's a fun little project if you want to have a go at it you can generate loads of different cubes you can actually render them on the screen and then um have a look at them right now up to about n equals eight at which point you know the graphing Library doesn't help doesn't thank you for trying to generate that many cubes um but I thought it was a really fun problem which was a little bit more difficult than I thought it would be and it's one of those nice problems where it's difficult enough and it's a fun challenge but you can actually do it just just thinking about it could you load this into something like beast and get the gpus going yeah so I mean that is sort of on my mind is that if I could implement this in a multi-threaded way using a different language python doesn't handle threading very well um but if I could do that I could run it on one of these 100 core machines and to see what happened right um and maybe I'll have a go at that record up and down and up and down and up and down and up and down and get yourself into a loop or here we've actually got an actual Loop we might just go round and round if we don't have any idea about where we is so like 12 mod 7 is five five times five is twenty five but the next multitude