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.

 

Advertisements

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!!