Orthogonal Triangle
Orthogonal Triangle solutionunknown
java
4 years ago
5.5 kB
11
Indexable
import java.io.File; // Import the File class
import java.io.FileNotFoundException; // Import this class to handle errors
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner; // Import the Scanner class to read text files
public class Orthogonal_Triangle {
private int[][] matrix;
private int rows, cols;
private ArrayList < Integer > sums;
/**
* Default constructor that initializes an empty integer matrix
* @param rows Number of rows
* @param cols Number of columns
*/
public Orthogonal_Triangle(int rows, int cols) {
// Create new integer matrix
matrix = new int[rows][cols];
this.rows = rows;
this.cols = cols;
// Create array list for sums
sums = new ArrayList < Integer > ();
// Fill matrix with minus 1s so it is empty
for (int i = 0; i < this.rows; i++) {
for (int j = 0; j < this.cols; j++) {
matrix[i][j] = -1;
}
}
}
public static void main(String[] args) {
Orthogonal_Triangle ot = new Orthogonal_Triangle("filename.txt", " ");
ot.print();
ot.traverse(0, 0, 0);
System.out.println("Maximum = " + ot.getMax());
}
/**
* Constructor that reads file and creates integer matrix with given data
* @param filename File name
* @param seperator Seperator to split string into values
*/
public Orthogonal_Triangle(String filename, String seperator) {
// Get number of lines in file
Path path = Paths.get(filename);
long lines = 0;
try {
lines = Files.lines(path).count();
} catch (IOException e) {
e.printStackTrace();
}
// Determine rows and cols by number of lines
this.rows = (int) lines;
this.cols = (int) lines;
// Create matrix
matrix = new int[rows][cols];
// Create array list for sums
sums = new ArrayList < Integer > ();
// Fill matrix with minus 1s so it is empty
for (int i = 0; i < this.rows; i++) {
for (int j = 0; j < this.cols; j++) {
matrix[i][j] = -1;
}
}
// Read file and fill matrix with given data
try {
File myObj = new File(filename);
Scanner myReader = new Scanner(myObj);
int i = 0;
while (myReader.hasNextLine()) {
String data = myReader.nextLine();
String[] arrOfStr = data.split(seperator);
int j = 0;
for (String a: arrOfStr) {
matrix[i][j] = Integer.parseInt(a);
j++;
}
i++;
}
myReader.close();
} catch (FileNotFoundException e) {
System.out.println("An error occurred.");
e.printStackTrace();
}
}
/**
* Simple print method for integer matrix
*/
public void print() {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] != -1)
System.out.print(matrix[i][j] + " ");
}
System.out.print("\n");
}
}
/**
* Check if a number is prime or not
* @param number Number to check
* @return Status of being number prime
*/
private boolean isPrime(int number) {
boolean result = true;
// Zero and one are not prime
if (number == 0 || number == 1)
result = false;
for (int i = 2; i <= number / 2; i++) {
if (number % i == 0)
result = false;
}
return result;
}
/**
* Traverses in integer matrix downward and digonally, calculates sum of numbers
* @param x Position of x
* @param y Position of y
* @param total Sum of numbers
*/
public void traverse(int x, int y, int total) {
// Base case: if it is last row in matrix
if (x == rows - 1) {
sums.add(total + matrix[x][y]);
} // Base case: if all three downward and diagonal adjacents are prime
else if ((y - 1 >= 0 && isPrime(matrix[x + 1][y - 1])) && isPrime(matrix[x + 1][y]) && (y + 1 <= x + 1 && isPrime(matrix[x + 1][y + 1]))) {
sums.add(total + matrix[x][y]);
} else {
// Traversing left diagonal
if (y - 1 >= 0)
if (!isPrime(matrix[x + 1][y - 1]))
traverse(x + 1, y - 1, total + matrix[x][y]);
// Traversing downward
if (!isPrime(matrix[x + 1][y]))
traverse(x + 1, y, total + matrix[x][y]);
// Traversing right diagonal
if (y + 1 <= x + 1 && !isPrime(matrix[x + 1][y + 1]))
if (!isPrime(matrix[x + 1][y + 1]))
traverse(x + 1, y + 1, total + matrix[x][y]);
}
}
/**
* Returns maximum integer value in a collection.
* @return Maximum value
*/
public int getMax() {
Integer max = Collections.max(sums);
return max;
}
}Editor is loading...