CodeMonkey CodeMonkey - 3 months ago 6
Javascript Question

Sorting a series of Tickets

This is the problem statement,

You've a bunch of tickets in a stack with departures and destinations. You're given a departure city and a destination city. How can you find from the stack your route.
This is my solution,

"use strict";


function app(){

var stack = [];
var one = new Ticket('London', 'NYC');
var two = new Ticket('Barcelona', 'Athens');
var three = new Ticket('Rio', 'ND');
var four = new Ticket('NYC', 'Barcelona');
var five = new Ticket('Athens', 'Rio');
var six = new Ticket('ND', "Lahore");
stack.push(one);
stack.push(two);
stack.push(three);
stack.push(four);
stack.push(five);
stack.push(six);

var res = sortDestinations(stack, 'London', 'Lahore');
for(var city in res){
console.out(res[city]);
}

}
function Ticket(departure, destination){

this.departure = departure;
this.destination = destination;
}

Ticket.prototype.getDeparture = function(){
return this.departure;
}

Ticket.prototype.getDestination = function(){
return this.destination;
}


function sortDestinations(stack, dep, dest){
var map = {};
for(var i= 0; i<stack.length; i++){
var ticket = stack.pop();
map[ticket.getDeparture()] = ticket.getDestination();
}
var res = [];
var curr = dep;
res.push(curr);

while(true){
if(curr == dest) {
break;
}
var next = map[curr];
res.push(next);
curr = next;
}

}

app();


This program goes into an infinite loop. When I debug I see that the curr variable is undefined. Can someone help me solve the problem. I'm rank new to Javascript.

Answer

I was debugging your code for a while and finally identified the reason for infinite loop. Since you are pop-ing from stack, length of stack keep decreasing and that of i increasing and the loop stops before completion. And your while loop keep looping since curr is never going to equal to dept because map does not contain London.

Change this

for(var i= 0; i<stack.length; i++){
    var ticket = stack.pop();
    map[ticket.getDeparture()] = ticket.getDestination();
}

To

while(stack.length>0){
    var ticket = stack.pop();
    map[ticket.getDeparture()] = ticket.getDestination();
}
Comments