Solving a HARD algorithm with Rust!

Transcript

English (Auto-generated)

it is your boy says today we're gonna be doing a kind of harder algorithm than normal. It's called snail sort. So basically if you just look at the geometry of the problem, it helps you understand it. You have this array 123456789. It's a two D. Array or matrix. You might call it or maybe a list of lists if you want to be literal. And what we're supposed to do is basically loop around it in a spiral. Working our way inwards. So we'll start out with 123 and 69874. And then we loop into the middle here with five and they give us a bigger one over here. So it's like 123. We loop around loop go in in in until we've gotten all of them and it'll go in order. So it'll be 1231477 blah blah blah going in that order. And we're just gonna make one single list or array or vector I believe in this case I think this is python, we're gonna be doing this in rust. If we look at rust, it'll want us to give it a vector. Yeah. Return of a vector of signed 32 bit integers which they're actually all positive. So I don't see why they need to be signed whatever. So how do we do it? That's the challenge. I don't know. Let's see if we can come up with something. So my thinking is we can just pop this top layer off, right, that's always gonna come first and then we can basically rotate this, like rotate the whole thing in a circle so that now we pop we get this one and just delete it. And now we have this these two right here are a new array right? Like this bottom half over here, let me highlight it, so you can see this Right? And then we we rotate that array so that now four and five are at the top basically just rotating it by 90° and then we take the top off and then we rotate what's left and take the top off and keep doing that until there's nothing left. So take this 123 off rotated. But it would not be would now be 69 on top then five a blah blah. We cut 69 off, rotated again, we'll have 5847 pop out off, so on and so forth, we'll have 123, pop that off. We got 69, Pop that off. Now, this is the top, we pop off 87. Now we have a four on top of a five because we rotated, we pop that four off, we're left with just a five. This might be a two parter because these four cues can be a little more time consuming than our standard problem. But nothing wrong with that. Just that I don't take up your whole uh already two minutes in, just describing the problem. And that's the easy part. So by the way, is here on code wars. So if you just look up like I look at code wars snail to find it so you should be able to just google it or use brave search or whatever you got. Yeah let us begin. So I'm gonna go ahead and copy what they have here and we're gonna need a main function. Okay? And I'll just start out with some Hello World here to make sure everything's working. Get the semicolons. I'm more of a python guy, so it's semicolons constantly because python doesn't happen. And then javascript is optional. That just builds up the worst possible happens. There we go Hello world. So I'm gonna copy over the snail function they made And it's mad because it's not returning that vector gonna create effect of I-32 so that it will be returning, it doesn't make the error message go away because I want to compile stuff later. We can see what they pass us is actually in array. So I'll just go ahead and create that array in here too. We can pass in the exact same type of data we're gonna be getting Okay. Okay beautiful. Let me did this a little bit super indented. And then we will say that let's say for example we'll call it like we'll just print out the results, Print lie and we'll use this feature to so we can print it out and we'll print out whatever our function returns. So we'll pass it square? What do you guys think? You ready? Alright. So I noticed this is an array it's an array of vectors. I really don't like dealing with a raise and rust. Unlike languages like C or javascript array really isn't our go to data structure and rust. We're gonna want something more dynamic in this case of vector. So I'm just gonna go ahead and convert it to a vector, create a vector called V. And say that it just eats equals and matrix matrix 0.2 vector. I have this really cool. I had to have co pilot doing all this really fancy. Ai it was amazing. But What happened you may wonder tell you exactly what happened they made it pay have to pay now. It's not free. The bait is over $10 a month. Not paying for that because I'm already a genius. Okay, so we've made it into a vector and let's think about how our algorithm works. Right? I was like okay, so we're gonna loop like keep going until we run out of numbers or something. Run out of numbers, keep going until we run out of numbers in V. Because V is our thingy that's where all the numbers are. And then you know, I can actually shout out by just saying let matrix equal that. Yeah, a round of numbers in matrix. So long as I have as long as our Matrix has numbers in it keep going. All right. What do we do while it has numbers on it? We're going to say like we store the first thing that's gonna be our top row, restore the first sub sub vector. All right. Then we remove the first sub vector. We pop it off and then we rotate our matrix rotate matrix. That's it. That's the whole algorithm doesn't mean it's gonna translate 1 to 1 to rest. But it basically should the gist of it. No, I'll just go ahead and say wow the length of our matrix on the length of our matrix. So while matrix dot length Yeah, Greater than zero. So as long as they have stuff in it, what do we want to do? I'm gonna store the first sub vector. So we'll say you know, we need to have a new vector where we're gonna store everything. That's the one we're gonna return. So we'll say I'll say let snail ified, which is gonna be the same type of this other stuff vector by 32's equal a new vector. And since we're gonna be pushing to this one this is going to go ahead and be mutable. And in fact matrix our new matrix is gonna be mutable as well because we're gonna be deleting stuff from it. Right? Alright. So we will say store it. Okay. So I will say snail ified Extil Matrix zero. So we're gonna extend this array by adding all this stuff on the first row. You have to pass a reference to that. That's why that's why it's mad if you're wondering why there's a little squiggly red line right there because I'm a bad programmer but not anymore because we fixed it now. We're good. Alright what do we do next? So we stored that then we remove it. I'm gonna use the drain feature to say that drain allows us to just keep sort of like python slice notation. We just keep one and after. So same Matrix equals matrix patron. And I'm mad that I'm doing something. Oh because it's not becoming a drain object so we collect it back into back into a vector. And the reason that works is that matrix is already a type of vector so it knows what to collect it as. And then we rotate the matrix. So make a function called rotate vic. And what are we gonna rotate? That'll be our matrix many cynical in there. Like we were talking about earlier and that's it. We'll just return our fixed vector. We will return Snail ified. That's the actual algorithm. But it's not that simple because we still have to find a way to actually rotate it. So let's see how we're doing on this video. Okay well we're 9 12 in. So let me save this. Do you have access to it in your editor. I'll go ahead and write the what did you call that and see back in the day where you have the function but then you have like the function prototype or whatever it was called. Go ahead and write like a little outline just showing you what types of this function is gonna have so that you can try it on your own and we'll be ready for the next video. So alright, rotate back. And by the way, what we really can do here is right, a right a trait on vectors that would be a lot colder cause then we could say, you know like matrix dot rotate, how cool would that be? But for now we'll just create a function. So we will take a vector. I'm gonna go ahead and call it V. It's gonna be whatever type matrix is. So that's a vector of I 30 two's and reality, this should be a generic right? We should be able to rotate any vector. It really doesn't matter what the types are. We're just gonna be pushing them in no matter what they are. So yeah, like why even worry about that. But for now we'll just have it be the vector we're actually using like we could be using a lot I guess all I'm saying is we could be using a lot of really advanced rust functionality to make this very clean and elegant and we're just keeping it simple for now. So yeah, and this is going to return something, gonna return that, it's gonna return the same types just rotated. And it's mad because it's not returning anything. So just to make it happy, we'll go ahead and return protector of unsigned 32 bit integers. Yo It's mad because mismatched types, it wants a vector and it got a vector. So why is it bad Is expected I. 32. All right, because this is a vector of vectors. Alright. Yeah. There we go. And borrow of moved value Matrix. Right. We borrowed after move here. Which is not implement the copy tree type, borrowed after move. Uh Well, that's it's definitely a problem. Let's see That's greater than zero. We could probably that's definitely not the right solution. Let's see. So, I guess that's saying that we're passing it. Oh right, right, right, right, right. We have to pass obviously we're gonna have to Oh no, my battery power is just another sign that I'm taking up too much of your time, but it's okay. So it's saying is that here I pass ownership of matrix to this rotate back function but I needed to pass a reference to Avec and now I'm gonna do that, we can still use Matrix. Otherwise this function would be the owner of matrix and it would now be responsible for freeing up its memory. So we're gonna say is no one's gonna give you a reference to it, you can free up the reference and we will still be the ones who will worry about freeing this memory after it goes out of scope. There you go. We just have to figure out how to rotate a vector. We have the actual algorithm for our simplification, and we're just gonna worry about how we actually are going to rotate this, and we will see how to do that in the next video. Just coming right up. Thank you a lot for your time and goodbye.
134 Views 0 Likes 0 Comments

A codewars 4 kyu...IN RUST?!?! Can we do it? Absolutely!

Comment
Leave a comment (supports markdown format)