Programming Assignment 1: Coin Stacks

Programming Assignment 1: Coin Stacks
CECS 328
1 Deadline
Friday, September 17, 
2 Introduction
Two third-graders, a boy and a girl, are playing King/Queen of the Hill with
coins in a grid formation. They have labeled the piles with coordinates (i, j)
where 0 ≤ i, j < N. (These are honors third-graders.) Each pile has a height
h(i, j), a nonnegative integer that represents the number of coins in the pile.
Aside from the coins in the piles, the children have an infinite number of spare
coins that they can add to any pile.
The way the game is played is as follows: The girl arranges the piles in the
shape of a grid with a nonnegative number of coins in each pile as described.
The tallest of the piles is going to hold the Queen of the Hill; that pile will have
at least as many coins as any other coin stack in the grid. It is now the boy’s
responsibility to add the minimum number of coins to the various piles in the
grid so that the following restrictions are respected:
1. For any given row x, assume that the maximum height of a pile in that
row occurs in column y. Then the heights of the piles must be decreasing
1
outward from column y in row x. Mathematically, ∀i < j ≤ y, h(x, i) ≤
h(x, j) and ∀i > j ≥ y, h(x, i) ≤ h(x, j).
2. For any given column x, assume that the maximum height of a pile in that
column occurs in row y. Then the heights of the piles must be decreasing
outward from row y in column x. Mathematically, ∀i < j ≤ y, h(i, x) ≤
h(j, x) and ∀i > j ≥ y, h(i, x) ≤ h(j, x).
3 Your code
You will write a class StudentSolver that determines the minimum number of
coins the boy needs to satisfy the grid restrictions, given a grid of coin heights.
You will also modify the input grid to show how tall the coin stacks should be
after the boy is finished modifying them.
If you are writing the file in Java: StudentSolver.java should have a function
with the header public static int solve(int[][] grid)
If you are writing the file in Python: studentsolver.py should have a function
with the header def solve(grid):
If you are writing the file in C++: StudentSolver.h should have a line with
the header static int solve1(int* grid[], const int n);
4 Example
The following is an example of the results for a 5 by 5 grid. The total number
of coins in this case should be 26.
1 2 5 3 3
2 4 1 5 1
2 1 1 5 2
1 1 5 1 3
4 3 1 5 1
1 2 5 3 3
2 4 5 5 3
2 4 5 5 3
2 4 5 5 3
4 4 4 5 1
2