The Search for Stable Search

This holiday season, I discovered a new favorite tradition: Advent of Code. It’s an online advent calendar with two new coding challenges each day. On day 4, I ran into a perplexing problem. I tested my code in every way I could think of, and I was pretty darn sure it worked, but I couldn’t get the right answer.

Why couldn’t I? Well, to find out, let’s flash back a couple months. I was answering questions for one of my first workshops as a teaching fellow. The students were writing two different sorting algorithms: merge sort and bubble sort. There are a number of sorting algorithms out there with different efficiencies, and learning to write them is a good way to build fundamental programming skills. Most developers rarely have to write these algorithms themselves, however,  because languages like JavaScript have a built in sorting function. The last question I was asked on that workshop was,  “So… under the hood, which algorithm does the JavaScript sort function use?”

“Interesting, ” I said, “let me look that up.”

It turns out that, like many things in JavaScript, the answer is “it depends.” It depends on the engine that JavaScript is running on (in most cases, this is determined by which  browser you are using). So, in short, different browsers will interpret the line array.sort() in different ways.

Fast forward a month. It turns out that my solution for day 4 of Advent of Code  relied on JavaScript’s sorting function. And my solution made an assumption about that function: that it would use a stable sorting algorithm.

A stable sorting algorithm will take two elements that it sees as equivalent and leave them in the order that it found them. An unstable sorting algorithm makes no such promises. It could leave them in the same order, or it could swap them.

A lot of the time, that makes no difference whatsoever. For example, let’s say you want to sort the following array:

[5, 3, 2, 3, 1, 4, 7]

 

It doesn’t really matter which 3 comes first in the solution –  you will get the same answer either way. An unstable sorting algorithm will do perfectly fine here. But let’s consider a situation in which you are sorting objects instead of numbers. These objects have both a name and an age property, and you want to sort by age.

[{name: 'bob',  age: 3},  {name: 'alice',  age: 5 },  {name: 'willow', age: 3}]

In this example, an unstable sorting algorithm might tell you Bob comes first, or it might tell you Willow comes first. A stable sorting algorithm will always say that Bob comes first.

And sometimes that matters, especially when you are trying to sort by two keys. For example, if you wanted to sort the above array by age and then alphabetically by name, you would need a stable sorting algorithm. This is essentially what I was doing in day 4 of Advent of Code.

So here’s the thing. Most browsers don’t consistently use a stable sorting algorithm. I was running my code in Node.js, which uses Chrome’s V8 engine, which does not use stable sorting. As soon as I ran my code in Firefox, I was able to get the correct solution. Magic!

 

 

 

Allergic React.js-ion

I can’t believe it, but the students are currently in their final week of Junior phase. This past 6-week session has felt quicker than any so far.

When I was a student, we spent the last week and a half of the program learning Angular.js, and, as avid readers might remember, I was very fond of it. But technology changes quickly, and Fullstack/Grace Hopper has already updated the curriculum to teach React.js instead of Angular. This means I have been learning a brand new technology, and then pretending I know enough about it to help other people learn it a few hours later.

React has been a bit of a tough sell for me. One thing I really like about Angular is the emphasis on separating concerns. The problem with this is that, in a large scale app, things can become very disorganized. The codebase of Learndot, the website used by Fullstack students, is an excellent example of this. Usually everything works, but when there is a bug it can be very difficult to track down. I have read that Angular is easy to write but hard to maintain for this very reason.

I am surprised, however, how much React seems to solve this problem by taking the exact opposite approach. At least in the workshop that the students have been working on this past week, there is a great deal of shared information between disparate apps. While this makes things clearer, to an extent, I can also imagine this structure getting out of hand in a large-scale application.

I am still very much in the process of learning React, and maybe I will be sold once I have a better sense of typical application structures. But, as of now, my opinion is that one can write clear and maintainable code using either React or Angular. One can also write terrible code using either framework.

 

Rotating a Matrix (with Gifs!)

This post is a bit more technical than usual, but don’t worry, there are pictures.

I was having a lovely time working through the Arrays and Strings section of Cracking the Coding Interview until I reached this problem:

Rotate Matrix: Given an image represented by an NxN matrix** … write a method to rotate the image by 90 degrees. Can you do this in place?

This is a deceptively tricky problem, and I had to draw quite a few diagrams in order to understand it. Let’s walk through it.

First, for our purposes, a matrix is a two-dimensional array. While the problem suggests that we should be able to apply this solution to a very large matrix (like an image), I have found that a 4×4 array is the easiest way to visualize this problem. Here  is the basic example that I will be referencing throughout the post:

[
[1,    2,   3,   4],
[5,    6,   7,   8],
[9,   10, 11, 12],
[13, 14, 15, 16]
]

Our function to rotate it by 90 degrees should return:

[
[13,  9,  5, 1],
[14, 10, 6, 2],
[15, 11, 7, 3],
[16, 12, 8, 4]
]

Note: The first element of a JavaScript array has an index of 0, the last element has an index of array.length -1. Each element of the matrix can be referenced by its position in the outer array followed by its position in the inner array, so matrix[0][2] = 3.

The Approach: We will tackle this matrix layer by layer, starting from the outermost layer and working inwards. Since the problem is to rotate the matrix “in place” instead of making a copy of the matrix, we will swap each element individually, moving it from its current position to the position 90 degrees from it.

This requires that, for any element, we can find the coordinates of its position when rotated 90 degrees. We can then loop through each element and rotate it by swapping it with the element that is a 90 degree rotation from it. 

It took a while to come up with a methodical system to find these coordinates, but with a little help from my friends and the internet, here’s what I’ve got:

The Coordinates: In order to find each set of coordinates, we need three variables:

1. The width of the matrix, N.
2. The Layer of the matrix that we are inspecting, starting with 0 (the outermost layer)
3. The Position of the element that we are inspecting within its row. This can also be thought of as the element’s offset from the end of the row.

Using these three variables, We can establish that for any layer and position, the four corresponding elements that need to be swapped are:

matrix[Layer][Pos]
matrix[Pos][N-Layer-1]
matrix[N-Layer-1][N-Pos-1]
matrix[N-Pos-1][Layer]

To help visualize this, I have created a diagram of these coordinates on our 4×4 matrix

You can view and test my final solution to the problem here.

** I have eliminated the portion of the question concerned with memory, since I am working in JavaScript and memory is magically taken care of.

The 6 Coolest things about ES6

ECMAScript 6 is the most recent update to JavaScript. Most of its features can be called “sugar”, things that don’t change the underlying processes or structure of Javascript, but make your code cleaner, easier to read, and more similar to code written in other common programming languages. Many browsers haven’t adapted to ES6 yet, but here are a few features that are already changing the way I write code, complete with examples.

1. Arrow Functions
   • Some say that arrow functions are funny looking, but I think they’re beautiful. They especially help clean up your code if you are writing simple callback functions. For example, this is the code to sort an array of numbers from least to greatest without arrow functions:

     var arr = [15, 8, 4, 16, 42, 23]; 
     arr.sort(function(a, b){
         return a>b; 
     }); 
     

     And here is the code to do the same thing with arrow functions:

     let arr = [15, 8, 4, 16, 42, 23];
     arr.sort((a,b) => a > b); 
     

     Nice right? I don’t even know what I’m going to do with all my extra time now that I don’t have to write “function” or “return.” They also help with certain situations where you want more control over the “this” keyword, but I won’t get into that here.

2. Default parameters
   • Another cool time saver. JavaScript allows you to call basically any function with basically any amount of parameters that you feel like at the time, which is cool,  but it can be problematic if you are writing a function and you expect all your parameters to be defined. It is often necessary to assign default parameters. For example, this function will say “hello” to you if you pass it your name, otherwise it will say “Hello, Earthling!” :

     function sayHello(name){
       var person = name || "Earthling";
       console.log("Hello," + person + "!");
     }
     

     There are a few other ways to assign defaults pre ES6, but as far as I know, they all require at least one extra line of code. Enter ES6 Default Parameters:

     function sayHello(name = "Earthling"){
       console.log("Hello," + name + "!");
     }
     

     Boom, there goes that line. Now, that might not seem like a lot in this context, but for functions with multiple parameters, you’re saving yourself a lot of code.

3. The for…of loop
   • ES6 does some really nice things for arrays, and the for… of loop is one of them. This loop has the potential to be pretty life changing, since basically everything that happens on a computer requires some array or array-esque thing to be looped through. Here are a few ways to loop through arrays the OLD way. You could use an old-school for loop:

     var arr = [4, 8, 15, 16, 23, 42]; // assume this line in each ex. 
     for (var i = 0; i< arr.length; i++){
        console.log(arr[i]); 
     }
     

     This is still sometimes the best option because it gives you total control over the array and the manner in which you’re iterating over it, but it’s not very semantic – the words on the page don’t tell you a lot about what you are trying to do. Enter for each, which is more semantic but annoyingly requires a callback function:

     arr.forEach(function(num){
        console.log(num); 
     }); 
     

     This is more semantic, since it tells us that we are performing an operation “for each” “num” in the array. And, admittedly, you can clean up the callback with an arrow function, but this is still just too much thinking sometimes. Pre-ES6 you still have one more option, if you REALLY want to, of using the object iterator for…in:

     for (var idx in arr){
        console.log(arr[idx]); 
     }
     

     This is a pretty good option, but we’re back to referring to array elements by their indexes instead of by name. Enter ES6’s for…of loop!

     for (let num of arr){
        console.log(num); 
     }
     

     Ahhh. perfect. So sleek, so clean, so semantic, no callbacks. You can even make other objects iterable in this way, although I’m not sold that that will ever be a good idea. Time will tell.

4. Assignment with Array Destructuring 
   • Let’s say you’ve got an array of stuff and you want to give names to that stuff. You could do that the old way:

     var prices = [2, 45, 6, 19, 32]; 
     var cookie = prices[0]; 
     var lobsterDinner = prices[1]; 
     var rest = prices.slice(2); 
     

     Now cookie = 2, lobsterDinner = 45, and rest = [6, 19, 32]. It did the job, but that was pretty hard to look at. Enter ES6:

     let prices = [2, 45, 6, 19, 32];
     let [cookie, lobsterDinner, ...rest] = prices;   
     

     Nuff said.

5. The Spread Operator 
   • This thing isn’t all that handy, except for when it’s VERY handy. Putting a … before an array essentially chops that array up into its individual elements, particularly in the argument of a function. Here’s a cool example. Say you want to find the maximum element in an array of numbers. You could do it the yuck way:

     var max = Math.max.apply(null, arr); 
     

     Or the ES6 way:

     var max = Math.max(...arr); 
     

     Much cuter. You can also do it in reverse, which comes in handy when you’re trying to convert the arguments object into a proper array. The old way:

     function example(){
        var args = Array.prototype.slice.call(arguments); 
     }
     

     I’m sorry I made you look at that. Let’s do it with ES6:

     function example(){
        var args = [...arguments]; 
     }
     

     Nice. Edit: You can even do away with the arguments object complely by simply declaring your function thusly:  function(...args){}

6.  Sleek object assignment 
   • I don’t actually know the technical name for this thing, or if it even has a technical name, but it’s awesome. Let’s say you want to create an object based on parameters in a function or some other variables that you have laying around. And let’s say you want the keys in the object to have the same names as the variables. This could get very repetitive:

     function eatYourVeggies(carrots, broccolini, beets){
        var veggieObj = {
           carrots: carrots, 
           broccolini: broccolini, 
           beets: beets
        }; 
     }

     but not with ES6!

     function eatYourVeggies(carrots, broccolini, beets){
        let veggieObj = {carrots, broccolini, beets}; 
     }

     Never again will you experience the agony of writing the same word twice in a row.

There’s a lot else to love about ES6. Const and let, for example, or native promises. But these 6 examples stand out to me as the most simple, elegant, and readable. I can’t wait to start using them!

 

An illustrated metaphor for HTTP

Complicated concepts are often best explained in metaphor, so I’m taking a shot here at explaining Hypertext Transfer Protocol through  a childhood experience.

You know that ‘HTTP’ that usually starts off urls? It represents one of many protocols that servers and clients (that’s your machine accessing the web right now) use to talk to each other. The HTTP tells both machines what to look for when parsing the information, and a developer with knowledge of these protocols will also know what to look for and can use the information being passed back and forth.

A protocol isn’t a language, it’s simply an agreed-upon structure for conveying information. For example, when my friend Oriana and I were bored in 9th grade history class, we would pass notes back and forth that obeyed ‘Galen and Oriana’s Disgruntled Onomatopoeia Protocol.’ It looked like this:

Here’s what that same conversation might have looked like in hypertext transfer protocol:

Hopefully this elucidates one aspect of the complex and seemingly magical Internet.