FreeCodeCamp and JavaScript: No Repeats Please

No Repeats Please had me baffled for awhile, I’ll admit.  Recursion is a concept I still struggle with, and it’s really the key to the solution.

Here’s the description of the problem:

“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 (aba and aba) don’t have the same letter (in this case a) repeating.”

The hints are:

Permutations – this is basically finding all the ways that a combination of items can be rearranged.  So, for example, if you have three letters (as in this exercise) you can rearrange them six ways – abc: abc acb bac bca cab cba.  There’a whole lot of theory here; go ahead and explore the link if you’d like.

RegExp – Regular Expression.  We’ve touched on these before, and I noted then that this was good for about a dozen posts.  So I suggest that you check out the page on MDN.

Here’s the code they give you to start with:

function permAlone(str) {
  return str;
}

permAlone(‘aab’);

Yes, well, that’s very helpful guys.  Thanks for that.  Very not helpful.

I had really no idea how to start.  I mean, I could see that I needed to loop through the string, I could use substr() to give me parts of the string that I could recombine to get the different permutations, and that it would involve some sort of recursion to go through the substrings, but beyond that, I was a little baffled.  So, step 1, Google it!

It turns out there are a TON of permutation algorithms out there.  But I didn’t want to just copy one – as I’ve noted in almost every previous blog post on a challenge, you don’t learn anything if you just copy and paste.  So I started deconstructing them, taking them apart, trying to figure out how they worked and what each part did.  Some of them, I found, were way too complicated and could be done an easier way.  Others were obviously written by someone with a lot of experience; they used all kinds of shortcuts.  Each one had a different concept of what should be included in what scope.  So when you look at my code below, remember that this is just the way I did it, and that there are many other ways.

function permAlone(str) {
  var perms = [];

  var string = str;

Perms is an array that’s going to hold all the permutations; string holds the string value that you want permuted.

  permute(str);
  function permute(string, letterIndex) {

So, when you first pass the values to the function, the first letter hasn’t been set yet, so we set it to 0.  You’ll see why we did this below.

  if (letterIndex == null) {
    letterIndex = 0;
  } else {
    letterIndex = letterIndex;
  }

When we hit the end of the string, push the value to an array that’s going to hold all the permutations.

    if (letterIndex == string.length) {
        console.log(string);
      perms.push(string);
        return;
    }
    for(var i = letterIndex; i < string.length; i++) {
      var s1;
        if (i > letterIndex) {
            s1 = string.substring(0, letterIndex) + string[i] + string.substring(letterIndex + 1, i) + string[letterIndex] + string.substring(i + 1);
        } else {
            s1 = string;
        }
        permute(s1, letterIndex + 1);
    }
}
  return perms.length;

}

This is the heart of the function.  We’re looping through the string, and recombining the letters in a string named ‘s1’.  Then we call permute() again from WITHIN permute() until we have hit the end of the string.  This is called recursion and, to my mind, is one of the hardest concepts in programming to master.  But it’s very powerful and if you can get it, it will open up a whole new world to you.  The easiest way to figure out what is going on here is to write it out by hand at each step, watching how the values change.

Finally, we call the function on a string:

permAlone(‘aab’);

But, this isn’t quite right yet.  The idea here is to delete all the permutations that have the same letter in a row, and return the amount of entries left, whereas the code above merely returns the number of permutations the string has.  Theoretically, we didn’t even need to write this code to figure out the number of permutations; we could have just taken the number of items – 3, and found its factorial – 3!, which is 3 x 2 x 1 or 6, and returned that number.  Instead, we generated all the permutations so that we could determine which ones had duplicate letters.  So let’s look at how to do that now.

So, my first attempt to get rid of the ones that had two of the same letters went like this:

  for (var item in perms) {
    console.log(perms[item]);
    if(perms[item].match(/\w{2,}/)) {
      perms.splice(0,1);
    }

  }

Note my use of a regular expression there, as per the hints.  Unfortunately, all this did was delete duplicate ENTRIES in the array – so instead of {aab, aab, aba, aba, baa, baa} for example, I ended up with {aab, aba, baa} which was not exactly what I was looking for.  So it was back to the drawing board…

Update:  Got it!  The filter() function should be familiar from my post here and the Inventory Update challenge.  The Regex threw me for awhile though.  I kept trying /w, from the MDN page, and not getting an answer.  Then I figured out that it was literally looking for a ‘w’.  The period was the right symbol to use to match any character.  I also had no parentheses around my period, which is for capture.  This ‘remembers’ the character, so it can match it to the previous character in the string.  Finally, I tried it as an if statement and that got messy.  So I just condensed the statement to return the items that needed to be in the array (answer).  I forgot the not symbol at first ( the !) and I kept getting it wrong until I figured out that I was getting the opposite of what I wanted, and that made me realize I was returning the wrong set of strings.  So, here’s the final solution:

function permAlone(str) {
  var perms = [];
  var string = str;
  permute(str);
  function permute(string, letterIndex) {
  if (letterIndex == null) {
    letterIndex = 0;
  } else {
    letterIndex = letterIndex;
  }
    if (letterIndex == string.length) {
        //console.log(string);
      perms.push(string);
        return;
    }
    for(var i = letterIndex; i < string.length; i++) {
      var s1;
        if (i > letterIndex) {
            s1 = string.substring(0, letterIndex) + string[i] + string.substring(letterIndex + 1, i) + string[letterIndex] + string.substring(i + 1);
        } else {
            s1 = string;
        }
        permute(s1, letterIndex + 1);
    }
}
var answer = [];
  answer = perms.filter(function(item) {
    return !item.match(/(.)\1+/);
  });
  return answer.length;
}

permAlone(‘aab’);

Okay, on to the next challenge, which is Friendly Date Ranges!

Advertisements

One thought on “FreeCodeCamp and JavaScript: No Repeats Please

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s