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 worth some number of points that represent the battlefields' strategic value (Note that the linked article discusses a limited version in which each battlefield is worth the same amount; we allow for a different value for each battlefield, and if you prefer a more peaceful context, 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. For each battlefield, the player who allocates more units to that battlefield wins the points for it (with the points split evenly in case of a tie, including a 0-0 tie), and the winner is the player with the most total points.

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 $1.5 + 4 = 5.5$ and player 2's score is $1 + 2 + 1.5 = 4.5$. Player 1 wins.

Overview

Write a program called Blotto that reads players' distributions from standard input, along with a list of head-to-head matchups between pairs of those players. Output gives the result of each matchup, where, for each matchup, points are awarded to each player based on who placed more units in each battlefield, and the value of the battlefields given on the command line. For example, if the file blotto.in contains

P1,2,2,2,3
P2,3,3,2,1
P3,2,2,5,0

P1 P2
P1 P3
P2 P3

then running ./Blotto 1 2 3 4 < blotto.in should result in output

P1 5.5 - P2 4.5
P1 5.5 - P3 4.5
P2 7.0 - P3 3.0

Implementing the gmap ADT

You must implement the gmap ADT according to the specification in /c/cs223/hw4/Required/gmap.h, which can then be used to store the players' distributions as you read them from standard input for retrieval later when you read the matchups. The gmap ADT defines a map from generic keys to generic values, with the functions used for hashing, copying, comparing, and freeing the keys passed to the map upon creation.

The gmap functions must run in the following time bounds, where $n$ is the number of key/value pairs in the map:

• 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)$

These bounds 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 (with supporting modules gmap_test_functions and string_key in the same directory) 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 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.

Your Blotto program must run in expected $O(n + m)$ time for a fixed number of battlefields and total number of units, where $n$ is the number of entries and $m$ is the number of matchups, under the assumption that malloc and free run in $O(1)$ time.

Details

Command-line Arguments

• there will be at least one command-line argument
• each command-line argument will be a positive integer in a format readable by atoi
• the number of battlefields is determined by the number of command-line arguments

Input

• standard input will consist of two parts separated by a blank line
• the first part lists the players' distributions as follows
  • there will be one line per player
  • there may be no players, in which case standard input will begin with a blank line
  • each line starts with a unique non-empty entry id for the player
  • the id will contain at most 31 characters and no commas or whitespace
  • the rest of the line will contain the number of units the player distributes to each battlefield, with each number being a non-negative integer in a format readable by scanf with the %d format specifier
  • each player's distribution will have a value for each battlefield
  • all parts of the data for each player are separated by commas
  • there is no whitespace on each line except for a newline at the end of each line
  • the total number of units for each player will be non-zero and equal to the number of units for all other players
• the second part lists the matchups as follows
  • there is one matchup per line
  • there may be no matchups, in which case standard input ends with the blank line that follows the players' distributions
  • each matchup is specified by giving the id of two different players that were given in the first part of the input, separated by a single space
  • there is no other whitespace on each line aside from the space that delimits the ids and the newline at the end of the line

Output

• there is exactly one line of output per matchup, written to standard output in the order the matchups appeared in standard input
• if there are duplicate matchups in standard input, then the corresponding output will appear repeated in the corresponding locations in the output
• each line contains the id of the winner of the matchup, or the id of the first player given in the matchup in the case of a draw, a single space, the score for that player given with one digit after the decimal point, a hyphen with a single space on either side as a separator, and then the id and score of the other player in the same format
• each line ends with a newline character
• there is no other output to either standard output or standard error

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

Hints and Other Considerations

• 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.
• Can you test your Blotto implementation before you complete your gmap 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.)
• Note that the checkpoint only tests Blotto with ids that are two characters long, distributions with 0-9 units in each battlefield, and battlefields valued $1, 2, 3, \ldots$.
• Can you test parts of Blotto before you've written code to read the matchups file?
• 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?
• In addition to the unsorted array implementation of gmap mentioned above, the partial implementation of simap using a chained hash table from the Oct 18 examples and the implementation of the Dict ADT in Prof. Aspnes's notes may be helpful as starting points.

Submissions

Submit your makefile, log file, 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.