Exercise 7: Chomp

Objectives

• to use a map ADT
• to implement a map ADT with a chained hash table
• to apply dynamic programming

Introduction

Chomp is a game played by two players on an r-by-c grid. The players alternate claiming one of the remaining locations on the grid; that location and all locations above and to the right are removed from play. The last player to make a move (taking the bottom-left location) loses. (Note that the Wikipedia article describes the game upside-down.)

Assignment

Write a program called Chomp that takes a single command-line argument that is a non-empty string of nonincreasing digits starting with a non-zero digit representing the state of a game of Chomp. The output should be a single line containing "LOSS" if there is no winning move from that state and "WIN" along with the state resulting from making the winning move if there is a winning move. The output should be in the format given in the example below. If there is more than one winning move then the output should reflect the one that selects the leftmost piece among all the winning moves.

Your program must be efficient in terms of time and memory, where "efficient" is defined as "passes the large public test cases without execeeding the time or memory limits".

Code

Map ADT

The code given in /c/cs223/hw7/Optional/gmap.c implements a map using an unsorted linked list. This gives $O(n)$ worst-case efficiency for all of the map operations. Change this implementation to use a hash table with collisions resolved by chaining so that gmap_put, gmap_get, and gmap_contains_key run in expected $O(1)$ time assuming a hash function and key distribution so that the keys are uniformly distributed over all possible hash values.

To implement the hash table, change the gmap struct so that it contains an array of node pointers, one per chain, instead of a single node pointer. Then change gmap_put, gmap_get, and gmap_contains_key so they first compute which chain they should operate on by computing the hash of the key and taking the remainder when dividing by the table size. Then, instead of working on the single linked list in the original implementation, do the same work on the chain at the resulting index.

The original implementations of gmap_for_each and gmap_destroy work with a single list; change them so their existing code operates on each chain in turn.

Finally, to ensure a bounded load factor, when the number of (key, value) pairs in the hash table exceeds the number of chains, grow the hash table by creating a new array of chains, adding each node in the old chains to the new chain determined by the hash value of the key and the new number of chains.

Chomp

The main module in /c/cs223/hw7/Optional/chomp_main.c implements the dynamic programming algorithm by creating a map to hold the winning move for each state (if there is one), initializing the entry for the terminal state to indicate that if it is your turn and the poisoned brownie has already been eaten then you have already won, and then iterating through the states returned by chomp_states – the order they are returned in guarantees that all successors of a state come before that state, and if you have already determined whether the successors of a state are winning or losing states then you can determine if the state itself is a winning of losing state.

For each state s in the array returned by chomp_states, get an array of its successors using chomp_successors, and for each of those determine if it is a losing state by checking it the value stored with it in the map is NULL. If it is, that means the successor is a losing position, and a winning move from s is to move to that losing successor. Save a copy of that losing successor in the map along with s, or save NULL if there is no losing successor of s (in which case s is a losing state). Note that storing the first losing successor in the array returned by chomp_successors will satisfy the requirement that you ultimately output that you select from multiple winning moves by outputting the one that moves in a column as far left as possible.

After working through the array of all states, look up the state given by the first command-line argument in the map and output "LOSS" or "WIN" as appropriate. Free all the values in the map and destroy the map.

Examples

Submissions

Submit your modified chomp_main.c and gmap.c files, any other files you created, and your makefile with the Chomp executable as the default target and the as assignment number 7. You need not submit the other given files, and your makefile should assume they have been copied into the current directory rather than that they are in their original locations.