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 military units over a number of battlefields. 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 smap ADT according to the specification in /c/cs223/hw4/Required/smap.h; and
• write a program called Blotto that runs a Blotto competition.

Implementing the smap ADT

Implement the smap ADT, which defines a map from strings as keys to void * values. The header file /c/cs223/hw4/Required/smap.h specifies the functions you must implement for the smap ADT and you may not change it.

In addition, there are efficiency requirements for each function:

• smap_create and smap_size must run in $O(1)$ worst-case time;
• smap_contains_key, smap_get, smap_put, and smap_remove must run in $O(1)$ expected time;
• smap_for_each, smap_keys, and smap_destroy must run in worst-case $O(n)$ time.

All time bounds assume that $n$ is the number of entries in the map and assume that the keys are randomly distributed and of bounded length, and that malloc and free work in $O(1)$ time.

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/smap_unit.c and /c/cs223/hw4/Required/smap_test_functions.c, which will be replaced with a complete test suite for the private test script. The public and private unit test modules will each contain a main function that will be linked with your smap implementation to produce an executable called Unit that executes the unit tests. Examine the public smap_unit.c to see how the individual tests work. All unit tests must pass with no errors reported from valgrind, and any proper use of your ADT must result in no errors from valgrind.

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

You may use code you find online to implement the smap_default_hash function as long as you include a proper citation.

Writing the Blotto program

Use your smap 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, 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, separated by a single space, with no other whitespace except for the newline at the end of the line.

Output

Output should give the average wins or score per game for each entry sorted in decreasing order, with entries that were not present in the matchups file excluded. Ties 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 smap using an unsorted array to hold the keys and values in /c/cs223/hw4/Optional/smap_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 smap that you can use unchanged in your hash table implementation?
• What functionality of smap is not strictly necessary to test other functionality?
• What test cases are missing from the public tests?
• Why is it necessary that smap copies keys rather than storing pointers to the ones passed to smap_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, and source code necessary to build the executables Blotto and Unit using your makefile. Your makefile should have rules with each of those executables as their targets as well as a default (first) rule that builds both targets. 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.