In Java: (10 pts) Suppose you want to find the best west-east route across this

Question

In Java:

(10 pts) Suppose you want to find the best west-east route across this terrain. We’ll define the “best” route as one that minimizes your cumulative elevation change across the route. By “cumulative elevation change,” I mean the sum of all individual changes over all steps of the route, not just the difference between your starting and ending points. Here’s a simple algorithm that tries to accomplish this:

a. Start from the minimum-elevation point on the western edge of the terrain.

b. Move east one column at a time. Each time you do this, you will have three choices (northeast, due east, or southeast), as sketched below.

This is an example of a greedy algorithm – it always makes what appears to be the best choice at each step. Since our goal here is to minimize the cumulative elevation change across the entire route, the algorithm always picks the direction that results in the lowest change from the current position. Greedy algorithms sometimes (but not always) result in the best overall solution.

Complete the findPath(int[][] a) method in the code. This method should implement the greedy algorithm above using the data in the array a. It should return a 1D array containing the row indices of each point on the resulting path, heading west to east. In the example above, the returned array would be {1, 2, 2} (since 2972 is in row 1, 2959 is in row 2, 2913 is in row 2).

3011 2900 2852 2972 2937 2886 3137 2959 2913 Current position 2972 options for next position 2900 ONE, elevation change 72) 2937 CE, elevation change 35) 2959 (SE, elevation change 130 To determine which way to go, pick the option that results in the lowest elevation change (which could be an increase or decrease in elevation). In this example, 2959 has the least elevation change, so we head southeast from 2972. If two or more ions give the smallest elevation change, pick any of them. In this example, following the algorithm gives the path below: 3011 2900 2852 2972 2937 2886 3137 2959 2913

Explanation / Answer

/**
* GUI application to read and visualize elevation data.
* Starting point for HW 5.
*
*/

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.io.*;
import java.util.ArrayList;
import java.util.Scanner;

public class ElevationVisualizer extends JFrame
{

// panel that displays the elevation data
private class DisplayPanel extends JPanel
{
private int[][] data; // elevation data stored in a 2D array
private int[] path; // path data - element i in this array corresponds to the row of
// column i that should be chosen to try to minimize elevation differences
  
public void setData(int[][] data)
{
this.data = data;
}
  
public void setPath(int[] path)
{
this.path = path;
}

// overrides the Swing paintComponent method -- defines how to draw this panel
public void paintComponent(Graphics g)
{
if (dataLoaded)
{
int max = findMax(data);
for (int r = 0; r < data.length; r++) // each pixel on the panel = 1 value in the data array
{
for (int c = 0; c < data[r].length; c++)
{
int h = (int)((double)data[r][c]/max*255); // lighter = higher, darker = lower
g.setColor(new Color(h, h, h));
g.drawRect(c, r, 1, 1);
}
}
}
  
if (pathRequested)
{
for (int i = 0; i < path.length; i++)
{
g.setColor(Color.GREEN);
g.drawRect(i, path[i], 1, 1);
}
}
}
}

// event handler for button presses
private class ButtonHandler implements ActionListener
{
public void actionPerformed(ActionEvent e) // gets called whenever an "action event" (e.g., button press) occurs
{
Object src = e.getSource();
if (src == bLoadFile)
chooseFile();
else if (src == bFindPath)
findPath();
}
}
  
private DisplayPanel pDisplay = new DisplayPanel();
private JButton bLoadFile = new JButton("Load new data file"),
bFindPath = new JButton("Find a path");
private JLabel lStatus = new JLabel("Use the Load button to open a data file");
private boolean dataLoaded = false, // has the user loaded map data yet?
pathRequested = false; // has the user requested a path yet?
  
// constructor - handles GUI construction tasks
public ElevationVisualizer()
{
ButtonHandler bh = new ButtonHandler(); // register event handler for buttons
bLoadFile.addActionListener(bh);
bFindPath.addActionListener(bh);
  
JPanel cp = new JPanel(); // content pane
cp.setLayout(new BorderLayout());
  
JPanel bp = new JPanel(); // panel to hold load/path buttons
bp.setLayout(new GridLayout(1, 2));
bp.add(bLoadFile);
bp.add(bFindPath);
  
cp.add(BorderLayout.NORTH, lStatus);
cp.add(BorderLayout.CENTER, pDisplay);
cp.add(BorderLayout.SOUTH, bp);
  
setDefaultCloseOperation(EXIT_ON_CLOSE);
setTitle("Elevation Data Visualizer");
setContentPane(cp);
setSize(600, 600);
setVisible(true);
}
  
// opens a file chooser dialog to read elevation data, and calls
// readElevationData to import that data into the application
private void chooseFile()
{
JFileChooser fc = new JFileChooser();
fc.setCurrentDirectory(new File("."));
int returnVal = fc.showOpenDialog(this);
  
if (returnVal == JFileChooser.APPROVE_OPTION)
{
File f = fc.getSelectedFile();
try
{
pDisplay.setData(readElevationData(f));
dataLoaded = true;
pathRequested = false;
repaint(); // triggers the paintComponent method to be called
lStatus.setText(f.getName() + " successfully opened!");
}
catch (FileNotFoundException e)
{
lStatus.setText("Can't find " + f.getName());
}
catch (ArrayIndexOutOfBoundsException e)
{
lStatus.setText(f.getName() + " seems to have inconsistent rows and columns");
}
catch (NumberFormatException e)
{
lStatus.setText(f.getName() + " seems to contain non-integer data");
}
}
}
  

// **** COMPLETE THIS METHOD ****
// reads elevation data from the specified file into a 2-D array
// returns the array created
// throws: FileNotFoundException if file isn't found
// ArrayIndexOutOfBoundsException if each row in the file doesn't have the same number of columns
// NumberFormatException if file contains non-integer data
private int[][] readElevationData(File f) throws FileNotFoundException, ArrayIndexOutOfBoundsException, NumberFormatException
{
  
BufferedReader input=new BufferedReader(new InputStreamReader(new FileInputStream(f)));
try
{
String data=input.readLine();
Scanner scr=new Scanner(data);
ArrayList<Integer> arr=new ArrayList<Integer>();
while(scr.hasNext())
{
arr.add(scr.nextInt());
}
int mat[][]=new int[arr.size()][arr.size()];
for(int i=0;i<mat.length;i++)
{
mat[0][i]=arr.get(i);
}
int count=1;
while(input.ready())
{
Scanner in=new Scanner(input.readLine());
for(int i=0;i<mat.length;i++)
{
mat[count][i]=in.nextInt();
}
count++;
}
return mat;
}
catch (IOException e)
{
System.out.println(e.getMessage());
}
  
return null;
}

private void findPath()
{
if (!dataLoaded)
lStatus.setText("Can't find path yet, must load a data file first!");
else
{
pDisplay.setPath(findPath(pDisplay.data));
pathRequested = true;
repaint(); // triggers the paintComponent method to be called
lStatus.setText("West-east path computed!");
}
}

// **** COMPLETE THIS METHOD ****
// finds and returns a west-east path through the area whose elevation is stored in data
private int[] findPath(int[][] data)
{
int arr[]=new int[data.length];
for(int i=0;i<data.length;i++)
{
arr[i]=indexOfMinFromCol(data,i);
}
return arr;
}
  
// **** COMPLETE THIS METHOD ****
// finds and returns the max element from the array a
public static int findMax(int[][] a)
{
int max=-1;
for(int i=0;i<a.length;i++)
{
for(int j=0;j<a[0].length;j++)
{
if(a[i][j]>max)
max=a[i][j];
}
}
return max;
}
  
// **** COMPLETE THIS METHOD ****
// finds and returns the index of the min element from column c of the array a
public static int indexOfMinFromCol(int[][] a, int c)
{
int min=0;
for(int i=1;i<a.length;i++)
{
if(a[i][c]<a[min][c])
min=i;
}
return min;
}
  
public static void main(String[] args)
{
new ElevationVisualizer();
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.