Accustom you to reading someone else’s code.
Empower you with Makefiles.
Practice debugging your code with more advanced techniques.
Begin to implement a party favor.
Page 17 of http://www.howstuffworks.com/c.htm.
Chapters 20 and 23 of Absolute Beginner’s Guide to C.
Chapters 13, 15, and 18 of Programming in C.
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.
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.
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.
Your work on this problem set will be evaluated along four axes primarily.
To what extent does your code implement the features required by our specification?
To what extent is your code consistent with our specifications and free of bugs?
To what extent is your code written well (i.e., clearly, efficiently, elegantly, and/or logically)?
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.
Have a more in-depth look at debugging techniques from Dan. (Odds are these 23 minutes with Dan will save you hours over the course of the term, since GDB is a far better tool than
printf in many cases!)
Recall that, for almost all of Units 1 and 2, you started writing programs from scratch, creating your own
unit2 directories with
mkdir. For this problem, you’ll instead download some "distribution code" (otherwise known as a "distro"), written by us, and add your own lines of code to it. You’ll first need to read and understand our code, though, so this problem set is as much about learning to read someone else’s code as it is about writing your own!
Let’s get you started. Log into cs50.io and execute
within a terminal window to make sure your workspace is up-to-date. If you somehow closed your terminal window (and can’t find it!), make sure that Console is checked under the View menu, then click the green, circled plus (+) in CS50 IDE’s bottom half, then select New Terminal.
at your prompt to ensure that you’re inside of
unit3 (which is inside of
workspace which is inside of your home directory). Then execute
to download a ZIP of this problem’s distro into your workspace (with a command-line program called
wget). You should see a bunch of output followed by:
Confirm that you’ve indeed downloaded
fifteen.zip by executing
and then run
to unzip the file. If you then run
ls again, you should see that you have a newly unzipped directory called
fifteen as well. You can now delete the ZIP, with:
confirming your intent to delete that file, then proceed to execute
and you should see that the directory contains three files:
Makefile fifteen.c questions.txt
Off we go!
To kick things off, just
You shouldn’t have touched anything yet, so this program should compile with no trouble.
make automates compilation of your code so that you don’t have to execute
clang manually along with a whole bunch of switches. Notice, in fact, how
make just executed a pretty long command for you, per the tool’s output. 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. And so we’ll start relying on "Makefiles," configuration files that tell
make exactly what to do.
Go ahead and look at the file called
Makefile is essentially a list of rules that we wrote for you that tells
make how to build
fifteen.c for you. The relevant lines appear below.
fifteen: fifteen.c clang -ggdb3 -O0 -std=c11 -Wall -Werror -o fifteen fifteen.c -lcs50 -lm
The first line tells
make that the "target" called
fifteen should be built by invoking the second line’s command. Moreover, that first line tells
fifteen is dependent on
fifteen.c, the implication of which is that
make will only re-build
fifteen on subsequent runs if that file was modified since
make last built
fifteen. Neat time-saving trick, eh? In fact, go ahead and execute the command below again, assuming you haven’t modified
You should be informed that
fifteen is already up-to-date. Incidentally, know that the leading whitespace on that second line is not a sequence of spaces but, rather, a tab. Unfortunately,
make requires that commands be preceded by tabs, so be careful not to change them to spaces, else you may encounter strange errors! The
-Werror flag, recall, tells
clang to treat warnings (bad) as though they’re errors (worse) so that you’re forced (in a good, instructive way!) to fix them.
Let’s finish looking at that
Makefile. Notice the line below.
This target implies that you can build
fifteen simply by executing the below.
Even better, the below is equivalent (because
make builds a
Makefile's first target by default).
If only you could whittle this whole assignment down to a single command! Finally, notice these last lines in
clean: rm -f *.o a.out core fifteen log.txt
This target allows you to delete all files ending in
.o or called
core (more on that soon!),
log.txt simply by executing the command below.
Be careful not to add, say,
*.c to that last line in
Makefile! (Why?) Any line, incidentally, that begins with
# is just a comment. This Makefile is among the least complex we could possibly write, but soon enough the principles we’ve just covered will make (pun intended!) our programming lives much simpler.
The Game of Fifteen is a puzzle played on a square, two-dimensional board with numbered tiles that slide. The goal of this puzzle is to arrange the board’s tiles from smallest to largest, left to right, top to bottom, with an empty space in board’s bottom-right corner, as in the below.
Sliding any tile that borders the board’s empty space in that space constitutes a "move." Although the configuration above depicts a game already won, notice how the tile numbered 12 or the tile numbered 15 could be slid into the empty space. Tiles may not be moved diagonally, though, or forcibly removed from the board.
Although other configurations are possible, we shall assume that this game begins with the board’s tiles in reverse order, from largest to smallest, left to right, top to bottom, with an empty space in the board’s bottom-right corner. If, however, and only if the board contains an odd number of tiles (i.e., the height and width of the board are even), the positions of tiles numbered 1 and 2 must be swapped, as in the below. The puzzle is solvable from this configuration.
Okay, navigate your way to
~/workspace/unit3/fifteen, and take a look at
fifteen.c. Within this file is an entire framework for the Game of Fifteen. The challenge coming up for you is to complete this game’s implementation.
You’ve already compiled it, so now go ahead and run the game. (Can you figure out how?) Odds are you’ll want to run it in a larger terminal window than usual, which you can open clicking the green plus (+) next to one of your code tabs and clicking New Terminal. Alternatively, you can full-screen the terminal window toward the bottom of CS50 IDE’s UI (within the UI’s "console") by clicking the Maximize icon in the console’s top-right corner.
Anyhow, it appears that the game is at least partly functional. Granted, it’s not much of a game yet. But that’s where you come in!
You’ll notice, if you have a look at the distro, that our
fifteen.c file is woefully lacking in comments. As we said upfront, part of this assignment is beginning to read and understand code others have written for you, and so your first objective is to replace all of the eleven (numbered 00 through 10)
TODO comments you see scattered about
fifteen.c with actual comments that explain what is happening in the game.
Don’t treat this portion of the problem lightly, and hopefully the fact that we don’t provide comments here on some stuff that may not be immediately apparent to you at first glance is a good reminder of just how important it is to provide high-quality comments in your own code!
Read over the code and comments that you’ve just prepared in
fifteen.c and then answer the questions below in
questions.txt, which is a (nearly empty) text file that we included for you inside of the distro’s
fifteen directory. No worries if you’re not quite sure how
fflush work; we’ll simply be using those to automate some testing.
Besides 4 × 4 (which are Game of Fifteen’s dimensions), what other dimensions does the framework allow?
With what sort of data structure is the game’s board represented?
What function is called to greet the player at game’s start?
What functions do you apparently need to implement?
Alright, get to it. Implement this game!
Err… maybe not at all of it. In this problem, you only need to implement two of the functions:
draw. (We’ll leave
won alone for now.)
Any design decisions not explicitly prescribed herein (e.g., how much space you should leave between numbers when printing the board) are intentionally left to you. Presumably the board, when printed, should look something like the below, but we leave it to you to implement your own vision.
15 14 13 12 11 10 9 8 7 6 5 4 3 1 2 _
Incidentally, recall that the positions of tiles numbered 1 and 2 should only start off swapped (as they are in the 4 × 4 example above) if the board has an odd number of tiles (as does the 4 × 4 example above). If the board has an even number of tiles, those positions should not start off swapped. And so they do not in the 3 × 3 example below:
8 7 6 5 4 3 2 1 _
To test your implementation of
fifteen, you can certainly try playing it. (Know that you can force your program to quit by hitting ctrl-c.) But by the time you’ve completed this portion of the problem, there won’t be terribly much you’ll be able to actually play. After all, you’re only initializing and drawing the board here.
You’re welcome to write your own functions and even change the prototypes of functions we wrote. But we ask that you not alter the flow of logic in
main itself so that we can automate some tests of your program once submitted. If in doubt as to whether some design decision of yours might run counter these wishes, simply reach out to your teacher.
Here are some tips from Zamyla to get you started. First, for
And also for
If you’d like to play with the staff’s own implementation of the full
fifteen game, you may execute the below.
If you’d like to see an even fancier version, one so good that it can play itself, try out the below.
Instead of typing a number at the game’s prompt in the latter, type
GOD (named for the so-called "God Mode" implemented in many games of this sort, where the computer plays the game itself) instead. Neat, eh?
And if you’d like to check the correctness of your program officially with
check50, you may execute the below. Note that
check50 assumes that your board’s blank space is implemented in
0; if you’ve chosen some other value, best to change to
check50's sake. Also note that
check50 assumes that you’re indexing into
board a la
check50 1516.unit3.fifteen1 fifteen.c
fifteen1… it’s not a typo!
This was Problem 3-1.