Reversing Strings (in C) and Divergent Thinking

hey everybody welcome back let's talk more about strings this video is really a follow-on to my previous video which was a beginner video about strings in C if you missed that one I put a link in the description I ended that last video with a homework assignment a challenge to write a function in C that takes a string as an argument and reverses it basically flips it around so that the first bites are at the end and the last bites are at the beginning basically you're just reversing the text and I encouraged you to try to find more than one way to do this so how did it go how many ways did you find to do it were you able to get it done so why did I do it why did I even bother it's because I wanted to talk with you about a topic that I think is vitally important if you want to become a great programmer a great engineer or just all-around a smart person and that topic is divergent thinking so a lot of the students that I teach seem laser-focused trying to figure out what the right answer is they're so focused on what is the right answer dr. suber what's the right way to do this what's the best way to implement this data structure this thing this algorithm whatever what's the best way to solve this problem but in this field that can be problematic because there is rarely just one way to solve a problem there's always a lot of different ways to solve a problem and the right one for you depends a lot on your situation and what you care about right now it may change from project to project and that's the point divergent thinking is thinking that diverges it takes you down multiple paths it's basically forcing yourself to think about different ways to solve the same problem different ways to get to answers to the same question and this is really important for programmers and application designers and system designers because real life isn't a multiple-choice exam there's not always going to be a right answer and life doesn't present you with all the different options you have to be able to find the options figure out what they are and then be able to figure out based on what you care about right now you've got to be able to see the right option for you and so the ability to look at a problem and see all the options that are available to you that's going to be critical in helping you make better decisions so let's get into the code and let's see how this plays out as promised I wrote a function in C that reverses a string I'm curious how many ways you came up with solve this problem I found eight and I included a nine that a students mitad to me thanks Julian or Julian or how I have no idea how to pronounce your name thanks for sending me your code I think it highlighted just some interesting variation into the process and so I included it and I could have come up with even more options but well time and I think this is enough to get the point across so first of all I want to talk about some of the options that we have available I didn't really specify exactly what your function needed to look like so it could look like this it could just take a string return nothing and reverse the whole string in place meaning that it changes the original string into a reverse version of itself this is a destructive reverse it basically destroys the original string and all you have is the result so writing it this way implies that I trust whoever calls this function to have null terminated the string and to have allocated enough memory for that string I could also pass in a length explicitly now I can use the length instead of looking for a null character so that can be useful in some cases but I may also not want my original string to be destroyed so I could also pass in a new array that will hold the reverse string when the function is done so that'll leave my original just fine or another option is I could use malloc to allocate the new copy and then return that copy and if you do it this way your original array will be preserved as well but remember that you need to free the memory when you're done with it unless of course you like memory leaks and you're okay with that and these copying versions could take a length argument or not depending on whether that's helpful to you or whether you just like extra arguments okay so let's start out with implementation number zero this is the first one that came to my mind I find the length of the string then I go from position zero to position length divided by two and at each position I swap the character at that position with the mirror position on the other side note that I use a temporary variable here to save one of the characters otherwise one of those characters is going to get destroyed during the swap and I don't need to worry about the null terminating character in this case because I'm not changing the length of the string so I'm just going to leave it where it is and we'll be fine now you may also be wondering about even and odd lengths my length divided by two actually takes care of this for me because if my length is even say six then it will go from zero to two and every character will be swapped and if my length is an odd number say seven well now length divided by two is 3.5 but we're dealing with integers so it's just three so we still go from zero to two and swap those but the middle character doesn't get swapped which is exactly how we want it so it works out nicely so this example is fairly straightforward and it's easy to see what's going on and it works now the next candidate is here for comic relief and to make a point I call it reverse zero a because it is functionally the same as the first one it's just passed through a code office cater but it still works so why would anyone do that well maybe I'm trying to make it more difficult for someone to tell what the code is doing maybe I'm trying to hide my logic so people don't steal my algorithm or steal my idea now the bad news is that this only makes it a little harder to figure out but it is a little harder so maybe it's useful in certain circumstances our next real candidate is similar to the first the algorithm is the same but it tries to make the inside of the for loop simpler by adding an extra variable J now variable I starts at the beginning J starts at the last character and they move together swapping as we go so the same idea we're still swapping we're just have two variables and we're moving in towards the center the loop terminates when they meet or cross in the middle and now the upside of this one is that the inside of the loop is simpler the downside is the loop itself the loop conditions the initializers and the incrementation here at the end is more complicated in fact some of you may be so used to seeing four loops always look the same way like this that this one might be a bit scary but it's really not that bad though it's just initializing two variables it still has one loop condition and it increments and decrements the two variables at the end and I'm not really sure which one of these is better or worse and that's not the point of this video the point is divergent thinking so for now we're just going to keep them both around our next candidate was submitted by Julian or maybe usually an I'm not sure how to pronounce it but thanks it is a bit similar to the last one the two variable for loop that is and this one also works just fine but it's different in that it doesn't change the original string it copies the characters in reverse order from s1 to s2 it uses two variables one at the end one at the start and the for loop goes the entire length of the string rather than only going half way and it copies instead of swapping also note because we are copying from one array to the other that we can't forget the null character at the end like we have in some of the previous examples with number three we're back to reversing strings in place and this one's for all you pointer lovers out there oh yeah two star-crossed pointers one was the original string you know it's already pointing to the start the string the other we pointed to the last character and then it's time to get close so close we permit one we decrement one until now all that pointer action might make some of you uncomfortable if it's not your thing that's totally cool but some of you that love pointers that might be a good option and 3a down here is just the for-loop version for those who prefer a little for loop to a while loop I'm not here to judge you do you my friends moving on to number four now number four is here for all of you who are saying well these options are different but they're not that different so let's change things up a bit and do it with recursion okay so we're still reversing in place but I'm gonna pass in the length argument because it's gonna help me with my recursive calls now some of you haven't seen recursion before that's okay the idea is simple it's a little mind-bending at times just give it time it'll be okay the main idea is that we have a function that's going to call itself one or more times in order to solve a problem and this is a good solution for those of you that don't like loops if loops just aren't your thing maybe recursion is so what we're gonna do is first check to see if the length is zero or one if it is then there's nothing to do the strings already reversed so returned so for all other cases we know we have at least two elements in our string so I'm just going to swap those two elements the outside elements just like we have in our other functions and then I'm going to call this function reverse four on the inside part of the string and that inside string will have two fewer characters so we'll decrement the length by two and then the process starts all over again we check to see if the length is zero or one it isn't so we swap the outside characters and call reverse four on the inside rest of the string and now it is only length one so we know we're done and we return now depending on how comfortable you are with recursion right now you're somewhere between ooh that's nice and it's okay let it marinade play around with a little bit I'll revisit recursion in some future videos don't worry you'll get it figured out moving on to number five this one is straightforward it just returns a new string we allocate it with malloc and then I go through the array from start to end copying the mirror position into the new array we make sure a null terminate it and return the pointer just make sure that you free it later and that is my biggest reservation with this style where we allocate inside the function and then rely on freeing to happen outside the function it's just really easy for people to forget or just not really understand the rules of the game they didn't allocate it so they don't feel any responsibility for it but otherwise it's perfectly fine it will work moving on to number six number six is a hybrid it's a solution for those of you who don't want to harm the original string but you already have a perfectly good in place reverse function like reverse three so you simply malloc a new string copy the original over and then call reverse three or any of our other in place reverse functions and return the new reverse string so surely at this point you're thinking we've exhausted all of our options I guess I could change the order take all the four loops that go front to back and go back to front or things like that but that's not really a meaningful change and so I'm not gonna take the time to do that but I do want to show you one whacky version and that is reverse seven now this is the reverse function that you pull out when you're at a programming theme party and it's your turn to entertain the crowd because really this is probably not one that you would ever really want to use in practice intuitively what this version does is just pick a random character in the front half of the string if it and it's mirror character haven't been put into position yet then it swaps them and puts them in position then it picks another random character and does this all over again until it has put the right number of characters into position so specifically we get the length of the string we allocate space for the new string then we set all the characters in the new string to zero that's very important because that's going to help us see when a character hasn't been reversed yet then we get the number of characters that we need to swamp and then each time through the loop we first get a random index between zero and length divided by two minus one then we check to see if that character in the result is still zero meaning that we haven't swamped it yet and if it is then we swap it and we decrement our left to swap counter and we keep doing that over and over again until left to swap reaches zero and then of course we know terminate the array and at that point we're done now this code works but it is slow maybe some of you could see that already but think about it especially as my string gets longer because as you get close to the end of the process you're going to find that most of the characters are already in position and you're gonna waste a lot of time trying to randomly pick the only one you have left to swamp but it's fun and while you probably would never actually use this technique for reversing strings in an actual program your writing don't rule out randomization in your projects because randomization can sometimes provide some fairly simple solutions or approximate solutions to some otherwise really challenging problems so it's a good tool to keep in your toolbox okay so just to make sure that all this works let's go down to main and actually run all these different versions we have for the in place examples will just reverse new string and print it out and we'll do this again and again and we'll print it out and okay for reverse - we need another string so we'll reverse it print it out and now let's keep going with more in place reversals okay now for the ones that return a copy print them out then free the pointer and we'll do that for reverse six and reverse seven okay that should be it we compile it and we run it and it works lots of reversed and reverse reverse strings which are just the original and now you're all experts on reversing strings but more importantly I hope this helps you look differently at the code you write I hope there from now on when you're faced with a problem that you see many paths that you actually take the time to think about all the different ways that you could solve this problem rather than just focusing on finding one single solution if you can learn to think this way it will make you a better problem solver and a better programmer so thanks everyone for watching keep an eye out for my next video if you don't want to miss it be sure to subscribe and click the bell if that's the kind of thing you're into until then I'll see you later [Music]

Channel: Jacob Sorber

Views: 26,902

Keywords:

Id: dcBcgPGIMpo

Length: 13min 15sec (795 seconds)

Published: Fri Jun 21 2019