StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>It's basically a dependency graph where every ticket represents a node and the <strong>src</strong> and <strong>dst</strong> airport represents directed links, so use a topological sort to determine the flight order.</p> <p>EDIT: Although since this is an airline ticket and you know you actually made an itinerary you could physically perform, sort by departure date and time in UTC.</p> <p>EDIT2: Assuming each airport you have a ticket to uses a three character code, you can use the algorithm described here (<a href="https://stackoverflow.com/questions/3003021/find-three-numbers-appeared-only-once-using-bit-manipulation/3003112#3003112">Find three numbers appeared only once</a>) to determine the two unique airports by xoring all the airports together. </p> <p>EDIT3: Here's some C++ to actually solve this problem using the xor method. The overall algorithm is as follows, assuming a unique encoding from airport to an integer (either assuming a three letter airport code or encoding the airport location in an integer using latitude and longitude):</p> <p>First, XOR all the airport codes together. This should be equal to the initial source airport XOR the final destination airport. Since we know that the initial airport and the final airport are unique, this value should not be zero. Since it's not zero, there will be at least one bit set in that value. That bit corresponds to a bit that is set in one of the airports and not set in the other; call it the designator bit.</p> <p>Next, set up two buckets, each with the XORed value from the first step. Now, for every ticket, bucket each airport according to whether it has the designator bit set or not, and xor the airport code with the value in the bucket. Also keep track for each bucket how many source airports and destination airports went to that bucket.</p> <p>After you process all the tickets, pick one of the buckets. The number of source airports sent to that bucket should be one greater or less than the number of destination airports sent to that bucket. If the number of source airports is less than the number of destination airports, that means the initial source airport (the only unique source airport) was sent to the other bucket. That means the value in the current bucket is the identifier for the initial source airport! Conversely, if the number of destination airports is less than the number of source airports, the final destination airport was sent to the other bucket, so the current bucket is the identifier for the final destination airport!</p> <pre><code>struct ticket { int src; int dst; }; int get_airport_bucket_index( int airport_code, int discriminating_bit) { return (airport_code & discriminating_bit)==discriminating_bit ? 1 : 0; } void find_trip_endpoints(const ticket *tickets, size_t ticket_count, int *out_src, int *out_dst) { int xor_residual= 0; for (const ticket *current_ticket= tickets, *end_ticket= tickets + ticket_count; current_ticket!=end_ticket; ++current_ticket) { xor_residual^= current_ticket->src; xor_residual^= current_ticket->dst; } // now xor_residual will be equal to the starting airport xor ending airport // since starting airport!=ending airport, they have at least one bit that is not in common // int discriminating_bit= xor_residual & (-xor_residual); assert(discriminating_bit!=0); int airport_codes[2]= { xor_residual, xor_residual }; int src_count[2]= { 0, 0 }; int dst_count[2]= { 0, 0 }; for (const ticket *current_ticket= tickets, *end_ticket= tickets + ticket_count; current_ticket!=end_ticket; ++current_ticket) { int src_index= get_airport_bucket_index(current_ticket->src, discriminating_bit); airport_codes[src_index]^= current_ticket->src; src_count[src_index]+= 1; int dst_index= get_airport_bucket_index(current_ticket->dst, discriminating_bit); airport_codes[dst_index]^= current_ticket->dst; dst_count[dst_index]+= 1; } assert((airport_codes[0]^airport_codes[1])==xor_residual); assert(abs(src_count[0]-dst_count[0])==1); // all airports with the bit set/unset will be accounted for as well as either the source or destination assert(abs(src_count[1]-dst_count[1])==1); assert((src_count[0]-dst_count[0])==-(src_count[1]-dst_count[1])); int src_index= src_count[0]-dst_count[0]<0 ? 0 : 1; // if src < dst, that means we put more dst into the source bucket than dst, which means the initial source went into the other bucket, which means it should be equal to this bucket! assert(get_airport_bucket_index(airport_codes[src_index], discriminating_bit)!=src_index); *out_src= airport_codes[src_index]; *out_dst= airport_codes[!src_index]; return; } int main() { ticket test0[]= { { 1, 2 } }; ticket test1[]= { { 1, 2 }, { 2, 3 } }; ticket test2[]= { { 1, 2 }, { 2, 3 }, { 3, 4 } }; ticket test3[]= { { 2, 3 }, { 3, 4 }, { 1, 2 } }; ticket test4[]= { { 2, 1 }, { 3, 2 }, { 4, 3 } }; ticket test5[]= { { 1, 3 }, { 3, 5 }, { 5, 2 } }; int initial_src, final_dst; find_trip_endpoints(test0, sizeof(test0)/sizeof(*test0), &initial_src, &final_dst); assert(initial_src==1); assert(final_dst==2); find_trip_endpoints(test1, sizeof(test1)/sizeof(*test1), &initial_src, &final_dst); assert(initial_src==1); assert(final_dst==3); find_trip_endpoints(test2, sizeof(test2)/sizeof(*test2), &initial_src, &final_dst); assert(initial_src==1); assert(final_dst==4); find_trip_endpoints(test3, sizeof(test3)/sizeof(*test3), &initial_src, &final_dst); assert(initial_src==1); assert(final_dst==4); find_trip_endpoints(test4, sizeof(test4)/sizeof(*test4), &initial_src, &final_dst); assert(initial_src==4); assert(final_dst==1); find_trip_endpoints(test5, sizeof(test5)/sizeof(*test5), &initial_src, &final_dst); assert(initial_src==1); assert(final_dst==2); return 0; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload