Programming Problem #5 - String Compression/Encryption (Intermediate)

Key Takeaways

hey guys and welcome back to another programming uh problem and solution video so in this video we're going to be going into probably I would say A medium level program or problem uh so if you're a beginner feel free to listen to the problem and see if you have any idea how you would solve it but I will note that it is a little bit more advanced it's not a crazy difficult solution but just to understand the problem and the process to go through to do it is you know a little bit more complicated than obviously what we did in the last video which was just very basic um programming problems so with that being said let's get started uh so actually quickly sorry before we get started all this stuff is going to be up on my website so like the actual problem and then the code and the solution so if you just click the link in the description it should bring you to the website I don't know if I'm going to do this for all of them but for ones where I have like longer Solutions uh and the problem something like this like not on a different website uh I'll just put on my website so you guys can go on there and look at it okay so essentially uh you guys can read through this problem if you want I mean feel free to pause the video video and attempt it it's not super difficult but what we need to do is given some input like this where the first uh line or the first input actually stands for the amount of uh inputs we're about to get so like we'll get four and that stands for how many lines is about to come so we know how to grab those we have to decompress this into kind of like an encoded form and the way we're going to do that or at least the problem outlines that we should do that is we should look for a series of consecutive characters and then instead of writing the those characters like doing like three plus signs we're going to do the number three and then the character so you can see down here we get three and then plus sign so it stands for there there was three plus signs and then we get three and then equal signs because there was three equal signs and then we get four and then exclamation points so four exclamation points so essentially you get an integer character integer character integer character and obviously for Strings like this where there might only be um there might be no consecutive characters you're still going to get one 3 1 period like so it stands for 1 1 1 4 1 1 4 5 now I would actually challenge you guys if you come up with the solution to try to do it the other way around so given this like this sequence turn it into this so if you guys think this is too easy do this take this sequence and turn it into this sequence okay so take your output and like do the inverse essentially of this okay so that's the problem and I want you guys to think about how you would go about solving this and I'm going to bring up my solution now and I'll go through how I solved it and just prove to you that it's working so my solution I did in two ways uh the first way is so the input right actually let me bring up this tab again uh make it a bit smaller the input's this and the way it wants you to read the input in is like using literally input um so it says like you're going to use input you're going to say how many lines are coming and then you're going to Loop through that many lines get the input store it in a list and then essentially solve that problem for each of the different inputs right and then give some kind of output uh for me I'm just put all my input into a text file just so when I uh what do you call it keep testing this I don't have to uh keep like typing in the input again I recommend you guys do that as well so if I go to python YouTube programming problems you can see the input that they had there I just put in a text file so that I can just read it in um constantly when I run the program rather than having to type it in but I mean you guys could type it in as well and I'll show you how each of them works we'll leave that open too so I'm going to open this text file right which was right here we're going to read in all of these lines now what I'm going to do is I'm going to say I actually need to change this one second uh like that I'm going to say four line in lines so essentially for each line so each line of input uh we're going to solve the problem right because we're going to have to solve the problem well four times now since I'm reading it in from a text file I just have to remove this back sln character because you can't actually see it but when you write a text file like this at the end of each line there's little back sln that stands for go to the next line but when you read that into python you'll see that so you got to get rid of it um okay so we get rid of back sln and then what I'm doing is I'm defining three variables that I'm going to use essentially to will solve the problem here and these are going to reset every time we do a new line and solve like the problem again right so I'm saying new string which is going to be essentially my output I'm saying last which is just the first character in the string and I'm saying count equals 1 and essentially the principle behind my solution is what I'm going to do is I'm going to keep track of the last character in the string I'm going to see if the current character I'm looping through is equal to that if it is I'm going to add one to the count so we're going to say we've seen two plus signs and then as soon as I reach a character where it's different from the last character what I'm going to do is I'm going to add the previous character I'm going to add sorry the amount so like whatever my count variable is at plus the previous character to that string that's going to be our output and then I'm going to reset the count and reset the last character to be like uh to be one and then whatever the next character is and then we're going to continue that process until eventually we get to a point where there's no more consecutive uh what do you call it characters at all and we're done looping through the string so I'll show you the solutions working and then I'll draw out exactly how it works so you guys get an idea and we'll go through like line by line what it does so uh let me run this and you can see we get 3 plus uh 3 + three and then so like three pluses three equal signs four exclamation points six sevens six periods 12 T's one bracket 2 a right so you can see and that obviously lines up with uh with this as well and you can see that I don't think I made any mistakes um in my solution and to give you guys an idea of how long this took me to make I programmed this solution in probably about like 5 minutes so I mean you guys can gauge how well or how good you're doing based on that I guess I don't know so anyways that uh is kind of the solution let's go through it line by line and then let's draw out a few examples and run through what the solution actually does for that so uh what we're doing obviously is for every line in line we're going to set the these variables already talked about that and this is really where the magic happens in this for Loop this is the main solution so I'm just going to do this so I can see it a bit easier um so essentially for every character in our line not including the first one and that's what it says in this comment here too now why do we not look at the first one well we've already looked at the first one here we've said we're getting the first character and we're going to say the count is one because well you're never going to have a count of zero because you're always going to have at least one character right like you can't have zero pluses otherwise you wouldn't have a plus so we say line zero count one which means we're getting the first character and we're saying its count is currently one we've seen that character one time now what we do is we go in this for Loop and we're going to Loop through every character past past that first character so we're going to loop from the second to the end what we're going to do is we're going to say if the current character so the second character in this case is equal to the first character or you know the last character then we're going to add one to count which means we've seen essentially two consecutive uh characters so they're the same thing and then that's all we're going to do for that Loop now in the instance where they're not the same so we see two different characters we're going to do exactly the process I talked about which is we're going to add to our output string which is new string here the count so the current count whatever it was because right now let's say we only seen this character once it's not equal to the next character well we're going to say well the current count was one so we're going to put one we're going to add a space cuz that's what the output requires and then we're going to add the last character which which was well whatever that character was so let's say it was an H we're going to do one space H and then add another space which is just going to be so next time we do we add to the string it's like spaced out correctly then we're going to reset the count and we're going to say last is equal to the current character because it's not a consecutive character um we need to change it because now we're looking to see if the if this is going to be consecutive and when I draw it out it'll be more clear then at the end here this Line's really important because essentially uh when we get to the very end if we had a series of consecutive characters right so let's say we get to the very last thing and the last character in our string was equal to the previous one we're not going to add anything to the string we're simply just going to exit the loop because well we added one to count so we have to make sure that we add the last element which is going to be whatever the count was and then whatever that sequence of character characters were to the string and then for each of these lines we're just going to print out the output and then it looks like it's stacking the output right and this is fairly efficient cuz this runs in uh what do you call it linear time because we're only doing one Loop so this actually run quite quickly or uh yeah well it runs linear time for the solution but obviously the amount of input lines is going to matter as well um so yeah so let's uh I mean like I'll run it one more time and show this and let's take one of these uh inputs so maybe we'll take like this plus plus equals equals and let's run through exactly how it works with like a little drawing uh example just so you guys get an idea okay so I actually decided I'm just going to do do a shorter input that I'll write up here um just to make this example a lot easier we'll do like that okay so this is going to be our input pretend this came in as a string we've read it in and we're going to do the solution now on this input so essentially what we need to do is well we're going to follow the steps from our program we're going to follow that that for Loop that we were doing so the first thing we're going to do is we're going to take this character and we're going to say last okay is equal to and in this case it's going to be a plus sign right I know that kind of looks like an X but you you get my point okay um so we'll say that all right so we're saying last is equal to X and we say count so we'll just say count as C in here okay make it better say Cals 1 so the last character is X or or plus even I'm reading it correctly and C equals 1 so what we'll do now that that's what we've set up we haven't even started looping yet so now we're going to Loop through this part of the string okay th so plus equals equals slash we're not going to look at this first element because well we already looked at it here and we already counted it so now what we're going to do is we're to look at the next element which in this case is like the first index or another plus sign so what we do is we say okay so what is this is it equal to last yes it is so what I'm going to do is I'm not going to change last and all I'm going to do is I'm going to add one to count so count is two and last is still plus sign because the last character is there so now what we've done is we've essentially let me change colors here to maybe make it a little nicer we've already looked at this and we've already looked at this and now we have last is plus and count is two so what we do now is we look at this equal sign we say well is equal sign equal to last no it's not so what's the procedure there well the procedure there is to add to our new string which will'll just says here okay this is like our new output string so we say output okay is that then what we're going to do is we're going to add to it the last character or the count and then the last character so we're going to say out output string so this right is going to be equal to plus 2 plus a space which is that plus the plus sign so now our output string if I erase all of this madness here uh is going to be changed and I'm just going to write it up here and continue to write it if I can erase all this so now our output string is going to look like two space plus and this is currently our output string okay so let's keep going so what we do after this is we have to change last and we have to change count so we're going to say last okay you're no longer plus sign you are equal sign cuz that's our last character right and count well what are you equal to you're equal to one because we just found this and we've counted it one time okay so let's repeat the procedure so we've we've already looked at that we looked at these first three now it's time to look at this equal sign all right so let's look at this equal sign is it equal to last well yes it is so what's our procedure just add one to count that's all we have to do so now Count's equal to two all right we've looked at this one now next element let's look at the slash is slash equal to last no it's not so what do we do well we got follow the procedure so we're going to add to our output string we're going to say well the count was two and our last element was equal sign so we're going to add this essentially um to this so our new output string is going to look like 2+ 2 equal sign okay this is our new output string I just put it in a squir squiggly thing so you can see it all right so now uh We've looked at slash right and we've looked at all these so we're actually out of the loop but look our um let me just clear this and I'll rewrite it so it's easier 2 + 2 equal sign remember in our input was Plus+ equal equal slash but where's our slash we don't have slash but how many slashes are there's one slash so that's why and if I exit this quickly we have this line here so that we account for the last um character in our string because if we don't have that line then we end up with well the input that you guys are seeing right now the output that you guys are seeing right now just this so we add that last line which means we're going to get the current count which is going to be equal to one we're going to get last which will be equal to slash cuz we set it there right and we're going to say one and Slash and that would be our output and that's how we solve the problem so that essentially is this problem um I believe the name of it actually was let's see here cold compress pretty decent problem um I say Yeah medium intermediate level nothing too crazy obviously there's a lot more difficult problems let me know what you guys thought of this in terms of a difficulty level and if you want to see something much more difficult than this in the future um and yeah with that being said make sure you are subscribed to the channel you like the video and I will see you again in another one [Music]