Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.Random;
- public class Tree {
- // Variable
- ArrayList < ArrayList <Integer> > matrix;
- // Constructor
- Tree(){
- matrix = new ArrayList < ArrayList <Integer> > ();
- }
- // Methods
- public void showStatus() {
- for(int i=0; i<matrix.size(); i++) {
- for(int j=0; j<matrix.get(i).size(); j++) {
- System.out.print(matrix.get(i).get(j) + " ");
- }
- System.out.println();
- }
- }
- public void fillWithElements() {
- // First, I have to consider about the size of the matrix
- // This will be also the size of each sub-matrix
- // I want this to be 5 <= size <= 8
- Random random = new Random();
- int size = random.nextInt(4) + 5;
- // First, I have to fill up my "big" list matrix with sub-matrices, that are lists/elements.
- for(int i=0; i<size; i++) {
- ArrayList <Integer> listElement = new ArrayList <Integer> ();
- matrix.add(listElement);
- }
- // Now, I am free to create
- for(int i=0; i<size; i++) {
- for(int j=0; j<size; j++) {
- // The variable "matrix.get(i)" is instance of list type
- matrix.get(i).add(random.nextInt(100));
- }
- }
- }
- public int findIndexOfFirstElement() {
- int min = matrix.get(0).get(0);
- int index = 0;
- for(int i=1; i<matrix.get(0).size(); i++) {
- if(matrix.get(0).get(i) < min) {
- min = matrix.get(0).get(i);
- index = i;
- }
- }
- return index;
- }
- public int findIndexOfNextElement(int indexI, int indexJ) {
- int sizeX = matrix.size();
- int sizeY = matrix.get(indexI).size();
- // Be careful to put "%" in the arguments of "get" instruction, in order to avoid overflow
- int first = matrix.get((indexI+1) % sizeX).get((indexJ-1) % sizeY);
- int second = matrix.get((indexI+1) % sizeX).get((indexJ) % sizeY);
- int third = matrix.get((indexI+1) % sizeX).get((indexJ+1) % sizeY);
- // Check the minimum of these 3 elements
- if(first <= second && first <= third) {
- return indexJ-1;
- }
- else if(second <= first && second <= third) {
- return indexJ;
- }
- else {
- return indexJ+1;
- }
- }
- public static ArrayList <Integer> findASmallPath(){
- ArrayList <Integer> indeces = new ArrayList <Integer> ();
- ArrayList <Integer> path = new ArrayList <Integer> ();
- // First, I select the first element
- int firstIndex = findIndexOfFirstElement();
- indeces.add(firstIndex);
- for(int i=0; i<matrix.size()-1; i++) {
- int indexIPlus1 = findIndexOfNextElement(i, indeces.get(i));
- indeces.add(indexIPlus1);
- }
- /*
- int secondIndex = findIndexOfNextElement(0, indeces.get(0));
- indeces.add(secondIndex);
- int thirdIndex = findIndexOfNextElement(1, indeces.get(1));
- indeces.add(thirdIndex);
- int fourthIndex = findIndexOfNextElement(2, indeces.get(2));
- indeces.add(fourthIndex);
- int fifthIndex = findIndexOfNextElement(3, indeces.get(3));
- indeces.add(fifthIndex);
- */
- for(int i=0; i<indeces.size(); i++) {
- path.add(matrix.get(i).get(indeces.get(i)));
- }
- return path;
- }
- // MAIN FUNCTION
- public static void main(String[] args) {
- // TODO Auto-generated method stub
- Tree tree = new Tree();
- tree.fillWithElements();
- System.out.println("**** Our Matrix is: ****");
- System.out.println();
- tree.showStatus();
- ArrayList <Integer> path = findASmallPath();
- for(int i=0; i<path.size(); i++) {
- if(i != path.size() - 1) {
- System.out.print(path.get(i) + " ----> ");
- }
- else {
- System.out.print(path.get(i));
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement