travelTickets.js

// travel tickets
// Output order of travels, from start to end

var cities = 'Seattle, San Francisco, Austin, New York, Los Angeles, Portland, Chicago, Shanghai'.split(', ');
var count = 150;
var trip = [];
for (var i = 0; i < count; i++) {
	var start = pickRand(cities);
	var end = pickRand(cities);
	while (end === start) {
		end = pickRand(cities)
	}
	trip.push({
		start: start,
		end: end
	});

}
function pickRand(arry) {
	return arry[rand(arry.length)];
}
function rand(n) {
	return Math.floor(Math.random()*n);
}

console.log(trip);
console.log('\n\n');

// var trip = [{
//     start: 'Seattle',
//     end: 'San Fransisco',
// },{
//     start: 'Austin', // ticket
//     end: 'New York',
// },{
//     start: 'New York',
//     end: 'Seattle',
// }];

function sortTickets(tickets) {
	var maxLoops = 5;
    var sources = {};
    var destinations = {};
    
    var ticket;
    for (var i = 0; i < tickets.length; i++) {
        ticket = tickets[i];
    	ticket.id = i;
    	if (sources[ticket.end]) {
    		sources[ticket.end].push(ticket);
    	} else {
    		sources[ticket.end] = [ticket];
    	}
    	
    	if (destinations[ticket.start]) {
        	destinations[ticket.start].push(ticket);
    	} else {
    		destinations[ticket.start] = [ticket];
    	}
    }
    
    
    // console.log('Sources:', JSON.stringify(sources, null, 2));
    // console.log('\n\n\n\n\n')
    // console.log('Destinations', JSON.stringify(destinations, null, 2));
    // return;

    var head   = tickets[0]
    head.head = true;
    var sorted = [head];
    var seen = {};

    var curr = head;
    while (curr && destinations[curr.end] && !seen[curr.id]) {
    	curr.used = true;
    	seen[curr.id] = true;
    	curr = destinations[curr.end].pop();
    	if (curr) {
			sorted.push(curr); 
    	}
    }
    
    seen[head.id] = false;

    curr = head;
    while (curr && sources[curr.start] && !seen[curr.id]) {
    	curr.used = true;
    	seen[curr.id] = true;
        curr = sources[curr.start].pop();
        if (curr) {
        	sorted.unshift(curr); 
        }
    }

    return sorted;
}

console.log(sortTickets(trip));
console.log('\n\n\n');
console.log(trip.filter(n => !n.used).length);
console.log('\n\n\n');

console.log(sortTickets(trip.filter(n => !n.used)));