advanced algorithm scripting

FCC Advanced Algorithm Scripting Challenge – No Repeats Please

There are a couple algorithms that are consistently asked about in the FCC forums because people are having trouble coming up with a solution. ‘No Repeats Please’ is definitely one of them…

No Repeats Please

In my opinion, the best place to start any of the algorithm scripting challenges is making sure you completely understand the problem.

Here is the challenge as stated by FCC:

Return the number of total permutations of the provided string that don’t have repeated consecutive letters. Assume that all characters in the provided string are each unique.

For example, aab should return 2 because it has 6 total permutations (aab, aab, aba, aba, baa, baa), but only 2 of them (abaand aba) don’t have the same letter (in this case a) repeating.

Ok, not exactly the clearest of problems… In my opinion, there are two concepts in this algorithm that add to the difficulty.

First, we’re going to have to understand what permutations are and how to find all of them for a given string. Once we have that, we’ll need to write a regular expression (regex) that looks for repeated letters in each permutation.

Let’s get a better understanding of each of these concepts before we attempt to solve the algorithm challenge.

What are permutations?

The wikipedia page on permutations is a pretty good start if you haven’t been exposed to permutations previously. It states:

In mathematics, the notion of permutation relates to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting. These differ from combinations, which are selections of some members of a set where order is disregarded.

The key takeaway from this should be that a permutation involves all the members of the set and the order matters.

Part of the given problem states that we should ‘assume that all characters in the provided string are unique’. This means that for the given example, ‘aab’, the first two letters should be considered unique even though they are both the letter ‘a’. Therefore, the two permutations without repeats, ‘aba’ and ‘aba’, are considered unique and we must count each of them in the solution.

A quick side note… If you’re looking for further clarification as to the difference between a permutation and a combination, this website does a good job comparing the two…

How can we find all permutations of a string?

Permutations are prevalent throughout many areas of mathematics and computer science. It should, therefore, be no surprise that there is a well known algorithm, called Heap’s Algorithm, that will find all the permutations for a set of objects.

Keep in mind, there are n! number of permutations for a set of n objects. So for a string of four letters there are (4 x 3 x 2 x 1) or 24 unique permutations.

Consequently, Heap’s algorithm works on the order of O(n!), the slowest order of functions. Therefore, as the set gets larger, increases of even one number will cause the algorithm to slow drastically. To put that into perspective, a set with 15 elements, will have over 1.3 Trillion permutations.

Ok, enough about the theory of permutations, how do we implement Heap’s algorithm?

Heap’s Algorithm

At this point, I’ll only post the pseudocode for Heap’s Algorithm found in Wikipedia, in case there is anyone reading this who is trying to solve ‘No Repeats Please’ and wants to attempt to implement in JavaScript on their own.

Given this isn’t a post specifically about Heap’s Algorithm, I’m not going to go into depth about how it works. Suffice to say that it systematically switches one pair of elements in each step, eventually yielding every possible permutation.

I encourage you to walk through the algorithm until you understand the workings ‘under the hood’. The image to the right shows the order of the elements after each iteration of Heap’s Algorithm for a set of 4 elements.

Here is the psuedocode for the recursive version of Heap’s algorithm. If you prefer to implement non-recursively, there is a version on the algorithm’s Wikipedia page.

procedure generate(n : integer, A : array of any):
    if n = 1 then
          output(A)
    else
        for i := 0; i < n - 1; i += 1 do
            generate(n - 1, A)
            if n is even then
                swap(A[i], A[n-1])
            else
                swap(A[0], A[n-1])
            end if
        end for
        generate(n - 1, A)
    end if

procedure generate(n : integer, A : array of any):

if n = 1 then

output(A)

else

for i := 0; i < n - 1; i += 1 do

generate(n - 1, A)

if n is even then

swap(A[i], A[n-1])

else

swap(A[0], A[n-1])

end if

end for

generate(n - 1, A)

end if

Let’s move on to regular expressions before we put everything together in the final algorithm.

Regular Expressions (RegExp)

In JavaScript, regular expressions are objects used to describe patterns of characters in text. They’re extremely useful when solving certain problems IF you know how to use them. That’s a big if, because they are very unintuitive to use and a weakness of many beginner programmers.

w3schools shows the syntax of regular expressions as /pattern/modifiers; . Rather than diving down the rabbit hole of regular expressions, I’ll point out some great resources to learn regex, then write and explain the one we’ll need to solve this challenge.

MDN is a good intro and explains most of what you’ll need for this challenge. For further learning, Eloquent JavaScript has an entire chapter on regular expressions. This site will let you practice writing them, and if you’re feeling really ambitious, although I haven’t read it, Mastering Regular Expressions was highly recommended by multiple people on the FCC forums.

A Regex for Repeating Letters

Let’s build a regex that will recognize repeating characters. We’ll start with /[a-zA-Z]/, which will match any and every letter in the string.

Patterns in parentheses are remembered and can be referenced in order (i.e. the pattern in the first set of () can later be referenced as \1 , the second as \2 and so on). Therefore, adding parenthesis like so, /([a-zA-Z])/, causes the letter that is matched to be remembered.

Next, adding \1 after ([a-zA-Z]) will cause the regex to look for a repeat of whatever the ([a-zA-Z]) matched (i.e. a pair of the same letter), which is what we need!

Therefore, our regex for finding a repeating letter is going to look like this /([a-zA-Z])\1/ .

Crystal clear right!!

An Additional Note on Regular Expressions

It’s important to note regular expressions are objects in JavaScript and inherit the methods associated with the RegExp prototype.

To solve ‘No Repeats Please’, we’ll be using the RegExp.test() method. When the test method is passed a string, it will return a Boolean telling you if that string contained the pattern. So /([a-zA-Z])\1/.test(str) will return true if there are repeating letters in str.

Structuring the Algorithm

Now that we have a better idea of the problem, we can start thinking about how to solve it… There are a couple ways we can structure this algorithm.

One, we could use Heap’s algorithm to iterate through all permutations of the given string, pushing each onto an array. Then, having an array with all permutations, we could check each element of the array for repeats.

Or two, we could use Heap’s algorithm to iterate through all permutations, each time checking for repeats and if not found, increment a counter.

I chose to write it the second way with efficiency in mind. Given the function is on the order of O(n!), we don’t want to iterate through all permutations to create the array, then iterate through again checking for repeats.

This won’t make much of a difference for strings of length 5 or 6, but it will make a huge difference on longer strings. In fact, to demonstrate this, I tested the function written both ways.

When running the function the first way (iterating twice), a string of 10 characters took 3523ms vs 2287ms for a function written the second way. When I increased the string to 11 characters it took the second function 26,802ms while the first function failed due to lack of memory.

Now that we have a structure in mind for the algorithm, let’s finally go ahead and write it!

My Solution to ‘No Repeats Please’

If you want to take a stab a writing the solution on your own, now’s the time… I’m going to post the solution that I came up with below. Again, there are multiple ways to solve this algorithm challenge, this is just the one that I came up with.

Spoilers_ahead

function permAlone(str) {
   
//create variable to store number of perms without a repeat
var noDupes = 0;

//split string into array
var strArray = str.split("");
  
// Call with an array of the original string
findPerm(strArray.length, strArray);
  
return noDupes;

//Heap's Algorithm
function findPerm(n, arr) {
    // If only 1 element, just output the array
    if (n == 1) {
//check for duplicates
     if(!(/([a-zA-Z])\1+/).test(arr.join(""))){
        noDupes += 1;
        }
      return;
    }

    for (var i = 0; i < n; i+= 1) {
        findPerm(n - 1, arr);

        // If n is even
        if (n % 2 === 0) {
            swap(i, n - 1);
        } else {
            swap(0, n - 1);
        }
    }

 function swap(idxA, idxB) {
    var tmp = arr[idxA];
    arr[idxA] = arr[idxB];
    arr[idxB] = tmp;
    }
  }
}

//call permAlone() with any string
permAlone("aab");

function permAlone(str) {

//create variable to store number of perms without a repeat

var noDupes = 0;

//split string into array

var strArray = str.split("");

// Call with an array of the original string

findPerm(strArray.length, strArray);

return noDupes;

//Heap's Algorithm

function findPerm(n, arr) {

// If only 1 element, just output the array

if (n == 1) {

//check for duplicates

if(!(/([a-zA-Z])\1+/).test(arr.join(""))){

noDupes += 1;

}

return;

}

for (var i = 0; i < n; i+= 1) {

findPerm(n - 1, arr);

// If n is even

if (n % 2 === 0) {

swap(i, n - 1);

} else {

swap(0, n - 1);

}

function swap(idxA, idxB) {

var tmp = arr[idxA];

arr[idxA] = arr[idxB];

arr[idxB] = tmp;

}

//call permAlone() with any string

permAlone("aab");

If you were having trouble with ‘No Repeats Please’, hopefully breaking it down like this helped. This is definitely one of the hardest of the FCC algorithm challenges.

I hope you found this post useful… If so, feel free to leave a comment and let me know. Thanks for reading, that’s all for now…

-Jeremy

FCC Advanced Algorithm Scripting Challenge – ‘Symmetric Difference’

Let’s tackle another Free Code Camp advanced algorithm – ‘Symmetric Difference’. The challenge here is to ‘create a function that takes two or more arrays and returns an array of the symmetric difference (△ or ⊕) of the provided arrays.’

The symmetric difference of two sets of elements is the set that occurs in either one of the two sets, but not both (i.e. the symmetric difference of [1,2,3,4] and [3,4,5,6] is [1,2,5,6]). For more reading on symmetric difference, check out this wiki page.

Free Code camp gives us the following as a starting point:

function sym(args) {
  return args;
}

sym([1, 2, 3], [5, 2, 1, 4]);

function sym(args) {

return args;

}

sym([1, 2, 3], [5, 2, 1, 4]);

This is another case where we have to write a function for which we need to handle an unknown number of arguments. To accomplish this, we’ll be using the arguments object. I’ve covered the arguments object in a previous post, ‘Seek and Destroy’. If you are unfamiliar with or would like a refresher of the arguments object, please check it out.

One of the helpful hints FCC provides us with is a link to the Array.prototype.reduce() method. The arr.reduce method is a great way to cycle through and apply a function to each element of an array.

The arr.reduce method takes 2 arguments, a callback function (which will be applied to each element of the array) and an initial value (the element to provide as the first argument to the first callback function call – see here for more).

If you’re new to JavaScript, or somewhat unclear of what a callback function is, JavaScriptIsSexy.com has an excellent post on callbacks.

The callback takes a possibility of 4 arguments – previousValue, currentValue, currentIndex and array. This is important, as it means when we write our callback function, we will have access to these 4 values within the function (for further clarity on exactly what the four values are, check out the MDN link mentioned previously).

I think we should break down this challenge into two main problems. We need to:

Write a function that returns an array of the symmetric difference (⊕) between two given arrays
Use this function to handle an unknown number of arguments. For example:
- find (arg1 ⊕ arg2)
- if there’s an agr3, find arg3 ⊕ (arg1 ⊕ arg2)
- continue for argX

At this point, I’m going to start discussing my solution to the problem. If you’re working through FCC, I’d suggest attempting a solution on your own given what we’ve discussed above. Otherwise, proceed on…

Spoilers_ahead

Let’s start by writing the function we’ll use to calculate the symmetric difference between two arrays.

In other words, we need to write a function that receives two arrays as arguments, then returns an array of the numbers that are in one of the argument arrays, but not both.

One way to do this is to

create a new empty array (curDiff) to store the symmetric diff
use arr.reduce() to cycle through each array (need to compare each array against the other, not just one against the other)
in the callback function of arr.reduce
- check if an element is in the other array or in the curDiff array (to prevent duplicates in curDiff)
- if not – push element to curDiff
  - hint – arr.indexOf() will return -1 if the given element is not found
return curDiff

Here’s the JavaScript code:

  function findSymDiff(a, b){
    //array to hold diffence
    var curDiff = [];
    //compare a against b and curDiff
    a.reduce(function(prevVal, curVal){
      if(b.indexOf(curVal)==-1 && curDiff.indexOf(curVal)==-1)
        curDiff.push(curVal);
    }, 0);
    //check b against a and currentDiff
    b.reduce(function(prevVal, curVal){
      if(a.indexOf(curVal)==-1 && curDiff.indexOf(curVal)==-1)
        curDiff.push(curVal);
    }, 0);
    
    return curDiff;
  }

function findSymDiff(a, b){

//array to hold diffence

var curDiff = [];

//compare a against b and curDiff

a.reduce(function(prevVal, curVal){

if(b.indexOf(curVal)==-1 && curDiff.indexOf(curVal)==-1)

curDiff.push(curVal);

}, 0);

//check b against a and currentDiff

b.reduce(function(prevVal, curVal){

if(a.indexOf(curVal)==-1 && curDiff.indexOf(curVal)==-1)

curDiff.push(curVal);

}, 0);

return curDiff;

}

We now have a function (findSymDiff()) that we can use within our main function to get the symmetric difference between two arrays. We now have to set up the logic to handle an unknown number of parameters received by our main function.

Our logic (using the arguments object) can look something like this:

create new array (symDiff) to store the array returned by findSymDiff()
compare arguments[0] to arguments[1] using findSymDiff()
cycle through argument[]
- compare symDiff to arguments[x]

To accomplish this, we can set up a simple for loop.

If we set

symDiff = arguments[0];

1	symDiff = arguments[0];

we can call

symDiff = findSymDiff(symDiff, arguments[i]);

1	symDiff = findSymDiff(symDiff, arguments[i]);

in our for loop starting at i=1 and loop while i<arguments.length.

Then all we have to do is return symDiff!

Here’s how everything looks when we put it together:

function sym(args) {

  //function to find symmetric difference between 2 arrays
  function findSymDiff(a, b){
    //array to hold diffence
    var curDiff = [];
    //check 1st array against 2nd and currentDiff (to prevent duplicates from same array)
    a.reduce(function(prevVal, curVal){
      if(b.indexOf(curVal)==-1 && curDiff.indexOf(curVal)==-1)
        curDiff.push(curVal);
    }, 0);
    //check 2nd against 1st and currentDiff
    b.reduce(function(prevVal, curVal){
      if(a.indexOf(curVal)==-1 && curDiff.indexOf(curVal)==-1)
        curDiff.push(curVal);
    }, 0);
    
    return curDiff;
  }
  
  //variable to hold the symmetric difference
  //set first arg equal to symDiff to make 1st call easier
  var symDiff = arguments[0];
  
  //loop through all arguments
  for(var i=1; i<arguments.length; i++){
    symDiff = findSymDiff(symDiff, arguments[i]);
  }
 
  return symDiff;
}

function sym(args) {

//function to find symmetric difference between 2 arrays

function findSymDiff(a, b){

//array to hold diffence

var curDiff = [];

//check 1st array against 2nd and currentDiff (to prevent duplicates from same array)

a.reduce(function(prevVal, curVal){

if(b.indexOf(curVal)==-1 && curDiff.indexOf(curVal)==-1)

curDiff.push(curVal);

}, 0);

//check 2nd against 1st and currentDiff

b.reduce(function(prevVal, curVal){

if(a.indexOf(curVal)==-1 && curDiff.indexOf(curVal)==-1)

curDiff.push(curVal);

}, 0);

return curDiff;

}

//variable to hold the symmetric difference

//set first arg equal to symDiff to make 1st call easier

var symDiff = arguments[0];

//loop through all arguments

for(var i=1; i<arguments.length; i++){

symDiff = findSymDiff(symDiff, arguments[i]);

}

return symDiff;

}

This solution passes all of the FCC test cases.

Thanks for reading, feel free to leave comments or additional solutions below. And if you’re working through Free Code Camp, hopefully this helped straighten out the code.

-Jeremy

FCC Advanced Algorithm Scripting Challenge – ‘Map the Debris’

Today we’ll work through our first Free Code Camp advanced algorithm challenge called ‘Map the Debris‘, which will give us some exposure to working with objects.

This challenge asks us to ‘Return a new array that transforms the element’s average altitude into their orbital periods’

It further tells us that the array will contain objects in the following format:

{
  name: 'name',
  avgAlt: 'avgAlt'
}

{

name: 'name',

avgAlt: 'avgAlt'

}

FCC also points us to this wikipedia page to read about orbital periods.

Finally, it gives us the following as a starting point:

function orbitalPeriod(arr) {
  var GM = 398600.4418;
  var earthRadius = 6367.4447;
  return arr;
}

orbitalPeriod([{name : "sputnik", avgAlt : 35873.5553}]);

function orbitalPeriod(arr) {

var GM = 398600.4418;

var earthRadius = 6367.4447;

return arr;

}

orbitalPeriod([{name : "sputnik", avgAlt : 35873.5553}]);

I think, given the limited amount that we’ve spent on objects here at crookedCode, we should start with a brief overview.

I’m not going to reinvent the wheel and write thousands of words on JavaScript objects when so many others have covered it much better than I ever could.

I will, however, point you to, and urge you to read, chapter 4 and chapter 6 of Eloquent JavaScript. This will take some time, especially if you work through the examples (which I highly recommend) but you’ll have a much greater understanding of objects once you’re done.

Some basics about JavaScript Objects:

Here, I’ll cover objects in enough detail to get us through this FCC algorithm. If you’ve read the chapters mentioned above, this should all be review.

In JavaScript, objects are basically a collection of properties that can be wrapped together and stored in one variable. Properties consist of {key: value} pairs.

I think the best way to demonstrate this concept is through an example. I don’t know why, but let’s say I wanted to create myself as an object… It might look something like this:

var me = {
         firstName: 'Jeremy',
         lastName: 'Hurley',
         age: 41,
         gender: 'male'
}

var me = {

firstName: 'Jeremy',

lastName: 'Hurley',

age: 41,

gender: 'male'

}

This example shows 4 sets of key: value pairs, the first of which is – firstName: ‘Jeremy’ – with firstName being the ‘key’ and ‘Jeremy’ the ‘value’. All 4 of these properties are now stored under the variable – me.

I can access and manipulate the properties through dot notation (bracket notation can also be used, but we’re going to stick with dot notation throughout this exercise).

In the example below I will access my age and change it to 21 (I know, I know, wishful thinking….).

//let's say I wanted to be a little younger...

me.age = 21;

console.log(me);  //Object {firstName: "Jeremy", lastName: "Hurley", age: 21, gender: "male"}

//let's say I wanted to be a little younger...

me.age = 21;

console.log(me); //Object {firstName: "Jeremy", lastName: "Hurley", age: 21, gender: "male"}

As you can see when I logged the ‘me’ object to the console, the age has now been changed from 41 to 21.

We’ve seen object properties above as strings or numbers, but they can really be any data type, including other objects or functions. When a property in an object is a function, it is said to be a ‘method’ of that function. I’ll demonstrate how we can add new properties to objects below by giving ‘me’ a hair color property and a method.

//adding a new property to the object me is as simple as this:
me.hairColor = 'brown';

console.log(me);  //Object {firstName: "Jeremy", lastName: "Hurley", age: 21, gender: "male", hairColor: "brown"}

//now add a method to the object me called sayHi
me.sayHi = function(){
               console.log('Hi!');
           };

//we can call the method as such:
me.sayHi();  //Hi!

//adding a new property to the object me is as simple as this:

me.hairColor = 'brown';

console.log(me); //Object {firstName: "Jeremy", lastName: "Hurley", age: 21, gender: "male", hairColor: "brown"}

//now add a method to the object me called sayHi

me.sayHi = function(){

console.log('Hi!');

};

//we can call the method as such:

me.sayHi(); //Hi!

Ok, suffice to say, this is only scratching the surface with objects in JavaScript, but I think we can move on to solving ‘Map the Debris’.

Before going any further I feel I should say there are many ways to solve this problem… Some of them, I’m sure, are much more ‘slick’ than mine. This is the solution, however, that I wrote and am providing here as a working solution in an attempt to help anyone who is struggling or looking for a different perspective.

Solving ‘Map the Debris’

We know from the problem description that we will be getting an array of objects as an argument, and that each object in this array will have name and avgAlt properties.

We need to take each of the avgAlt properties, calculate the orbital periods (based on the equation given to us on the Wikipedia page referenced above), and return an array of objects that contain name and orbitalPeriod properties.

First things first, how do we calculate an orbital period? Below is the formula given on Wikipedia.

orbperiod for crookedcode

This equation might look a little intimidating if it’s been a while since your last math class, but we have all the elements we need. We just have to rewrite the equation in JavaScript and fill in the correct values.

Fortunately, there’s a Math object in JavaScript that has all the methods associated with it that we’ll need (i.e. pi=Math.PI, squareroot=Math.sqrt(), exponents=Math.pow(base,exponent). We’ll also use Math.round() to round our answer to the nearest whole number as required by the challenge.

My logic for setting up the solution was as follows:

Write a function that solved the orbital period given the avgAlt (let’s call the function findOrbPeriod)
Then write a loop to cycle through the array of objects that
- adds an orbitalPeriod property with a value calculated using the findOrbPeriod function.
- deletes the avgAlt property for each object in the array.
Return the array.

If you’re working through Free Code Camp, I would suggest taking what we just talked about and try to solve the equation on your own.

Otherwise, proceed on…

Spoilers_ahead

Let’s start by writing the function that will solve the orbital period.

 //avgAlt of each object passed as a parameter to the following function 
 //the earth's radius was included by FCC at the starting point (earthRadius)

  function findOrbPeriod(alt){
    var axis = alt + earthRadius;
    var orbPeriod = Math.round(2 * Math.PI * Math.sqrt(Math.pow(axis, 3)/GM));
    return orbPeriod;
  }

//avgAlt of each object passed as a parameter to the following function

//the earth's radius was included by FCC at the starting point (earthRadius)

function findOrbPeriod(alt){

var axis = alt + earthRadius;

var orbPeriod = Math.round(2 * Math.PI * Math.sqrt(Math.pow(axis, 3)/GM));

return orbPeriod;

}

As you can see, we use the avgAlt plus the earth’s radius for ‘axis’ in the equation. The second line in the function is the orbital period equation listed above, only written using the JavaScript Math object. Finally, we return the orbital period so we can use this function to populate the new orbitalPeriod property of each object.

Now we can tie everything together by cycling through the array of objects (arr) and calling the function we just wrote (findOrbPeriod()) for each object.

function orbitalPeriod(arr) {
  //values given by FCC as starting point
  var GM = 398600.4418;
  var earthRadius = 6367.4447;
 
//loop through array; for each element calculate and add orbital period and delete avgAlt property
  for(var i=0; i<arr.length; i++){
    arr[i].orbitalPeriod = findOrbPeriod(arr[i].avgAlt);
    delete arr[i].avgAlt;
  }
  
//calculates orbital period for object around earth given avgAlt
  function findOrbPeriod(alt){
    var axis = alt + earthRadius;
    var orbPeriod = Math.round(2 * Math.PI * Math.sqrt(Math.pow(axis, 3)/GM));
    return orbPeriod;
  }
  
  return arr;
}

function orbitalPeriod(arr) {

//values given by FCC as starting point

var GM = 398600.4418;

var earthRadius = 6367.4447;

//loop through array; for each element calculate and add orbital period and delete avgAlt property

for(var i=0; i<arr.length; i++){

arr[i].orbitalPeriod = findOrbPeriod(arr[i].avgAlt);

delete arr[i].avgAlt;

}

//calculates orbital period for object around earth given avgAlt

function findOrbPeriod(alt){

var axis = alt + earthRadius;

var orbPeriod = Math.round(2 * Math.PI * Math.sqrt(Math.pow(axis, 3)/GM));

return orbPeriod;

}

return arr;

}

As you can see, the for loop adds an orbitalPeriod property to and removes the avgAlt property from each object in arr. Then all we have to do is return arr.

There we go!! We made it through our first FCC advanced algorithm. Hopefully this helped straighten out the code for you, feel free to leave any questions or comments below. Until next time…

-Jeremy