Angular 2, or just Angular as it’s now called, is new, exciting and constantly evolving. While it’s great to be on the cutting edge of a JS framework, the process can be extremely frustrating at times…
I wanted to take a quick break to test how much of the course has sunk in, so I went back and rebuilt my Random Quote Generator App from the Free Code Camp frontend projects. I picked this because it was fairly simple and I wanted to build an Angular project from creation to deployment without investing too much time.
Building the project was relatively quick and painless, which is a testament to Max’s course mentioned above. You can see my GitHub repo here (and the app finally deployed here). Given that it’s a static app (i.e. no backend), I figured GitHub pages would be a good place for deployment.
This is where the headache started… One of the inherent problems when working something like Angular, that’s constantly changing is that many of the resources become irrelevant and incorrect very quickly (this one, no doubt, included).
I found multiple blogs and Stack Overflow answers, some written only months ago, claiming that you could deploy to GitHub pages with the following one command:
MS DOS
1
$nggithub-pages:deploy
After much frustration, and multiple attempts at rebuilding and redeploying, I found that the deploy command was removed from the angular-cli.
So the command written above certainly wouldn’t work. The functionality, however, is available through the angular-cli-ghpages npm package.
Before we proceed on how to use the angular-cli-ghpages package, there are a couple assumptions being made in this process that will need to be met if this is going to work…
First, I’m assuming that you have Node.js installed on your computer. If not, visit the Node.js site for instructions for download.
I’m also assuming that you have an Angular app, associated with a GitHub repo, written and ready to deploy… If not, go create something and commit it to GitHub!!
With those assumptions out of the way, input the following in a terminal to install the npm package globally:
MS DOS
1
npmi -gangular-cli-ghpages
Once installed, you’ll need to build the app. In the app’s folder, run:
This will create a dist folder that contains the compiled code for your app. Obviously, you’re going to want to change the above command to include your GitHub username and the repo name.
This will deploy a new branch to your GitHub repo called gh-pages branch. Make sure you’re using this branch as the source for your app. You can find/change this option under the GitHub Pages section of the Settings tab of your repo.
It might take a few minutes for the app to show up on your page, be patient!
That’s it for now, I hope this was able to help.
-Jeremy
Prefer Heroku? Here’s a good article if you’re having trouble deploying a static angular app to heroku. The title says Vue, but it works great for angular now that they’re using webpack…
It’s been about 8 months since I began the Crooked Code blog… And so far it’s been a great experience!
While the overall purpose for writing the Crooked Code blog has been, and will continue to be, helping others learn to code, most of the posts fall under one of two major themes…
The first of these themes has been articles covering Algorithm Scripting Challenges in the Free Code Camp curriculum. Two of the most popular of these posts, based on pageviews, have been Symmetric Difference and Map the Debris.
The second major theme has been tutorials on JavaScript, including the Rubber Ducking Series I started a couple months ago based on (but not affiliated with) ‘You Don’t Know JS’.
While I plan to continue adding JavaScript tutorials, particularly the Rubber Ducking Series, I’m planning on putting a temporary hold on new posts covering Free Code Camp algorithms.
As you may have heard, Free Code Camp has announced they are adding a major expansion to their curriculum. A look at the current map of the beta version shows that many of the advanced algorithms will be supplemental to the main program.
Because of this, I’ve decided to wait until the beta is released into production before I continue writing up more algorithm challenges, as I have no way of knowing which challenges will make the final cut.
I am, however, very excited to announce that I’ve decided to add a third major theme here at Crooked Code – Angular 2 (ng2) and the MEAN stack.
I’m doing this for several reasons…
First, about 90% of my focus lately has been on learning Angular 2. It’s the first JS framework I’ve learned, so the process has been a long one, and judging by many of the comments I’ve seen throughout the FCC community, I’m not the only one on this journey. Which brings me to my second reason…
The final release of ng2 is so recent, many of the tutorials and videos out there are a mix of earlier release candidates and the final release all mashed together…
This causes some major confusion in building a working ng2 app, particularly in how to structure the project. So I hope to shed some light on what I’ve found and save others some of the time I’ve spent (and continue to spend) making sense of it all.
Further, I plan to highlight how the ng2 frontend framework ties into the rest of the MEAN stack.
Now that I’ve spent some time digging into Angular 2 on a deeper level, I’m planning on using my previous experience with Node, Express and MongoDB (with Mongoose) to build larger full stack apps. I think this will be a great opportunity to share what I’m learning with the Crooked Code community.
This is a follow up to ‘Intro to Scope’, previously posted here at CrookedCode. It’s part of our rubber ducking series, where we’re attempting to work through some of the more difficult parts of JavaScript using Kyle Simpson’s book series, You Don’t Know JS, as a guide.
If you want to know more about the project, check out this post. If you’re thinking to yourself “Where does this guy get off thinking he can explain this stuff better than Kyle Simpson?”, check out the disclaimer here. Otherwise, read on…
As the title suggests, this post will cover block scope versus function scope, particularly as they pertains to var, let and const. I’d like to start with the concept of hoisting, however, as I think it’ll help understand the rest of the article.
WTF is Hoisting? (And Do I need a boat to do it?)
Consider the following:
JavaScript
1
2
3
4
5
6
7
8
9
10
11
functionhoist(a){
hoisted=a;
console.log(hoisted);
varhoisted;
}
hoist("Will this get logged?");
The question here is will “Will this get logged?” actually get logged to the console even though hoisted is declared after it A) has a value assigned to it and B) gets logged.
The answer is yes, “Will this get logged?” is logged to the console.
You’ve also probably seen examples of functions getting invoked before they’re even declared. Have you wondered why that works too…
Something like:
JavaScript
1
2
3
4
5
6
7
varb=printYourDogsName('Henry');
console.log(b);
functionprintYourDogsName(name){
returnname;
}
The above snippet will log ‘Henry’ to the console.
Both of the above examples work because of hoisting. As we mentioned in the previous article, JavaScript is a compiled language. Part of the compilation step is finding all the declarations (variables and functions) and associate them with the appropriate scope.
This part actually occurs first, before the code is executed. Therefore any function or variable declared in a given scope will be available throughout that scope.
In the first example above, var hoisted would have been ‘hoisted’ to the top of scope within the hoist() function. So when the JS engine comes across hoisted = a and searches for a variable called hoisted in the lexical scope within the hoist() function, it’ll find it!
One more note on hoisting…
Don’t confuse declaring a variable with assigning a value to a variable, even if that happens in the same line of code.
var name = 'Henry'; is seen as two statements by the JS engine, var name; and name = 'Henry';. The declaration is hoisted, the assignment is not…
If you think this is just semantics, consider the following:
JavaScript
1
2
3
4
5
6
7
8
9
functionprintYourDogsName(name){
console.log(a);
vara=name;
}
printYourDogsName('Henry');
Someone with a tenuous grasp on scope might look at this snippet of code and think there are a couple possibilities…
“That’ll probably be a ReferenceError because a is declared after it’s logged..”
Nope…
or if they’ve heard of hoisting….
“Maybe it’ll print ‘Henry’ to the console because a is hoisted within the printYourDogsName function”
Nope again…
The actual answer is that the snippet logs undefined. If you think back to the last article, undefined (as opposed to ReferenceError) means that the JS engine found the variable a (because it was hoisted), but a was undefined (because the a = name assignment didn’t happen until after console.log(a).
Ok, enough about hoisting… I think that should give us a pretty good grasp on how things work. For more detail please refer to YDKJS.
The Complexity of Scope
I hope my previous article, along with what’s covered here, has given you a pretty good understanding of lexical scope and how it works in JavaScript. So why did Kyle Simpson feel the need to devote an entire book to scope and closures?
You know the old saying ‘You don’t know what you don’t know…”? Well, there are several special circumstances that are covered in ‘Scope and Closures’ that I won’t be addressing here at Crooked Code of which you should be aware.
One such concept is using scope to hide access to variables. I plan to touch upon some of this in a future article on Modules, but in the meantime, YDKJS covers it here.
You can also read about the specifics of scope as it pertains to function expressions, including Immediately Invoked Function Expressions or IIFEs, here.
The final topic you should be aware of that I won’t be covering in this article is closure. Simpson devotes an entire chapter to closure and I highly recommend reading it.
I’ve read it a couple times and my pulse still quickens a bit when someone mentions closure (I’ll be writing a rubber ducking article here on closure in the near future to solidify the concept in my own head).
Now on to Block Scope
We’ve discussed previously that JavaScript uses functions to define scope.
This was, for the most part, entirely true until ES6. Among the changes in ES6 were the keywords let and const, which provide us ways to declare variables with block scope.
The only difference between the two is const declares a constant, which can’t be changed once assigned a value.
Before we get into what block scope is, there’s a key note to remember when dealing with let and const. They are NOT hoisted within their block of scope. This means that you must declare them before you use them or it will result in a ReferenceError.
Now, what’s block scope? Simpson tells us a block is commonly a {...} pair. So think for loops, if statements, etc.. You can even create your own block of scope by enclosing code in curly brackets.
Block scope can be useful in several key ways… Consider the following:
JavaScript
1
2
3
4
5
6
7
8
9
10
11
functionredundantI(num){
vari=num;
for(vari=0;i<10;i++){
//do something really important
}
console.log(i);
}
redundantI(42);
In this example, as I’m sure you can figure out by now, 10 (not 42) would get logged to the console. This is because i would be hoisted to the scope within the redundantI function. So when the engine comes across the var i = 0 statement in the for loop, it will already see the i variable and use that one. Now consider:
JavaScript
1
2
3
4
5
6
7
8
9
10
11
functionredundantI(num){
vari=num;
for(leti=0;i<10;i++){
//do something really important
}
console.log(i);
}
redundantI(42);
This snippet would actually result in 42 getting logged. Why? Because let created a new i variable for use ONLY in the for loop!
I realize this example is pretty idiotic and you’re probably thinking to yourself “This guy is effing nuts… I’d never make that mistake in my code…”.
I know you wouldn’t make a mistake like that, but think about functions that are 100+ lines of code with a couple additional functions nested within.
If you’re using a variable for the sole purpose of controlling the for loop, wouldn’t you prefer to keep it out of the overall scope? Wouldn’t it be nice if you could use the variable in the loop, then have it go away? let enables that…
Simpson also discussed using block scope to enable garbage collecting when you’re handling large amounts of data. It’s a pretty interesting concept and can be read in the garbage collection section of Chapter 3.
The final point to mention regarding the use of let concerns its use in loops. Simpson points out that, not only does let bind the variable to the body of the for loop, but it re-binds the variable to each iteration of the loop.
This may seem trivial, but when you consider closure it can be a very useful behavior if you understand it enough to use it properly. I’ll cover this in more detail in my article on closure, but you can read about it now in the YDKJS section called ‘Block Scoping Revisited’.
That’s it for now… If anyone’s still reading, thanks for taking the time. I hope I was able to straighten out the code for you.
As I stated previously, I’ll be writing a series of posts attempting to explain, or rubber duck, some of the more difficult topics in the You Don’t Know JS (YDKJS) series by Kyle Simpson.
Before you start screaming at me that Kyle Simpson has forgotten more about JavaScript than I ever knew, to which I would wholeheartedly agree, please read the following disclaimer…
Disclaimer:
I have great respect for Kyle Simpson, his method for teaching and the YDKJS series. This series of posts were not endorsed by Simpson and are merely an attempt to supplement his books. This project is being created for the sole purpose of helping to solidify these concepts in both your mind and mine. If you are learning to code in JavaScript, I highly encourage you to read the YDKJS series.
What is Scope?
Variables are extremely important to computer programming. They allow us to write complex and dynamic programs.
But how and where should we create variables? How and where do we store them? And, maybe most importantly, how and from what part of the program are we able to access a particular variable?
Each language has very specific rules for these questions. These rules can be thought of as Scope. Here we’ll introduce the rules of scope specific to JavaScript.
Given that scope is a fairly broad topic, with many different aspects to cover, I think it best to break this into multiple blog posts. The goal here will be to introduce the topic of scope and provide a foundation that we can build upon in later discussions.
What we cover here can be found in far greater depth in the 2nd YDKJS book – “Scope and Closures”.
Let’s begin by taking a step back…
JavaScript is a Compiled Language (surprise!!)
For those who have worked with more traditionally compiled languages like C++ or Java, it may come as a bit of a surprise that JavaScript is actually compiled before it runs. This misunderstanding is likely because, unlike many other languages, JavaScript is compiled just before run time rather than in an entirely different build step.
Right now you may be asking yourself why this is relevant to a discussion on Scope… That’s a great question, let me try to explain.
Simpson describes that, at a very high level, the 3 basic steps in compilation are 1) tokenizing/lexing, 2) parsing and 3) code-generation.
The tokenizing or lexing step breaks up strings of characters in your code into chunks (tokens) that are easier to understand. Next, the parsing step takes all these tokens and forms a tree of nested elements called an Abstract Syntax Tree. This tree represents the grammatical structure of the program. It is from this AST that code is generated in step 3.
Still not clear on how this relates to scope, right?
To clear this up, you must understand that JavaScript employs lexical scoping rather than dynamic scoping.
This means that the scoping for a program is determined at the time of lexing, based on where the variables fall within the blocks of scope. Therefore the author is able to control the scope at the time he is writing the program without worrying that the scopes will change at run time.
This is a key concept in understanding the behavior of scope. For more detail, please read the first 2 chapters in “Scope and Closures”.
As with most rules, there are exceptions…. Simpson discusses several ways to change lexical scoping at run time. This can be accomplished using eval() and with(), both of which he frowns upon using. I don’t plan on going over these here, but you can be read about them in Ch. 2 .
General rules and behavior of scope in JavaScript
Generally speaking, (and again, there are several exceptions to this rule, which we will likely cover in later posts) JavaScript derives its scope from functions.
What does this mean?
You can think of scope as a series of boxes contained within each other. These boxes contain the functions and variables that are declared within that function. This structure enables control over how one block of scope is allowed to access another.
In JavaScript, there is a scope (or box) that contains the entire program, called global scope. Each time you create a new function, a new scope box is created. This new scope will contain any new variables or function declared within (including any parameters declared in the function definition).
And so on, and so on, as functions continue to be nested within other functions…
Mentally, you can picture scope as something like this:
When you reference a variable within a JS function, the current scope will be searched. If the variable is found, great, that’s what will be used. If it isn’t found, the JavaScript engine will continue to search the scope boxes incrementally outward. The first match it comes across will be used.
Let’s use the model depicted above… Let’s say the function for scope #5 referenced a variable called ‘foobar’. If ‘foobar’ was not found in scope #5, the JS engine would then search scope #3. If not found in #3, it would search #2, then #1. Scopes #6 and #4 would not be searched.
What happens if the JS engine reaches the global scope and is unsuccessful in finding ‘foobar’? The answer to that depends on what you are trying to do with the variable.
LHS vs RHS References
Simpson describes two scenarios for referencing a variable. He calls them LHS (Left hand side) or RHS (Right hand side) references and they are handled differently in the case of an unsuccessful lookup.
While LHS and RHS refer to which side of the assignment operator (=) the variable is found, this shouldn’t be taken literally, as there are multiple ways to assign a value to a variable.
Rather, think of the difference as such… LHS is a lookup where we are trying to assign a new value to the variable, whereas RHS is merely looking up the value of the variable to use within your function.
Let’s look at an example:
JavaScript
1
2
3
4
5
6
functionaddOne(a){
varsum=a+1;
console.log(sum);
}
addOne(9);
First, let’s go through this code, find the variables and decide in which scope they reside. There are 2 distinct blocks of scope here. The global scope and the scope inside the addOne function.
There’s only 1 variable in the global scope and it’s the function addOne. The scope nested inside the addOne function contains 2 variables, sum and a.
Now, where and how are these variables referenced?
There are 2 references to each variable in the addOne function.
Line 1 contains an LHS lookup for a. It’s LHS because we are assigning the value of 9 to the variable a when the function is called. Then there is an RHS lookup of a in line 2, as we are only looking up the value of a to use in a+1 (the value of a will not change as a result of this reference).
There’s also one of each type of reference to sum. The LHS reference to sum is on line 2, where we are assigning the value derived from a+1 to sum. The RHS reference to sum occurs on line 3, where we lookup and log its value.
The last lookup is on line 6 where we perform an RHS lookup to addOne by invoking the function.
Note: Originally, I mistakenly assumed there was also an LHS reference to addOne on line 1 when we declared the function. Simpson states in ch. 1, however, that due to the way the compiler handles function declarations, it would be wrong to think of them as LHS references. Please see YDKJS for further clarification.
RHS… LHS… Why does it matter?
You may be saying to yourself RHS… LHS… ABC… XYZ… Who gives a $*&# as long as I have access to my variable… The distinction comes when the engine is unsuccessful in finding the variable for which it’s looking. Knowing the difference now might save you a loooong time in debugging later.
So, what is the difference between an unsuccessful RHS vs LHS lookup? The difference lies in how the engine handles them.
When the engine is unsuccessful in an RHS lookup it throws a ReferenceError. If the engine does find the variable, but the program is trying to do something with the variable that doesn’t make sense (i.e. invoke as a function a non-function variable), the engine will throw a TypeError.
LHS lookups, on the other hand, are a different story. If the engine is unsuccessful in an LHS lookup, it simply creates the new variable in the global scope and hands it back to the engine. As you can imagine, this can lead to all kinds of headaches.
You can prevent this by running in strict mode with "use strict";. An unsuccessful LHS lookup in strict mode will result in a ReferenceError, similar to that of an unsuccessful RHS lookup.
Let’s look at some examples…
Let’s say we make a typo on line 3 when we are logging sum and mistakenly write sums.
JavaScript
1
2
3
4
5
6
7
8
functionaddOne(a){
varsum=a+1;
console.log(sums);
}
addOne(9);
//ReferenceError: sums is not defined
Getting a ReferenceError: sums is not defined tells us that we tried to reference a variable named sums that we failed to declare in a relevant scope.
Another example… Let’s say we try to invoke something that isn’t a function.
JavaScript
1
2
3
4
5
6
7
8
9
10
varb;
functionaddOne(a){
varsum=a+1;
console.log(sum);
}
b(9);
//TypeError: b is not a function
Again, the error we get tells us exactly what we should be looking to fix.
Now for an LHS example. Consider the following:
JavaScript
1
2
3
4
5
6
7
8
functionaddOne(a){
sum=a+1;
console.log(sum);
}
addOne(9);
//10
You can see here that 10 is logged to the console. Even though we didn’t declare sum as a variable, the engine went ahead and created it for us and the function completed without an error.
What about strict mode?
JavaScript
1
2
3
4
5
6
7
8
9
"use strict";
functionaddOne(a){
sum=a+1;
console.log(sum);
}
addOne(9);
//ReferenceError: sum is not defined
We can see here that strict mode prohibited the creation of an undeclared LHS reference.
As you can see, knowing the rules of scope and how errors are thrown can significantly cut down your troubleshooting time.
I am the scope master!!
Ok, that was a lot to take in, but seemed pretty straightforward. Is there more to learn on scope or am I now a scope master?
Settle down Yoda… There are some more advanced topics on scope that I plan to cover in a future post, such as function expressions, IIFEs, hoisting, block scope and the use of let and const.
There are also scope closures to discuss… I’m not exactly looking forward to writing that one, as closures can be pretty damn confusing. But, hey, that’s what these rubber ducking exercises are all about, right?
I hope you found this helpful, feel free to leave your comments below.
That’s it for now, I hope this helped straighten out the code…
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.
Psuedocode for Heap's Algorithm
JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
procedure generate(n:integer,A:arrayof any):
ifn=1then
output(A)
else
for i :=0;i<n-1;i+=1do
generate(n-1,A)
ifniseven then
swap(A[i],A[n-1])
else
swap(A[0],A[n-1])
endif
endfor
generate(n-1,A)
endif
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.
My 'No Repeats Please' Solution
JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
functionpermAlone(str){
//create variable to store number of perms without a repeat
varnoDupes=0;
//split string into array
varstrArray=str.split("");
// Call with an array of the original string
findPerm(strArray.length,strArray);
returnnoDupes;
//Heap's Algorithm
functionfindPerm(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(vari=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);
}
}
functionswap(idxA,idxB){
vartmp=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…
I’ve recently been working my way through the You Don’t Know JS books by Kyle Simpson. If you are learning JavaScript and haven’t taken a look at these books, uhhh, what are you waiting for??
“JavaScript sucks man….”
There are a lot of arguments out there as to why JavaScript is such a shitty programming language. Accompanying each of these arguments are books and blogs by authors that try to teach JavaScript in spiteof it’s shittiness!!
“Uhhh, no, you just don’t get it…”
Kyle Simpson takes the opposite approach… As you can see in the Preface of his YDKJS series, his opinion is that JavaScript is a deep and rich language that few developers take the time to know properly. His argument is that when faced with an obstacle, many JS developers blame the language rather than their lack of understanding.
Now that sounds like someone I want to learn from! Taking this approach establishes a level of accountability and responsibility to one’s craft.
So when other authors are saying ‘JS is a shitty language, here’s how to get around it’s shittiness’, Kyle Simpson is saying ‘JS is a deep and powerful language, here’s how to embrace it and have it work for you.’
I’ve read three of the six YDKJS books completely and skimmed through the other three. There are some really difficult concepts covered that take a couple times reading through to fully grasp. Concepts like closures, modules, ‘this’, prototypes and async to name a few..
What’s the point of this post??
I plan on writing a series of blog posts that work through these concepts and explain them at a basic level. Do I think I can explain these better than the author? Absolutely not, so I encourage you to read the books (in addition to my blog, of course).
I am, however, doing this for two reasons.
First, obviously I’m far closer to a beginner than Kyle Simpson, which, believe it or not, can have it’s advantages when trying to explain complex concepts. It’s possible that I can word these concepts in a way that might be more relatable to someone just starting out. (I’m not saying it’s going to happen, just that it’s possible)
If you haven’t heard the term, rubber ducking is a technique by which you try to understand something by explaining it to a rubber duck.
The theory is, in order to teach it to someone who has no previous understanding (i.e. the duck), you must completely understand the concept yourself! (if you haven’t noticed, I do a lot of rubber ducking here at Crooked Code)
So rather than just read through these books for a second time, I’m going to work through them and try to teach these concepts so they might be understood by a beginner.
Even if nobody reads or visits these posts, I will have gained a better grasp of the difficult parts of JavaScript by teaching them…
More rubber ducking posts to come, I hope you enjoy and get something out of them. That’s it for now…
I recently wrote a post here at Crooked Code discussing that, as a relative beginner to JavaScript, I’ve had a tendency to use loops exclusively when traversing an array.
Further, I wondered if it would be better if I were taking advantage of the methods built into the array prototype. Methods such as forEach(), reduce(), map() and filter().
Let’s take a look…
For reference, MDN is a great resource to learn more about arrays and the array prototype. They cover forEach() in far greater detail than I will here, so I encourage you to go read it.
How do you use forEach()?
Simply put, forEach() takes a callback function as an argument and executes that function on each element of the calling array.
The callback function takes 3 arguments – the element value, the element index and the array being traversed. Instances where the index and array are not needed in the callback function, you’ll see it invoked with only the element value.
A simple example of forEach():
Simple example of using forEach()
JavaScript
1
2
3
4
5
6
7
8
9
10
vararray=['one','two','three','four'];
array.forEach(function(val){
console.log(val);
});
//one
//two
//three
//four
When should I use forEach vs. a for loop?
Researching the differences between a for loop and forEach() to write this post has been somewhat enlightening (there are some very opinionated people out there).
First, if you need to stop or break out of the loop before every element is visited, forEach() is not the right function. In such cases, use a for loop, or look into using every() or some().
Other than that, it seems to come down to performance vs. readability.
Improved Readability with forEach()
Let’s revisit the example above and compare the same functionality using a for loop.
JavaScript
1
2
3
4
5
6
7
8
9
10
11
vararray=['one','two','three','four'];
//log array using forEach()
array.forEach(function(val){
console.log(val);
});
//log array using for loop
for(leti=0;i<array.length;i++){
console.log(array[i]);
};
I’ll let you be the judge as to which one is more readable…
Personally, I think the more you use forEach(), the more you’ll prefer it to a for loop for readability. Clearly, not using additional variables or worrying about ‘off by one errors’ is an added benefit too.
It’s also worth mentioning that ES6 syntax, with the arrow function, improves the readability even further. I’m still writing my functions the archaic way, which is what I did above, but the same function written in ES6 would look something like this:
JavaScript
1
2
//log array using forEach()
array.forEach((val)=>{console.log(val);});
Performance
I used jsperf to run performance tests to compare for loops, while loops and forEach().The tests were run in the Chrome browser.
The for and while loops were the clear winners (6,233 and 6,261 Ops/sec respectively). forEach() was 18% slower at 5,202 Ops/sec.
So, on a sheer performance basis, the loops were faster than the function call to forEach(). I was a little surprised, however, that forEach() was only 18% slower than the loops.
Bottom Line…
I think you could argue either way of which one, the for loop or forEach(), is better. Ultimately, I think it depends on the use case…
If you’re developing something that is very data intensive, and the extra performance of the for loop will make a difference, go with the for loop.
Otherwise, if you find forEach() to be more readable and aren’t iterating over huge data sets, use forEach()…
Either way, get out there and build something cool… That’s it for now, see you next time.
-Jeremy
Side Note
Finally, I need to mention that the forEach() method takes an optional second argument that provides the value to use as this when executing the callback.