Sign in to follow this  
  • entries
    34
  • comments
    29
  • views
    17592

About this blog

It's summertime, that means internship and general relaxing

Entries in this blog

We have a fairly strong research team at Endeca, and as part of that we occasionally have speakers on various topics. Last week we had a PhD student from MIT (David Huynh) give a talk on reusing data on the web - it was really very interesting.

I would encourage anybody interested in web 2.0 to take a look at some of the stuff the SIMILE team at MIT has been working on:

Exhibit - makes it very easy for non-programmers to take data in a variety of formats and publish it to the web in useful ways

Potluck - Doesn't seem to be available for use yet, but as this screencast shows how you can take any number of Exhibit applications from anywhere on the web and create a mashup on the fly

Sifter - Plugin for Firefox that can add modify websites in place to add faceted browsing.

Ahh VMWare

I'm working on a fairly interesting problem at work right now, so I thought I would share. Your input is, as always, quite welcome!

See previous post for more overview of exactly what I'm doing, but basically we're developing a distributed test system to cut down on test turnaround. Given that we're farming this work out to developers machines when they are not around, we are using virtual machines to ensure both a) consistency of environment and b) ability to test arbitrary platforms.

The issue here is that a VM isn't a small thing, the final ones that will be in use will take up space in the 10's of gigabytes, so the cost is high to transfer these around and also to store them (we currently test on something like 9-10 platforms). The criteria for where to put them are in my mind the following: a) redundancy, if one of the locations the VM is available is offline, it should be available elsewhere. b) transfer capacity, if we need to distribute multiple VM's at the same time, we shouldn't incur too much of a performance hit to do so.

My initial solution to this was to have the client machines themselves store the VM's for distribution. After all, they need to have VM's anyways to actually run the tests, so they ought to be able to redistribute those same VMs. This meets the criteria, several systems will be running tests on each platform, and if we need 3 copies of the same VM, we can grab each copy from a different machine. The problem becomes the "churn" of the platform configuration. Since these are developers machines, its possible something might happen and various machines go offline at different times - how does the system reconfigure itself to handle the loss of these machines? As an example, lets suppose by chance all the machines that go offline were running platform X. Our capacity for running tests on X is now severely reduced, do we copy VM's for X to other machines that were previously running some other platform? The cost for doing this is quite high, especially if there is any kind of ripple effect. And then when the previously disabled machines come back online, how does the system revert to the old configuration?

At the moment I'm letting this brew in the back of my head - I don't know exactly what the best solution is. Basically I think a good solution will end up revolving around an idea of minimum and optimal capacity - if some machines go offline we can accept running at lower capacity temporarily, but if too many are lost then it is worth the cost to transfer some VM's around.

Anyhow, typing that out gave me a better handle on the issue I think.
I haven't posted in a while, and I can pretty much say that Libertas is staying inactive for the moment - I haven't the time or the inclination (though I have picked up some other non-game projects)

I started my internship at Endeca Technologies about two weeks ago, and I think I've settled in enough that I can make decent comments on my experiences so far. First of all, although you may not have heard of Endeca specifically, if you ever shopped online at Walmart, Newegg, Overstock.com, Barnes & Noble, Home Depot, and others I won't list here, you've used an Endeca powered website. Basically Endeca provides search technology that customers, like those above, can build their websites on top of. Specifically, what we call "guided navigation" is one of the key features of the Endeca software. Personally I think you can see this the best at Newegg, but essentially as you move through the page you are building up a query, and along with the actual query results, the Endeca software gives "refinements" that suggest the most promising ways to narrow your search. I could go on, and on, but suffice it to say both external facing and corporate internal sites have done some really exciting stuff with our software, and theres a lot more (secret) stuff in the works.

Anyhow, my specific project actually has little to do with the search side of the business. The team I'm on is developing a grid computing system to live on a group of new high-end computers we're getting in the office. The system can run any group of commands in parallel, but the first specific need for this system is to speed up our building and testing. We support somewhere in the neighborhood of a dozen platforms, the code for which needs to be built and tested very frequently. My end of the project is to write the client application that will live on the grid machines. It's a fairly interesting project, the client is responsible for determining the state of the computer, updating anything if neccesary, and when the computer falls below a certain usage level, spawning a VM and picking up a task or tasks from the grid. To make things a little more exciting for myself, I've chose to go about this using a combination of Ruby and C/C++ when necessary. So far it's been an enlightening experience, and I'm excited for what the rest of the summer has in store.

At work I switched to using solely Ubuntu on my machine, since the client I'm writing will live in a linux environment. So far I've found it very productive, and I've actually switched at home as well (though I keep a XP partition so I can play games). I've found it an interesting experience, expect another post in the near future that fully fleshes out my joys and difficulties in switching to Ubuntu from XP - for anyone interested in trying the same or with good advice for some of the issues I've confronted.

Pirates!

OK so I succeeded in making something of a demo level. It's not that full featured because you have no way to know where anything is, nor do you get any kind of introduction to the level. I did however start implementing some simple AI that I've dubbed "static shooters". Basically they are guns that don't move around and will rotate to follow the player, shooting when the player gets within a specified distance.




It turned out to be more difficult than I thought, because I had to add some features that would let guns fire from on top of other collidable objects without damaging them (as in the gun on top of the station in the above picture). Now when each bullet fires, the sprite object that represents the particle carries with it a) the name of its weapon b) an array of sprite names that are "safe" from it. This way the collision method never even gets executed if the particle is being checked against a "safe" object.

Currently the gun platforms aren't very smart, if you fly fast enough they can't catch up. Fortunately if you have a bunch of them fairly near to the object they are meant to protect, it actually is fairly difficult to avoid them.

This officially concludes the 4 weeks of my final project, and I'd say that what I have is pretty good for the time I had. I plan to continue working on it, but I may be more slow over the coming weeks because next week is the last week of classes, then the following weekend/week is final exams, and then I have to drive back to Massachusetts and get settled in my apartment in Boston.
This morning I woke up, skipped both my morning classes and just studied hardcore in the library for my linear algebra test in the afternoon. I think I did OK, the computational questions were easy, but I know my answers on the proof questions weren't entirely correct. I'm hoping for the best, I did about as well as possible.

After that I came home and started working on the project, which I've given the (not necessarily permanent) name Libertas. Anyhow I fixed up a bunch of dangling bugs: problems with assets not getting removed on screen transitions, exception that gets thrown when you exit, etc. I also fixed up the collygon collision a bit - due to some floating point error in the engine bouncing doesn't really work quite right. With a little finesse I've got it working, though currently it just inverts your velocity vector instead of realistically bouncing you. Thats not too hard a fix, but its lower down on the priority list.

Screenshots:





Control Scheme
I never really intended the initial AWSD control scheme to be permanent, but I hadn't come up with any great ideas for a new control scheme. I think I want to make it mouse based, the ships heading will follow the cursor, left click will fire, and the keyboard will still control the throttle. I think this will make it easier to steer. Also I'm considering dumbing down the physics, maybe make the ship decelerate slowly anytime you aren't using your thrusters.

AI?
So up until now the only ship in the game was the player, but really thats boring. So I'd like to implement some kind of simple enemy ship AI soon. Realistically, it probably won't happen this week. I'm going to stick to some simple scripted stuff for the demo mission, and maybe throw in some stationary weapons platforms that will shoot at you. One of the biggest issues with the enemy AI is how to make them move, the player continues moving in the same direction once they get going, regardless of how they turn (unless they reapply thrusters). If I use this scheme with the AI ships, it could be difficult to make the ship move around accurately, but if I don't, it will seem like the ships are moving unnaturally compared to the player.

Demo Level
Without getting too ambitious, I've got a basic idea in my head what the demo level will consist of. You'll start out launching out of a friendly station on the map, and get some text cues that introduce you to the controls and direct you to kill some dummy satellites. Being realistic, I probably will only get about that much done, but in the future I want to evolve the mission to let you raid a small pirate base. Really the biggest obstacle is generating the art, I've managed to not do a terrible job so far, but it is time consuming.

HUD
I implemented a basic HUD today, the players shield and HP are displayed bottom center, and then a list of the equipped weapons is bottom right (similar to Freelancer). Right now theres nothing in the game to damage the player, and no way to change the weapons, but everything is set up so that the HUD updates itself to reflect the current player status. My next goal is to add a basic object selection system (cycle through nearby stations, nearby ships), and have it point you towards what you have selected. Without a minimap this is going to be key for a map of any size. A minimap will come eventually, but one step at a time.

Bedtime!

Pickles

I haven't written an update in a little while, but really theres not much to comment on - well maybe there is:

School/Work
This next week is the last full week of classes, then theres a week before final exams. But damnitall I've got a linear algebra exam on Monday, so I'm spending most of my weekend going through all the material so I can cross my fingers and hope for the best on Monday. On the work front, I signed/sent the lease for my apartment in Cambridge. My other 4 intern-roommates include 1 other guy from UIUC and 3 from CMU, hopefully it will be a good combo.

Progress
This week was particularly busy, which didn't leave much time for development. This was compounded by a string of bugs with FRB, the engine I'm using. Thankfully the guy who develops it is extremely nice and helpful, and helped me sort out my problems over AIM and sent me bug fixes. Anyhow now all the data in the game is loaded from XML. Basically theres a pre-set directory structure that contains all the data on game assets (ships, weapons, maps, players) and it is all loaded when the game starts, and then referenced when needed. Also I changed up the collision; FRB supports arbitrary bounding shapes, so I reworked things to use this. Unfortunately one of the bugs is that I can't get bounce collision with this method, at least not without some still-to-be-done messing around.

Level Design?
This coming week is the last week of the project (at least for grade purposes) so I want to put out something pretty cool using what I've got so far. I didn't get as far down my feature list as I had hoped, and I won't really have much time to work on it until after my exam Monday. I started making a simple level, bu then I discovered I hadn't really thought through the gameplay very much. I had no idea what kind of objects to put in the game world - or what exactly to have the player do. I modelled the mechanics originally after Cosmic Rift - but that is an online game and it isn't story-based - so I need to do some rethinking. I'd like to come up with one cool level that shows off everything that I've managed to put together thus far.

I'll throw another update up this week sometime, with screenshots. If I manage to get a decent level working I might put out a demo as well; I've gotten more used to Inkscape, and even though I suck at art I've started making all the assets myself.
I didn't have as much time to work on the project today as I put off my theory of comp. homework until today, and I've still got to go to office hours to sort out some parts before I turn it in :(

Anyway I did get some overlays working, you can toggle on and off a border and health/shield indicator over all the game objects. When you shoot at something, it will update the indicators accordingly. At the same time I realized my structure and ship classes were really similar, so I abstracted that functionality into a GameObject class and made Ship and Structure children. Then I moved a large portion of the initialization into those classes instead of having it sitting in my main initialization method.

Also figured out that my ship looked needlessly degraded because I was scaling down a large version in-game. I went back into Inkscape and scaled the original down and its not noticeable from the screenshot, but when you move the ship around it looks a lot better.



Hopefully I can do some heavy work on it this weekend, but I've got a lot of other work to do: catch up on reading my linear algebra book, do a mountain of linear algebra homework and start working on my linguistics project.
I made some progress on the art, the tip about starting out tracing over another picture was helpful. I took a top-down schematic of a Raptor from Battlestar Galactica and went at it in Inkscape. What I came up with is in the screenshot below - it's not great, but for my first try I'll take it. Next up, new space station and other structures.



On the coding side of things, it turns out I should have done a little more research about serialization in C#. I threw away my xml/reflection class and decided to just use the XML serialization that C# comes with. As for how to handle separating data from the engine classes - I just created an EmitterConfig class, and then derived subclasses for explosion, weapon and engine emitter configurations. This makes it easier to create specific emitter types, since you only have to specify relevant values and the rest is filled in automatically. Each class has a Construct() method that takes in some game state data, and passes you back the engine object with all the configuration data filled in. If I want another type of emitter it might become a pain in the ass, but besides the occasional special case, particles usually come in the form of bullets, explosions or engine flames.

Next up is streamlining the way the XML is loaded. I want to have specific folders that weapon data, ship data, etc belong in, and then these are all loaded into a hash table with names as the key. Then all a ship needs to know is the name of the weapon it wants, and it can grab it easily.

Finally I said I was going to do overlays and menu's this week - that may or may not happen depending on the next two days.
This past weekend was my birthday, so I did a lot more drinking than coding.

Sunday I did try and make some art for the game, since the art I'm using now isn't mine (and hence I wouldn't feel comfortable letting people download a demo until thats resolved). Unfortunately computer art isn't my thing - I'm not the greatest artist, but I could *draw* a spaceship on paper. I can't however seem to make a good one on the computer. I tried to use Inkscape - no luck. If anybody has any tips/tricks/advice on how to get the best out of my programmer art skills, please leave a comment.

In the coding side, I started writing a class to let me define objects in XML. The motive behind this is so that all the game data (ships, weapons, extra map data, etc) can be created quickly and modified easily, and not live in code. For the first pass, I went with a straightforward XML to object idea. Basically some simple XML like this:


Reflection Weapon
10


Becomes a GameName.Data.Weapon object with the included values.

I finished this and now I'm rethinking the way I've gone about it. For example, the Weapon class contains the "name" and "damagePerHit" fields, but it also contains a field that is an Emitter from the graphics engine. I initially mixed some graphics objects in with the other data because I need to define how the weapon particles look. However initializing the Emitter object is too complex for my reflection class - its constructor takes arguments that aren't available until the game is started.

So the most direct route solution is to create new classes to be twins with classes like Emitter, but these classes only contain specific data items that don't depend on the game state. Then these classes can be filled with the XML, and at the appropriate time that data will be copied to the right place in the real in-engine object.

However, this doesn't seem optimal either. If I'm going to go to all that work - the result should be easier to use than simply filling in fields on an object. I'd like to find a way that makes creating these objects easier - but doesn't put any limitations on how much control I have over object creation. Not sure what that solution is going to be yet, but in the next couple days hopefully I'll bang something out.
Did some more work over the past couple days. Mostly I've been coding the storage classes that hold information about ships, weapons, maps, the player etc. I've also done a bunch of stuff with the FRB particle engine. The sprites are well designed so that you can attach emitters to them as children, and then attach emitters to those emitters to do things like have bullets explode.

I'm still trying to think about the best way to do collision, right now I have every sprite held in a series of arrays depending on how they should collide with other objects. Bullet particles are held in one array, moving objects like the player in another, and static structures in another. The downside to this is detecting collisions involves looking at every sprite, onscreen or not - which is expensive.

Screenshots (Art not mine, I need to find some more legal art to use soon):









Next up is moving static data like ship information, weapon information and map information into XML files that can be parsed into storage classes when the game is loaded. Also I need to find a generic way to make large explosions using the particle engine - something fairly random that can be used for any structures or ships.
I started today on my space shooter project, which is immediately in dire need of a good name so I can stop calling it "the space shooter project".

I spent the last week or so surfing around and looking at various free graphics engines, (thanks gamedev for the nice list in the Alternative Libraries forum) and couldn't seem to quite find anything that sparked my interest. Either using it looked too difficult, it lacked a critical feature, or it didn't seem well supported. Finally, I ran across Flat Red Ball which seemed to really fit the bill. It had all the features I needed, plenty of documentation, still in active developement, had a good community behind it, and most of all, it's in C#.

Friday/Saturday I spent a little bit of time fooling around with the template to see how things work, and read most of the documentation that was available. Today I started putting something together and in a couple hours I made a lot better progress than I expected. I've got a fairly data-driven application that will show a map with some collidable stationary objects, and then add in a configurable ship that the player can control. Best yet, for once it is fairly well architected and not just a shitty-on-the-fly prototype.

The rest of this week:

- Come up with a good collision scheme. FRB provides a lot of collision capabilities but I can't find a great way to encode each objects collision behavior in some form that can be loaded for each map.

- Work on some basic polish issues. Right now you can fly off the map - need to fix that. Also the control scheme needs tweaking, I've got it so that pressing the "up" key for instance makes you accelerate forward, but turning doesn't change your direction of motion. This may be how it would actually work in space, but it makes it hard to control. I need to find a balance between the standard controls and the realistic ones I've got now.

- Implement particles. FRB has some fairly powerful features that let you do a lot with sprites in general, and particle sprites in particular. One thing the game desperately needs is some graphical flair, so I want some cool particles for engines and for weapons, and for anything else I can think of.

One cool idea I've had is for the level backgrounds. I've always been a big fan of cool space pictures, and it turns out Hubble images from NASA are available in super high resolution (6000x6000), and don't seem to have any prohibition on use - the perfect backgrounds for a space game.

The plan going forward is for a couple journal updates every week (hopefully including screenshots from now on) and a demo at the end of every week. (I have to show a demo in the class this is for every week, so why shouldn't I post it as well - or at least a video).
People seem to read journals with pictures in them, so in lieu of screenshots of a cool project (since I have none - though scroll down for details on whats coming up) I'll put up my favorite pictures from spring break. I went backpacking down in Big Bend Texas for the week, definitely tiring but it was a beautiful place.


Early Morning at Boot Canyon


Cliffs in Mexico to the West of Santa Elena Canyon


Pinnacles


View off the South Rim


Just before Sunset on the Southwest Rim


View off Emory Peak

Anyhow, in other news I'm supposed to turn in a summary and schedule for a 4-week project in my programming studio class. I'm looking at it as a good way to actually develop a game for once, even if its pretty small. I'm going to relook at the little space shooter demo I did over winter break and make it into a full fledged space shooter.

Right now I'm having trouble deciding what to use for a graphics library, I don't want to have to be writing the low level functionality when I only have 4 weeks. Ideally I'd like to already have:

- Basic animated sprites with collision
- Simple particle engine (for explosions, weapons etc)
- Sound & Music Support
- Input support

I think that so far SxDL looks the most promising, but I've never used it before so theres always a chance it may take more time to rampup to than I expect. I used Ravuya's Propane Injector for the original demo and I'm tempted to stick with that - we'll see.

Anyway you can expect some more frequent journal entries in the near future as I'll have some game development related things to write about :)

Web 2.0 Goodness

Last week Kent Brewster of Yahoo came to my programming studio class and challenged us to develop a web application in the spirit of the annual Yahoo Hack Day. This being my first lengthy exposure to javascript and AJAX, it took a little bit to pick up (and the code isn't as clean as it could be) but I wrote a pretty neat little application called WorldTraveler. Beware that it is running on one of those freebie servers (I needed PHP and my school accounts don't allow it), so theres occasional downtime.

Basically WorldTraveler is a mashup that brings together Google Maps, Flickr and WikiTravel into a (somewhat) clean interface that lets you explore the world through words and pictures.

It works like this:
  • User clicks a location on the map.
  • The latitude and longitude are transformed into a 0.5x0.5 degree bounding box and sent via javascript to a GeoNames REST service which reverse geocodes them and returns the largest city in that area.
  • A collapsible container for that location is created.
  • javascript makes a call to the Flickr API and asks for the 30 most relevant pictures that have the city name and the tag "Travel". A slideshow image viewer is added to the location's container, which displays 3 images at a time.
  • An XMLHttpRequest is made via javascript to a PHP file on the server which in turn requests the appropriate page from WikiTravel (uses Special:Export to get an XML document that has an element containing the full wikicode for the page). The PHP script then uses a series of regular expressions to extract the "See" section from the wikicode and turn it into text and HTML, which are then grouped into an XML document and sent back to the main page and parsed into the location container.


I'd say it's not too bad for my first real attempt at doing anything special with javascript or using any web 2.0 api's. It's fairly fun to play around and look at pictures of various places, I could see where another week of work would let you view all the WikiTravel information in a nicer format. I probably will just leave it as it is though, since it's not exactly revolutionary or anything. It was fun though.

New Semester

OK so I pretty much sacked that little space game, I just can't get into it and now I've got so much stuff to do that unless I was in love with it, it's just not going to get any attention. That said, I'm going to revisit the idea when Ravuya comes out with PI 1.0 and the example 2D game, maybe it will give me a clue how to put things together better so it's less tedious.

The beginning of the semester has been pretty good so far - I've got a lot more programming related things going on than last semester.

One particularly cool class I have is a programming studio, every week we have a project to code that is designed to improve various coding skills, and then we meet in groups of 5 with a TA to talk about each others code and what we can improve. I think it will help improve my coding style, which will be good for my internship this summer. We also have to do a final project, which might be a good excuse to make some kind of little game :)

I've also got a programming language & compilers class that uses OCaml, so that should be interesting, I haven't done much functional programming except using Scheme a couple years ago.

I also tried Ruby on Rails this weekend on a whim - I've got to say there is definitely something to the hype, it was VERY easy to make a little web application. I'm trying to think of something cool to make with it, but I've never been much of a web developer. I've heard cool things about llor.nu, but right now it seems to be over-capacity and I can't even see the website.

Oh yeah, and I bought FFXII today - it looks like a great game and it's definitely going to be occupying a lot of my time. It's much more fluid than the previous FF games, no screen changes when you fight, mostly seamless environments, and a less annoying way of having monsters in the wild.

Yay Vacation

Vacation is going beautifully. My finals week back in December really, really mentally killed me - good news is I ended the semester with a 3.74 and no B's in sight. Unfortunately the price for that was me having no memory whatsoever for about a week - thank god for winter break.

Anyhow after I played my fair share of BF2142 I got bored and decided to start on a programming project. Now, I have a pretty poor track record of starting what I finish, so at the moment I'm just tinkering rather than trying to start a real project. I've been using Ravuya's Propane Injector to see if I could make a top-down 2D space shooter demo, and so far I've had decent success (I've only put about 2 days work into it).


In the interest of full disclosure the ship and station I stole from Cosmic Rift, if I actually ever make a game out of this I'll have to draw up some nifty programmer art.


So far I've got the following things implemented:

  • Ship controlled with WASD, uses some really simple physics to let you accelerate/decelerate and bounces you off of obstacles.
  • Simple particle class to let you fire a weapon from the ship.
  • Camera follows the ship as you move it around, scrolling over a map.

Here's a partial list of what I hope to get done in the near future:

  • Get a simple HUD working that can display some game data
  • Finish the weapons system so that you can shoot AND destroy objects
  • Figure out a better system for scrolling background, right now the background is actually a huge PropaneActor object that just never moves. I'd like to make some kind of simple tiled background.
  • Add sound effects to the ship and some background music
  • Do some all around polishing, and come up with a simple task to complete in the demo so that it's fun.


No guarantees on any of that - I'm hoping to finish it in the next week before I go back to the university. Once I get there I won't have too much time on my hands, so unless I'm excited about what I got done in the demo it'll probably get dropped.
I realize there is only so much complaining I can do about having to pick the best of a number of good options, but it is still hard. Here's whats been served up to me so far:

- Internship offer at Endeca Technologies in Cambridge, MA. Sounds like a great opportunity, they work in high-powered search technologies, and Boston is a great city.

- Fog Creek wants to fly me down to New York for an in-person interview. Honestly they would be my #1 choice, but the Endeca deadline is in a week, and only about 1/3 of candidates they fly down actually get hired.

- Rockwell Collins has an interesting project (some kind of in-cockpit LCD touch display) that I got a callback for, but I think I'm ready to move out of aerospace after 3 summers doing that.

I'm going to sign the acceptance letter for Endeca tomorrow, but I'm disappointed that I have to turn down Fog Creek. But in the end I think I would be taking too big a gamble to turn down a confirmed, good-sounding internship for only a chance at a great one. Mostly I'm disappointed that I don't get a free weekend trip to New York City, especially since they are one of the only places that will actually pamper interns while recruiting them.

Amazon Interview

I had my interview with Amazon today, at the ungodly hour of 8:30am.

Overall I think it went pretty well, the first 45 minute interview I thought went spectacular, and the second one was so-so.

First Guy
- Talked about previous projects, career/research interests
- Talked about Amazon, what I like about the site (recommendation system)
- Asks how I would implement the recommendation system, talk about mix of offline-online data analysis

- Talk about the pros/cons, running times of various algorithms to find the a number that occurs an odd number of times in an array. I basically went through every data structure I could think of and described how you might use it and any challenges it would present.
- Do the same thing using only an integer and the given array, I didn't figure this one out - if you XOR all the elements together, the integer occuring an odd number of times is the result.

- Code a function to count the number of set bits in a byte (did a loop with a shift)
- Now do it recursively
- Now do it faster, assuming space is not an issue (use a 256-element lookup table)

- Asked some questions about what he does, and about how it is to work at Amazon

Second Guy:

- Pick a data structure to help evaluate a mathematical expression. I couldn't think of what was needed, but I brainstormed out loud to at least not be sitting there looking stupid.
- He suggests a tree, and we work through together how to put the expression in the tree to make it easy to compute. (This whole thing was hard to wrap my brain around because at any node there is either an operator OR a number)
- Now code a function to compute the value of the expression, and code a tree node data structure to use. I thought out loud for a while and decided to go with an in-order traversal of the tree, which turned out to be correct.

- Now consider a generic binary tree, code a level-order traversal. I knew that to do this you needed to put the elements in queue, so I started going with that. I messed up by using the queue to store the values at the nodes instead of the nodes themselves, once he points this out I finish pretty quickly.

- I ask some questions about things interns have worked on in the past, and Amazon's test strategies.

I hope that I didn't mess up the last bit too much, especially since the first part went extremely well. We'll see, I should know within the week if they are going to give me an offer or not.



This semester is insanely busy, but yet somehow the fact that I'm managing to juggle about 5000 tasks (and none of that day planner shit either) is strangely satisfying.

Right now I'm trying to read through some papers and come up with a good idea for my honors project, which this semester happens to be for my Computer Architecture II class.

A portion of the class deals with parallel computing, so the basic premise of the project is supposed to be taking some useful (but cpu intensive) task and parallelizing it.

My idea at the moment is to implement a parallel implementation of a graph coloring algorithm. This might at first seem a little arbitrary, but theres actually a nice application of graph coloring that relates to the class. The problem is this: when you write a program in a high-level language you can use arbitrary numbers of variables. Underneath the hood however, the processor has a fixed number of registers where these values can be held. The problem is to figure out firstly, can we efficiently use registers in such away to avoid spilling extra data onto the stack? And if not, which registers should we spill?

Graph coloring comes into play for the first portion of the problem. The basic idea is this:

1. Draw a control flow graph of your code. Every statement is a vertex and edges exist between two vertices U and V if you can go directly from statement U to statement V.

2. Establish which variables are "live" on every edge. A variable is live on an edge if it's value needs to be saved when moving between the two statements (vertices).

3. Draw another graph, the interference graph. Every variable is a vertex, and an edge exists between two vertices U and V if the variable U and the variable V are live together at some time.

4. Suppose you have K registers, if the interference graph is K-colorable, then you can accomodate all the variables without spilling. (k-colorable means that you can use k different colors to color in the vertices without 2 adjacent vertices having the same color).

Right, anyway I went off on a tangent.

In other news, I have an interview next week with Amazon and Microsoft. I'm not exactly sure why I have an interview with MS after making myself look not-so-smart at the career fair, but there are no complaints here.

Regardless, Amazon is the more promising interview - I have two 45-minute interviews back-to-back, after which they should know if they are hiring me or not. The MS one is only 30 minutes (and there are a lot more people), so I suspect it's just a weed-out round.
Right, so today was the Engineering EXPO, so I went in hopes a pawning off my resume on some unsuspecting recruiters to try and get a summer internship. For the most part, my encounters seemed pretty successful: Amazon, Boston Scientific, Expedia, Rockwell Collins all seem reasonably promising.

The guy from Amazon asked me a few simple technical questions (whats the difference between an array and a linked list, what is the difference between inheritance and polymorphism, how does a hash table work), and said there was a good chance I'd get a callback.

Microsoft didn't go as well as that though, I told them I was interested in their Program Manager internship (I prefer writing specs and designs and managing people to doing the grunt work).

After he looked at my resume we sat down at a table for some questions. First he set up a scenario involving a telephone booth company, and asked how I would go about designing an electronic phonebook. That was pretty much the last time we were ever on the same page..

My intuition with a design problem is to analyze what the customer needs first and then try and work out the big picture from there - so I raffled off some basic use cases. At this point he stopped me and asked me to refocus on the topology of a network of these things, at which point I said each telephone booth could sync up to a central data center to get and store the records.

Next he asked me to describe the UI to him, which I did, but then he stopped me during that to ask how I would sort the results. I have no experience at all in databases, but I tried to quickly scan my brain for something and I came up with a trie. A trie seemed like a good data structure to use because lookup time is not dependent on the number of entries in the trie itself, just on the length of the word (in this case someones name). Well, he didn't know what a trie was, super. I try to explain it, at which point he mentions that it seems like it would take up too much space (this is a valid trade-off, you get almost O(1) performance but the trie takes up a lot of space). I mention here that he said previously "space wasn't a problem". He ignores me and goes on to say he would stick everything in an array and do a binary search.

He moves on to another topic now, do I like Netflix? Yes, I have an account there. What is my favorite feature? I like the personalized recommendations. What feature would you add if you could? *very long pause* (I hate these sorts of questions, someone else at Netflix probably wonders what a good answer to this is too). I mention that it would be neat if you could make your own groups based on common movie preferences, and then share lists on the site. He chuckles and says I should go to Netflix more often because they already have that feature. I try to explain that last time I checked you could publish lists and make a profile, but there wasn't any more social networking than that, and I was talking about adding more interaction. He says "so you'd add groups where people could share movie ideas and lists?", I say "yes" banking on the fact that I didn't miss that part of Netflix.

At this point I either satisfied his curiousity or he decided I wasn't working out, so I shook his hand and left. I suspect I won't hear from them again, but I felt somewhat shortchanged by the exchange.

Fortunately there are plenty of other interesting possiblities out there, but I know a lot of people target msft for internships, so maybe my firsthand account can be useful to someone else.
Everybody has been putting in their two cents on education lately, so now I probably a good time to air out some of my own opinions.

My own story up until middle school is reminiscent of most other bright young kids. I rarely did the same lessons the other kids did - I'd say I divided my time between finishing assignments and slacking off, and finishing assignments and doing my own projects or explorations.

In middle school, I really almost lost everything at the hands of a bad teacher. I don't remember how, but I got put into the normal math class - in which I would just finish everything really quickly and twiddle my thumbs. Luckily, at the insistence of my parents, I was moved up.

Anyway the real issue I wanted to bring up was where I spent my last two years of high school. My normal public high school was so-so, it wasn't bad, but neither did it afford me any special opportunities beyond traditional "honors" (read: classes with people that aren't totally retarded) classes.

Then, somewhat by chance, I found out about a different kind of school. It was a magnet school attached to a reasonably well known university in my area - but it was still public and free. Catch - you had to be accepted. Long story short, I was, and it was wonderful. The place was filled with people like myself who just wanted to learn, and each and every teacher cared about every student and would make sure he/she was working to their full potential. It was difficult, but I can't even begin to imagine where I would be if I didn't have that experience. Senior year I attended classes strictly at the university, sort of a guided transition - still under the watchful eye of the school staff, but fully immersed in a college curriculum.

It changed my whole life basically, and I'd firmly advocate having more of these places (and in fact, there are, the organization is NCSSSMST - the National Consortium for Specialized Secondary Schools of Math, Science and Technology).

If the public schools can't be fixed to not alienate their best students - then send those students to publicly funded places designed with their type in mind.

Ok so I'm trying to determine whether or not I should take my car with me out to Illinois (a little background - I live in Massachusetts and go to school at the Univ. of Illinois).

I've figured out that no matter what I have to pay $1300 for a year of insurance here so I'll have my car when I come home. Then, if I take it out to Illinois my premium will go up about $200 + gas money + wear & tear.

Pros: Don't have to drive places with my roommates, don't have to deal with shipping my belongings to and from school, and I get more value for my money than if I just leave my car here.

Cons: My car (2000 Subaru Impreza) already has 107,000 miles on it and its a 1000 mile drive to school from here. My parents agreed to pay for a hotel halfway in between here and there and gas money - but I'm still working on the $180/semester it costs to park. I have to stop working a day early - which doesn't seem like too much but its like an additional 100 bucks or so I don't get.

I think I'm leaning towards taking it - but I need to get my insurance agent to tell me the exact premium price as they've been slightly shady in the past.

--------------------------

Work is going well. Right now I'm concentrated on cleaning up a large body of legacy C code - and although its slightly aggrevating, I think it's a good experience.

I think every programmer as they become more experienced will go back at look at something they wrote a while ago and be clueless as to what they were doing. Those are the breaks of not writing the most readable, commented or efficient code while you're learning.

This is kind of a similar thing - only it is someone elses mess. I think looking at and fixing all this stuff is a pretty good way to improve your own coding and debugging skills. Definitely the last one - theres no debugger because this stuff is so close to the metal, so you really have to use your intuition to decide what to attack first - see the results - and try something else.

Now, I'm pretty sure that the original authors were pretty competent - but a combination of a change of domains and time periods makes it need serious reworking.

Basically the code achieves the minimum standard possible to be commercially viable - it usually does what you expect it to and its not pretty, but who did they expect was going to look at it? The reality in the way we are using it is that there is no room for bugs - it needs to either work as specified or shut down.

The second part - and the reason why it's a struggle to interpret sometimes, I think comes from when it was written. Here are a couple of the things I'm seeing, and a reasonable guess as to the original rationale:

  • No header files -
    Instead any external functions or variables are declared at the beginning of the function with the "extern" keyword. In the early 90's C I don't think was heavily standardized. Also, systems back then would have been slower and a compile of a project with tens of thousands of lines of source code could have taken a long time, so they would have tried to compartmentalize everything so that changing one file would just mean recompiling once and relinking - instead of changing a header file thats included across dozens of files.

  • Playing fast and loose with typing -
    Any data structure that is reused seems to have one or more void* fields that they will stick a different type in with every use. In some places - I think this is a cheap hack to get around a bad software design - other times it's sort of a poor man's template.

  • No defensive programming and convoluted code for the sake of brevity -
    Today, we've got loads of space to keep the program in - but obviously that hasn't always been the case. Theres a lot of code where they leave out defensive programming constructs (like null checking), reuse variables to save space, or write less than readable code to increase speed or reduce the application's footprint.


Overall, I think I'm going to come out of this a better developer and definitely if I have to look at legacy code again I'll have a lot of tricks up my sleeve.

Anyway I need some dinner!
Once upon a time, merely years after I was born, and only very shortly after the first ANSI C standard - the following was apparently an acceptable and widely understood cast:


(uint32 *((*)()))&var


Not only is it bad enough that they widely declare void pointers instead of typing variables - but they even go so far as to use casts that change the return type and arguments of a function.
I was reading Slashdot yesterday when I noticed an ad for a purse rental service. Apparently the concept is that women get tired of their purses frequently so why not just rent one and get a new one in a month? Talk about wrong audience with that one.

I bought some new RAM for my notebook. It came originally with 1GB of pc4200, and I'm upping it to 2GB. I'm told something about dual-channel and that beyond the increase in capacity, it will run faster. Not entirely sure how that works (feel free to enlighten me).

I seem to be somewhat falling victim to the phenomenon where the more resources you have available - the more you use. I used to run XP with almost all the non-essential visual frills turned off - with the Windows Classic theme on so everything was simple. Then I discovered WindowBlinds, which while I love having semi-transparent sexy windows - probably eats up a lot of resources.

While I was grabbing that RAM, I also snagged one of the Razer mice Apoch was raving about the other day - I'm a sucker for new things.

In productive news - I cracked open my graph theory text the past couple days in moments of end-of-summer education yearning. I originally bought it intending that I'd start in the beginning of the summer - but better late than never.
Believe it or not I really wish summer would be over. Like, seriously. I'm actually beginning to crave going to class and doing work - in fact, doing anything thats not my job.

I found that learning is difficult outside a classroom setting for me. For example - I really love mathematics, going to an interesting math lecture at school is at the top of my reasons to get up in the morning (that might be a stretch - but I'll go with it). Yet at home, although the interest is still eating away at the back of my mind I can't stay focused enough to read anything or learn on my own. This is something I really have to work on - my goal is to either become a professor or do some mix of heavy math and CS in industry. Both of those require constant learning of new subjects in the field.

Work is actually pretty decent these days, I just finished up a huge slew of test cases for the communications driver on the hardware we're certifying. Prefacing this with the fact that I know I would have trouble doing a lot better - the code is total crap. If you take anything away from reading this, let it be that unit tests are not enough to make sure you're software works. We have the luxury of having all their test code and procedure documents along with the source, given that it is supposed to be "production" quality code. Every test basically pokes one feature of the driver, and doesn't do it in a way that someone would really use the code. So surprise surprise, as I go through and write tests that correspond to real use cases - shit breaks left and right.

Anyway I'm starting to think up stuff to put in my apartment when I get back to school mid-august. After reading ApochPIQ's last post, I think one of those Razer Diamondback mice makes the list - if only so I can map the extra buttons to something useful.

On the subject of productivity - I'm considering trying to find a cheap LCD monitor to use as a secondary screen on my laptop. It was without a doubt a KILLER decision to go for the 17" laptop screen - but if I can double my screen space without losing too much desk real estate then bring it on.

Also I need to decorate (a man's attempt at decorating, mind you) my room. I'm a big fan of posters, though I seem to always fall victim to the phenomenon that my posters start off taught against the wall and sag over time and look retarded. I'm thinking of just ordering ones I want online and getting them laminated or cheapo-framed if they are art prints (somehow the idea of having some Van Gogh prints in my room seems like a great idea).
Sign in to follow this