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!

 

 

 

Advertisements

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.

 

Tessel, Again

One of the highlights of my week was being a team leader for this round of the tessel hackathon, helping to bring in another victory for Grace Hopper.

The project, called Stop, Teaf! is designed to help to protect the user against the rampant herbal tea theft in the Grace Hopper kitchen. Simply slip a discrete tessel into one of your tea bags, and the  accelerometer module will sense a thief trying to snatch it. This sets off an alarm on your computer, and you will receive a command line prompt, into which you can type a stern message to the thief. Back in the kitchen, the tessel’s audio module will then robotically shout this message to the thief using text-to-speech technology. And if that’s not enough to scare them, there is also a little flag waving that says “Stop, thief!”

This time I wasn’t doing any of the coding or planning (although the result had some things in common with my first tessel project). Instead, I spent my time running around trying to help my team of four debug and refine the plan to fit the time constraints. We ultimately got the project fully functional about 5 minutes after the judges came by, but nonetheless we took home the “Best Campus Solution” award.

 

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. 

flipmatrix

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

screen-shot-2016-11-18-at-10-15-48-amscreen-shot-2016-11-18-at-10-16-15-amscreen-shot-2016-11-18-at-10-16-27-amscreen-shot-2016-11-18-at-10-16-37-am

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 Beginning (kinda)

For the past week and a half I have been working as a teaching fellow at Grace Hopper. The transition from being a student to an employee has been pretty smooth. Maybe it’s my teaching background, but it seems perfectly natural that, after devoting three intensive months to learning to code, I should spend another three months helping a new group of students do the same (while continuing to learn myself).

As a teaching fellow, I spend about two to three hours per day helping students with their workshops. This is a very engaging mixture of fun and stressful, since the current group of students is extremely talented. Several of them have studied computer science, and others have work experience in related fields. There are also a number of students who, like myself, have no formal background before Grace Hopper, but on the whole this group is very capable. So far, I haven’t felt like there were questions that I couldn’t answer, but as it definitely keeps me on my toes.

I also spend a good chunk of time each day going over the next workshop that I will be covering. This is something that I always wished that my own TAs had done when I was a student, since it’s difficult to jump in and debug code when you don’t know the context. There isn’t explicitly time allotted to this, but I think it’s essential to doing my job well and helping the students as much as possible.

Another aspect of my job is engineering for Learndot, the website that students and instructors at Grace Hopper and Fullstack use. My first task was writing tests for some methods that had already been written. This was pretty challenging, because the methods were for MongoDB and JSData, neither of which I have any prior experience with. I needed quite a bit of help to get started, but yesterday I finally got my work merged into the master branch, which felt amazing. My second task has been entirely Angular, which, as readers of this blog know, I love. It’s been going much more smoothly.

The final aspect of my job is interviewing candidates to be future students. I am currently still in training for that, and probably can’t talk much about it, but it is something that really excites me.

That’s all for now! Happy election day (let’s hope) and thanks for reading!!

Week 13 – THE END (kinda)

So, yesterday was my official graduation from Grace Hopper. However, since I am staying for an additional three months as a fellow, it didn’t feel like much of an ending. I have already started learning React so that I will be able to help the new students with it (future cohorts are learning React instead of Angular), and it feels very much like, even though I have learned so much, there is still a great deal of new information ahead of me. I am excited that I will get to hear some old material described by new instructors, and particularly excited that I will be a part of the engineering team for the online learning platform that we use at Grace Hopper and Fullstack. I will continue to document my adventures here, possibly adding some new structure to the site.

The entire last week was taken up by rehearsing our presentations for hiring day. We made screencasts that walked through our final projects, and we practiced delivering out demos in front of each other 5 or 6 times. This was a bit painful but I thought that everyone’s presentation ended up being extremely polished as a result, and in general it helped us build the good habits of practicing presentations.

Speaking of presentations, here is a link to my tech talk from week 11!