SPELLER IS EASY (IN PYTHON) - CS50 on Twitch, EP. 1

Key Takeaways

hey everyone this is cs50 zone David Malin and Colton Ogden so this is a new approach for us we of course have lecturers once a week here in Cambridge and of course we've done a number of live streams over the past few years but we thought we chart we thought we'd try something new with our twitch channel here Colton is a big fan of twitch is quite the gamer himself in the programmer of games and we thought we'd use this as a more interactive time it's actually chat with some folks in the twitch chat room and actually walk through some code in real time live coding to get into the more depth on some of the things that we might otherwise talk about in class and then ultimately take people's questions and steer the conversation in any direction folks out there would like to go yeah so very flexible format everybody who's in feel free definitely to chime innovate chat if you aren't following the cs50.tv account that believe there's a ten minute waiting period so definitely follow us so you can talk to us but I see we do have one person Sreenivas Anka says hello so hello shouldn't be so nice to see you here hello nice to meet you as well so yeah I guess well we can take a transition here to your laptop or we have your code there maduk yep so we're actually sitting here in Cambridge Massachusetts on Harvard's campus with a magical green screen behind us and so we're superimposing ourselves the two humans which is why you see this nice glow where both of us today I wish I had a shot of just the green sky now all I have is this so that's green but you see it is gray perhaps and this allows us to superimpose ourselves over the code like you've seen in some other channels so that we can actually talk in the greater proximity do it for lecture that itself we do we do this in Sanders theater but the green screens way behind and we use some camera magic to actually capture it across the the room as well yeah all right any more hellos to tend to not just yet no just a srinivasan we have 10 viewers currently active so all right wonderful well so glad to have you here in class it's like a cs50 section here on campus what we thought we'd do today is our first trial of this is take a closer look at one of the topics we look at in cs50 those of you have been following along for some time and they're pretty much through half of the course or so might have implemented your own spell checker at some point and for those unfamiliar roughly halfway during cs50 semester here on campus and online we challenge students to their own spellchecker which is a piece of software that looks over all the words you've typed out in a file and tells you often with red underlines which words you've misspelled they aren't in a dictionary and that's where the CS comes in that dictionary is just a really big list of words hopefully alphabetical alphabetically sorted and it's a non-trivial problem to actually look up every one of the words in your file against every word in the dictionary if you recall from our discussion of asymptotic notation that's like an N squared problem if n is the number of words in each just simplify a bit and that can actually take quite a bit of CPU cycles and memory and so one of the challenges in cs50 is do that efficiently minimize your use of memory minimize your use of CPU time so to speak and just write the fastest spell checker possible now what language of course do we tend to write this in though oh we started see yeah and early for the course yeah and that's great because C is super low-level it's super fast it really takes that Vantage of the hardware but what are some of the prices you'd say you pay by writing stuff in C programmer time number number one you know what obviously looking for memory leaks and you know seg faults and all those sorts of things that trip up a lot of programmers yeah those of you programmed in C maybe C++ have dealt with pointers memory addresses segmentation faults buffer overflow exploits and the like all of that comes into play and so why don't we start there why don't we actually take a look at what it is you have had to do or if you're following along with cs50 for the first time might have to do if you tackle this particular problem down the road and then let's actually do it in a much more friendly environment of Python but consider what prices we actually pay for doing that so we have up here behind us Dictionary dot h this is the so-called header file that we give to cs50 students and in this header file do we define for functions do you want to summarize what functions they have to implement oh actually I've handed I don't remember I have to look at the source code oh that's cool we are right here if you'd like ok well we clearly prepped here it looks like check it check is one of them isn't it load size now fortunately the files completely commented so we can kind of follow along here so these four functions characterize if you will the API for spell checker API is just application programming interface and while this might sometimes mean some web-based service or third party you're using it can also refer to local software that you yourself are writing or that someone else has started writing and you now need to finish and indeed the challenge for this problem is to flesh out that API and write the actual implementation thereof all right so in order of operation not alphabetically load is the first function that students on in this class have to write this is a function that takes as input in C it looks like cons char star dictionary and how should folks think about what that means a constant meaning that it can't be mutated so whatever data that they pass into this function should be not tampered with by the function okay a char star is just a sequence of chars or a pointer to a char there's gonna be you know any number of chars after that but it's a string effectively yep I agree yeah text data that's gonna become their dictionary and then the name of this parameter of course is just dictionary and so the idea is that this is the name or the path to the file containing all of those words that I mentioned earlier that represent the actual dictionary in lodz purpose in life per the common to top it is to load dictionary into memory and it's supposed to return a bool true if successful else false for those unfamiliar we are using standard bool h which is a header file that you can include in c that actually gives you access to two definitions of true and false as 1 and 0 respectively effectively so after load is called once implemented then it's the function called check that's supposed to get it called again and again and again for every word in the file you're actually spell checking so it's that one that's got to be especially performance super fast super minimal memory usage hopefully if you're really trying to optimize those through things what does it appear that this takes as input too if you want to talk about load function or sorry the check function so it looks like the same thing so char star meaning a pointer to a char so a variable length string or sequence of chars and in word so it's basically going to be any size word and we're gonna basically check for the per the sort of string header representing the signature whether the word is actually in the dictionary so when you check our dictionary for this word and see whether it's actually inside that dictionary that data structure yeah and so strictly speaking you don't have to use constant either of these definitions this is just a nice mechanism for really protecting yourself from yourself lest you accidentally try changing word or try changing dictionary the fact that you defensively or whoever wrote this file defensively put Const there means you just won't accidentally screw up change the value and introduce some bug that could be very easily avoidable by making it read only as Const effectively does so lastly there's two other functions in this file per the comments those are size and unload unload is meant to do the opposite of load so whatever work we end up doing in load is supposed to be undone freed up and unload and then size is supposed to just return the number of words in the dictionary now maybe that's a linear operation you just iterate over whatever your data structure is counting up every one of the words and return that value or if you're smart about it you could probably just keep like an int or long around and just as you're loading words keep track of how many words there are and then just spit out in constant time that's that same value so in C this is a pain in the neck to actually implement this thing you can implement it as a big array a linked list to give you some dynamism and growth you can implement it as a hash table which is often implemented as an array with multiple linked lists or you can implement it using a try and even fancier data structure that just consumes lots of memory but theoretically is constant time in its operation at least asymptotically so we're not going to do that though in C indeed that's one of the challenges in cs50 itself and one of the great moments in a course like this is when you actually change context and you switch from C a very low-level language to something like Python which is higher level so to speak that has lots more abstractions lots more features lots more capabilities built into the language itself you can whittle down at 10 20 30 40 our project into truly just minutes if not seconds once you're actually super learning than the language should we dive into some actual live Koecher before we do srini of a song has a question yeah so past by value can be used instead of Const short answer no you are already technically passing in the dictionary by its value but the catch is that the value you're passing in is its address and insofar as passing in an address allows you to dereference that address and go to that low dress in memory means that it's potentially vulnerable to being changed and so we're declaring constitute for the very reason that we're technically passing by reference here or by value but that value is an address and so this is why we have this defense mechanism in place if we were instead passing in a specific char or an int or float or any other primitive type that doesn't involve memory addresses then yes pass by value avoids this because the worst you can do is change a copy of the print of the arguments but in this case by definition we are passing in a string which is indeed a char star or address of a character or sequence of characters so we can't it's not as easily said as passing by value the values here what's what a risky I guess the equivalent would be maybe like duplicating the data structure in the function but then that would be like horribly inefficient for something massive yeah big dictionary file yeah you could totally copy the whole dictionary but even then you have this window of a few lines of code where you could still screw up and accidentally change things just by the nature of making a mistake if that's true really good question so keep the questions common if you have any as we move ahead but let me go ahead and open up a file let's call it the dictionary dot pi and actually implement this API but using Python and therefore python syntax and the equivalent and then if we have time we can take a look at a new speller dot pi which is a porting or translation of speller dot c which we haven't looked at yet but cs50 students do in the class that actually implements the spell checker itself but the real intellectual work and the data structure stuff really takes place in Dictionary dot C or today Dictionary dot Pi so let me go ahead and proactively save this as dictionary dot pi so we get our syntax highlighting and let me propose that we just have placeholders initially for those four functions so again we can't use dictionary dot pi with speller dot C and so this is just a porting of the whole project to another language so in Python you declare functions using slightly different since Python you don't specify a return type and you don't specify the types of your arguments to functions but you do specify their names and recall that one of those names was check it does take an argument in this case which we'll call word just as we did in C but you have to define the function which in Python uses the DEF keyword and then of course instead of currently braces in Python if you're familiar you instead indent and instead of using those curly braces often with colons implying that here comes some indentation and I'm not ready to do this yet so I'm just gonna say pass sort of literally passing on implementing the function but we'll come back to that but that will get the IDE here we're using cs50 IDE or cloud9 to just stop yelling at us with some some red marks and quite welcome for the pass by value question there so let's go ahead and do two others let's go ahead and define load and load takes in a dictionary here - I'm just gonna pass for now and actually implementing it I'm gonna go ahead and implement size which takes no arguments so you just specify open paren close paren you don't need to say void as you do in C let's pass on implementing that for now and then unload which frankly we're probably not gonna need it all in Python because memory is managed for you you might have to allocate it albeit implicitly but you're not gonna have to worry about managing it I can see so there's the API poured it to Python and again you'll notice no return types and no parameter types pythons loosely typed it still has type strings and incent and floats and other values but it doesn't actually require that the programmer like us actually specify those things all right so what do you think we should do to think about this we have to implement a spa dictionary for spell checker a dictionary by definition is a whole bunch of words that are passed in in a big text file how would you go about thinking about how to begin solving this in Python I think the first thing I would want to do is understand the dictionary file so that we can parse it and we can load it into the dictionary okay all right well so if we want to parse the dictionary file it's it's nice that we're actually in Python because it's even easier in Python than in C where you have to really think about how long your lines are and how many bytes of memory you might need so let me go ahead and go up there let's implement load first or at least the beginning of it and if I want to open a file in Python it's actually as simple as saying open the file name dictionary being the file and then you can specify do you want to read the file or maybe read and write the file and so just as in C with the F open function if you recall you can say quote unquote read which just says a Python open the file called dictionary or whatever that value actually is and then read it for me but this is going to return essentially a file handle to the file so to speak kind of like a reference there too so I want to keep that around and I'm just gonna declare a variable on the Left called file but I could call it anything I want F or whatever and assign that the return value of open notice I don't have to specify the type of file it's going to return it's gonna store some kind of file object but I don't need to worry about that and now in C you would probably proceed to iterate using like F read or F scan F or F get s or F get C or any number of other file I overeating functions but in Python there's these higher level abstractions where if you know that text file just contains word after word after word you can just say that as say as much in Python by literally saying you know what for each line in the file go ahead and do this and so just as I kind of rattled that off early so you can you type it in Python and it's a lot more English like if you will in that sense now I don't really know what we want to do with this word yet so let's just say for now store word in some data structure because that's kind of an interesting design question to come back to but once we're done doing that we're just going to go ahead and call closed on the file or rather I'm using C syntax already we're gonna call file closed and here's where python is also object-oriented the file reference that came back itself has functions or methods built into it and if you look at the documentation one of those is closed so file dot closed actually closes that specific file and then after that let's assume for the sake of discussion that everything went well so I'm just gonna go ahead and return true here in this case so in returning true just signifies everything is good I do seem to have an error here but that's only because I haven't actually done something in this for loop so let me also just say pass on implementing that for now and that error should go away as well there's a there's an even cleaner way to do what you've done with the file right the lay using what's called a context manager all right how we do that lay like the with the with keyword so if you have the instead of having NASA needing to open a file handler with file well you still need a file handler but instead of having basically the doc closed you can kind of enclose all of this sort of all these operations that require this file within its own indented block and you're using the with key word and this is essentially just what's called a context manager manages the context of this file and the operations on it so basically it saves you a line of code yeah so perfect for great point to make this is more pythonic if you will here on line seven what I've done a perk Alton suggestion is actually say with the opening of this file in read only mode call the return value file and then notice how I've indented by tabbing everything below that line eight nine and ten at the moment inside of that indentation thereby implying that this file variable is useful within every intended line underneath and what i Scholten remarks this this notion of context is important because what's gonna happen ultimately is that python is gonna close this file for me by the time we hit line 11 so I just don't need to think about it so this is a very common approach just to kind of clean up your thinking focus on the work you actually care about which is opening file and getting at it it's less interesting intellectually to close the file and indeed much better if the language itself deals with that overhead for you plenty of people forget to close their files and see as well indeed in fact one of the most common sources of memory leaks where you allocate Ram and forget to give it back is indeed because you forgot to close some data structure like a file we have a few people in the chat we have Trevon aider says greetings from Germany greetings from America I meet Microsoft in the SS greetings from India nice to meet you on it as well from Cambridge and then a Srinivasan as another says comment and line 9 is stores W comment and line 9 store word in some data structure ah yeah so entire line instead of one yes it is so tech well it depends what I do with this so I can save myself here Ivan actually written this line of code so I can claim it's gonna do whatever I want but yes if we do no other action here in the commented line on line 9 yeah we'd be storing the whole line but if we assume as we're allowed to in cs50 see version of the pset that the dictionary contains words one word per line then with a bit of fanciness can I actually extract from that line the one and only one word that's on it get rid of maybe any leading or trailing whitespace or messiness and just load that word and indeed that's the to do on line nine that remains for context do we do you happen to have the dictionary file available for us to look at yeah absolutely if you want to take a look at the dictionary let's go into another folder and in that folder we have a dictionaries folder and I'm gonna go ahead and open up a large dictionary here which has got like 140 thousand words and even the idea here we're struggling for a moment to open it and here we go so here are the lines in the file a is the shortest English word I can think of that starts with a apparently AAA and a s had meaning to sorry mark so we've gone ahead how we so we've lowercased all the words in this case in advance we have and so that's kind of an assumption we're making if we didn't want to make that assumption that's fine we can deal with it in code but yes that would have been one of the setups in the C version of the problem which is that yeah it's all lowercase okay for so when is e sorry for 7f sorry greetings from Italy hello for that one s m1 join the fourth side we have a SB venner greetings from London nice hello see you nice form the Canberra chair shame it's not sorry if i'm jump hey no that's okay that's totally fine it's good I think it was a good thing to catch it yeah no that's fine call me on anything that we're missing here so if you run to see all hundred and forty thousand words we can scroll here for quite a while you can see there's a lot of a words in English and this is why it's actually important at the end of the day to think about how much memory you're using how many CPU cycles you're using because at the end of the day this is gonna add up and indeed I've not I've gotten bored with scrolling we haven't even gotten through all of the a words and there's a lot of words there and that's what we have a small and a large I'm guessing so that we have a dichotomy we can performance measure between the small but our algorithm operating on the small database versus the last database you do not want to try to debug a problem in your code with 140,000 inputs coming at you can you even imagine setting like a breakpoint in a debugger and walking through that so we have small which just has two words cat and Caterpillar so this is actually fun fact so this is kind of curious that we have these two words why might you in writing some test code use two words like this as opposed to cat and dog I'm thinking from the perspective of the try because they both gonna operate on the same nodes in the tree hmm and then caterpillar caterpillar is kind of a superset of cat in that sense that's my first inclination ya know and that was the motivation because you want to try to think when testing your code of potential corner cases and it's definitely potentially worrisome if two of your words are so similar but different so whether you're using a try or anything else just choosing those kinds of corner cases one letter words 2 letter words substrings of other words it's really good defensive mindset to go into debugging with Oh fun fact - it was just a few years ago that I learned how to spell caterpillar because it occurred to me since childhood I could pronounce this word I knew what a caterpillar was and then the one time off-the-cuff I said oh why don't we spellcheck caterpillar I had a google the darn word in the front of class do I did you think it was both I cat a cat a pillar cat I don't know you take for granted for 30 years it's a weird it's a weird word I yeah there's other words like that I was embarrassed any of us on says sorry I didn't realize that dictionary file contains only one word no need to apologise we didn't tell you so you wouldn't have known no big deal all right so let's go back to the Python API that we've been in the midst of implementing here and see if we can't flesh this out a little more so I feel like the big to do is really this we've kind of cut some corners and we've only thought about we have a special guest here today we've only really thought about what to do logically but where are we gonna tuck this data away so how do you think about how should anyone think about actually storing these words would you say well in cs50 I think normally we use what's called a hash table so some way for us to essentially map a word to some storage some storage bucket somewhere using a function that's optimized for even distribution if I were you don't have all of the same words and like basically one long linked list but I think we should show people maybe how to implement a hash table in Python oh yeah you want to do a hash table in Python Yeah right so if you want to declare a hash table for instance a variable called hash table and Python alright you could technically just do that oh wow and then done what would you like me to do next okay so now I'm done kind of but this actually does invite some interesting design questions so this is indeed the definition of a hash table or in Python it's called a dictionary or dict where you map keys to values and that's the fundamental definition of a hash table it's a mapping of keys to values but cat equals one dog equals two for example it could be yeah but you don't have to use numeric indices like that like it really suffice is in a dictionary to say yes or no the word is in it so you could probably just say cat true dog true caterpillar true but even that feels a little redundant and so when it comes to designing a data structure like this hash table might not necessarily me be what you want you can actually use bunches of others so you could actually get away with just using a list in Python which is a dynamically resizable array or vector if you're coming from the C++ world that's nice too because will automatically grow to fill the data and you're also not unnecessarily storing true true true true or one two three four you're just storing the words themselves the keys we're finished in terms of memory so memory yeah I mean you're saving some number of bytes however Python implements true and false it's got to be nonzero presumably but would you have caution against using just a list would you say I would for access purposes because if you want to find out whether something's in a list it's gonna be a no of in operation yeah so a no event Big O of n the linear time operation because if that word like is zu and it's all the way at the end of your list if it's alphabetize then you know you've got to search all 140,000 words just looking for the darn word that you care about we had a couple questions also terminator are you doing piece at five in Python yes yes essentially yeah fun fact he said five just became piece at four this year so stay tuned for cs50 x 2019 and you want to read off SP banners the last question sure SP vendors ask so what is the past reserved keyword do in Python I've not really seen that before Steve so it's actually just kind of literally a pass when you want to just have a placeholder line that does nothing as I'm doing here sort of pedagogically you can just say pass that's a bit of a contrived use case it really means when you need a line of code but you don't want to take any action there you can use pass so just to pull up a separate file here let me just create food a pie for the sake of discussion this would not be the best design but it's one possible use of this if you wanted to say something like if X is greater than Y but in that case you don't want to do anything about it you could just say pass now I say this is bad design because frankly if you just want to check a condition and then not do something and instead do something only if the opposite is true like do this you can just flip the logic frankly and you can instead say if X is less than or equal to Y then do this and you can avoid the pass altogether but I've been in the habit on some applications of actually using in the context of exceptions so we don't tend to talk about these in cs50 but you might in higher-level class or in your own professional work often it's the case in Python that you want to try to do something inside of which you might have some lines of code except something bad might happen and so you might say accept exception as e for exception but if you want to do something with the exception you might not want sometimes to do something with the exception but you do want to catch it and then ignore it because you know more than the computer and you know that sometimes an exception might happen but if you decide not a big deal you can literally just say pass effectively ignoring the exception but still handling it so the whole program doesn't abord so I would say that's a more compelling use of pass that's not pedagogical but it is functional essentially because in Python if you try to do like like a function definition without a body it'll just give you a compiler error yeah yeah indeed so if you actually want to have the equivalent of like abstract methods inside of a class that you then override in a child's class you might just say pass because you don't want the function to have to do anything by default but it does need to be well-defined grammatically in the language really good question keep them coming hope that helps Steve all right so if we turn our attention back to Dictionary Pi I would propose we could take this one step further Python has a whole buffet if you will of data structures not just lists not just hash tables but it also has one that we introduced in class albeit briefly it actually has what are called sets you might not have thought about these recently but mathematically a set is a collection of numbers taken typically but a key detail is that the set does not contain duplicates which is great because your dictionary probably shouldn't contain duplicates the word is either a word or it's not and so a set is kind of nice because it maintains that property but more importantly if you read the documentation for Python set is more performant than lists it will give you an approximation of constant time access so it's probably implemented with a hash table underneath the diction eath the hood much like a dictionary but it does have this property where you can just think about membership therein not an association of keys with values kind of like the hash table but rather than even to store that true every time what you said probably amounts to some nonzero amount of bytes mm-hmm we just get all of that sort of for free but the same functionality it's a membership check yeah indeed and so a set is what you would often call an abstract data type but you don't necessarily know or have to care how it's implemented underneath the hood all you care about is its properties the fact that you can add to it remove from it and get an approximately constant time access to it that's what you care about but underneath the hood it probably is implemented with some kind of tree or hash table or anything that's not for us to worry about in a language like Python so let's call this actually what it is this is our dictionary of words so let's just say we've got a variable called words and it's initialized to be just an empty set containing no words initially until we're ready to put them into the file create a question from an j on j we see i'm j on the facebook group all the time I love Andre nice to see you here on Twitch we're checking access the line bounding box collisions be a good use case for past since you are typically testing whether four cases are not true in that case you still would check all four conditions so I don't think you would because you want to make sure all of them aren't true because that's just part of how that algorithm works so yeah I don't think paths and that particular instance would be appropriate yeah you can still flip the logic even if syntactically it starts to get a little messy or sloppy generally in any language having just empty code blocks where you take no action or explicitly say pass it usually suggests that the better design is possible I usually see it as I can on implemented sort of thing yeah to do it's like in the real world at least in the US and in English you sometimes have silly business or legal documents that say this page intentionally left blank I mean everyone kind of rolls their eyes at that because well this is kind of silly and I think this same idea there you don't want to just have placeholders for code you want to get the logic right from the get-go cool good question yeah nice to see you here on another venue all right so this the line nine still kind of remains store line in some data structure so honestly this is pretty straightforward in Python if I have this data structure called words and I just want to go ahead and add to it I can literally just add the line to the to the set now this isn't quite right and you noticed this earlier I think one of our who is that sugandha I think we need a yes noted earlier that doesn't contain a full line and it does but if we know that the dictionary contains one word per line but every line probably ends with a backslash N or crlf or the like we're one I'm gonna we're gonna want to strip that off and if when you read they cs50 specification you'll know that indeed it ends with backslash n or a new line or a line feed so what's nice in Python is you can actually strip this off pretty nicely you can say reverse strip or strip a specific character or characters from the end of the string hence a write strip from the end and that's actually going to strip off one or more new lines from the end of the string thereby giving us effectively the whole word finite final clean and that's it now even though Colton and I have been talking for quite a few minutes here I mean at the end of the day we wrote what like six or so lines of code to get done much of a cs50 problem namely the load function here so let's do it let's take a bit of a breather and let's go ahead and just implement size this function according to the problem statement is return the number of words and the in the file or in the dictionary file which is now loaded into memory presumably how would you go about thinking about this well one approach might be to use some sort of loop to basically go over our data structure and say for in Python for example for something in our collection for word in words and then just increment the counter that you've declared sighs so size plus equals one and then you have just returned to society okay all right so that's pretty straightforward it feels like if words is a data structure it probably supports the notion of length could we Whittle this down into something more pythonic yeah most most I would say most abstract Davis has probably do have some sort of length function or length field on them so I believe you can just call le n on set the length function which is a function that works on pretty much any core Python data structure and I should just give you the number of words should be stored internally indeed this is a nice generalization it's a little inconsistent across Python that you don't call words Lang but this is essentially an API in Python Lang or length is a function that works across various different data structures and data types and can't even work across your own customized ones that you yourself invent so long is your data structure implements itself sort of a magical method called Lang itself which is built into the object this Len function will call that length method thereby making sure that you can get the length of any data structure in a standard way in this case so actually just letting the data structure the set itself tell us what's your length it could probably now be done in constant time instead of linear and again that's the goal we'll speed everything up today well let's do a spoiler here with unload in Python even though in C you would have to allocate all this memory maybe it's on the stack or the heap or wherever once you've decided that you have to actually free that memory in Python mmm there's really no work to be done here so I'm just gonna go ahead and boldly say done like turn true yeah what's the mechanism called that sort of does that for us so it would be called garbage collection and duck wasn't sure that's what you were fishing for that I'd be called garbage collection which is kind of a cool way of describing a process that happens behind the scenes whenever the program isn't really doing much else or has a breather or just needs to collect garbage it will free up any memory that you seem not to actually that you are known not to be using anymore so that it can be used for other purposes in your program or somewhere else yeah we just like Java and Ruby and such also include typically interpreted languages and some compiled languages have this feature gotcha C definitely does not have this feature no no and that's what makes it all the more painful sometimes you use and syringe you got it thank you for the summer there to everyone few people have some long long user names here today so we're kind of left with just one function that we passed on earlier literally that the check so check recall is going to be the function that we're gonna call again and again and again the spell check any of the words that are actually passed in so let's consider how we can go implement this up top we know that the data structure in question is called words it's said and it turns out it's pretty easy to just ask the question is this string in this set you can literally just say something like if word in sets then go ahead and return true or if that's not the case with your colons here you can go ahead and return false but in Python anytime you find yourself in the habit of very verbose ly saying if this then return true else if that return false you can probably Whittle it down even more cleanly and indeed you can actually do this in C but we tend not to do it in the earliest weeks of cs50 I could actually just be a little more elegant here and just say what return word in words and that in itself is a boolean expression that will return true or false I might want to do one enhancement here and you would only know this from reading the problem statement even though the dictionary that we were given with one hundred and forty thousand words is sorted and all lowercase is in the problem statement the file your spell checking might not be because that could be any file that some human typed out so we should probably if we're looking for words in in lowercase dictionary we should probably force every word that we're being passed to lowercase just to make sure that we're comparing apples and apples so to speak good point yeah so any questions then on how we've tackled this believe it or not in 17 lines or fewer can you implement a spell checker in Python that conforms to cs50 zone API which takes many more lines and undoubtedly many many many more hours if not tiers in C to implement sure maybe a couple minutes for questions well in the meantime when was the first year that we had this pset you remember I do remember in cs50 here at Harvard 2007 and AI has yet to replace spell checkers so we haven't had to replace it yet is that did you come up with this from scratch or was this an in hair I did come up with this from scratch I believe it's while ago now and in fact I think I first wrote this piece set or problem sets even years prior let's roll back to like 2002 or 2003 I was teaching at Tufts University another school up the road in their computer science department and was making all new homework assignments for that class and I think unless I'm rewriting history here I think I did write that from scratch way back line and it's evolved a little bit over time and in fact it started off as a C++ problem set if this was true that or I'm completely making all of this up and in 2007 did I first write this pset was it because you're having issues with words spell checker no I mean we had Microsoft Word in my day you can actually just ask the software to do this the aliens got a couple kappas for us that's a hazy alien good to see you thank you very much tripping a turtle of your course and so teaching oh thank you all pset 5 and see I'm sorry we showed you answer in Python otherwise this is easier yeah Dictionary dot H the file we started with is actually given to students so that's not even a spoiler there so fun fact when I was a kid Microsoft Word came on for floppy disks oh man and that had all the features I actually needed or cared about back in what like 1995 give or take Microsoft Word 5.1 a how much smaller was the dictionary back then we had as many words I think in English although you hear about more and more stupid words coming out every year that are apparently immortalized in the dictionary I can't remember any from this year I don't know you have the floppy from from word in your office do it and 125 buncher oh maybe Excel you know you have the Excel floppy disk Oh possibly yeah it was cool actually a few couple of years ago now cs50 video team went on the road to visit our friends at Microsoft so I probably should have said things about we're just now and they have a wonderful archive and we got to explore some of the boxes and shelves of old stuff and they just had all of the oldest software right there on floppy disk we have some fun photos of picking up like entire boxes of really really heavy products but the stupid thing is the heavy products was not like the actual software it was the damn like instruction manuals they used to come with like dictionary sized user manuals that we that we've held up above our head I don't think I can find the photo on on such quick demand yeah that's okay maybe can we do that alright let's so um cs50 zone dan coffey here's this jesting that we go to our own photo website here so let's see if we can't dig up a little memory from yesteryear if I go here I think we can probably search shree knees asking is that a 3.5 inch oh hey look at that Hey look at that search that's a good dictionary we've got it here Wow so this is me looking very surprised at how heavy Microsoft Office was a long time ago there's a manual for the full software this is mostly the manuals so if let's enhance here and yeah there were a few floppy disks or maybe CDs by then in there but those are mostly manuals that's not even the biggest one here we go this is visual C++ oh that's the compiler wow that's that's me a long time ago - that's a compiler in the manuals for it slightly creepily - okay is that photo but also Microsoft apparently what are those called Teletubbies Teletubbies Micro Teletubbies used to be powered by Microsoft they don't even I have no idea yeah Windows 3.1 was distributed on 8 3.5 inch floppies says Andre I believe it hundred percent indeed indeed oh and it's apropos here off camera is our friend dan coffey who's right there on camera with that so and then of course it wouldn't be cs50 without our friend Natasha tor neski nacho who's at Microsoft with other colleagues of hers well and there she is cs50 proud having taken cs50 here so you remember / Serena's comment whether it was three point five or five point five o'clock i've let's see for office you know i don't in my day the version we had but on macs was three point five but i don't think max ever had five points in a quarter inch discs but windows might have certainly if there was windows me Dawson windows 3.1 at onward might have yeah I remember having windows 95 machine with floppies on it but I don't it's been a long time yeah hey we're all sounding really old right now so if there's any of you kids tuning in wondering what the hell this channel just became I think we should have prefaced it with a picture what a floppy disk is that is true so here let's do that what's a floppy disk floppy there they come in different shapes and forms they're mostly died out now I used to have really good presentation in cs50 where you would have people rip open a floppy so have those in storage by the way we do still have some floppy disks in stock yeah fun fact it was uh it actually got really expensive to do because the price of storage and media just went down and down and down and down and so for a few pennies we could give thousand students in the room their own floppy disk and then tear it apart in class but then once nobody started using them you could only get them on like eBay not even staples and so then it's like $1 each and that makes for a really expensive demo I remember we booked order those who were like thousands of them yeah so that's a this is a somewhat hard floppy disk inside is the actual floppy material and then as CERN II was referring we had five and a quarter inch disks and even bigger ones back in the day small medium and large if you will and I kind of started off life I think with the middle disks there but Oh fun fact - if we had enhanced this these five and a quarter inch floppy disks which were indeed flexible came with a little divot out of the corner which was help to help align them so you would know which is on the left and which is on the right so you don't put the disk in upside down but the catch is that the materials inside the disk are actually perfectly symmetric and so if you actually take a scissors or a special $5 device you could snip a hole in the floppy disk exactly symmetrically on the other side thereby tricking the floppy disk drive to write bits on to the other side of the actual floppy disk inside now I'm sure if I had any notion of electrical engineering at the time I would know that this just creates interference and bad things but to a kid trying to you know double his storage space it doubled my storage space so all of us used to do this and make your floppy disks double-sided that's a TI oh for me I didn't know you could do that yeah well it probably wasn't recommended the better practice would be just buy more floppy disks but that what that's what we did back in the day yeah that's a good piece of history yeah so any questions from the audience there anything we can pluck off either on C Python or anything in between if you guys have any sort of small exercises or you know examples you want us to implement in Python list know do we see said potentially resize as well as that one that you have I can print it for you we do every size but I think we'd also have the speller which we can go from I found another spell yeah we could do that all right sorry interested we should let people decide what they want my desk has a few of those impulse items do folks prefer us to do resize or to take a closer look at speller and see maybe get a chance for some feedback I do think speller and see is nice cause we can literally do it side by side you see a housing lines no that's a good point all right so let's do that let's start on that yeah all right all right so let's go ahead and let me unenhanced close a couple of our distractions there and let me go into my same folder as before let me go ahead and open up speller dot C which is indeed the version of this program that students are given so I'm afraid - this won't help you out with a terminator with pset 5 since you two are given this distribution code but what's nice about the IDE here is we can split our windows and actually do some side-by-side coding and essentially comport or translate C from Python from left to right here so can also do this magic and now we're out of the scene oh nice we can even get rid of it for you and make nice alright so here we go let me go ahead and create a new file will call this speller dot pi and essentially we're gonna try to recreate this file over at the right hand side so we'll do some simple some more sophisticated things for a moment you can keep watching terminator we won't show you dictionary dot C that's where the real magic is actually if you want me to do you want me to maybe make a smaller put us in the middle so we can still see yeah can we yeah let's do that unenhanced us here we go whoo goodbye let's do oh there we go there we go oh we could do little Mac versus PC like C versus Python game yeah I think I should get on the other side then yeah this is kind of backwards but the keyboard sit that's ok we'll all look this way you look this way and we'll focus on our own code all right so one thing to note first of all in Python there's there's different ways to write comments and so for multi-line comments like this how would you go about writing them in your file in seiren oh and python python has a cool syntax I mean one way you could do it is just preface every single line with the hash mark okay so they can do every single line like it's very tedious yeah for sure Python has another way you can do it using either triple full quotes or single quotes uh-huh yeah which will allow you to do the same thing essentially as this except on the left but you don't need to have the star on each line you can just write strings literally as you want yeah so a problem set five influenced a spell checker and then down here we can close that thought using double or single quote so long as we're actually consistent across the two and now now those are our comments and you can see it's nicely highlighted it's drug color coded a little differently just because the ID treats comments and seeing Python a little differently the same exact idea I think she had the right idea he had the triple hash mark but just the off on just the quote being the the key there indeed definitely want to use the single or the double quotes there and then be consistent throughout so on the left in see we had a whole bunch of header files that we included one of which was our own dictionary H and then a bunch of which were some lower-level things really used for instrumentation no problem at all and the comparables that we'll need are a little different so there's not necessarily a one-to-one mapping left to right and in fact rather than do these preemptively we'll come back to some of our imports and let's just trip over the libraries we need once we actua