1
\$\begingroup\$

Here is my Javascript solution to the following problem:

Given an un-ordered list of flights taken by someone compute the person's itinerary, given a starting airport.

If none valid itinerary, return none. If more than one journey is valid, print any valid solution.

Examples

Array: [['SFO', 'HKO'], ['YYZ', 'SFO'], ['YUL', 'YYZ'], ['HKO', 'ORD']]
Starting: 'YUL'
Return: ['YUL', 'YYZ', 'SFO', 'HKO', 'ORD'].
Array: [['SFO', 'COM'], ['COM', 'YYZ']] 
Starting airport 'COM'
Return None
Array: [['A', 'B'], ['A', 'C'], ['B', 'C'], ['C', 'A']] 
Starting: 'A'
Return ['A', 'B', 'C', 'A', 'C']

Please can someone comment on readability and efficiency of the code

Thank you

function plan_journey(place, journeys, route, itinerary){
    if(journeys.length == 0){
        itinerary.push(route + place) 
    }
    let stops = []
    for(i=0; i<journeys.length; i++){
        if(journeys[i][0] == place){
            stops.push(i)
        }
    }
    if(stops == []){
        return 
    }

    for(var i=0; i<stops.length; i++){
        let slice_index = stops[i]
        let remaining_journeys = journeys.slice(0,slice_index).concat(journeys.slice(slice_index + 1))
        let new_route = route + place + "-"
        let next_place = journeys[stops[i]][1]
        plan_journey(next_place, remaining_journeys, new_route, itinerary) 
    }    
    return itinerary
}

let first_stop = "A"
let journeys = [['A', 'B'], ['A', 'C'], ['B', 'C'], ['C', 'A']] 
itinerary = plan_journey(first_stop, journeys, "", [])
if(itinerary.length != 0){
    console.log(itinerary[0])
}else{
    console.log("None")
}
\$\endgroup\$
2
\$\begingroup\$

Your current implementation is a brute force method, that has some hefty space performance problems (you are copying large parts of the journey every step of the way). Note that both the runtime and space costs are exponential in the worst case in this form.

This problem can be solved more elegantly through some of graph theory. First we note that every location has to be entered the same number of times as it is leaved, except the end and start points which counts as an extra leaving and entry respectively. If this isn't the case then there is no solution, and if it is the case we are guaranteed for there to be a solution. To find such a solution we can separate the locations into places that have only one way to enter and leave, and then the rest (remember that we have already identified our endpoint based on which place had one place less to leave). For those will multiple ways through, we need to find enough cycles that passes through other locations to have it returned to being a one pass in and out, such that we can have a route enter it, go through the cycles and then leave through the remaining exit. The algorithm then is as follows:

  1. Calculate the order (amount of flights entering and leaving) of each location.
  2. Determine if it is possible to solve and identify the ending location.
  3. Start from the starting point and go through any combination of journeys until you reach the end location (there is no way to screw yourself over on this one).
  4. While there are still journeys left untaken, connect them in separate cycles, by just starting at any one of its locations and walk until you get back to the starting location.
  5. Combine the results from results from step 3 and 4, by injecting the cycles from step 4 as parts of other routes when those other routes reach a location in such a cycle. Repeat this until there is only one route left, that is the result.

There are different ways to implement this, mainly based on how you deal with storing the information of the journeys, routes and locations. It should be possible to implement the above algorithm in such a way that it only require \$O(E)\$ runtime and extra space, with \$E\$ being the number of journeys.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.