[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 #13

Assume that we have the following short JavaScript code:

<script>
    var result = 3..valueOf() + (1, 2, 4);
    alert(result);
</script>

Will this code succeed or fail? and if it succeeds, what is the output of the alert?
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
The code will work fine. The final result is 7. Let’s understand why we will have this result. Let’s divide the expression in two parts. In the first part, we have:

3..valueOf()

This expression will work fine because in JavaScript, it is valid to trail decimal points in float numbers, so for example 3 can be represented as 3 or 3.0 or 3. (without having to mention the extra 0 after the decimal dot).
So the expression can be read simply as (3.).valueOf() which will return 3.

The second part is straightforward:

(1, 2, 4)

In order to know the result of this expression, we have to know how expressions work with the comma operator, if we have an expression that contains many comma operators then this expression will be evaluated to the last mentioned value. This means that
(1, 2, 4) will be evaluated to 4.

Adding the first part result to the second part result will result in: 3 + 4 = 7.

JavaScript Quiz #11

Assume that we have the following short JavaScript code:

<script>
    var x = !!"Hello" + (!"world", !!"from here!!");
    
    alert(x);
</script> 

Will this code succeed or fail? and if it succeeds, what is the output of the alert?
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
The code will work fine. The alert will output 2. Let’s understand why we will have this result.

The following sequence of operations occurs:
1. !!"Hello" ==> This operand will be evaluated to !false which will be finally true.
2. (!"world", !!"from here!!") ==> The comma operator evaluates both of its operands (from left to right) and returns the value of the second operand. which means that !!"from here!!" will be returned and will be evaluated to true.
3. As none of the operands is of String type, the + operands will be converted to number which means true + true will be evaluated to 1 + 1 which will equal finally 2.

JavaScript Quiz #10 (Short Quiz)

Assume that we have the following short JavaScript code:

<script>
    var y = 10;

    if (!(x in window)) {
        var x = 10;
    } else {
        ++y;
    }

    alert(x);
    alert(y);
</script>

Will this code succeed or fail? and if it succeeds, what is the output of the alerts?
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
The code will work fine. The alerts will output undefined and 11 in sequence. Let’s understand why we will have these results.

First of all, y variable is created and is assigned to 10 then we will come to the following if condition:

if (!(x in window)) {
    var x = 10;
}

Excluding functions blocks, JavaScript does not support block scopes (such as if or for loop blocks). This means that x which is defined inside the if statement will be available in window scope even if the if branch is not executed at all.
This means that x in window will be evaluated to true which will result that the if branch will not be executed at all. The else branch of the if statement will be executed which will add 1 to the current value of y so it will be 11.

This explains why the final result will be undefined and 11.

JavaScript Quiz #9

Assume that we have the following short JavaScript code which runs on a browser that is ECMA 5 compatible:

<script>
    var x = [1, 2, 3, 4].map(function(x, y) { return x + y } );

    alert(x);
</script>

Will this code succeed or fail? and if it succeeds, what is the output of the alert?
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
The code will work fine. The final result is [1, 3, 5, 7]. Let’s understand why we will have this result. The main idea of the previous expression is to understand how Array.prototype.map works.

According to ECMA documentation, Array.prototype.map creates a new array with the results of calling a provided function on every element in this array; this provided function represents the first parameter. This means that the following function will be called on every element in the array:

function(x, y) { return x + y } 

Array.prototype.map passes the array element and its index to the provided function; this means that the resulting array will be as follows:
[1 + 0, 2 + 1, 3 + 2, 4 + 3] ==> [1, 3, 5, 7].