COMP 211-002 | Spring 2023 (Bakita)
These steps were last updated .
Tuesday, March 7th, 1:59 PM.
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.
qsort. See man qsort for details and info libc "Array Sort" for more information, including an example.Your program is to be called rank, and will be implemented in the C file rank.c.
rank is to take two arguments:
score or lines.
occupancy. (Note that TA/LAs can not provide help with extra credit.)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.
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.
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.
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.binWhere each of these files has the contents as follows:
| Filename | Score | Lines |
|---|---|---|
| jonas_the_unbeatable.bin | 999912367 | 83857 |
| alex_the_best.bin | 887644555 | 97777 |
| bob_the_novice.bin | 777688 | 250 |
| terminator_tom.bin | 74259879 | 8000 |
| harry_hong.bin | 88876383 | 9500 |
| mihara, robin.bin | 5556789 | 4500 |
| nk anon.bin | 99999999 | 9999 |
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.binOr, we could ask rank for the top player by lines:
john@comp211-2sp23:~$ ./rank lines 1 < submitted_game_list.txt
alex_the_best.binNote: 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.
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.
As mentioned on Piazza, there are far more extensive test inputs in /playpen/a3/ on the course server. Here’s a listing of everything located there:
jbakita@comp211-2sp23:~$ tree -L 2 /playpen/a3
/playpen/a3
├── answer_cases
│ ├── lines_128k.txt <= 128k tetris quicksaves, sorted by lines
│ ├── lines_256.txt
│ ├── lines_4.txt
│ ├── lines_64k.txt
│ ├── lines_75.txt
│ ├── lines_8000.txt
│ ├── score_128k.txt
│ ├── score_256.txt
│ ├── score_4.txt
│ ├── score_64k.txt
│ ├── score_75.txt
│ └── score_8000.txt
├── test_cases
│ ├── team_quicksaves
│ ├── test_128k <= Directory containing the 128k Tetris quicksaves
│ ├── test_128k.txt <= List of 128k Tetris quicksaves to rank
│ ├── test_256
│ ├── test_256.txt
│ ├── test_4.txt
│ ├── test_64k
│ ├── test_64k.txt
│ ├── test_8k
│ ├── test_8k.txt
│ ├── test_team.txt
│ └── tetris_quicksaves
└── tetris.h
8 directories, 19 filesFun Fact: You can use the tree command to list out directory hierarchies. This is not installed by default on most systems, but can be a helpful complement to ls when available.
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.
In addition to the course readings assigned before the release of this assignment, you likely want to read:
info libc malloc and following pages)info libc "Array Sort)malloc and qsortAs 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.)
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:
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.)
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.
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.
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.
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!)
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).
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.
A minimalistic autograder will be posted shortly which simply confirms that:
gcc *.c -o rankrank.c includes the honor code pledge/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.
Full rubric to be determined. Difference between a “B”- and “A”-level grade will be the performance (that is, speed) of your implementation.
Rubric:
/playpen/tetris_quicksaves)Some common style mistakes I saw on Assignment 1:
int by default.const qualifier (see Sec. 2.4 and pg. 211 in The C Programming Language)#include directives
#include directives result in more code to compile, and consequently slow compile times.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.
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:
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.
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.binAnd rank was invoked as:
john@comp211-2sp23:~$ ./rank score 3 check < suspicious_game_list.txtOn stdout it would print:
alexis.binAnd 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:
score should always be greater than lines.You can obtain tetris.c here if you would like to examine the game logic to determine what states are, and are not, possible.