I made something (kind of) useful!

I made something (kinda) useful and put it on GitHub! Look look!

https://github.com/AndrewSouthpaw/DisjointSets-CPP

It's an implementation in C++ of the disjoint-set forest data structure. Building it for my specific purpose was fairly easy; abstracting it into template form and removing use of the Stanford library (namely, the HashMap) took AGES. I gained a lot of appreciation for how the Stanford libraries reduce C++ complexity so students can focus on learning objectives and not get lost in the esoteric details.

Any feedback on my implementation is very welcome.

Trailblazer (final assignment in CS106B).

Wrapping up my final assignment in CS106B, Programming Abstractions in C++. I've enjoyed this class immensely and has given me a much stronger working knowledge of programming. It's amazing what you can do when you know how to think about data!

The last assignment is called Trailblazer. It focuses on two sections: 1) pathfinding, and 2) maze building.

Pathfinding

I was tasked with implementing Dijkstra's algorithm. It's an algorithm that finds the shortest path from one node to another by searching along a graph. It takes an unvisited node with shortest distance, calculates the distance to neighboring nodes by following the path through it, and updates the distance to those nodes if they are smaller than before. Here's a handy animation.

Source: Wikipedia article.

As is typical for the introductory CS courses at Stanford, we are not simply asked to merely code the algorithm. Instead, we must implement it as part of a grander task. In this case, they provide us with a start program that generates a random terrain with variable elevation. (White regions are mountains, dark regions are valleys.)

We were to use Dijkstra's search to find the shortest path. The "cost" of the path is evaluated based upon a provided cost function that considers elevation change and whether it's moving cardinally or diagonally. We also color the cells that are queued and then visited, to see how Dijkstra's algorithm progresses. The end result is quite visually interesting. On a relatively flat playing field, it becomes clear how Dijkstra's is (essentially) a breadth-first search algorithm.

It can also be used to solve mazes.

Dijkstra's algorithm clearly lacks a broad understanding of the problem, as with the terrain search. It expands all the way outward in every direction, worried that maybe some other path with a shorter distance just might happen to be the end node. The algorithm can be augmented with a form of "intelligence," a heuristic that helps it to prioritize nodes that get closer to the end node. Such heuristic functions may be something as simple as the distance "as the crow flies" from the intermediate node to the end node. With such a heuristic, steps along a path leading toward the end node can be prioritized over nodes a short distance away but in the wrong direction because they are given a lesser candidate distance. 

The augmented algorithm, called A* search, clearly performs better.

Of course, it doesn't always work perfectly. 

And on the terrain…

My favorite aspect of this last animation: the way it shoots out tendrils on its path toward the end node. It clearly is "seeking" toward the end point, it has a guess as to where it might be located. 

Gorey implementation details for the programming-literate:

- Wanting more practice with structs and pointers, I created a struct Node to track whether the node has been visited, the distance associated with the node, and the parent node (not a pointer, just a Location). This setup had the added benefit to not have multiple data structures that each stored one piece of data (e.g. node -> distance, or Set<node> of visited nodes, etc.).

- A Map<Loc, Node*> parent map that used a node (Loc) as the key and pointed to the parent Node.

- Once the end node is processed, the parent map is flattened and its path reversed (because a parent map traces from end to beginning, it must be reversed to reveal the path from beginning to end). 

I was less satisfied with my implementation here. Upon reflection, I don't think pointers were necessary. I'm so accustomed now to only using pointers to refer to my arbitrarily created structs, that it feels foreign to use them as a regular type. I could have made the parentMap as Map<Loc, Node> and it would've worked just fine, I think.

For some reason, the algorithm bogs down in the final stages and slow dramatically more than the demo version provided by Stanford. Not quite sure what's going on there. I tried implementing using HashMap instead of Map to get O(1) access to the nodes, but that made no difference.

I was pleased with my insight to try out storing all my information in one place with a struct. This approach has not been strongly emphasized through the course, but I think it's a handy tool.

 

Maze-building

The second portion of the assignment was to implement an algorithm that generates mazes. We used Kruskal's minimum spanning tree algorithm. Given a graph of nodes and edges with associated weights (e.g. distance), a "minimum spanning tree" is a tree that connects all the nodes with the lowest cost.

Kruskal's algorithm is crafty. It starts with setting each node to be in a separate cluster. Edges are viewed in order of priority, i.e. least cost. If the edge has two nodes in separate clusters, the clusters are merged and the edge added to the resulting tree. In this way, cycles are avoided: a cluster means the nodes are connected, so adding an edge to two nodes within the same cluster would create a loop.

For example, if you take a grid graph and assign random weights to the edges:

Kruskal's algorithm produces this result. (Actually, there's an error here: the edge "4" between columns 2 and 3 should be included, instead of "6.")

The neat thing about minimum spanning trees of a grid graph is that they can be used to generate a maze. The edges are inverted and become the "solution" or path through the maze that connects all the nodes together.

Results from my program aren't anything you haven't seen already; it just allows me to generate mazes at random.

For the programming inclined, here's some more gorey details about my implementation.

- Edges were tracked using Sets. Edges are a type defined as having a start node and an end node (neither were pointers). 

- The cluster a node belongs to is tracked with a HashMap<node, int>.

- The nodes a cluster contains is tracked with a HashMap<int, HashSet<node> >.

- Merge was a simple process of taking the union of sets, and deleting the excess entry from the HashMap.

This implementation leans on data structures presented on class, namely the HashMap, HashSet, and Set. I have also been pointed to the Union Find datastructure, which will be my next extension to keep learning.

A rare opportunity, a new adventure, a return to San Francisco.

Einstein once said, "Time exists so everything doesn't happen at once." I think he got it wrong, and I submit as evidence the past several days of my life. It has been a rollercoaster of emotions, the result from a confluence of several events that have challenged my groundedness to the breaking point. While all the threads are too much to follow in detail, I will focus on one that has been the source of greatest fluctuation.

On Wednesday evening, I received an offer for a summer sustainable engineering internship in San Francisco. This offer was the result of 30+ hours to assemble an entirely new cover letter, resume, and interview prep in response to a job announcement that floated through my inbox. Stanford is pretty good for that -- you receive a steady flow of job and event announcements; if you're smart about fishing in that stream, you can nab some real gems. (That was also how I discovered the internship that took me to Nigeria in 2011.) No doubt competing with many other highly qualified applicants, I somehow rose to the top and caught their eye. It was a major victory.

The question of "What am I doing with my life, really?" comes up at least every other week. Always the tug-of-war between engineering and dance. When I came across this internship, however, the path seemed perfectly clear. This was a job I could get behind with all my spirit, even if it meant some sacrifices in the world of dance. It's been a long time since I've had that feeling. Most of the job searches I've done in the past were honestly half-hearted: applying to construction companies where you're just a cog in the giant machinery of human development, where you can't make a difference really, where 95% of the work you do isn't related to sustainability anyway. 

This internship was a perfect for me. The company performs energy retrofits for existing buildings to make them carbon neutral. They even provide measurement and verification to prove that the building performs as expected. It's a small startup with passionate team members whom want to make a difference. Sounds right up my alley, right? 

The internship involves three main projects: build a database for tracking equipment, research innovative and cutting-edge sustainable building technologies, and revamp the teaching process for incoming engineers. A combination of programming, sustainability, and teaching. What could be a better fit? I have never seen a job opportunity that exercised so many of my diverse skillsets. Further, it was the perfect amount of commitment for me to keep involved with engineering without forsaking future teaching plans. 

The internship was a dream job, exactly what I wanted, and now it was right there in front of me.

There was one catch, however -- a number: my compensation. It was lower than I expected, for various reasons. It dampened the elation over receiving the offer, for now I had to decide if it would still be worth it. Despite the best intentions, the negotiation subsequently broke down and I was informed they would look for another candidate.

It felt like a dope-slap upside the head. I suddenly realized how financial concerns (over a summer internship, no less) caused me to lose sight of the tremendous value this internship offered as an experience. (I'm glossing over a number of details here, for I think it would not be professional to discuss them here.)

I descended into a full-on shame breakdown. My mind buzzed with dark, negative, self-critical thoughts. You've really messed things up now, you're a total failure. Thoroughly dispirited, all my insecurities about my life path surfaced. My stream of thoughts soon turned despairing: you'll never achieve long-term happiness, and you don't deserve it anyway because you're a failure and overly pushy.

As I have mentioned before, I struggle with shame. I am really, really, really good at shaming myself when things go wrong. I have spent the past several months developing awareness and working really hard to deal with it. But, it will always be a battle, and here I lost that battle to maintain a constructive thought stream.

I reached out for help, verbalizing my shame tape. Buoyed by encouraging words, I did not allow all hope to disappear. (And, as it turns out, sometimes all it takes is for another voice to shout back as loudly as my shame tape.) Rallying once more, I finished my night with a final response. I acknowledged my mistake in allowing concerns to estrange me from what I truly valued. I thought asking to reconsider the negotiation might make me look weak, but it was worth a shot. I'd already messed it up, there was no hurt in trying. 

All of the next day passed without word. The quieter moments -- sitting on trains, for example -- brought me back to a similar state of despair. It was fortunate I had a lot of work booked that day (5 hours of teaching in two cities) to keep me busy. When I was teaching, I was fully focused and in the moment. The Lindy workshop in Fribourg went splendidly, working with a wonderful batch of students that were a lot of fun. People were much closer by the end and all had seen dramatic changes in their movement. Everyone was blissed out on the endorphins of dancing and discovering new and better movement. We all went out for food and drinks afterwards. It reminded me of why I absolutely love teaching in small scenes: the intimacy of classes, the passion of the students, the obvious change seen over a workshop, and the eagerness to connect as humans. I went to bed thoroughly exhausted from the day, too tired to hold any longer the mixed emotions.

The following morning, I received a reply at last. Remarking upon my dogged pursuit of my mission, the offer was once again extended to me.

The storm clouds have parted, and the sun is shining bright. Nothing but blue skies ahead. (Figuratively and literally: the weather that day was fantastic in Switzerland.)

I am overwhelmed with gratitude. Gratitude for the universe giving me a second chance. Gratitude for learning an important lesson without suffering the dire consequences. (Even though it turned out alright, I recognize that I made a mistake in that negotiation.) Gratitude for the support I received, being talked through my shame meltdown, being challenged to think constructively and not give up, and being encouraged to write that final email. If not for that support, I would have gone to bed that night a mess, never would have sent that email, and the internship would indeed have been lost.

While I stand by my original opinions, I see the opportunity cost as worth it to me. This internship will be an amazing experience, I will learn a lot and contribute a lot; all in a field that I deeply care about. That is worth a brief stint of living cheaply. (Good thing I have a lot of practice in that regard.)

I do not walk away from the table empty-handed. I have been granted some leniency to work remotely. I also get flexibility for my hard commitments; they are allowing me to stick with most of my summer plans. That means PBEx, Nocturne, MLB Choreography, and Winnipeg are still happening.

It does mean changing soft commitments and shuffling around a lot of flights. I will likely pay ~$1,000-1,500 in change fees / extra airfare to make travel work out. I'm okay with those changes, however. They're expensive both monetarily and experientially, but the benefits certainly outweight the costs.

My internship begins end of June. One month away. In one month, I will be working an internship in San Francisco where I get to leverage my background in sustainable engineering, programming, and teaching. I will be able to do so while still taking time away to teach dance and train, and not give up my fall tour plans for Europe.

w00t.

Confounded by Huffman. (Consarnit!)

This week, I am finishing up my "coursework" in Stanford's CS106B course. It covers programming abstractions in C++.

I have two more assignments, plus I'll probably tackle some of the section homeworks for additional review.

I am currently working on an Huffman encoding program. Even though I've done this already for my Scala course, writing it again through the imperative paradigm has proven challenging.

The decoding process leaves me stuck. This was how I originally wrote the code.

This approach worked fine for text-only files, but crashed upon decoding a compressed image file. I found this alternative formulation through a repo. (Which was infuriatingly more elegant than my approach.)

This version works fine with image fines. Comparing the two, I'm at a loss for why theirs works and mine does not.

Any thoughts?

Work week.

I have often wondered how a person can put in an 80-hr work week. It sounds insane to me.

This Monday, I received this report from Toggl, my favorite time-tracking platform, about my hours for the previous week.

Huh. So that's what an 80-hr work week looks like.

(In case you're wondering, "Tomato break" are the break times allotted in the Pomodoro Technique. Technically I'm not working, but I count it because the work I do spend is highly focused.) 

My time in Aberdeen has been rejuvenating. With a solid base, I can settle in with tea and my laptop. Day after day, I produce a solid 6-10 productive hours in dance, programming, job searching, and other odds'n'ends. Having a routine is grounding for me. It means I haven't done any sightseeing, but I'm quite okay with that. Putting my nose to the grindstone feels good. It reminds me of being in graduate school, working constantly and always learning.