This past week my wife, our granddaughters and I returned from a holiday trip to Europe. We visited several cities in Italy, Belgium and Amsterdam. We flew commercial airlines to move between large cities. This made me think of airplane routes and filling up the tanks with fuel. For efficiency reasons airplanes do not get refueled on each stop if it can be avoided. Depending on the part of the world you travel to, airplanes have minimum amounts of fuel they must have on board when they takeoff. The amount depends on the distance to the next stop. I know a few things about the subject because I flew for fun private planes for a few years. For personal reasons (wife and family) I decided to stop.
Let’s assume that planes fly different routes that end up on different cities.
Let’s also assume that the final destination is considered an outgoing route. A route may have none (besides the final city on the outgoing route), one or more stops. When the route is completed, the plane needs to fly back home. On the way back the plane may make none, one or more stops. The incoming route will in some cases be the same while in other would be different. For efficiency (refueling takes time and in occasions the plane needs to be on specific gates or by specific pumps) the round trips should be long enough to land with a minimum amount of fuel as dictated by laws and regulations.
The airline company in question has a set of outgoing and incoming routes from each airport they service. The goal of the exercise if to fly an outgoing route and an incoming one from a specific airport which should not exceed the minimum amount of fuel needed in the tanks when returning home. For simplicity the amount of fuel is associated with miles flown.
We need to determine if a plane with a maximum flying capacity, expressed in miles, will be able to service a set of outgoing and incoming routes given the maximum number of miles associated with the plane and the set of outgoing and incoming routes in questions. The airline needs this computation to make sure that different types of planes are able to be assigned different routes at the start of the day. By the end of the day, all planes based on an airport, need to return home and readied for the next day.
On a separate topic, last night I was thinking about a few articles I read regarding security and SCADA (Supervisory Control and Data Acquisition). There was one that called my attention as far as how possible it would be to implement. I thought the article was in Communications of the ACM so I checked it this morning and could not find it. I checked on Twitter and could not find the article. It must have been on Google news.
What bothered me was a picture and associated description on how a hacker 
replaced a resistor (which has two connections) with a micro CPU which needs power and access to data. That requires at least a dozen connections. On top of that what happens to the original circuit when the resistor in question is removed? The designers put it there to reduce current or drop voltage. How can a CPU handle such condition? I was planning on finding the article and sending these and other questions to the author. I guess I will not.
Let’s get back to the topic of this post.
I apologize for the lack of detail on the white board but my board is not large enough and the full code did not fit in it. In addition while I was using the IDE to write the actual code, I decided to explore different scenarios (e.g., return all the routes that were not optimal) that might be useful in case the code would be used in an actual application.
/*
* Build a list of optimal routes for a plane given its range.
*/
public class Solution {
// **** ****
static final boolean REMOVE_NON_OPTIMAL = false;
/*
* Test scaffolding.
*/
public static void main(String[] args) {
// **** ****
ArrayList<ArrayList<Integer>> outgoingRoutes = new ArrayList<ArrayList<Integer>>();
ArrayList<ArrayList<Integer>> incomingRoutes = new ArrayList<ArrayList<Integer>>();
int planeRange = -1;
// **** open scannner ****
final Scanner sc = new Scanner(System.in);
// **** number of outgoing routes ****
int n = sc.nextInt();
// **** populate outgoing routes ****
for (int i = 0; i < n; i++) {
// **** route number ****
int r = sc.nextInt();
// **** distance ****
int distance = sc.nextInt();
// **** ****
ArrayList<Integer> route = new ArrayList<>();
route.add(r);
route.add(distance);
outgoingRoutes.add(route);
}
// ???? ????
System.out.println("main <<< outgoingRoutes: " + outgoingRoutes.toString());
// **** number of incoming routes ****
n = sc.nextInt();
// **** populate incoming routes ****
for (int i = 0; i < n; i++) {
// **** route number ****
int r = sc.nextInt();
// **** distance ****
int distance = sc.nextInt();
// **** ****
ArrayList<Integer> route = new ArrayList<>();
route.add(r);
route.add(distance);
incomingRoutes.add(route);
}
// ???? ????
System.out.println("main <<< incomingRoutes: " + incomingRoutes.toString());
// **** populate plane range ****
planeRange = sc.nextInt();
// **** close scanner ****
sc.close();
// ???? ????
System.out.println("main <<< planeRange: " + planeRange);
// **** ****
ArrayList<ArrayList<Integer>> routeList = bestRoutes( outgoingRoutes,
incomingRoutes,
planeRange);
// **** display the best routes ****
System.out.println("main <<< routeList: " + routeList.toString());
}
}
Note the Boolean at the start of the code. It will be used to determine if the final results should or should not contain non-optimal solutions. If the flag is set, then if there are non-optimal solutions, the returned routes list would be left empty. If the flag is set, and there are no optimal solutions, then the best non-optimal solution will be present. This could help the user to analyze the condition and come up with an educated approach.
We have to read a list of outgoing and incoming routes. In addition we need to get the maximum range for the plane.
After opening the scanner we get the number of outgoing routes and read them in a loop. Note that each route has a unique number.
The process is repeated with the incoming routes.
Finally the range for the plane is read in.
We now call the bestRoutes() method to determine the optimal routes and display them.
5 1 200 2 300 3 400 4 500 5 600 4 6 150 7 200 8 370 9 400 1000 main <<< outgoingRoutes: [[1, 200], [2, 300], [3, 400], [4, 500], [5, 600]] main <<< incomingRoutes: [[6, 150], [7, 200], [8, 370], [9, 400]] main <<< planeRange: 1000 main <<< routeList: [[5, 9, 1000]]
In this run we see that route [5, 9] is optimal. I decided to leave the distance but it would be simple to eliminate it and just return the route numbers. Once again, the program at this level of understanding, could provide additional info to help the user planning / accepting routes.
5 1 200 2 300 3 400 4 500 5 500 4 6 150 7 200 8 370 9 400 1000 main <<< outgoingRoutes: [[1, 200], [2, 300], [3, 400], [4, 500], [5, 500]] main <<< incomingRoutes: [[6, 150], [7, 200], [8, 370], [9, 400]] main <<< planeRange: 1000 main <<< routeList: [[4, 9, 900], [5, 9, 900]]
In this case no optimal routes were found. Two non-optimal routes with 900 miles were found and displayed. This is because the REMOVE_NON_OPTIMAL flag was set to false;
5 1 200 2 300 3 400 4 500 5 500 4 6 150 7 200 8 370 9 400 1000 main <<< outgoingRoutes: [[1, 200], [2, 300], [3, 400], [4, 500], [5, 500]] main <<< incomingRoutes: [[6, 150], [7, 200], [8, 370], [9, 400]] main <<< planeRange: 1000 main <<< routeList: []
The same set of values as the last case is fed to the program, but in this case we have set the REMOVE_NON_OPTIMAL flag to true. We are setting the flag in the software. Perhaps it would be more adequate to set it as an additional parameter. These are decisions that need to be considered in the architecture, design and implementation cycles. That will also help optimize the production version of the software.
/*
* Select the best route(s) for this plane.
* The outgoing and incoming routes are in monotonically ascending order.
*/
static ArrayList<ArrayList<Integer>> bestRoutes(ArrayList<ArrayList<Integer>> outgoingRoutes,
ArrayList<ArrayList<Integer>> incomingRoutes,
int planeRange) {
// **** ****
ArrayList<ArrayList<Integer>> routes = new ArrayList<ArrayList<Integer>>();
// **** traverse the outgoing routes ****
for (int i = 0; i < outgoingRoutes.size(); i++) {
// **** get the outgoing route ****
ArrayList<Integer> outgoing = outgoingRoutes.get(i);
// // ???? ????
// System.out.println("bestRoutes <<< outgoing: " + outgoing.toString());
// **** extract the outgoing route and range ****
int outRoute = outgoing.get(0);
int outRange = outgoing.get(1);
// // ???? ????
// System.out.println("bestRoutes <<< outRoute: " + outRoute + " outRange: " + outRange); // **** check if the plane is out of range **** if (outRange > planeRange)
break;
// **** traverse the incomming routes ****
for (int j = 0; j < incomingRoutes.size(); j++) {
// **** get the incoming route ****
ArrayList<Integer> incoming = incomingRoutes.get(j);
// // ???? ????
// System.out.println("bestRoutes <<< incoming: " + incoming.toString());
// **** extract the incoming route and range ****
int inRoute = incoming.get(0);
int inRange = incoming.get(1);
// // ???? ????
// System.out.println("bestRoutes <<< inRoute: " + inRoute + " inRange: " + inRange); // **** check if the plane is out of range **** if (outRange + inRange > planeRange) {
// // ???? ????
// System.out.println("bestRoutes <<< outRange + inRange: " + (outRange + inRange) + " > planeRange: " + planeRange);
break;
}
// **** remove previous route (if shorter than this route) ****
routes = removePrevRange( routes,
outRange + inRange);
// // ???? ????
// System.out.println("bestRoutes <<< routes: " + routes.toString());
// **** check if this route is shorter than the best one ****
if ((routes.size() != 0) &&
(outRange + inRange < routes.get(0).get(2)))
continue;
// **** add better route ****
routes = addBetterRoute(routes,
outgoing,
incoming);
// // ???? ????
// System.out.println("bestRoutes <<< routes: " + routes.toString());
}
// // ???? ????
// System.out.println();
}
// // ???? ????
// System.out.println("bestRoutes <<< routes: " + routes.toString());
// **** remove non-optimal routes (if needed) ****
if (REMOVE_NON_OPTIMAL)
routes = removeNonOptimal( routes,
planeRange);
// // ???? ????
// System.out.println("bestRoutes <<< routes: " + routes.toString());
// **** ****
return routes;
}
This method is at the core of the solution. We start by defining an empty list of routes.
The outer loop traverses the outgoing routes. Note that at this point we are interested in developing a good solution so we are pulling and displaying some data that we could remove from the production implementation. Always remember that you or someone else from your team may come back weeks or months later to address issues or most likely enhance the software. Make it easier to maintain by commenting what the code does and how it is doing it!
We check if the outgoing route is too long for the range of the plane and leave the loop. The reason is that the outgoing and incoming routes are in monotonically ascending distance order.
We have an inner loop used to traverse the incoming routes. The planes must return to the base airport. The loop traverses the incoming routes checking if the route is too long. If so the loop exits.
At this point it time, if we are in the inner loop we will remove the previous route if the current route is shorter.
We check if the current route is shorter than the best one and skip it. There is no need to add this route to the list because it is shorter than the current best route.
If we continue in the inner loop is because we need to add the current route as the better route so far to the list.
When we come out of the outer loop we check if we need to remove non-optimal routes. This gives us an empty list is we did not find a single optimal route.
Finally we return the list of selected routes.
Note that the comments that I used to test while design and implementation have been left behind. In production one should remove most (if not all) to make the code readable. Remember that one should enable debug flags to write to the system log when they are set. That provides invaluable help when looking for issues in production code.
/*
* Remove previous range if smaller than the new one.
*/
static ArrayList<ArrayList<Integer>> removePrevRange( ArrayList<ArrayList<Integer>> routes,
int newRange) {
// **** check for empty routes ****
if (routes.size() == 0)
return routes;
// **** ****
ArrayList<Integer> optimalRange = routes.get(0);
// // ???? ????
// System.out.println("removePrevRange <<< optimalRange: " + optimalRange.toString() + " newRange: " + newRange); // **** remove route (if needed) **** if (newRange > optimalRange.get(2))
routes.remove(0);
// **** ****
return routes;
}
This method removes the previous range (larger so far before this new one) in preparation to be replaced by the proper route and range in a following call.
/*
* Add new best route.
*/
static ArrayList<ArrayList<Integer>> addBetterRoute(ArrayList<ArrayList<Integer>> routes,
ArrayList<Integer> outgoing,
ArrayList<Integer> incoming) {
// **** extract the outgoing route and range ****
int outRoute = outgoing.get(0);
int outRange = outgoing.get(1);
// **** extract the incoming route and range ****
int inRoute = incoming.get(0);
int inRange = incoming.get(1);
// **** build new route ****
ArrayList<Integer> route = new ArrayList<Integer>();
// **** populate new route ****
route.add(outRoute);
route.add(inRoute);
route.add(outRange + inRange);
// // ???? ????
// System.out.println("addBetterRoute <<< route: " + route.toString());
// **** add new route ****
routes.add(route);
// **** ****
return routes;
}
This method takes care on inserting the new best route. It does so by creating a list and adding it to the routes list. Note that we are inserting the rout and the distance.
/*
* Remove non-optimal routes.
*/
static ArrayList<ArrayList<Integer>> removeNonOptimal( ArrayList<ArrayList<Integer>> routes,
int planeRange) {
// **** check if routes is empty ****
if (routes.size() == 0)
return routes;
// **** traverse list of routes ****
int i = 0;
do {
// **** get the current route ****
ArrayList<Integer> route = routes.get(i);
// // ???? ????
// System.out.println("removeNonOptimal <<< route: " + route.toString());
// **** if non-optimal then remmove route ****
int range = route.get(2);
if (range < planeRange)
routes.remove(i);
else
i++;
} while (i < routes.size());
// **** ****
return routes;
}
This method removes from the routes the non optimal routes. We needed the routes and their distance so we could manage them. This method deletes all the non-optimal routes.
Hope you fund this exercise interesting. I know I did. I believe it is a good refresher for Lists in Java.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this or any other post in this blog, or if you would like me to help with any phase in the SDLC (Software Development Life Cycle) of a product or service, please do not hesitate and leave me a note below. Requests for help will remain private.
Keep on reading and experimenting. It is the best way to learn and refresh your knowledge!
John
Follow me on Twitter: @john_canessa