Programming Assignment 3: Tetris Tournament

These steps were last updated .

Due Date

Tuesday, March 7th, 1:59 PM.

Introduction

We’re hosting a Tetris tournament! Well, not the class, but somebody is, and they’ve called upon you to create a ranking program. Given a list of Tetris quicksaves, your program needs to read and sort them, outputting a list of the top saves. Unfortunately, the tournament administrator has yet to decide if they’ll rank players by score, or by the number of lines they’ve completed. They’re also not sure how many players will advance in each round, so the sorting metric and number of players will need to be configurable via arguments to your ranking program.

Key Challenges

• Dealing with large, variable-size inputs
• Heavily working with pointers, including function pointers
• Storing and processing large amounts of internal state quickly
• Dynamically allocating and freeing memory, while cleanly handling out-of-memory errors

Non-Challenges

• Implementing a sorting algorithm. The C standard library includes qsort. See man qsort for details and info libc "Array Sort" for more information, including an example.

Detailed Specification

Your program is to be called rank, and will be implemented in the C file rank.c.

Command-Line Arguments

rank is to take two arguments:

1. The metric to sort on, score or lines.
   • Extra credit opportunity: [Board] occupancy. (Note that TA/LAs can not provide help with extra credit.)
2. The number, N, of top games to print.

Input

On stdin, rank will recieve a newline-delimited list of Tetris quicksave file locations (relative and/or absolute paths), terminated by the end-of-file byte (EOF, aka EOT, byte 0x04). Anywhere from zero to one million filenames may be provided.

Output

On stdout, rank should output the filenames of the top N quicksaves, sorted in decending order by the user-specified metric. If there are ties, you may break them arbitrarily.

Extra credit opportunity: Break the tie using the other metric, i.e. if the user requests a ranking by score, break ties by examining lines.

Error Handling

If any library call (such as malloc()) fails due to an out-of-memory condition, your program should detect this and exit with a non-zero return code. You are also welcome to print error messages to stderr.

Example

Given the file submitted_game_list.txt, containing the following list of quicksave filenames:

jonas_the_unbeatable.bin
alex_the_best.bin
bob_the_novice.bin
terminator_tom.bin
/home/hhong/harry_hong.bin
mihara, robin.bin
nk anon.bin

Where each of these files has the contents as follows:

We could ask rank to determine the top four player saves by score:

john@comp211-2sp23:~$ ./rank score 4 < submitted_game_list.txt
jonas_the_unbeatable.bin
alex_the_best.bin
nk anon.bin
/home/hhong/harry_hong.bin

Or, we could ask rank for the top player by lines:

john@comp211-2sp23:~$ ./rank lines 1 < submitted_game_list.txt
alex_the_best.bin

Note: The < syntax tells your shell to redirect the contents of some file (in this case submitted_game_list.txt) to stdin. This means that if you were to call getc() from inside rank, it would receive characters from that file rather than from your command line.

Test Data

Several quicksaves are provided in /playpen/tetris_quicksaves directory on the course server. For example, you can test your program with all these quicksaves by running ./rank score 3 < /playpen/tetris_quicksaves/test_files.txt to ask your program to display the top three filenames by score.

The tetris command has also been updated to allow you to specify the quicksave path, eg. tetris /playpen/tetris_quicksaves/starter3.bin. This allows you to more easily open, inspect, and play some of the provided quicksaves. Note that you cannot overwrite our sample files, so copy them elsewhere if you will want to overwrite them with updated data.

Getting Started

As with prior assignments, we provide the server comp211-2sp23.cs.unc.edu for you to develop your solutions on. This will be a challenging assignment. Start early, and build your program incrementally. We suggest several steps below to help you get started. Advanced students are welcome to develop their program any way they choose, as long as it meets the specification.

Step 1: Preparatory Readings

In addition to the course readings assigned before the release of this assignment, you likely want to read:

• For useful principles and examples:
  • Sec. 5.6 (review), 5.11, 7.7, and 7.8.5 in The C Programming Language
  • Sec. 3.2.3.1-5 in The GNU C Library Reference Manual (info libc malloc and following pages)
  • Sec. 9.3-9.4 The GNU C Library Reference Manual (info libc "Array Sort)
• For quick reference:
  • The manpages for malloc and qsort

Step 2: Support Dynamically Sized Input

As your program will be provided anywhere from one to a million file names, you will need to dynamically allocate memory on the heap to store input. It would be best to first allocate a small amount of memory, and then resize the buffer as necessary for large inputs. An alternative, but less-efficient, solution would be to allocate a buffer for each file name. To test that this is successfully working, try temporarily adding code at the end of your program to print the input back out. Alternatively, you could test by inspecting the allocated memory using the gdb debugger.

Make sure that this works robustly before moving on to the next step. We suggest using valgrind to verify valid use and freeing of memory (remember the -g option to gcc for symbols). To make sure that your program cleanly exits when insufficient memory is available, run the ulimit shell built-in (documented in man bash rather than man ulimit—search in the bash manpage with /). ulimit limits the amount of various resources available to your shell and its children (like rank). For example, to update the limit on the amount of memory to 100KiB, run ulimit -Sv 100. After running this, subsequent invokations of rank will be allowed to use only 100KiB of virtual memory. (Note that this limit applies to everything you run until you remove it with ulimit -Sv unlimited.)

Step 3: Handle File Data

Now we need to read the data inside each of the specified files. This presents a branch in the road, as there are at least three different ways to access the file data throughout the sort:

1. Open, read, and close the file every time we need to compare its contents with another file.
2. Open, read into memory, and close all the files before sorting.
3. Open and mmap all the files before sorting, and close them when the sort is done.

There are many other variations, but in all cases you will need to be able to read specific data from every provided save file. To make sure that you can do that, try modifying your program to print out the high score from every save file. Leverage your knowledge from Assignment 2 to do this well. (Please reuse the tetris.h header from Assignment 2 in your Assignment 3 submission. Use the cp command to make a copy of tetris.h if you would like.)

Step 4: Add Sorting

Choose a field to experiment with, say score, and implement the code to print the filenames in order of increasing score. Fortunately, you do not have to implement your own sorting algorithm. The C standard library (libc) provides the qsort() function. See man qsort for details and info libc "Array Sort" for more information, including an example. The trickiest part here will be writing your comparison function. Sec. 5.11 in The C Programming Language (3 pg.) explains how to do this. Note that if you decide to open and read the files before the sort, you likely will want to store your internal state as an array of structs (where perhaps each struct holds a pointer to the file name as well as any data read from that file).

Once you have this working, take some time to verify everything still works with a low ulimit setting, and that valgrind cannot identify any errors. This would also be a good opportunity to cleanup and/or restructure your code before continuing.

Step 5: Parameterize Your Sort

Given a working sort on a fixed field in the save state, expand your program to support sorting on other fields. I suggest internally hardcoding the mode at first, and then adding the argument parsing once you verify that each mode works on its own.

Step 6: Final Tweaks

Only print out the number of top players requested by the user via command line arguments, and clean up your code style.

To auto-reformat your code style, you can use the clang-format command (among others, indent is also installed on the server). If you want to reformat to comply with the Google C++ style guide, run clang-format -i --style=Google rank.c. (Note that this will overwrite your rank.c file with the reformatted version. You may want to first use cp to create a backup copy of your file.) For clang-format, I would suggest the Chromium, Google, or Microsoft with the --style= parameter. For indent, I would suggest -kr to match the coding style in the textbook.

Submission

Honor Code

Remember, per the syllabus, any form of code sharing is strictly forbidden. You’re welcome to consult online resources, but please cite them. (Kudos to the students already doing proper citations!)

Honor Code Pledge

As a signed honor code pledge is a university requirement on all submitted assignments, the first line in your submission file (rank.c) must be the following:

// I, John Doe (730777777), pledge that I have neither given nor received unauthorized aid on this assignment.

Where John Doe is replaced with your name, and 730777777 is replaced with your PID. This statement constitutes your legally binding signature.

If you collaborated with others on your assignment submission, you must list them on the second line of your submission, as follows:

// Collaborators: onyenA, onyenB, ...

Where onyenA, onyenB, ... is replaced with a comma-separated list of the Onyens of your collaborators. Your “collaborators” listed here are simply those you non-trivially discussed high-level concepts, approaches, and pseudocode ideas with (as defined in the syllabus).

If you are finding this assignment insurmountably difficult, please try coming to office hours first, but note that you have until March 3rd to drop the class (with a ‘W’ grade).

Uploading your Assignment

Gradescope will be used for autograding and for style grading. Upload your assignment from the course server using submit_a3. Example:

john@comp211-2sp23:~$ submit_a3 ~/rank.c
Welcome to the COMP 211-002, Spring 2023, Assignment 3 Uploader.
This uploader does not save your credentials, and only uses them to
login to Gradescope over an encrypted (SSL) connection.
Gradescope Email: johndoe@email.unc.edu
Gradescope Password:
Login successful!
File "rank.c" uploaded.

After submitting, you are welcome to log in to Gradescope and confirm that your file uploaded as desired. Note that every submission has its own page in Gradescope, so refreshing the page after resubmission may not be sufficient to see your updated code. You have unlimited (re)submissions before the deadline. Note that if the next two weeks look to be highly challenging in your other courses, this may be a wise time to use one of your two permitted late assignment submissions.

Autograder

A minimalistic autograder will be posted shortly which simply confirms that:

1. Your code can compile with gcc *.c -o rank
2. rank.c includes the honor code pledge
3. Your program runs, and outputs the correct results for the test cases in /playpen/tetris_quicksaves for the score and lines metrics.

We will test your code more fully, according to the below rubric, with our internal autograder after the deadline. Resultant scores will be curved.

As this assignment has many pieces, the autograder is unlikely to be of little help until you have completed most of the above steps. Note that in most industry settings, you will need to develop your own tests. Learning to think up edge cases in your code, and to develop tests for them is a great skill to start to learn now.

Think of an interesting edge case that you think everyone’s code should be able to handle? Create a post on Piazza describing the edge case, and include the detailed command sequence needed to test rank in your described case. Excellent edge cases may be included in the autograder, and if so, you will receive extra credit for your contribution.

Grading Rubric

Full rubric to be determined. Difference between a “B”- and “A”-level grade will be the performance (that is, speed) of your implementation.

Rubric:

• 80% autograded:
  • 65% Correctness in simple test cases (such as those in /playpen/tetris_quicksaves)
  • 25% Correctness for edge cases
  • 10% Performance
• 20% style

Comments on Style Grading

Some common style mistakes I saw on Assignment 1:

• Be consistent in spacing and indenting
• Don’t use implicit return types
  • If you don’t specify the return type, it’s int by default.
• Don’t redeclare library functions or types
• Avoid lines longer than 80 characters
• Consider initializing variables on the same line that you declare them
• For variables you only set once, use the const qualifier (see Sec. 2.4 and pg. 211 in The C Programming Language)
• Avoid unecessary #include directives
  • As the preprocessor copies in included code, superfluous #include directives result in more code to compile, and consequently slow compile times.
• Avoid repeated calls to library functions when a single call would have sufficed
  • Eg. don’t call printf() five times to print a single line. Every function call has an associated overhead cost, and uncessesary calls slow your program.
• Don’t include commented out code

Extra Credit Opportunities

There are several extra credit opportunities available in this assignment. The number of points that you can gain is a function of the noted difficulty. Please verify that every other part of your assignment is working before you start adding extra-credit code.

Sort by Board Occupancy (moderate)

Implement logic to quantify how full a Tetris board is, and allow the tournament administrator to sort games by this metric. Less occupied boards are better. You are free to be creative with how you quantify board occupancy.

Some potential ways to quantify board occupancy:

1. Number of tiles occupied (lower is better)
2. Height of highest line containing a filled tile (lower is better)
3. Number of empty, unreachable tile slots (lower is better)

Break Ties (easy)

If games are sorted by score, break ties by considering lines (and vice-versa). If you implemented the board occupancy option, also break simultaneous ties of lines and score by board occupancy.

Detect Falsified Quicksaves (very difficult)

Given the known existence of falsified Tetris quicksaves out in the wild, (I hear a class allegedly had their students make such an abomination!), detect and remove these quicksaves from your program’s output if asked via the addition of a third argument, check. There is no one way to do this, and the course staff will largely be unable to provide guidance.

Example:

If suspicious_game_list.txt contained:

john_def_the_best.bin
nk anon.bin
alexis.bin

And rank was invoked as:

john@comp211-2sp23:~$ ./rank score 3 check < suspicious_game_list.txt

On stdout it would print:

alexis.bin

And on stderr it may print (you are free to be creative with these messages):

"nk anon.bin" excluded---quicksave likely falsified.
"john_def_the_best.bin" excluded---quicksave likely falsified.

If the third argument check were excluded, your implementation of rank should not check validity of the quicksaves, and instead behave as though they are all valid.

Some guesses on what to check for:

1. To reach a certain number of lines, you need to have reached a minimum score. For example, I suspect that score should always be greater than lines.
2. Some board configurations are only reachable via manual modification. For example, floating tiles (as with your initials in Assignment 2) are certain indicators of modification.
3. It is probably impossible for a human or AI player to pass a certain score/lines ceiling, as pieces would immediately fall all the way, without any time for placement.

You can obtain tetris.c here if you would like to examine the game logic to determine what states are, and are not, possible.