[JavaScript Quiz #16] Smallest number of flights

Consider you have a set of places (CAI, FRA, MAD, NYC, SFO) and there are available flights between some of these destinations as shown below.

CAI -> FRA
FRA -> MAD
MAD -> NYC
CAI -> MAD
NYC -> SFO
FRA -> CAI
MAD -> FRA

Design and develop a JavaScript function that can get the shortest possible path from a destination X to destination Y if there is any.
.
.
.
.
.
.
.
.
.
.
.
.
.
In order to develop a JavaScript function which can get the shortest path between two destinations, first of all, we need to think about the proper data structure which can represent these places and the connections between them. If we think about it, we will find that these placed can be represented as nodes and the connections between these places can be represented as edges which is typically a Graph. We can represent this Graph as a 2D N X N array as shown below.

    CAI FRA MAD NYC SFO
CAI  0   1   1   0   0
FRA  1   0   1   0   0
MAD  0   1   0   1   0
NYC  0   0   0   0   1
SFO  0   0   0   0   0

The previous matrix can be translated to the following JavaScript code.

var mapping = {
    "CAI": 0,
    "FRA": 1,
    "MAD": 2,
    "NYC": 3,
    "SFO": 4
};

var routeGraph = 
[
    [0, 1, 1, 0, 0],
    [1, 0, 1, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0]    
];

After make the proper representation, we need to think about how to get the shortest path between any two nodes in this unweighted graph. Since this graph is unweighted, we can use directly BFS (Breath First Search) in order to get the shortest path. For more information about BFS, check: https://en.wikipedia.org/wiki/Breadth-first_search.

In order to implement BFS, there are some notes for our implementation below:

  1. We utilized the Queue data structure for storing the nodes in a first-in, first-out (FIFO) style, we explore the oldest unexplored nodes first. Thus our explorations radiate out slowly from the starting node, defining a breadth-first search.
  2. In order to keep track of the shortest path, we have a JavaScript map nodeParent object which stores the first visited parent of the current visited node.
  3. Finally, when the search finds the destination then we construct the final path from the nodeParent object and stores it in the finalPath array.

The code below shows our BFS implementation in order to get the shortest path between the start and destination nodes.

var ShortestPathFinder = function() {
}

ShortestPathFinder.find = function (start, destination) {
    var visited = {}; // A map containing all of the visited nodes ...
    var nodeParent = {}; // An map containing the node parents ...
    var queue = [start], i, found = false, finalPath = [], neighbours = [];    
    
    nodeParent[start] = null;
    
    var current = queue.shift();
    
    while ((neighbours = ShortestPathFinder.getNeighbours(current)) != null) {
    
        for (i = 0; i < neighbours.length; ++i) {
            
            // If we find the destination then exit these loops ...
            if (neighbours[i] == destination) {
                found = true;
                nodeParent[neighbours[i]] = current;
                break;
            }
        
            if (! visited[neighbours[i]]) {
                
                // Mark this node as "visited" ...
                visited[neighbours[i]] = true;
            
                // Add element to the queue ...
                queue.push(neighbours[i]);
                nodeParent[neighbours[i]] = current;
            }
        }
        
        if (queue.length == 0) {
            break;
        }
        
        current = queue.shift();
    }
    
    if (! found) {
        console.error("No path is found between " + start + " and " + destination);
        
        return null;
    }
    
    // Construct the final path from the node parent map ...
    current = destination;
    
    finalPath.push(destination);
    
    while (nodeParent[current] != start) {
        finalPath.push(nodeParent[current]);
        
        current = nodeParent[current];
    }
    
    finalPath.push(start);    
    
    return finalPath.reverse();
}

In order to get the neighbours of the current node, a simple function is implemented to get the neighbours from the routeGraph matrix as follows.

ShortestPathFinder.getNeighbours = function(current) {
    var currentIndex = mapping[current], i, result = [];
    
    for (i = 0; i < routeGraph[currentIndex].length; ++i) {
        if (routeGraph[currentIndex][i] == 1) {
            result.push(mapping.getKey(i));
        }
    }
    
    return result;
}

Finally, we can test our developed JavaScript function by having the following test cases.

console.log(ShortestPathFinder.find("CAI", "NYC"));
console.log(ShortestPathFinder.find("CAI", "SFO"));
console.log(ShortestPathFinder.find("FRA", "NYC"));
console.log(ShortestPathFinder.find("SFO", "CAI"));
console.log(ShortestPathFinder.find("MAD", "CAI"));

Below is the output of the console.

["CAI", "MAD", "NYC"]
["CAI", "MAD", "NYC", "SFO"]
["FRA", "MAD", "NYC"]
No path is found between SFO and CAI
null
["MAD", "FRA", "CAI"]

Attached below, the complete solution code for your reference, if you have comments or a better solution, feel free to comment below.

/*
CAI -> FRA
FRA -> MAD
MAD -> NYC
CAI -> MAD
NYC -> SFO
FRA -> CAI
MAD -> FRA

    CAI FRA MAD NYC SFO
CAI  0   1   1   0   0
FRA  1   0   1   0   0
MAD  0   1   0   1   0
NYC  0   0   0   0   1
SFO  0   0   0   0   0
*/

var mapping = {
    "CAI": 0,
    "FRA": 1,
    "MAD": 2,
    "NYC": 3,
    "SFO": 4
};

var routeGraph = 
[
    [0, 1, 1, 0, 0],
    [1, 0, 1, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0]    
];

Object.prototype.getKey = function(value){
  for(var key in this){
    if(this[key] == value){
      return key;
    }
  }
  return null;
};


var ShortestPathFinder = function() {
}

ShortestPathFinder.find = function (start, destination) {
    var visited = {}; // A map containing all of the visited nodes ...
    var nodeParent = {}; // An map containing the node parents ...
    var queue = [start], i, found = false, finalPath = [], neighbours = [];    
    
    nodeParent[start] = null;
    
    var current = queue.shift();
    
    while ((neighbours = ShortestPathFinder.getNeighbours(current)) != null) {
    
        for (i = 0; i < neighbours.length; ++i) {
            
            // If we find the destination then exit these loops ...
            if (neighbours[i] == destination) {
                found = true;
                nodeParent[neighbours[i]] = current;
                break;
            }
        
            if (! visited[neighbours[i]]) {
                
                // Mark this node as "visited" ...
                visited[neighbours[i]] = true;
            
                // Add element to the queue ...
                queue.push(neighbours[i]);
                nodeParent[neighbours[i]] = current;
            }
        }
        
        if (queue.length == 0) {
            break;
        }
        
        current = queue.shift();
    }
    
    if (! found) {
        console.error("No path is found between " + start + " and " + destination);
        
        return null;
    }
    
    // Construct the final path from the node parent map ...
    current = destination;
    
    finalPath.push(destination);
    
    while (nodeParent[current] != start) {
        finalPath.push(nodeParent[current]);
        
        current = nodeParent[current];
    }
    
    finalPath.push(start);    
    
    return finalPath.reverse();
}

ShortestPathFinder.getNeighbours = function(current) {
    var currentIndex = mapping[current], i, result = [];
    
    for (i = 0; i < routeGraph[currentIndex].length; ++i) {
        if (routeGraph[currentIndex][i] == 1) {
            result.push(mapping.getKey(i));
        }
    }
    
    return result;
}

console.log(ShortestPathFinder.find("CAI", "NYC"));
console.log(ShortestPathFinder.find("CAI", "SFO"));
console.log(ShortestPathFinder.find("FRA", "NYC"));
console.log(ShortestPathFinder.find("SFO", "CAI"));
console.log(ShortestPathFinder.find("MAD", "CAI"));

[JavaScript Quiz #15] All possible compositions of a number

Today’s JavaScript quiz is about finding all the possible compositions of a number. For example if we have a number 4, we would like to find all the possible compositions that sums up to 4 as follows.

1111
112
121
13
211
22
31
4

.
.
.
.
.
.
.
.
.
.
.
.
.
In order to develop this utility, it is important to understand its nature. For a number n, it has the following possible compositions:
n (for a composition length of 1)
1 n-1 (for a composition length of 2)
1 1 n-2 (for a composition of length 3)

1 1 1 … 1 (for a composition of length n)

This can be handled using recursive function as follows.

function compositions(n, temp, output) {
    var i, newTemp;
    
    if (n == 0) {
        output.push(temp);
    } else {
        for (i = 1; i <= n; ++i) {
            newTemp = temp + i;
            
            compositions(n - i, newTemp, output);
        }
    }
}

As shown, the base is if n is equal to 0 then we add the temp string (which is initialized to "") to the output list, else we subtract i from n and adds i to the temp string. The following function getAllCompositions calls compositions with the initial values.

function getAllCompositions(n) {
    var out = [];
    
    compositions(n, "", out);
    
    return out;
}

Finally, we can test getAllCompositions as follows.

// Test ...
var num = 4;
var out = getAllCompositions(num), i;

console.log("Compositions number for (" + num + ") = " + out.length);
for (i = 0; i < out.length; ++i) {
	console.log(out[i]);
}

The output will be:

Compositions number for (4) = 8
    
1111 
112 
121  
13 
211  
22  
31  
4

If you have a better solution, feel free to put in the comments below. The current solution complexity is n!.

[JavaScript Quiz #14] Number Text Representation

Today’s JavaScript quiz is about creating a Number to String utility. Assume that we have the following numbers as an input to our utility:

23
1999
199999
1000000999

Our JavaScript utility should output the following results:

twenty three
one thousand nine hundreds ninety nine
one hundred ninety nine thousand nine hundred ninety nine
one billion nine hundred ninety nine

.
.
.
.
.
.
.
.
.
.
.
.
.
In order to develop this utility, it is important to break-down this problem into small sub-problems and then solve each of them individually. For example, if we wish to print numbers from 0 to 9, this is an easy Job, just create an array that contains the numbers from 0 to 9 and call it digits as follows.

digits = ["zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"];

If we want to print numbers from 10 to 19, we can create another array that represents teens as follows:

teens = ["ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"];

Then if we want to print numbers from 20 up to 99, we can create another array that represents tys as follows.

tys = ["twenty", "thirty", "fourty", "fifty", "sixty", "seventy", "eighty", "ninety"];

But for numbers from 20 to 99, how can we utilize the previous array for printing their values, if we think little about it, we will find that a number like 39 is about 30 + 9 which will produce at the end "thirty nine". But how to divide a number like 39 to 30 + 9 and get its corresponding text representation, simply this can be done by performing three steps:

  1. Dividing 39 (or generally numbers from 20 to 99) by 10 (Integer Division), and then subtract 2 from the result number in order to pick its text representation "thirty" from its corresponding array (tys array).
  2. Having the mod of 39 (or generally numbers from 20 to 99) and 10 which will give us 9, and then we can get simply pick its text representation "nine" from its corresponding array (digits array).
  3. Finally, augment the two text representations to get the final number text representation which is “thirty nine”.

For numbers from 100 up to 999, For example: 205, we can divide it 205 by 100 to know how many hundred units does it has (2 hundreds) and then have the reminder of this number 205 with 100 which is 5 and “five” representation can be got simply using the previous mentioned procedures. Let’s look into the code which can get the text representation of numbers from 0 to 999.

NumberReader.prototype.readThreeDigitNumber = function(number) { /* 0 ... 999 */
    if (number == 0) {
        return "zero";
    }
    
    var output = "", result, reminder;
    
    if (number > 99) {
        result  = Math.floor(number / 100);
        number = number % 100;
        
        output += this.digits[result] + " hundred";
        
        if (number == 0) {
            return output;
        }
    }
    
    if (number < 10) {
        output = NumberReader.appendToOutput(output, this.digits[number]);    
    } else if (number < 20) {
        output = NumberReader.appendToOutput(output, this.teens[number - 10]);                
    } else {
        result = Math.floor(number / 10);
        reminder = number % 10;
        
        output = NumberReader.appendToOutput(output, this.tys[result - 2]);
        
        if (reminder > 0) {
            output = NumberReader.appendToOutput(output, this.digits[reminder]);
        }
    }
    
    return output;
}

We can apply the same concept with thousands by diving them by 1000 to know the thousands units and having mod with 1000 which can be resolved using the previous procedure. Thankfully, we can apply the same concept with millions and billions as shown below.

NumberReader.prototype.readNumber = function (number) {
    var output = "", result, reminder;
    
    if (number >= 1e9) {
        result = Math.floor(number / 1000000000);
        reminder = number % 1000000000;
        
        output += this.readNumber(result) + " billion " + ((reminder > 0) ? this.readNumber(reminder) : "");
    } else if (number >= 1e6 && number < 1e9) {
        result = Math.floor(number / 1000000);
        reminder = number % 1000000;
        
        output += this.readNumber(result) + " million " + ((reminder > 0) ? this.readNumber(reminder) : "");
    } else if (number >= 1000 && number < 1e6) {
        result = Math.floor(number / 1000);
        reminder = number % 1000;
        
        output += this.readNumber(result) + " thousand " + ((reminder > 0) ? this.readNumber(reminder) : "");
    } else {
        output += this.readThreeDigitNumber(number);
    }
    
    return output;
}

The complete quiz code is shown below.

var NumberReader = function() {
    this.digits = ["zero", "one", "two", "three", "four", "five",
        "six", "seven", "eight", "nine"];

    this.teens = ["ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"];
    
    this.tys = ["twenty", "thirty", "fourty", "fifty", "sixty", "seventy", "eighty", "ninety"];    
}

NumberReader.prototype.readThreeDigitNumber = function(number) { /* 0 ... 999 */
    if (number == 0) {
        return "zero";
    }
    
    var output = "", result, reminder;
    
    if (number > 99) {
        result  = Math.floor(number / 100);
        number = number % 100;
        
        output += this.digits[result] + " hundred";
        
        if (number == 0) {
            return output;
        }
    }
    
    if (number < 10) {
        output = NumberReader.appendToOutput(output, this.digits[number]);    
    } else if (number < 20) {
        output = NumberReader.appendToOutput(output, this.teens[number - 10]);                
    } else {
        result = Math.floor(number / 10);
        reminder = number % 10;
        
        output = NumberReader.appendToOutput(output, this.tys[result - 2]);
        
        if (reminder > 0) {
            output = NumberReader.appendToOutput(output, this.digits[reminder]);
        }
    }
    
    return output;
}

NumberReader.prototype.readNumber = function (number) {
    var output = "", result, reminder;
    
    if (number >= 1e9) {
        result = Math.floor(number / 1000000000);
        reminder = number % 1000000000;
        
        output += this.readNumber(result) + " billion " + ((reminder > 0) ? this.readNumber(reminder) : "");
    } else if (number >= 1e6 && number < 1e9) {
        result = Math.floor(number / 1000000);
        reminder = number % 1000000;
        
        output += this.readNumber(result) + " million " + ((reminder > 0) ? this.readNumber(reminder) : "");
    } else if (number >= 1000 && number < 1e6) {
        result = Math.floor(number / 1000);
        reminder = number % 1000;
        
        output += this.readNumber(result) + " thousand " + ((reminder > 0) ? this.readNumber(reminder) : "");
    } else {
        output += this.readThreeDigitNumber(number);
    }
    
    return output;
}

NumberReader.appendToOutput = function (output, parameter) {
    if (output == "") {
        output += parameter;
    } else {
        output += " " + parameter;
    }
    
    return output;
}

And this is a test code for NumberReader.

// Test our API ...
var numberReader = new NumberReader();

console.log(numberReader.readNumber(1999999999));
console.log(numberReader.readNumber(1000000999));    
console.log(numberReader.readNumber(100000999));        
console.log(numberReader.readNumber(1000999));
console.log(numberReader.readNumber(199999));
console.log(numberReader.readNumber(100000));
console.log(numberReader.readNumber(1999));    
console.log(numberReader.readNumber(9));        
console.log(numberReader.readNumber(999));        
console.log(numberReader.readNumber(193));
console.log(numberReader.readNumber(23));        
console.log(numberReader.readNumber(333));

The output will be:

one million nine hundred ninety nine
one hundred ninety nine thousand nine hundred ninety nine
one hundred thousand 
one thousand nine hundred ninety nine
nine
nine hundred ninety nine
one hundred ninety three
twenty three
three hundred thirty three

[JavaScript Quiz #13] Finding longest common substring of strings

Finding the longest common substring of strings is one of the interesting problems. Assume that we have two JavaScript strings like “ababccd” and “abccw”, Can we write a JavaScript utility function that can find the common substrings of these two strings which is “abcc” in this case.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
One of the possible solutions to this problem is to create a 2D comparison array (of size [First string length][Second string length]) which will hold the comparisons between every character in the first and the second strings. If the character of the first string does not match the second string character then set the array cell to 0.
If we find the first string current character matches the second string current character then set the corresponding array cell to 1 but take care if the upper left diagonal cell of the current cell in the comparison array is greater than 0 then you need set the current cell value to the upper left diagonal cell value + 1 (Upper left diagonal cell refers to the previous character of both strings).

Coding this is very simple and the complexity of this code is O(length of the first string * length of the second string) as follows.

var StringUtils = function() {
}

StringUtils.findLongestCommonSubstring = function(string1, string2) {
	var comparsions = []; //2D array for the char comparsions ...
	var maxSubStrLength = 0;
	var lastMaxSubStrIndex = -1, i, j, char1, char2, startIndex;

	for (i = 0; i < string1.length; ++i) {
		comparsions[i] = new Array();

		for (j = 0; j < string2.length; ++j) {
			char1 = string1.charAt(i);
			char2 = string2.charAt(j);

			if (char1 === char2) {
				if (i > 0 && j > 0) {
					comparsions[i][j] = comparsions[i - 1][j - 1] + 1;
				} else {
					comparsions[i][j] = 1;
				}
			} else {
				comparsions[i][j] = 0;
			}

			if (comparsions[i][j] > maxSubStrLength) {
				maxSubStrLength = comparsions[i][j];
				lastMaxSubStrIndex = i;
			}
		}
	}

	if (maxSubStrLength > 0) {
		startIndex = lastMaxSubStrIndex - maxSubStrLength + 1;

		return string1.substr(startIndex, maxSubStrLength);
	}

	return null;
}

// Test code
console.log(StringUtils.findLongestCommonSubstring("ababccd", "abccx"));
console.log(StringUtils.findLongestCommonSubstring("ababccd", "ccxaba"));
console.log(StringUtils.findLongestCommonSubstring("becooltopeople", "topeoplebecool"));    
console.log(StringUtils.findLongestCommonSubstring("ababccd", "zzzz")); 

As shown in the implementation, we store two main items, the maximum common substring length and its last index and thankfully using JavaScript substr function, we can get the desired common substring string. The output will be as follows.

abcc
aba
topeople
null

Finally, note that if you have two longest substrings then this code will get the first of them.

JavaScript Quiz #12

Assume that we have the following short JavaScript code:

<script>
    var number = 50;
    var obj = {
        number: 60,
        getNum: function () {
	    var number = 70;
	    return this.number;
	}
    }; 

    alert(obj.getNum());
    alert(obj.getNum.call());
    alert(obj.getNum.call({number:20}));
</script> 

Will this code succeed or fail? and if it succeeds, what is the output of the alerts?

Read the complete answer

JavaScript Quiz #7

Assume that we have the following short JavaScript code:

<script>
    var result = typeof("Hello" instanceof String);
    alert(result); //What is the output of the alert? 
	
    result = typeof typeof("Hello" instanceof String);
    alert(result); //What is the output of the alert? 
	
    result = typeof typeof typeof("Hello" instanceof String);
    alert(result); //What is the output of the alert? 	
</script>

What is the output of each alert?

Know the complete answer