* You are given a map indicating the elevation of * a small area like a desk. A
ID: 3881116 • Letter: #
Question
* You are given a map indicating the elevation of
* a small area like a desk. A ball is placed on the desk.
* The ball will roll downhill going north south east or west.
*
* The ball always starts at position 1,1
*
* It will always choose the path of steepest descent.
* It will eventually come to rest when it is at a position
* where all neighboring positions are higher/equal.
* Return the elevation of that position.
*
* You can assume that map will be such that the ball
* will always come to rest without moving through an edge
*
* You can assume there will always be one steepest
* position for the ball to go to
*
* For example, in an array like this:
* 9999
* 9549
* 9999 yields 4
* The ball would start in 1,1 (5) rolls to 4 and stops
*
* 99999999999
* 98711111199
* 96999999999
* 95444444399
* 99999999999 yields 4
* The ball starts at 8, follows steepest decent to 6
* Then at the first 4 there is no lower position so it
* stops
*
* @param map map indicating elevation
* @return height where the ball stops
public void testBallRestElevation() {
int[][] array1 = {
{9,9,9,9,9,9},
{9,8,5,4,9,9},
{9,7,9,9,9,9},
{9,7,5,2,2,9},
{9,9,9,9,9,9}};
assertEquals(4,MapAnd2DArrayHomework.ballRestElevation(array1));
int[][] array3 = {
{9,9,9,9,9,9},
{9,8,9,4,1,9},
{9,7,9,9,2,9},
{9,6,5,4,3,9},
{0,9,9,9,9,9}};
assertEquals(1,MapAnd2DArrayHomework.ballRestElevation(array3));
int[][] array2 = {
{9,9,9,9,9,9},
{9,8,6,4,9,9},
{9,5,9,9,9,9},
{9,5,5,2,2,9},
{9,9,9,9,9,9}};
assertEquals(5,MapAnd2DArrayHomework.ballRestElevation(array2));
Explanation / Answer
MapAnd2DArrayHomework.java
-------------------------------------
public class MapAnd2DArrayHomework {
public static int ballRestElevation(int[][] map)
{
int i=0;
int j=0;
while (true)
{
int min = map[i][j];
if (i== 0&& j==0)
// at the start point
{
int flag = 0;
int itmp = i;
int jtmp = j;
if (map[i+1][j] < min)
//South
{
min = map[i+1][j];
itmp = i + 1;
jtmp = j;
flag = 1;
}
if (map[i][j+1] < min)
//East
{
min = map[i][j+1];
itmp = i;
jtmp = j + 1;
flag = 1;
}
if (map[i+1][j+1] < min)
//EastSouth
{
min = map[i+1][j+1];
itmp = i + 1;
jtmp = j + 1;
flag = 1;
}
if (flag == 0)
{
return map[i][j];
}
i = itmp;
j = jtmp;
}
else if (i==0)
// when the point is at the top of the map
{
int flag = 0;
int itmp = i;
int jtmp = j;
if (map[i+1][j] < min)
//South
{
min = map[i+1][j];
itmp = i + 1;
jtmp = j;
flag = 1;
}
if (map[i][j+1] < min)
//East
{
min = map[i][j+1];
itmp = i;
jtmp = j + 1;
flag = 1;
}
if (map[i][j-1] < min)
//West
{
min = map[i][j-1];
itmp = i;
jtmp = j - 1;
flag = 1;
}
if (map[i+1][j+1] < min)
//EastSouth
{
min = map[i+1][j+1];
itmp = i + 1;
jtmp = j + 1;
flag = 1;
}
if (map[i+1][j-1] < min)
//WestSouth
{
min = map[i+1][j-1];
itmp = i + 1;
jtmp = j - 1;
flag = 1;
}
if (flag == 0)
{
return map[i][j];
}
i = itmp;
j = jtmp;
}
else if (j==0)
// if it at the start of each rows
{
int flag = 0;
int itmp = i;
int jtmp = j;
if (map[i+1][j] < min)
//South
{
min = map[i+1][j];
itmp = i + 1;
jtmp = j;
flag = 1;
}
if (map[i][j+1] < min)
//East
{
min = map[i][j+1];
jtmp = j+1;
itmp = i;
flag = 1;
}
if (map[i-1][j] < min)
//North
{
min = map[i-1][j];
itmp = i - 1;
jtmp = j;
flag = 1;
}
if (map[i+1][j+1] < min)
//EastSouth
{
min = map[i+1][j+1];
itmp = i + 1;
jtmp = j + 1;
flag = 1;
}
if (map[i-1][j+1] < min)
//NorthEast
{
min = map[i-1][j+1];
itmp = i - 1;
jtmp = j + 1;
flag = 1;
}
if (flag == 0)
{
return map[i][j];
}
i = itmp;
j = jtmp;
}
else if (j==map[0].length-1)
//end of the array
{
int flag = 0;
int itmp = i;
int jtmp = j;
if (map[i+1][j] < min)
//South
{
min = map[i+1][j];
itmp = i + 1;
jtmp = j;
flag = 1;
}
if (map[i-1][j] < min)
//North
{
min = map[i-1][j];
itmp = i - 1;
jtmp = j;
flag = 1;
}
if (map[i][j-1] < min)
//West
{
min = map[i][j-1];
jtmp = j-1;
itmp = i;
flag = 1;
}
if (map[i-1][j-1] < min)
//NorthWest
{
min = map[i-1][j-1];
itmp = i - 1;
jtmp = j - 1;
flag = 1;
}
if (map[i+1][j-1] < min)
//WestSouth
{
min = map[i+1][j-1];
itmp = i + 1;
jtmp = j - 1;
flag = 1;
}
if (flag == 0)
{
return map[i][j];
}
i = itmp;
j = jtmp;
}
else if (i==map.length-1)
//at the top of the array
{
int flag = 0;
int itmp = i;
int jtmp = j;
if (map[i][j+1] < min)
//East
{
min = map[i][j+1];
itmp = i;
jtmp = j + 1;
flag = 1;
}
if (map[i-1][j] < min)
//North
{
min = map[i-1][j];
itmp = i - 1;
jtmp = j;
flag = 1;
}
if (map[i][j-1] < min)
//West
{
min = map[i][j-1];
jtmp = j-1;
itmp = i;
flag = 1;
}
if (map[i-1][j-1] < min)
//NorthWest
{
min = map[i-1][j-1];
itmp = i - 1;
jtmp = j - 1;
flag = 1;
}
if (map[i-1][j+1] < min)
//NorthEast
{
min = map[i-1][j+1];
itmp = i - 1;
jtmp = j + 1;
flag = 1;
}
if (flag == 0)
{
return map[i][j];
}
i = itmp;
j = jtmp;
}
else
{
int flag = 0;
int itmp = i;
int jtmp = j;
if (map[i+1][j] < min)
//South
{
min = map[i+1][j];
itmp= i + 1;
jtmp = j;
flag = 1;
}
if (map[i][j+1] < min)
//East
{
min = map[i][j+1];
jtmp = j+1;
itmp = i;
flag = 1;
}
if (map[i-1][j] < min)
//North
{
min = map[i-1][j];
itmp = i - 1;
jtmp = j;
flag = 1;
}
if (map[i][j-1] < min)
//West
{
min = map[i][j-1];
itmp = i;
jtmp = j-1;
flag = 1;
}
if (map[i+1][j+1] < min)
//EastSouth
{
min = map[i+1][j+1];
itmp = i+1;
jtmp = j+1;
flag = 1;
}
if (map[i-1][j-1] < min)
//NorthWest
{
min = map[i-1][j-1];
itmp = i - 1;
jtmp = j - 1;
flag = 1;
}
if (map[i-1][j+1] < min)
//NorthEast
{
min = map[i-1][j+1];
itmp = i - 1;
jtmp = j + 1;
flag = 1;
}
if (map[i+1][j-1] < min)
//WestSouth
{
min = map[i+1][j-1];
itmp = i + 1;
jtmp = j - 1;
flag = 1;
}
if (flag == 0)
{
return map[i][j];
}
i = itmp;
j = jtmp;
}
}
}
}
----------------------------------------------------------------------------------------------
Other method
-------------------------------------------
public static int ballRestElevation(int[][] map) {
int col = 1;
int row = 1;
int now = map[1][1];
int up = map[1][1];
int down = map[1][1];
int left = map[1][1];
int right = map[1][1];
int min = now;
int[] nextPosition = new int[5];
while (true){
int count = 0;
nextPosition[0] = map[row][col];
nextPosition[1] = map[row-1][col];
nextPosition[2] = map[row+1][col];
nextPosition[3] = map[row][col-1];
nextPosition[4] = map[row][col+1];
int index = 0;
for(int i=0; i<5; i++){
if (nextPosition[i] < min){
min = nextPosition[i];
index = i;
}
}
for(int j=0; j<5; j++){
if(nextPosition[j] == min){
count++;
}
}
if(count >= 2){
return min;
}
else{
if (index == 0){
return nextPosition[index];
}
if (index == 1){
row--;
}
if (index == 2){
row++;
}
if (index == 3){
col--;
}
if (index == 4){
col++;
}
}
}
}
}
--------------------------------------------------------------------------------------------
MapAnd2DArrayHomeworkTest.java
-----------------------------------------------------
import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import java.util.ArrayList;
import java.util.HashMap;
import org.junit.Test;
@SuppressWarnings("javadoc")
public class MapAnd2DArrayHomeworkTest {
@Test
public void testBallRestElevation() {
int[][] array1 = {
{9,9,9,9,9,9},
{9,8,5,4,9,9},
{9,7,9,9,9,9},
{9,7,5,2,2,9},
{9,9,9,9,9,9}};
assertEquals(4,MapAnd2DArrayHomework.ballRestElevation(array1));
int[][] array3 = {
{9,9,9,9,9,9},
{9,8,9,4,1,9},
{9,7,9,9,2,9},
{9,6,5,4,3,9},
{0,9,9,9,9,9}};
assertEquals(1,MapAnd2DArrayHomework.ballRestElevation(array3));
int[][] array2 = {
{9,9,9,9,9,9},
{9,8,6,4,9,9},
{9,5,9,9,9,9},
{9,5,5,2,2,9},
{9,9,9,9,9,9}};
assertEquals(5,MapAnd2DArrayHomework.ballRestElevation(array2));
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.