Java solution to CodeChef "Surgical Strikes" challenge

Question

I've just recently completed this programming "challenge" called surgical strikes:

\$N\$ Indian Air Force fighter planes are located in different bases across the country. Each airbase is described by some integer coordinate \$(x,y)\$. The Air Force plans to do surgical strikes on a maximum of \$M\$ different targets in enemy territory (which are also described by cartesian coordinates) and then come back to the common main airbase at coordinate (baseX,baseY).

Each army base and the targets are recognised by a secret integer ID. The time taken for an aircraft to go from a base to a target is the prime factor of the Manhattan Distance between the base and the target that is just greater than the ID of the source base (In case the ID is greater than or equal to the largest prime factor, then consider the ID itself). Similarly, the time taken for an aircraft to go from a target to the main base is the prime factor of the Manhattan Distance between the target and the main base that is just greater than the ID of the target (In case the ID is greater than or equal to the largest prime factor, then consider the ID itself).

Each Aircraft needs to leave the base, reach target and come back to the main base in a maximum time of T. One aircraft can go to only one target before going to the main base.

Find the maximum number of targets that can be reached in the enemy territory.

Here's my solution, which is also on GitHub. I'm coming here looking for suggestions on how I can improve my conventions, structure, and etc.

package me.charlesmgrube.airforce_model;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class Application {
 private ArrayList<Location> targets = new ArrayList<Location>();
 private ArrayList<Location> bases = new ArrayList<Location>();
 private Location mainBase;
 private int numBases = 0;
 private int numTargets = 0;
 private int maxTime = 0;
 public void run() {
 BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
 boolean running = true;
 ArrayList<String> data = new ArrayList<String>();
 while (running) {
 String read = null;
 try {
 read = bfr.readLine();
 } catch (IOException e) {
 e.printStackTrace();
 }
 
 if(data.size() != maxInputLines()) {
 data.add(read);
 
 if(data.size() == 1) {
 String[] split = read.split(" ");
 numBases = Integer.parseInt(split[0]);
 numTargets = Integer.parseInt(split[1]);
 maxTime = Integer.parseInt(split[2]);
 }
 } else {
 running = false;
 break;
 }
 }
 
 for(int i = 0; i < data.size() ; i++) {
 if(i == 0) continue;
 if(i <= numBases) {
 String[] split = data.get(i).split(" ");
 int x = Integer.parseInt(split[0]);
 int y = Integer.parseInt(split[1]);
 int id = Integer.parseInt(split[2]);
 bases.add(new Location(x, y, id));
 } else if (i > numBases && i <= numTargets+numBases) {
 String[] split = data.get(i).split(" ");
 int x = Integer.parseInt(split[0]);
 int y = Integer.parseInt(split[1]);
 int id = Integer.parseInt(split[2]);
 targets.add(new Location(x, y, id));
 } else {
 String[] split = data.get(i).split(" ");
 int x = Integer.parseInt(split[0]);
 int y = Integer.parseInt(split[1]);
 mainBase = new Location(x, y, -1);
 }
 }
 
 ArrayList<Integer> times = new ArrayList<Integer>();
 for(int x = 0; x < bases.size(); x++) {
 int quickestTime = -1;
 for(int y = 0; y < targets.size(); y++) {
 int time = timeElapsed(bases.get(x), targets.get(y)) + timeElapsed(targets.get(y), mainBase);
 if(time < quickestTime || quickestTime==-1) {
 quickestTime = time;
 }
 }
 times.add(quickestTime);
 }
 
 times.sort(Comparator.naturalOrder());
 int num = 0;
 int totalTime = 0;
 for(int i = 0; i < times.size(); i++) {
 if(totalTime + times.get(i) <= maxTime) {
 num++;
 totalTime += times.get(i);
 }
 }
 
 System.out.println(num);
 }
 
 private int timeElapsed(Location loc1, Location loc2) {
 int manhattanDistance = Math.abs(loc2.getX() - loc1.getX()) + Math.abs(loc2.getY() - loc1.getY());
 List<Integer> factors = primeFactorization(manhattanDistance);
 factors.sort(Comparator.naturalOrder());
 int factor = -1;
 for(int i = 0; i < factors.size(); i++) {
 if(factors.get(i) > loc1.getId()) {
 factor = i;
 }
 }
 if(factor == -1) factor = loc1.getId();
 return 0;
 }
 private List<Integer> primeFactorization(int n) {
 int num = n;
 ArrayList<Integer> factors = new ArrayList<Integer>();
 for (int i = 2; i < num; i++) {
 while (num % i == 0) {
 factors.add(i);
 num /= i;
 }
 }
 if (num > 1) {
 factors.add(num);
 }
 return factors;
 }
 private int maxInputLines() {
 return numTargets + numBases + 2;
 }
 public static void main(String[] args) {
 new Application().run();
 }
}

Location class:

package me.charlesmgrube.airforce_model;
public class Location {
 private int x;
 private int y;
 private int id;
 
 public Location(int x, int y, int id) {
 this.x = x;
 this.y = y;
 this.id = id;
 }
 public int getX() {
 return x;
 }
 public void setX(int x) {
 this.x = x;
 }
 public int getY() {
 return y;
 }
 public void setY(int y) {
 this.y = y;
 }
 public int getId() {
 return id;
 }
 public void setId(int id) {
 this.id = id;
 }
 
}

Answer 1

Referential immutability

You don't reassign your lists - targets and bases - so make them final.

Type weakening

So far as I can see, you aren't doing anything in your class that requires reference to the ArrayList methods of targets and bases. You should weaken them to Collection, or maybe List depending on some of your index-dependent loops. Also, omit the generic type during construction. So:

private final Collection<Location> targets = new ArrayList<>();
private final Collection<Location> bases = new ArrayList<>();
// ...
Collection<Integer> times = new ArrayList<>();

Loop sanitization

This should go away if possible:

for(int i = 0; i < data.size() ; i++) {

Just use three separate loops, i.e.

int i = 1;
for (; i <= numBases; i++) // ...
for (; i <= numTargets + numBases; i++) // ...
for (; i < data.size(); i++) // ...

and these:

 for(int x = 0; x < bases.size(); x++) {
 for(int y = 0; y < targets.size(); y++) {

should just be

for (Location base: bases) {
 for (Location target: targets) {

and

for(int i = 0; i < times.size(); i++) {

should just be

for (Integer time: times) {

Class methods

This:

private int timeElapsed(Location loc1, Location loc2) {
 int manhattanDistance = Math.abs(loc2.getX() - loc1.getX()) + Math.abs(loc2.getY() - loc1.getY());
 List<Integer> factors = primeFactorization(manhattanDistance);
 factors.sort(Comparator.naturalOrder());
 int factor = -1;
 for(int i = 0; i < factors.size(); i++) {
 if(factors.get(i) > loc1.getId()) {
 factor = i;
 }
 }
 if(factor == -1) factor = loc1.getId();
 return 0;
}

definitely belongs as a method on Location, either static accepting two locations, or where loc1 is implied as this.

Make primeFactorization a static method.

Location mutability

Your habit is to do the "standard Java thing" and make set methods for all of your members - but you should really only do so if you need to mutate your locations, which you absolutely don't. Delete all of your set methods.

You should also make a convenience constructor on Location that accepts a String and does this code for you:

 String[] split = data.split(" ");
 int x = Integer.parseInt(split[0]);
 int y = Integer.parseInt(split[1]);
 int id = Integer.parseInt(split[2]);

• Sharon Ben Asher: what's the advantages of making variables final?
• Reinderien: Good question! Adding final allows the Java optimizer additional opportunities to optimize. Also, it makes your code more predictable and testable - if a thing is guaranteed to never change during its lifetime, you don't need to test it for changes.
• charlesgrube: thank you sm for the answer! I am curious though, why should I get rid of generic type in my construction and weaken the type to Collection?
• Reinderien: Lose repetition of the generic type for brevity. Weaken your type so that you can change the implementation of a data structure without having to change the code that uses it. There's a principle in object oriented programming where code that uses a class should have the minimum amount of knowledge and access to that class.