UND Travel processes airline tickets. This application is to find the path to redeem miles based on a network of airline partners. The following list shows the network of airline partners saved in the file
airlines.txt.
For example, the partners of Aero Mexico are [Delta, Air Canada, British Airways] and the partners of Air Alaska are [Northwest, Air Canada].
Aero Mexico, Delta, Air Canada, British Airways Air Alaska, Northwest, Air Canada Air Canada, Aero Mexico, Delta, Air Alaska AlohaAir, Quantas Aria, United, Lufthansa Avolar, Northwest, Ocean Air BMI, Northwest British Airways, United, Aero Mexico Canjet, Girjet Delta, Air Canada, Aero Mexico, Ocean Air EVA Air, Northwest, Lufthansa Girjet, Southwest, Canjet, Maxair Lufthansa, United, Aria, EVA Air Maxair, Southwest, Girjet Northwest, Air Alaska, BMI, Avolar, EVA Air Ocean Air, Delta, United, Quantas, Avolar Quantas, United, Ocean Air, AlohaAir Southwest, Girjet, Maxair United, Aria, Lufthansa, Ocean Air, Quantas, British Airways |
Another way to show the network of all airline partners is given next:
Aero Mexico, partners: [Delta → Air Canada → British Airways] Air Alaska, partners: [Northwest → Air Canada] Air Canada, partners: [Aero Mexico → Delta → Air Alaska] AlohaAir, partners: [Quantas] Aria, partners: [United → Lufthansa] Avolar, partners: [Northwest → Ocean Air] BMI, partners: [Northwest] British Airways, partners: [United → Aero Mexico] Canjet, partners: [Girjet] Delta, partners: [Air Canada → Aero Mexico → Ocean Air] EVA Air, partners: [Northwest → Lufthansa] Girjet, partners: [Southwest → Canjet → Maxair] Lufthansa, partners: [United → Aria → EVA Air] Maxair, partners: [Southwest → Girjet] Northwest, partners: [Air Alaska → BMI → Avolar → EVA Air] Ocean Air, partners: [Delta → United → Quantas → Avolar] Quantas, partners: [United → Ocean Air → AlohaAir] Southwest, partners: [Girjet → Maxair] United, partners: [Aria → Lufthansa → Ocean Air → Quantas → British Airways] |
This application is to find the path to redeem miles based on a network of airline partners. For example, the path of the airline mileage starting on Northwest and ending on United is
-
[Northwest, Air Alaska, Air Canada, Aero Mexico, Delta, Ocean Air, United]
-
Northwest, partners: [Air Alaska → BMI → Avolar → EVA Air]
Air Alaska, partners: [Northwest → Air Canada]
Air Canada, partners: [Aero Mexico → Delta → Air Alaska]
Aero Mexico, partners: [Delta → Air Canada → British Airways]
Delta, partners: [Air Canada → Aero Mexico → Ocean Air]
Ocean Air, partners: [Delta → United → Quantas → Avolar]
|
|
|
|
|
import java.util.ArrayList;
import java.util.Scanner;
import java.io.File;
import java.io.IOException;
public class TestAirline {
public static void main( String[ ] args ) {
Scanner scannerToReadAirlines = null;
try {
scannerToReadAirlines = new Scanner( new File( "airlines.txt" ) );
}
catch( IOException e ) {
System.out.println( "Could not connect to file airlines.txt." );
System.exit( 0 );
}
if ( scannerToReadAirlines != null ) {
ArrayList<Airline> airlinesPartnersNetwork = new ArrayList<Airline>( );
Airline newAirline;
String lineFromFile;
String[ ] airlineNames;
// Building the partner network
while( scannerToReadAirlines.hasNext( ) ) {
lineFromFile = scannerToReadAirlines.nextLine( );
airlineNames = lineFromFile.split( ", " );
newAirline = new Airline( airlineNames );
airlinesPartnersNetwork.add( newAirline );
}
// Finding the path
String start = args[0];
String goal = args[1];
ArrayList<String> pathForMiles = new ArrayList<String>( );
ArrayList<String> airlinesVisited = new ArrayList<String>( );
if ( AirlineProblem.canRedeem( start,
goal,
pathForMiles,
airlinesVisited,
airlinesPartnersNetwork ) )
System.out.println( "Path to redeem miles: " + pathForMiles );
else
System.out.println( "Cannot convert miles from " + start + " to " + goal + "." );
}
}
}
|
|
|
|
import java.util.ArrayList;
public class AirlineProblem {
public static boolean canRedeem( String current,
String goal,
ArrayList<String> pathForMiles,
ArrayList<String> airlinesVisited,
ArrayList<Airline> network ) {
if ( current.equals( goal ) ) {
// Base case 1: I have found a path!
pathForMiles.add( current );
return true;
}
else if ( airlinesVisited.contains( current ) )
// Base case 2: I have already been here. Don't go into a cycle.
return false;
else {
// I have not been here and it isn't the goal,
// so check its partners. Now I have been here.
airlinesVisited.add( current );
// Add this to the path.
pathForMiles.add( current );
// Find this airline in the network.
int pos = -1;
int index = 0;
while ( pos == -1 && index < network.size( ) ) {
if ( network.get( index ).getName( ).equals( current ) ) pos = index;
index++;
}
// If not in the network, no partners.
if ( pos == -1 ) return false;
// Loop through partners.
index = 0;
String[ ] partners = network.get(pos).getPartners( );
boolean foundPath = false;
while( !foundPath && index < partners.length ) {
foundPath = canRedeem( partners[index],
goal,
pathForMiles,
airlinesVisited,
network );
index++;
}
if ( !foundPath )
pathForMiles.remove( pathForMiles.size( ) - 1 );
return foundPath;
}
}
}
|
|
|
|
import java.util.ArrayList;
public class Airline {
private String name;
private ArrayList<String> partners;
// pre: data != null, data.length > 0
public Airline( String[ ] data ) {
assert data != null && data.length > 0 : "Failed precondition";
name = data[0];
partners = new ArrayList<String>( );
for( int i = 1; i < data.length; i++ )
partners.add( data[i] );
}
public String[ ] getPartners( ) {
return partners.toArray( new String[ partners.size( ) ] );
}
public boolean isPartner( String name ) {
return partners.contains( name );
}
public String getName( ) {
return name;
}
public String toString( ) {
return name + ", partners: " + partners;
}
}
|
|
Doctor: You’re overweight. Patient: I think I want a second opinion. Doctor: You’re also ugly. |