// Sample test case
int[][] grassData = {
{2, 3, 1, 4, 3, 2, 5},
{1, 2, 3, 1, 4, 2, 3},
{3, 4, 2, 5, 1, 3, 2}
};
int[] sum = new int[grassData[0].length];
for(int col = 0; col < grassData[0].length; col++)
{
for(int row = 0; row < grassData.length; row++)
{
sum[col] += grassData[row][col];
}
}
// Expected Output: [6, 9, 6, 10, 8, 7, 10]
System.out.println(java.util.Arrays.toString(sum));
[6, 9, 6, 10, 8, 7, 10]
FRQ Stuff
public class ArrayResizer
{
/**
* Returns true if and only if every value in row r of array2D is non-zero.
* Precondition: r is a valid row index in array2D.
* Postcondition: array2D is unchanged.
*/
public static boolean isNonZeroRow(int[][] array2D, int r)
{
/* to be implemented in part (a) */
for(int col = 0; col < array2D[0].length; col++)
{
if(array2D[r][col] == 0)
{
return false;
}
}
return true;
}
/**
* Returns the number of rows in array2D that contain all non-zero values.
* Postcondition: array2D is unchanged.
*/
public static int numNonZeroRows(int[][] array2D) {
int num = 0;
for (int row = 0; row < array2D.length; row++) {
boolean allNonZero = true;
for (int col = 0; col < array2D[row].length; col++) {
if (array2D[row][col] == 0) {
allNonZero = false;
break;
}
}
if (allNonZero) {
num++;
}
}
return num;
}
/**
* Returns a new, possibly smaller, two-dimensional array that contains only rows
* from array2D with no zeros, as described in part (b).
* Precondition: array2D contains at least one column and at least one row with no zeros.
* Postcondition: array2D is unchanged.
*/
public static int[][] resize(int[][] array2D)
{
/* to be implemented in part (b) */
}
}
| { /* implementation not shown */ }
missing return statement
| { /* to be implemented in part (b) */ }
missing return statement
// Run this code cell so that using the location class doesn't throw errors in future code cells!
public class Location {
private int theRow;
private int theCol;
public Location(int r, int c) {
theRow = r;
theCol = c;
}
public int getRow() {
return theRow;
}
public int getCol() {
return theCol;
}
}
public class GridPath {
/** Initialized in the constructor with distinct values that never change */
private int[][] grid;
public GridPath(int[][] values)
{
grid = values;
}
/**
* Returns the Location representing a neighbor of the grid element at row and col,
* as described in part (a)
* Preconditions: row is a valid row index and col is a valid column index in grid.
* row and col do not specify the element in the last row and last column of grid.
*/
public Location getNextLoc(int row, int col) {
Integer downValue = null;
Integer rightValue = null;
Location downLoc = null;
Location rightLoc = null;
if (row + 1 < grid.length) {
downValue = grid[row + 1][col];
downLoc = new Location(row + 1, col);
}
if (col + 1 < grid[0].length) {
rightValue = grid[row][col + 1];
rightLoc = new Location(row, col + 1);
}
if (downValue != null && rightValue != null) {
if (downValue < rightValue) {
return downLoc;
} else {
return rightLoc;
}
} else if (downValue != null) {
return downLoc;
} else if (rightValue != null) {
return rightLoc;
}
return null;
}
/**
* Computes and returns the sum of all values on a path through grid, as described in
* part (b)
* Preconditions: row is a valid row index and col is a valid column index in grid.
* row and col do not specify the element in the last row and last column of grid.
*/
public int sumPath(int row, int col) {
int total = grid[row][col];
while (row < grid.length - 1 && col < grid[0].length - 1) {
Location nextLoc = getNextLoc(row, col);
if(nextLoc == null)
{
break;
}
row = nextLoc.getRow();
col = nextLoc.getCol();
total += grid[row][col];
}
return total;
}
}
HW stuff
Problem Farmer John has a rectangular grass pasture with N rows and M columns for the cows to graze on. Each pasture has a certain tastiness value. However, the gen alpha Bessie has gotten quite picky with what she eats.
Given a 2D array (template below) with size NxM, please write functions for the following:
getTotalGrass() Return total sum of all “tastiness values” from the pastures in the 2D array maxSquare() Because Bessie sometimes likes enjoying square grass patches, she wants to find the best one. Returns the maximum sum of tastiness value of a square in the 2D array. (Square could be 1x1, 2x2, 3x3, etc.) maxSubarraySum() Sometimes, Bessie enjoys eating grass in a line. Return the maximum sum of a continuous subarray in this array if it was “flattened” to be a 1D array. In other words, make the 2D array into a 1D array by combining all rows and find the max subarray sum. For an example case, see below in the code.
public class GrassPasture {
/** The 2D grid of pasture tastineess values */
private int[][] pastures;
/** Constructor initializes the field */
public GrassPasture(int[][] pastures) {
this.pastures = pastures;
}
/**
* Returns sum of total tastiness for all values in 2D array
*/
public int getTotalGrass() {
int sum = 0;
for(int row = 0; row < pastures.length; row++)
{
for(int col = 0; col < pastures[row].length; col++)
{
sum += pastures[row][col];
}
}
return sum;
}
/**
* Returns max sum of tastiness of a square in the 2D array (square can be 1x1, 2x2, etc.)
*/
public int maxSquare() {
int max = 0;
for(int row = 0; row < pastures.length; row++)
{
for(int col = 0; col < pastures[row].length; col++)
{
if(pastures[row][col] > max)
{
max = pastures[row][col];
}
}
}
return max;
}
/**
* Returns the maximum tastiness sum subarray in the flattened 2D grid
*/
public int maxSubarraySum() {
int[] pastureArray = new int[pastures.length * pastures[0].length];
int index = 0;
for(int row = 0; row < pastures.length; row++)
{
for(int col = 0; col < pastures[row].length; col++)
{
pastureArray[index++] = pastures[row][col];
}
}
// now calculate the max subarraysum
int maxSum = pastureArray[0];
int currentSum = pastureArray[0];
for (int i = 1; i < pastureArray.length; i++) {
currentSum = Math.max(pastureArray[i], currentSum + pastureArray[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
}
int[][] pastures = {
{-3, 6, -1},
{2, -1, 5},
{-9, 4, -1}
};
GrassPasture gp = new GrassPasture(pastures);
System.out.println("Total Tastiness: " + gp.getTotalGrass());
// answer should be 2
System.out.println("Max Square Sum: " + gp.maxSquare());
// answer should be 6
System.out.println("Max Subarray Sum: " + gp.maxSubarraySum());
// answer should be 11
Total Tastiness: 2
Max Square Sum: 6
Max Subarray Sum: 11