/* Author: Denise Roßberg Date: 03.03.2019 Program: Travelling in Sololand Challenge created by michal (see comments) Update: 05.03.2019 Rework of the whole code Input a number >= 5. TRAVELLING IN SOLOLAND In Sololand there are N cities which are located along a long road in a row. Let's number the cities 1 to N from the left to the right. There are at least 5 cities in Sololand. Mr. Henry Milton is a travelling salesman. He travels across countries selling various things. Now he is in the city number 1 and would like to visit each city exactly once and return back to the city 1. Many people don't like travelling salesmen because they often sell low quality goods and when they know one is coming, they rather stay at home. However, Mr. H. Milton is not such (but people don't know that), he sells books about coding, too. Hence, he would like to make his journey not so regular and predictable. More precisely, he wants to move from city a to city b if and only if their distance |b-a| is a prime number. (If he doesn't stop in a city, it isn't counted as visited.) Help Mr. H. Milton find any such journey or announce that there is no solution. The length of the journey does not matter. Examples: n = 5 output: 1 3 5 2 4 1 distance: 2 2 3 2 3 n = 12 output: 1 3 5 7 2 4 6 9 11 8 10 12 1 distance: 2 2 2 5 2 2 3 3 3 2 2 11 */ import java.util.ArrayList; import java.util.Scanner; public class Travel{ private ArrayList cities; private ArrayList forward; private ArrayList backward; private int n; public Travel(int n){ cities = new ArrayList<>(); forward = new ArrayList<>(); backward = new ArrayList<>(); this.n = n; //cities from 2 to n for(int i = 2; i <= n; i++){ cities.add(i); } //travel starts and ends at 1 forward.add(1); backward.add(1); } //search forward and backward //e.g. n = 7 //1234567 //1 3 ... 6 1 //1 3 5 ... 4 6 1 //1 3 5 7 4 6 1 public int searchForward(){ for(int i = 0; i < cities.size(); i++){ int d = Math.abs(cities.get(i) - forward.get(forward.size()-1)); if(isPrime(d) == true){ int city = cities.get(i); cities.remove(i); return city; } } return -1; } public int searchBackward(){ for(int i = cities.size()-1; i >= 0; i--){ int d = Math.abs(cities.get(i) - backward.get(backward.size()-1)); if(isPrime(d) == true){ int city = cities.get(i); cities.remove(i); return city; } } return -1; } //distance = prime number? public boolean isPrime(int distance){ if(distance == 1 || distance == 0){ return false; } for(int i = 2; i <= Math.sqrt(distance); i++){ if(distance % i == 0){ return false; } } return true; } public void getTravel(){ while(cities.size() != 0){ int search = searchForward(); if(search != -1){ forward.add(search); } search = searchBackward(); if(search != -1){ backward.add(search); } //add the wrong city to prevent an infinity loop //it will corrected in the checkTravel() method if(search == -1 && cities.size() == 1){ backward.add(cities.get(0)); cities.clear(); } } } //travel = forward + reversedBackward public void printTravel(){ //see that all numbers are used //complete travel route = n+1 System.out.println("n = " + n); System.out.println("number of all cities = " + (forward.size()+backward.size()) + " (n + 1)"); System.out.println(); System.out.print("travel route: "); for(int i = 0; i < forward.size(); i++){ System.out.print(forward.get(i) + " "); } for(int i = backward.size()-1; i >= 0; i--){ System.out.print(backward.get(i) + " "); } } //check the solution //right --> print it //false --> find new solution public void checkTravel(){ int d = Math.abs(forward.get(forward.size()-1) - backward.get(backward.size()-1)); if(isPrime(d) == true){ printTravel(); return; } //new route //find a new place for the last number (or the last two numbers) in the backward list int city = backward.get(backward.size()-1); backward.remove(backward.size()-1); newPosition(city); d = Math.abs(forward.get(forward.size()-1) - backward.get(backward.size()-1)); if(isPrime(d) == true){ printTravel(); return; }else{ city = backward.get(backward.size()-1); backward.remove(backward.size()-1); newPosition(city); } d = Math.abs(forward.get(forward.size()-1) - backward.get(backward.size()-1)); if(isPrime(d) == false){ System.out.println("No travel route found."); }else{ printTravel(); } } public void newPosition(int city){ boolean isFound = false; int d = 0; int d2 = 0; for(int i = 0; i < forward.size(); i++){ if(i + 1 < forward.size()){ d = Math.abs(forward.get(i) - city); d2 = Math.abs(forward.get(i+1) - city); } if(isPrime(d) == true && isPrime(d2) == true){ forward.add(i+1, city); isFound = true; break; } } if(isFound == false){ for(int i = 0; i < backward.size(); i++){ if(i + 1 < backward.size()){ d = Math.abs(backward.get(i) - city); d2 = Math.abs(backward.get(i+1) - city); } if(isPrime(d) == true && isPrime(d2) == true){ backward.add(i+1, city); isFound = true; break; } } } if(isFound == false){ System.out.println("No travel route found."); return; } } } public class Program { public static void main(String[] args) { Scanner input = new Scanner(System.in); int n = 0; try{ n = input.nextInt(); }catch(Exception e){ System.out.println("Please input a number >= 5."); return; } if(n < 5){ System.out.println("Please input a number >= 5."); return; } Travel route = new Travel(n); route.getTravel(); route.checkTravel(); input.close(); } }

travelling in sololand