Problem: Mispellings[1]
tl;dr
Implement a program that spell-checks a file, per the below.
$ ./speller texts/austinpowers.txt
MISSPELLED WORDS
[...]
Bigglesworth
[...]
Virtucon
[...]
friggin'
[...]
trippy
[...]
WORDS MISSPELLED:
WORDS IN DICTIONARY:
WORDS IN TEXT:
TIME IN load:
TIME IN check:
TIME IN size:
TIME IN unload:
TIME IN TOTAL:
Academic Honesty
This course’s philosophy on academic honesty is best stated as "be reasonable." The course recognizes that interactions with classmates and others can facilitate mastery of the course’s material. However, there remains a line between enlisting the help of another and submitting the work of another. This policy characterizes both sides of that line.
The essence of all work that you submit to this course must be your own. Collaboration on problems is not permitted (unless explicitly stated otherwise) except to the extent that you may ask classmates and others for help so long as that help does not reduce to another doing your work for you. Generally speaking, when asking for help, you may show your code or writing to others, but you may not view theirs, so long as you and they respect this policy’s other constraints. Collaboration on quizzes and tests is not permitted at all. Collaboration on the final project is permitted to the extent prescribed by its specification.
Below are rules of thumb that (inexhaustively) characterize acts that the course considers reasonable and not reasonable. If in doubt as to whether some act is reasonable, do not commit it until you solicit and receive approval in writing from your instructor. If a violation of this policy is suspected and confirmed, your instructor reserves the right to impose local sanctions on top of any disciplinary outcome that may include an unsatisfactory or failing grade for work submitted or for the course itself.
Reasonable
-
Communicating with classmates about problems in English (or some other spoken language).
-
Discussing the course’s material with others in order to understand it better.
-
Helping a classmate identify a bug in his or her code, such as by viewing, compiling, or running his or her code, even on your own computer.
-
Incorporating snippets of code that you find online or elsewhere into your own code, provided that those snippets are not themselves solutions to assigned problems and that you cite the snippets' origins.
-
Reviewing past years' quizzes, tests, and solutions thereto.
-
Sending or showing code that you’ve written to someone, possibly a classmate, so that he or she might help you identify and fix a bug.
-
Sharing snippets of your own solutions to problems online so that others might help you identify and fix a bug or other issue.
-
Turning to the web or elsewhere for instruction beyond the course’s own, for references, and for solutions to technical difficulties, but not for outright solutions to problems or your own final project.
-
Whiteboarding solutions to problems with others using diagrams or pseudocode but not actual code.
-
Working with (and even paying) a tutor to help you with the course, provided the tutor does not do your work for you.
Not Reasonable
-
Accessing a solution to some problem prior to (re-)submitting your own.
-
Asking a classmate to see his or her solution to a problem before (re-)submitting your own.
-
Decompiling, deobfuscating, or disassembling the staff’s solutions to problems.
-
Failing to cite (as with comments) the origins of code, writing, or techniques that you discover outside of the course’s own lessons and integrate into your own work, even while respecting this policy’s other constraints.
-
Giving or showing to a classmate a solution to a problem when it is he or she, and not you, who is struggling to solve it.
-
Looking at another individual’s work during a quiz or test.
-
Paying or offering to pay an individual for work that you may submit as (part of) your own.
-
Providing or making available solutions to problems to individuals who might take this course in the future.
-
Searching for, soliciting, or viewing a quiz’s questions or answers prior to taking the quiz.
-
Searching for or soliciting outright solutions to problems online or elsewhere.
-
Splitting a problem’s workload with another individual and combining your work (unless explicitly authorized by the problem itself).
-
Submitting (after possibly modifying) the work of another individual beyond allowed snippets.
-
Submitting the same or similar work to this course that you have submitted or will submit to another.
-
Using resources during a quiz beyond those explicitly allowed in the quiz’s instructions.
-
Viewing another’s solution to a problem and basing your own solution on it.
Assessment
Your work on this problem set will be evaluated along three axes primarily.
- Correctness
-
To what extent is your code consistent with our specifications and free of bugs?
- Design
-
To what extent is your code written well (i.e., clearly, efficiently, elegantly, and/or logically)?
- Style
-
To what extent is your code readable (i.e., commented and indented with variables aptly named)?
To obtain a passing grade in this course, all students must ordinarily submit all assigned problems unless granted an exception in writing by the instructor.
Getting Ready
Let’s brush up on a few recent topics before diving in. First, join Jackson and Lauren for tours of singly linked lists and hash tables.
Then, brush up your valgrind
knowledge with Nate!
If still desiring more practice with linked lists or hash tables, Doug is here to help!
Getting Started
Log into CS50 IDE and, in a terminal window, execute
update50
to ensure that your workspace is up-to-date! Next, navigate to the location in your IDE where you are writing code for unit A and execute the below:
wget http://docs.cs50.net/2018/ap/problems/mispellings/mispellings.zip
If you unzip the file and navigate inside the directory, you’ll see that it contains quite a few things!
Makefile dictionaries/ dictionary.c dictionary.h keys/ questions.txt speller.c texts/
More on these in a bit!
Understanding
Theoretically, on input of size n, an algorithm with a running time of n is asymptotically equivalent, in terms of O, to an algorithm with a running time of 2n. In the real world, though, the fact of the matter is that the latter feels twice as slow as the former.
The challenge ahead of you is to implement the fastest spell checker you can! By "fastest," though, we’re talking actual, real-world, noticeable time—none of that asymptotic stuff this time.
In speller.c
, we’ve put together a program that’s designed to spell-check a file after loading a dictionary of words from disk into memory. Unfortunately, we didn’t quite get around to implementing the loading part. Or the checking part. Both (and a bit more) we leave to you! But first, a tour.
dictionary.{c,h}
Open up dictionary.h
. Declared in that file are four functions; take note of what each should do. Now open up dictionary.c
. Notice that we’ve implemented those four functions, but only barely, just enough for this code to compile. Your job, ultimately, is to re-implement those functions as cleverly as possible so that this spell checker works as advertised. And fast!
Makefile
Recall that make
automates compilation of your code so that you don’t have to execute clang
manually along with a whole bunch of switches. However, as your programs grow in size, make won’t be able to infer from context anymore how to compile your code; you’ll need to start telling make how to compile your program, particularly when they involve multiple source (i.e., .c
) files, as in the case of this problem. And so we’ll utilize a Makefile
, a configuration file that tells make exactly what to do. Open up Makefile
, and let’s take a tour of its lines.
The line below defines a variable called CC
that specifies that make should use clang
for compiling.
CC = clang
The line below defines a variable called CFLAGS
that specifies, in turn, that clang
should use some flags, most of which should look familiar.
CFLAGS = -ggdb3 -O0 -Qunused-arguments -std=c11 -Wall -Werror
The line below defines a variable called EXE
, the value of which will be our program’s name.
EXE = speller
The line below defines a variable called HDRS
, the value of which is a space-separated list of header files used by speller
.
HDRS = dictionary.h
The line below defines a variable called LIBS
, the value of which is should be a space-separated list of libraries, each of which should be prefixed with -l
. (Recall our use of -lcs50
earlier this term.) Odds are you won’t need to enumerate any libraries for this problem, but we’ve included the variable just in case.
LIBS =
The line below defines a variable called SRCS
, the value of which is a space-separated list of C files that will collectively implement speller
.
SRCS = speller.c dictionary.c
The line below defines a variable called OBJS
, the value of which is identical to that of SRCS
, except that each file’s extension is not .c
but .o
.
OBJS = $(SRCS:.c=.o)
The lines below define a "target" using these variables that tells make how to compile speller
.
$(EXE): $(OBJS) Makefile
$(CC) $(CFLAGS) -o $@ $(OBJS) $(LIBS)
The line below specifies that our .o
files all "depend on" dictionary.h
and Makefile
so that changes to either induce recompilation of the former when you run make
.
$(OBJS): $(HDRS) Makefile
Finally, the lines below define another target for cleaning up this problem’s directory.
clean:
rm -f core $(EXE) *.o
Know that you’re welcome to modify this Makefile
as you see fit. In fact, you should if you create any .c
or .h
files of your own. But be sure not to change any tabs (i.e., \t
) to spaces, since make
expects the former to be present below each target.
The net effect of all these lines is that you can compile speller
with a single command, even though it comprises quite a few files:
make speller
Even better, you can also just execute:
make
And if you ever want to delete speller plus any core
or .o
files, you can do so with a single command:
make clean
In general, though, anytime you want to compile your code for this problem, it should suffice to run:
make
speller.c
Okay, next open up speller.c
and spend some time looking over the code and comments therein. You won’t need to change anything in this file, but you should understand it nonetheless. Notice how, by way of getrusage
, we’ll be "benchmarking" (i.e., timing the execution of) your implementations of check
, load
, size
, and unload
. Also notice how we go about passing check
, word by word, the contents of some file to be spell-checked. Ultimately, we report each misspelling in that file along with a bunch of statistics.
Notice, incidentally, that we have defined the usage of speller
to be
Usage: speller [dictionary] text
where dictionary
is assumed to be a file containing a list of lowercase words, one per line, and text
is a file to be spell-checked. As the brackets suggest, provision of dictionary
is optional; if this argument is omitted, speller
will use dictionaries/large
by default. In other words, running
./speller text
will be equivalent to running
./speller dictionaries/large text
where text
is the file you wish to spell-check. Suffice it to say, the former is easier to type! (Of course, speller
will not be able to load any dictionaries until you implement load
in dictionary.c
! Until then, you’ll see Could not load.)
Within the default dictionary, mind you, are 143,091 words, all of which must be loaded into memory! In fact, take a peek at that file to get a sense of its structure and size. Notice that every word in that file appears in lowercase (even, for simplicity, proper nouns and acronyms). From top to bottom, the file is sorted lexicographically, with only one word per line (each of which ends with \n
). No word is longer than 45 characters, and no word appears more than once. During development, you may find it helpful to provide speller
with a dictionary
of your own that contains far fewer words, lest you struggle to debug an otherwise enormous structure in memory. In dictionaries/small
is one such dictionary. To use it, execute
./speller dictionaries/small text
where text
is the file you wish to spell-check. Don’t move on until you’re sure you understand how speller
itself works!
Odds are, you didn’t spend enough time looking over speller.c
. Go back one square and walk yourself through it again!
texts/
So that you can test your implementation of speller
, we’ve also provided you with a whole bunch of texts, among them the script from Austin Powers: International Man of Mystery, a sound bite from Ralph Wiggum, three million bytes from Tolstoy, some excerpts from Machiavelli and Shakespeare, the entirety of the King James V Bible, and more. So that you know what to expect, open and skim each of those files, all of which are in a directory called texts
within your mispellings
directory.
Now, as you should know from having read over speller.c
carefully, the output of speller
, if executed with, say,
./speller texts/austinpowers.txt
will eventually resemble the below. For now, try executing the staff’s solution (using the default dictionary) with the below.
~cs50/unitA/speller texts/austinpowers.txt
Below’s some of the output you’ll see. For amusement’s sake, we’ve excerpted some of our favorite "mispellings." And lest we spoil the fun, we’ve omitted our own statistics for now.
MISSPELLED WORDS
[...]
Bigglesworth
[...]
Virtucon
[...]
friggin'
[...]
trippy
[...]
WORDS MISSPELLED:
WORDS IN DICTIONARY:
WORDS IN TEXT:
TIME IN load:
TIME IN check:
TIME IN size:
TIME IN unload:
TIME IN TOTAL:
TIME IN load
represents the number of seconds that speller
spends executing your implementation of load
. TIME IN check
represents the number of seconds that speller
spends, in total, executing your implementation of check
. TIME IN size
represents the number of seconds that speller
spends executing your implementation of size
. TIME IN unload
represents the number of seconds that speller
spends executing your implementation of unload
. TIME IN TOTAL
is the sum of those four measurements.
Note that these times may vary somewhat across executions of speller
, depending on what else CS50 IDE is doing, even if you don’t change your code.
Incidentally, to be clear, by "misspelled" we simply mean that some word is not in the dictionary
provided.
Questions
Open up questions.txt
and answer each of the following questions in one or more sentences.
-
What is pneumonoultramicroscopicsilicovolcanoconiosis?
-
According to its man page, what does
getrusage
do? -
Per that same man page, how many members are in a variable of type
struct rusage
? -
Why do you think we pass
before
andafter
by reference (instead of by value) tocalculate
, even though we’re not changing their contents? -
Explain as precisely as possible, in a paragraph or more, how
main
goes about reading words from a file. In other words, convince us that you indeed understand how that function’sfor
loop works. -
Why do you think we used
fgetc
to read each word’s characters one at a time rather than usefscanf
with a format string like"%s"
to read whole words at a time? Put another way, what problems might arise by relying onfscanf
alone? -
Why do you think we declared the parameters for
check
andload
asconst
(which means "constant")?
Specification
Alright, the challenge now before you is to implement load
, check
, size
, and unload
as efficiently as possible, in such a way that TIME IN load
, TIME IN check
, TIME IN size
, and TIME IN unload
are all minimized. To be sure, it’s not obvious what it even means to be minimized, inasmuch as these benchmarks will certainly vary as you feed speller
different values for dictionary
and for text
. But therein lies the challenge, if not the fun, of this problem. This problem is your chance to design. Although we invite you to minimize space, your ultimate enemy is time. But before you dive in, some specifications from us.
-
You may not alter
speller.c
. -
You may alter
dictionary.c
(and, in fact, must in order to complete the implementations ofload
,check
,size
, andunload
), but you may not alter the declarations ofload
,check
,size
, orunload
. -
You may alter
dictionary.h
, but you may not alter the declarations ofload
,check
,size
, orunload
. -
You may alter
Makefile
. -
You may add functions to
dictionary.c
or to files of your own creation so long as all of your code compiles viamake
. -
Your implementation of
check
must be case-insensitive. In other words, iffoo
is in dictionary, thencheck
should return true given any capitalization thereof; none offoo
,foO
,fOo
,fOO
,fOO
,Foo
,FoO
,FOo
, andFOO
should be considered misspelled. -
Capitalization aside, your implementation of
check
should only returntrue
for words actually indictionary
. Beware hard-coding common words (e.g.,the
), lest we pass your implementation adictionary
without those same words. Moreover, the only possessives allowed are those actually indictionary
. In other words, even iffoo
is indictionary
,check
should returnfalse
givenfoo’s
iffoo’s
is not also indictionary
. -
You may assume that
check
will only be passed strings with alphabetical characters and/or apostrophes. -
You may assume that any
dictionary
passed to your program will be structured exactly like ours, lexicographically sorted from top to bottom with one word per line, each of which ends with\n
. You may also assume thatdictionary
will contain at least one word, that no word will be longer thanLENGTH
(a constant defined indictionary.h
) characters, that no word will appear more than once, and that each word will contain only lowercase alphabetical characters and possibly apostrophes. -
Your spell checker may only take
text
and, optionally,dictionary
as input. Although you might be inclined (particularly if among those more comfortable) to "pre-process" our default dictionary in order to derive an "ideal hash function" for it, you may not save the output of any such pre-processing to disk in order to load it back into memory on subsequent runs of your spell checker in order to gain an advantage. -
Your spell checker may not leak any memory.
-
You may search for (good) hash functions online, so long as you cite the origin of any hash function you integrate into your own code.
Alright, ready to go?
-
Implement
load
. -
Implement
check
. -
Implement
size
. -
Implement
unload
.
Hints
Be sure to free
in unload
any memory that you allocated in load
! Recall that valgrind
is your newest best friend. Know that valgrind
watches for leaks while your program is actually running, so be sure to provide command-line arguments if you want valgrind
to analyze speller
while you use a particular dictionary
and/or text, as in the below. Best to use a small text, though, else valgrind
could take quite a while to run.
valgrind --leak-check=full ./speller texts/ralph.txt
If you run valgrind
without specifying a text
for speller
, your implementations of load
and unload
won’t actually get called (and thus analyzed).
If unsure how to interpret the output of valgrind
, do just ask help50
for help:
help50 valgrind --leak-check=full ./speller texts/ralph.txt
Testing
How to check whether your program is outting the right misspelled words? Well, you’re welcome to consult the "answer keys" that are inside of the keys
directory that’s inside of your speller
directory. For instance, inside of keys/austinpowers.txt
are all of the words that your program should think are misspelled.
You could therefore run your program on some text in one window, as with the below.
./speller texts/austinpowers.txt
And you could then compare the windows visually side by side. That could get tedious quickly, though. So you might instead want to "redirect" your program’s output to a file (just like you may have done with generate
in Problem Set 3), as with the below.
./speller texts/austinpowers.txt > student.txt
~cs50/unitA/speller texts/austinpowers.txt > staff.txt
You can then compare both files side by side in the same window with a program like diff
, as with the below.
diff -y student.txt staff.txt
Alternatively, to save time, you could just compare your program’s output (assuming you redirected it to, e.g., student.txt
) against one of the answer keys without running the staff’s solution, as with the below.
diff -y student.txt keys/austinpowers.txt
If your program’s output matches the staff’s, diff
will output two columns that should be identical except for, perhaps, the running times at the bottom. If the columns differ, though, you’ll see a >
or |
where they differ. For instance, if you see
MISSPELLED WORDS MISSPELLED WORDS
FOTTAGE FOTTAGE
INT INT
> EVIL'S
s s
> EVIL'S
Farbissina Farbissina
that means your program (whose output is on the left) does not think that EVIL’s
is misspelled, even though the staff’s output (on the right) does, as is implied by the absence of EVIL’s
in the lefthand column and the presence of EVIL’s
in the righthand column.
Correctness
To test your code less manually (though still not exhaustively), you may also execute the below.
check50 cs50/problems/2018/ap/speller