fork download
copy 
  1. import java.lang.Math;
  2. import java.util.*;
  3.  
  4. public class SaveIntegers
  5. {
  6.   public static int[][] timeArray;
  7.  
  8.   public static void main(String[] args)
  9.   {
  10.     // Test Case 1
  11.     //int[][] times = {{0, 1, 1, 1, 1}, {1, 0, 1, 1, 1}, {1, 1, 0, 1, 1}, {1, 1, 1, 0, 1}, {1, 1, 1, 1, 0}};
  12.     //int time_limit = 3;
  13.  
  14.     // Test Case 2
  15.     //int[][] times = {{0, 2, 2, 2, -1}, {9, 0, 2, 2, -1}, {9, 3, 0, 2, -1}, {9, 3, 2, 0, -1}, {9, 3, 2, 2, 0}};
  16.     //int time_limit = 1;
  17.  
  18.     // Infinite Loop Test 1
  19.     //int[][] times = {{0, 2, 2, 2, -1}, {9, -1, 2, 2, -1}, {9, 3, 0, 2, -1}, {9, 3, 2, 0, -1}, {9, 3, 2, 2, 0}};
  20.     //int time_limit = 3;
  21.  
  22.     // Infinite Loop Test 2
  23.     //int[][] times = {{0, 9, 9, 9, 3}, {9, 0, 9, 1, 9}, {1, 9, 0, 9, 9}, {9, 9, -5, 0, 9}, {9, -2, 9, 9, 0}};
  24.     //int time_limit = 3;
  25.  
  26.     // lots of looping
  27.     int[][] times = {{0, 0, 0, 0, 0}, {1, 0, 9, 9, 9}, {1, 9, 0, 9, 9}, {1, 9, 9, 0, 9}, {0, 9, 9, 9, 0}};
  28.     int time_limit = 8;
  29.  
  30.     timeArray = times;
  31.     List<Integer> savedBunnies = new ArrayList<Integer>();
  32.  
  33.     //Search for time-gaining infinite loops. Return all if found.
  34.     if(findTimeGainingInfiniteLoop())
  35.     {
  36.       System.out.println("Infinite loops!");
  37.       //add all bunnies (none at start or bulkhead)
  38.       for (int i = 0; i < timeArray.length - 2; i++)
  39.       {
  40.         savedBunnies.add(i);
  41.       }
  42.     }
  43.     else
  44.     {
  45.  
  46.       //TODO: can this get integrated into findBestPath?
  47.       //List<List<Integer>> escapePaths = findAllMinLengthPaths(0, timeArray.length - 1, new ArrayList<Integer>());
  48.       //if (getDistanceFromPath(escapePaths.get(0)) <= time_limit)
  49.       //{
  50.         //Can't even save yourself!
  51.         //System.out.println("Can't even save yourself!");
  52.       //}
  53.  
  54.       List<Integer> bestPath = findBestPath(0, timeArray.length - 1, time_limit, new ArrayList<Integer>());
  55.       System.out.println("Best path: " + Arrays.toString(bestPath.toArray()));
  56.       savedBunnies = getSavedBunniesFromPath(bestPath);
  57.     }
  58.  
  59.     System.out.println("Saved bunnies: " + Arrays.toString(savedBunnies.toArray()));
  60.   }
  61.  
  62.   public static Boolean findTimeGainingInfiniteLoop()
  63.   {
  64.     for (int i = 0; i < timeArray.length; i++)
  65.     {
  66.       for (int j = 0; j < timeArray[i].length; j++)
  67.       {
  68.         if (i == j && timeArray[i][j] < 0)
  69.         {
  70.           //System.out.println("location " + i + " can loop itself for infinite time!");
  71.           return true;
  72.         }
  73.         if (timeArray[i][j] < 0)
  74.         {
  75.           // Going from location i to location j adds to the clock!
  76.           // Can we get from j to i in one less time than is added?
  77.           return findPathWithinTime(j, i, (timeArray[i][j] * -1) - 1);
  78.         }
  79.       }
  80.  
  81.     }
  82.     return false;
  83.   }
  84.  
  85.   public static Boolean findPathWithinTime(int start, int finish, int time)
  86.   {
  87.     //System.out.println("Looking for path from " + start + " to " + finish + " below " + time + " excluding " + Arrays.toString(history.toArray()));
  88.     if (timeArray[start][finish] <= time)
  89.     {
  90.       //System.out.println("Found path from " + start + " to " + finish + " under " + time);
  91.       return true;
  92.     }
  93.     if (start == finish)
  94.     {
  95.       //System.out.println("Find path to self: " + start);
  96.       if (time >= 0)
  97.       {
  98.         return true;
  99.       }
  100.       else
  101.       {
  102.         return false;
  103.       }
  104.     }
  105.     List<List<Integer>> minPaths = findAllMinLengthPaths(start, finish, new ArrayList<Integer>());
  106.  
  107.     return getDistanceFromPath(minPaths.get(0)) <= time;
  108.   }
  109.  
  110.   public static List<List<Integer>> findAllMinLengthPaths(int start, int finish, List<Integer> history)
  111.   {
  112.     List<List<Integer>> listOfPaths = new ArrayList<List<Integer>>();
  113.     //System.out.println("Finding paths from " + start + " to " + finish + " excluding " + Arrays.toString(history.toArray()));
  114.     history.add(start);
  115.     List<Integer> directPath = new ArrayList<Integer>(history);
  116.     //Might be able to remove this if/check and always add finish to directPath
  117.     if (!directPath.contains(finish))
  118.     {
  119.       directPath.add(finish);
  120.     }
  121.     listOfPaths.add(directPath);
  122.  
  123.     //for each possible next step, get the min length paths and update listOfPaths
  124.     for (int j = 0; j < timeArray[start].length; j++)
  125.     {
  126.       if (!history.contains(j) && j != finish)
  127.       {
  128.         List<List<Integer>> nextPaths = findAllMinLengthPaths(j, finish, new ArrayList<Integer>(history));
  129.         int nextPathLength = getDistanceFromPath(nextPaths.get(0));
  130.         int currentPathLength = getDistanceFromPath(listOfPaths.get(0));
  131.         if (currentPathLength > nextPathLength)
  132.         {
  133.           //System.out.println("Shorter path from " + start + " to " + finish + ": " + Arrays.toString(nextPaths.get(0).toArray()));
  134.           listOfPaths.clear();
  135.           listOfPaths.addAll(nextPaths);
  136.         }
  137.         if (currentPathLength == nextPathLength)
  138.         {
  139.           listOfPaths.addAll(nextPaths);
  140.         }
  141.       }           
  142.     }
  143.  
  144.     if (listOfPaths.size() > 0)
  145.     {
  146. 		//System.out.println("Found paths from " + start + " to " + finish + " including " + Arrays.toString(listOfPaths.get(0).toArray()));
  147.     }
  148.     else
  149.     {
  150.       System.out.println("Found no paths from " + start + " to " + finish + " shorter than " + Arrays.toString(history.toArray()));
  151.     }
  152.     return listOfPaths;
  153.   }
  154.  
  155.   public static List<Integer> findBestPath(int start, int finish, int time_limit, List<Integer> history)
  156.   {
  157.     List<Integer> targetList = new ArrayList<Integer>(Arrays.asList(0, 1, 0, 2, 0, 3, 0));
  158.     history.add(start);
  159.     if (history.equals(targetList))
  160.     {
  161.       System.out.println("Found solution: " + Arrays.toString(history.toArray()));
  162.     }
  163.     List<Integer> workingPath = new ArrayList<Integer>(history);
  164.     if (workingPath.get(workingPath.size() - 1) != finish)
  165.     {
  166.       workingPath.add(finish);
  167.     }
  168.     //for each possible next step, get the best paths and update workingPath
  169.     for (int j = 0; j < timeArray[start].length; j++)
  170.     {
  171.       if (validMove(j, history))
  172.       {
  173.         if (history.equals(targetList))
  174.         {
  175.         	System.out.println("Calling findBestPath for " + Arrays.toString(history.toArray()) + " to " + j);
  176.         }
  177.         List<Integer> nextPath = findBestPath(j, finish, time_limit, new ArrayList<Integer>(history));
  178.         targetList.add(4);
  179.         if (nextPath.equals(targetList))
  180.         {
  181.         	System.out.println("Now looking at answer " + Arrays.toString(nextPath.toArray()) + ", j: " + j + " history: " + Arrays.toString(history.toArray()));
  182.         }
  183.         int nextPathLength = getDistanceFromPath(nextPath);
  184.         if (nextPath.size() > history.size() + 2)
  185.         {
  186.           System.out.println("Size of " + Arrays.toString(nextPath.toArray()) + " is > 2 more than " + Arrays.toString(history.toArray()));
  187.         }
  188.         if (time_limit >= nextPathLength)
  189.         {
  190.           if (nextPath.equals(targetList))
  191.           {
  192.             System.out.println("Answer valid for " + Arrays.toString(history.toArray()) + " with j: " + j);
  193.           }
  194.           //System.out.println("Length " + nextPathLength + " of " + Arrays.toString(nextPath.toArray()) + " is under " + time_limit);
  195.           List<Integer> currentPathSaved = getSavedBunniesFromPath(workingPath);
  196.           List<Integer> nextPathSaved = getSavedBunniesFromPath(nextPath);
  197.           if (isBetterListOfSavedBunnies(nextPathSaved, currentPathSaved))
  198.           {
  199.             System.out.println("Replacing path " + Arrays.toString(workingPath.toArray()) + " with " + Arrays.toString(nextPath.toArray()));
  200.             workingPath = nextPath;
  201.           }
  202.           //else
  203.           //{
  204.           //  System.out.println("List " + Arrays.toString(nextPathSaved.toArray()) + " isn't better than " + Arrays.toString(currentPathSaved.toArray()));
  205.           //}
  206.         }
  207.         //else
  208.         //{
  209.         //  System.out.println("Length " + nextPathLength + " of " + Arrays.toString(nextPath.toArray()) + " is over " + time_limit);
  210.         //}
  211.       }
  212.       //else
  213.       //{
  214.       //  System.out.println("Invalid move " + j + " on " + Arrays.toString(history.toArray()));
  215.       //}
  216.       //if (j == timeArray[start].length - 1)
  217.       //{
  218.       //  System.out.println("Finishing " + Arrays.toString(history.toArray()) + " and workingPath is " + Arrays.toString(workingPath.toArray()));
  219.       //}
  220.     }
  221.     if (history.equals(targetList))
  222.     {
  223.       System.out.println("Returning answer: " + Arrays.toString(workingPath.toArray()));
  224.     }
  225.  
  226.     return workingPath;        
  227.   }
  228.  
  229.   public static Boolean validMove(int move, List<Integer> history)
  230.   {
  231.     //We've already found infinite loops by standing still. Don't allow others.
  232.     if (move == history.get(history.size() - 1))
  233.     {
  234.       return false;
  235.     }
  236.     //Moving to the bulkhead or start are almost always allowed
  237.     if (move == timeArray.length - 1 || move == 0)
  238.     {
  239.       //Don't allow start-bulkhead infinite loops
  240.       if (history.size() >= 2 &&
  241.         history.get(history.size() - 1) == 0 &&
  242.         history.get(history.size() - 2) == timeArray.length - 1)
  243.       {
  244.         //System.out.println("Rejecting loop: " + Arrays.toString(history.toArray()) + ", move " + move);
  245.         return false;
  246.       }
  247.       return true;
  248.     }
  249.     //Otherwise it's only valid if we haven't already grabbed the bunny
  250.     return !history.contains(move);
  251.   }
  252.  
  253.   public static int getDistanceFromPath(List<Integer> history)
  254.   {
  255.     //System.out.print("Distance of " + Arrays.toString(history.toArray()) + " is ");
  256.     if (history.size() <= 1)
  257.     {
  258.       //System.out.print(0);
  259.       //System.out.println();
  260.       return 0;
  261.     }
  262.     //int historyHash = history.hashCode();
  263.     //if (hmap.containsKey(historyHash))
  264.     //{
  265.     //  System.out.print("hashed as " + hmap.get(historyHash));
  266.     //        System.out.println();
  267.     //  return hmap.get(historyHash);
  268.     //}
  269.     Iterator<Integer> distanceIter = history.iterator();
  270.     int distance = 0, start = distanceIter.next();
  271.     while (distanceIter.hasNext())
  272.     {
  273.       int next = distanceIter.next();
  274.       distance += timeArray[start][next];
  275.       start = next;
  276.     }
  277.     //System.out.print(distance);
  278.     //      System.out.println();
  279.     //hmap.put(historyHash, distance);
  280.     return distance;
  281.   }
  282.  
  283.   public static List<Integer> getSavedBunniesFromPath(List<Integer> history)
  284.   {
  285.     List<Integer> savedBunnies = new ArrayList<Integer>();
  286.     Iterator<Integer> saveIter = history.iterator();
  287.     while (saveIter.hasNext())
  288.     {
  289.       int move = saveIter.next();
  290.       if (move != 0 && move != timeArray.length - 1)
  291.       {
  292.         savedBunnies.add(move-1);
  293.       }
  294.     }
  295.     //System.out.println("Saved " + Arrays.toString(savedBunnies.toArray()) + " from " + Arrays.toString(history.toArray()));
  296.     return savedBunnies;
  297.   }
  298.  
  299.   public static Boolean isBetterListOfSavedBunnies(List<Integer> firstBunnyList, List<Integer> secondBunnyList)
  300.   {
  301.     if (firstBunnyList.size() == secondBunnyList.size())
  302.     {
  303.       for (int i = 0; i < firstBunnyList.size(); i++)
  304.       {
  305.         if (firstBunnyList.get(i) < secondBunnyList.get(i))
  306.         {
  307.           System.out.println("Better " + Arrays.toString(firstBunnyList.toArray()) + " than " + Arrays.toString(secondBunnyList.toArray()));
  308.           return true;
  309.         }
  310.         else if (firstBunnyList.get(i) > secondBunnyList.get(i))
  311.         {
  312.           System.out.println("Worse " + Arrays.toString(firstBunnyList.toArray()) + " than " + Arrays.toString(secondBunnyList.toArray()));
  313.           return false;
  314.         }
  315.       }
  316.     }
  317.     else
  318.     {
  319.       if (firstBunnyList.size() > secondBunnyList.size())
  320.       {
  321.         System.out.println("Better size " + Arrays.toString(firstBunnyList.toArray()) + " than " + Arrays.toString(secondBunnyList.toArray()));
  322.       }
  323.       else
  324.       {
  325.         System.out.println("Worse size " + Arrays.toString(firstBunnyList.toArray()) + " than " + Arrays.toString(secondBunnyList.toArray()));
  326.       }
  327.       return firstBunnyList.size() > secondBunnyList.size();
  328.     }
  329.     //System.out.println("Equal " + Arrays.toString(firstBunnyList.toArray()) + " and " + Arrays.toString(secondBunnyList.toArray()));
  330.     // equal lists
  331.     return false;
  332.   }
  333. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:4: error: class SaveIntegers is public, should be declared in a file named SaveIntegers.java
public class SaveIntegers
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/6tUVMY
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!