Advertisement
makispaiktis

Tree - Trying to find the best path from top to the bottom

Mar 28th, 2020 (edited)
338
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.43 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.Random;
  3.  
  4. public class Tree {
  5.  
  6.     // Variable
  7.     ArrayList < ArrayList <Integer> > matrix;
  8.    
  9.     // Constructor
  10.     Tree(){
  11.         matrix = new ArrayList < ArrayList <Integer> > ();
  12.     }
  13.    
  14.     // Methods
  15.     public void showStatus() {
  16.         for(int i=0; i<matrix.size(); i++) {
  17.             for(int j=0; j<matrix.get(i).size(); j++) {
  18.                 System.out.print(matrix.get(i).get(j) + " ");
  19.             }
  20.             System.out.println();
  21.         }
  22.     }
  23.    
  24.     public void fillWithElements() {
  25.         // First, I have to consider about the size of the matrix
  26.         // This will be also the size of each sub-matrix
  27.         // I want this to be 5 <= size <= 8
  28.         Random random = new Random();
  29.         int size = random.nextInt(4) + 5;
  30.         // First, I have to fill up my "big" list matrix with sub-matrices, that are lists/elements.
  31.         for(int i=0; i<size; i++) {
  32.             ArrayList <Integer> listElement = new ArrayList <Integer> ();
  33.             matrix.add(listElement);
  34.         }
  35.         // Now, I am free to create
  36.         for(int i=0; i<size; i++) {
  37.             for(int j=0; j<size; j++) {
  38.                 // The variable "matrix.get(i)" is instance of list type
  39.                 matrix.get(i).add(random.nextInt(100));
  40.             }
  41.         }
  42.     }
  43.    
  44.     public int findIndexOfFirstElement() {
  45.         int min = matrix.get(0).get(0);
  46.         int index = 0;
  47.         for(int i=1; i<matrix.get(0).size(); i++) {
  48.             if(matrix.get(0).get(i) < min) {
  49.                 min = matrix.get(0).get(i);
  50.                 index = i;
  51.             }
  52.         }
  53.         return index;
  54.     }
  55.    
  56.     public int findIndexOfNextElement(int indexI, int indexJ) {
  57.         int sizeX = matrix.size();
  58.         int sizeY = matrix.get(indexI).size();
  59.         // Be careful to put "%" in the arguments of "get" instruction, in order to avoid overflow
  60.         int first = matrix.get((indexI+1) % sizeX).get((indexJ-1) % sizeY);
  61.         int second = matrix.get((indexI+1) % sizeX).get((indexJ) % sizeY);
  62.         int third = matrix.get((indexI+1) % sizeX).get((indexJ+1) % sizeY);
  63.         // Check the minimum of these 3 elements
  64.         if(first <= second && first <= third) {
  65.             return indexJ-1;
  66.         }
  67.         else if(second <= first && second <= third) {
  68.             return indexJ;
  69.         }
  70.         else {
  71.             return indexJ+1;
  72.         }
  73.     }
  74.    
  75.     public static ArrayList <Integer> findASmallPath(){
  76.         ArrayList <Integer> indeces = new ArrayList <Integer> ();
  77.         ArrayList <Integer> path = new ArrayList <Integer> ();
  78.         // First, I select the first element
  79.         int firstIndex = findIndexOfFirstElement();
  80.         indeces.add(firstIndex);
  81.         for(int i=0; i<matrix.size()-1; i++) {
  82.             int indexIPlus1 = findIndexOfNextElement(i, indeces.get(i));
  83.             indeces.add(indexIPlus1);
  84.         }
  85.        
  86.         /*
  87.         int secondIndex = findIndexOfNextElement(0, indeces.get(0));
  88.         indeces.add(secondIndex);
  89.         int thirdIndex = findIndexOfNextElement(1, indeces.get(1));
  90.         indeces.add(thirdIndex);
  91.         int fourthIndex = findIndexOfNextElement(2, indeces.get(2));
  92.         indeces.add(fourthIndex);
  93.         int fifthIndex = findIndexOfNextElement(3, indeces.get(3));
  94.         indeces.add(fifthIndex);
  95.         */
  96.        
  97.         for(int i=0; i<indeces.size(); i++) {
  98.             path.add(matrix.get(i).get(indeces.get(i)));
  99.         }
  100.         return path;
  101.     }
  102.    
  103.    
  104.     // MAIN FUNCTION
  105.     public static void main(String[] args) {
  106.         // TODO Auto-generated method stub
  107.         Tree tree = new Tree();
  108.         tree.fillWithElements();
  109.         System.out.println("**** Our Matrix is: ****");
  110.         System.out.println();
  111.         tree.showStatus();
  112.         ArrayList <Integer> path = findASmallPath();
  113.         for(int i=0; i<path.size(); i++) {
  114.             if(i != path.size() - 1) {
  115.                 System.out.print(path.get(i) + " ----> ");
  116.             }
  117.             else {
  118.                 System.out.print(path.get(i));
  119.             }
  120.         }
  121.     }
  122.  
  123. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement