Assignment 4: Blotto Competition

Objectives

• to use the map ADT
• to implement the map ADT using a hash table

Introduction

Blotto is a simultaneous game for two players in which the players distribute militatry units over a number of battlefields (in addition to simulating military conflicts over multiple battlefields, Blotto can be seen a a model of allocating campaign resources over contested areas, or spreading advertising resources across various media outlets). Each player has a set number of units to distribute, each unit is equivalent to each other unit, and a unit must be allocated entirely to a single battlefield. Each battlefield is worth a given number of points based on its strategic value, and the player who allocates more units to a battlefield wins the points for that battlefield (with the points split evenly in case of a tie, including a 0-0 tie).

For example, suppose there are four battlefields worth 1, 2, 3, and 4 points respectively and each player has 10 units to distribute. If player 1's distribution is $(2, 2, 2, 4)$ and player 2's distribution is $(3, 4, 2, 1)$ then player 1 wins battlefield 4, player 2 wins battlefields 1 and 2, and the players tie on battlefield 3. Player 1's score is then 5.5 and player 2's score is 4.5.

The winner of a single one-on-one competition is the player with the most points in that competition; the competition is a draw ($\frac{1}{2}$ win each) if the score is tied.

A variant of Blotto allows for multiple players. Each player submits a single entry, and the entries are played against each other two at a time. The objective can be to accumulate the most wins or the most total points. For example, if we have the two entries above and a third entry $(2, 2, 6, 0)$ then P1 beats P2 5.5-4.5, P1 beats P3 5.5-4.5, and P2 beats P3 7-3. If the overall champion is determined by number of wins, then P1 is the champion with 2 wins. If the overall champion is determined by total score then the champion is P2 with 11.5.

Assignment

There are two parts to this assignment:

• implement the gmap ADT according to the specification in /c/cs223/hw4/Required/gmap.h; and
• write a program called Blotto that runs a Blotto competition.

Implementing the gmap ADT

Complete the implementation of the functions declared in /c/cs223/hw4/Required/gmap.h to implement a map from generic keys to generic values so that the functions run in the following time bounds:

• gmap_create: $O(1)$
• gmap_size: $O(1)$ (worst-case)
• gmap_contains_key: expected $O(1)$, worst-case $O(n)$
• gmap_get: expected $O(1)$, worst-case $O(n)$
• gmap_put: expected $O(1)$, worst-case $O(n)$
• gmap_remove: expected $O(1)$, worst-case $O(n)$
• gmap_for_each: $O(n)$ (assuming f runs in $O(1)$ time)
• gmap_keys: $O(n)$
• gmap_destroy: $O(n)$

Assume that the key operations (copy, compare, hash, and free), and malloc and free run in $O(1)$ time. Expected running times are under the assumption that the distribution of keys and the hash function are such that the hash values of the keys are distributed randomly and uniformly across the range of the size_t type.

Your ADT will be tested with a series of unit tests that test individual functions. An incomplete suite of unit tests is implemented in /c/cs223/hw4/Required/gmap_unit.c and /c/cs223/hw4/Required/gmap_test_functions.c, which will be replaced with a complete test suite for the private test script. Your makefile must include a target GmapUnit that is built from those two files and your implementation of the gmap module. All unit tests must pass with no errors reported from valgrind, and any use of your gmap module that doesn't violate the functions' preconditions must result in no errors from valgrind. No public or private tests will violate the preconditions, and we will not test out-of-memory conditions for this part or the Blotto executable described below.

Note that although you may not use all of the functions provided by the gmap module when writing the Blotto program, you must implement all of them for this part of the assignment.

Writing the Blotto program

Use your gmap ADT implementation to write a program that displays the results for a Blotto competition. Competition entries will be read from standard input. Which entries to play against which other entries will be determined by a file whose name is given as a command-line argument. Other parameters of the competition will be given as further command-line arguments. Your program must run in expected $O(n \log n + m)$ time, where $n$ is the number of entries and $m$ is the number of matchups, assuming that the number of battlefields is constant and that qsort runs in expected $O(n \log n)$ time.

Input

The command-line arguments will be as follows.

• The first command-line argument will be the name of the matchups file.
• The second command-line argument will be either "score" or "win" to determine whether the program keeps track of wins for each entry or the total score for each entry.
• The remaining command-line arguments (there will be at least one) determine the values of each battlefield, which will be given as positive integers in a format readable by atoi. The number of battlefields is determined by the number of values.

Standard input will contain one entry per line, where each entry contains a unique non-empty entry id (a string of at most 31 characters containing no commas or whitespace) and the distribution of units given as nonnegative integers in a format readable by atoi. There will be one integer per battlefield, where the number of battlefields is determined by the number of battlefield values given on the command line, and the sum of the integers for each entry will be the same. All parts of an entry will be separated by commas, with no whitespace except for the newline at the end of the line. You can use the entry module in /c/cs223/hw4/Optional to read entries, but we do not guarantee that the entry_read function in that module will handle all invalid inputs without errors. If you modify the module then you must submit your modifications, otherwise you can omit it from your submission.

The matchups input file will contain one matchup per line, where each matchup is specified by giving the id of two different entries that were given in standard input. The two ids for each matchup will be separated by a single space, and there will be no other whitespace except for the newline at the end of each line.

Output

Output should give the average wins or score over all the matchups for each entry, with repeated matchups counted separately for each occurrence. The entries should be sorted in order of decreasing average, with entries that were not present in the matchups file excluded. Ties in average wins or score should be broken in order of increasing entry id as determined by strcmp. The output should be formatted as in the example below. Note that there are two spaces before the digit in the ones place, and those spaces would be used for digits in the case that an entry has an average score of at least 10 and less than 1000. Average scores 1000 and higher may be formatted as you see fit but must be followed by a single space and then the entry id.

If any of the input (standard input, the matchups file, or the command-line arguments) is invalid for any reason, then the output can be anything and your program must not crash or hang.

Considerations

• Can you test your Blotto implementation before you complete your smap implementation? (Hint: there is an incomplete, inefficient implementation of gmap using an unsorted array to hold the keys and values in /c/cs223/hw4/Optional/gmap_array.c.)
• Can you test parts of Blotto before you've written code to read the matchups file? (Hint: the public tests run complete round-robin competitions with each entry matched up against each other entry exactly once.)
• What functions might be helpful to divide your Blotto implementation into?
• Are there any functions from the unsorted array implementation of gmap that you can use unchanged in your hash table implementation?
• What functionality of gmap is not strictly necessary to test other functionality?
• What test cases are missing from the public tests?
• Why is it necessary that gmap copies keys rather than storing pointers to the ones passed to gmap_put? Why does it not need to do the same thing for the values?

Examples

[jrg94@jaguar code]$ ./Blotto /c/cs223/hw4/Tests/round_robin_3.in win 1 2 3 4 <  /c/cs223/hw4/Tests/example_3.in
  1.000 P1
  0.500 P2
  0.000 P3
[jrg94@jaguar code]$ ./Blotto /c/cs223/hw4/Tests/round_robin_3.in score 1 2 3 4 < /c/cs223/hw4/Tests/example_3.in
  5.750 P2
  5.500 P1
  3.750 P3
[jrg94@jaguar code]$ ./Blotto /c/cs223/hw4/Tests/round_robin_25_5.in win 1 2 3 4 5 < /c/cs223/hw4/Tests/blotto_25_5.in
  0.789 entry15
  0.763 entry23
  0.750 entry20
  0.724 entry32
  0.697 entry1
  0.697 entry37
  0.645 entry11
  0.645 entry22
  0.645 entry35
  0.618 entry34
  0.605 entry29
  0.592 entry14
  0.579 entry12
  0.579 entry3
  0.526 entry28
  0.526 entry7
  0.513 entry39
  0.500 entry21
  0.500 entry24
  0.487 entry6
  0.474 entry4
  0.474 entry9
  0.461 entry10
  0.461 entry16
  0.461 entry17
  0.461 entry19
  0.461 entry25
  0.461 entry8
  0.447 entry13
  0.447 entry33
  0.434 entry18
  0.421 entry38
  0.408 entry26
  0.355 entry2
  0.303 entry30
  0.250 entry5
  0.211 entry31
  0.132 entry36
  0.000 entry27

Submissions

Submit your makefile, log file (note the updated format to facilitate automatic analysis of your difficulties section), and source code necessary to build the executables Blotto and GmapUnit using your makefile. Your makefile should assume that the files from /c/cs223/hw4/Required have been copied into the current directory but not that they are still in their original locations, and you should not submit those files.