Problem 3-2: Fifteen (Part 2)

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.

Your work on this problem set will be evaluated along four axes primarily.

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 year, since GDB is a far better tool than printf in many cases!)

Unlike any other problem you’ve worked on up through this point in the course, this problem has been split into multiple parts, which means that to complete it fully you need to carry your work from the previous problem to this one. Maybe that’s a good thing… perhaps you enjoyed working on Part 1 of the Game of Fifteen and can’t wait to conclude it here. But perhaps you didn’t do well on it, and dread the thought.

We don’t want the struggles you may have encountered in the first part of this problem compound and create even more trouble for you now. And to that end, any time you encounter a split problem like this in CS50 AP (or indeed any time prior work is necessary in a subsequent problem) you’ll always have the opportunity for a clean slate by using a partial staff solution to get you going.

Below are two options for getting started with this problem. The first option is for those who wish to start with the staff’s implementation of init and draw from Problem 3-1 already implemented for them. The second option is for those who wish to complete their own implementation of the Game of Fifteen, relying on their own solution to Problem 3-1 as their foundation. Only choose one of the below two options, though if you choose Option 2 you may still be interested in reading up on what your classmates who choose Option 1 are doing, particularly as it is an early look at how you might automate the creation of a single executable from multiple sources.

Then, after having chosen your option and followed all the steps therein, pick up at "The Game Continues".

But first, in either case, log into cs50.io and execute

within a terminal window to make sure your workspace is up-to-date.

Recall that 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.

Your objective here is to complete the implementation of fifteen.c by implementing two functions: move, which simulates the action of sliding a tile around the board; and won, which determines if the game is in a winning state.

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.) Be sure that you (and we) cannot crash your program, as by providing bogus tile numbers. And know that it is possible for you to automate execution of this game. In fact, in ~cs50/unit3 are 3x3.txt and 4x4.txt, winning sequences of moves for a 3 × 3 board and a 4 × 4 board, respectively. To test your program with, say, the first of those inputs, execute the below.

Recall that the < allows us to "redirect" input to a program. Instead of having to type each individual move at the terminal window, we wrote up the correct set of moves required to win the Game of Fifteen and placed it in a file, and they’ll be read from the file line-by-line, allowing us to just sit back and watch the action.

Feel free to tweak the appropriate argument(s) to usleep to speed up animation for testing, if you wish. In fact, you’re welcome to alter the aesthetics of the game. For (optional) fun with "ANSI escape sequences," including color, take a look at our implementation of clear and check out http://isthe.com/chongo/tech/comp/ansi_escapes.html for more tricks.

You’re welcome to write your own functions and even change the prototypes of functions we wrote (though, if using the staff solution as your starting point, it would not be wise to modify the prototypes of init or draw!). 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. In particular, main must only returns 0 if and when the user has actually won the game; non-zero values should be returned in any cases of error, as implied by our distribution code. If in doubt as to whether some design decision of yours might run counter these wishes, simply reach out to your teacher.

Finally, here are some tips from Zamyla. First, for move:

And also for won:

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?

You’ve written a game! Now go show it off to family and friends!

This was Problem 3-2.