Programming Assignment #7

> > > > Programming Assignments > Assignment 7 - Chomp

Objectives

to implement a dynamic programming algorithm
to use maps

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 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".

If the input file or command-line arguments are not as specified then your program must behave gracefully: it must not crash or go into an infinite loop.

Your program and any program must not produce any error messages when run with valgrind --tool=memcheck --leak-check=yes -q.

We reserve the right to deduct points from submissions for violations of the following guidelines.

All source code should be easily comprehended, with adequate and consistent spacing, concise but descriptive idenitifiers, comments before long sequences of code, and enumerations and constants favored over literals.
Submissions should be modularized, with collections of related functions divided into separate files.
Each function should be documented with a comment before its declaration. The comment should include 1) a description of the parameters including any limitations on the values allowed (preconditions), and 2) a description of what the function does and/or what it returns (postconditions).
Header files should be written so that they can be #included regardless of what other files have been #included -- if a declaration is required by your header files, then #include the appropriate header file in your header file (or write a forward declaration in your header) rather than relying on your #includers to have already #included those header files before they #include yours.
Things that make sense to be declared as const should be declared as const.
There should be no warnings when your code is compiled with the -Wall and -pedantic options.

Example

[jrg94@tick Chomp]$ ./Chomp 33333
WIN: 33322
[jrg94@tick Chomp]$ ./Chomp 33322
LOSS
[jrg94@tick Chomp]$ ./Chomp 33321
WIN: 22221

Files and Submissions

A suggested partial implementation is available in /home/httpd/html/zoo/classes/cs223/f2017/Assignments/Chomp. You may make any changes to this code as you see fit.

string_helpers.h string_helpers.c (utility functions for arrays of strings)
chomp.h chomp.c (utility functions for Chomp)
chomp_main.c (a skeleton of main)