My Calling- To Grok

To Rick Schonfeld of the American Red Cross (and other random readers):

We were having a discussion about how we, the students in CRASAR, got into computer science and robotics. I said my reason was I had found my calling in CS in high school, and you asked what my calling was, specifically.

I said that it was system design- starting with a blank slate and a desired functionality and producing a working system. That’s a bit of a lie.

Designing systems is one of the things I enjoy, but developing a working system (something from nothing) isn’t quite why I like it. The actual reason is the understanding that comes with being a systems developer. I have a friend (and former coworker) that when asked how well he understood computers (part of a “what should be a students first language” debate) replied “I understand it down to the level of electrons moving… I stopped at why the electrons are moving, but above that I understand.”

Being a computer scientist teaches you how to think; it teaches you how to analyze a problem and how to come to a solution. Once you have a solution in mind, you learn to implement it. When you implement a solution, if you are worth your salt, you don’t just know how it works in vague and abstract terms, but rather you understand it. You grok it. You can watch it run and envision each individual component operating, running along at 2 billion operations per second (or merely 1 million depending on your platform). You can envision it flowing as one fluid entity, existing within its own reality.

Groking how something works is an amazing experience (similar to an ‘Ah ha!’ moment, but more awesome and less fleeting). Learning, understanding, and groking new and complex systems is why I am glad to be in Computer Science; and being exposed to new physical and electronic systems is why I am glad I am a Systems Developer.

It can also be quite terrifying. I designed and developed the software for a frac pump control system from scratch. I raised it from a wee tike that could barely blink LED’s to a system now deployed on million dollar industrial vehicles. I know that it works, and I grok it. But, every once in a while a problem comes up that doesn’t leave you wondering what happened, but rather exclaiming “That’s impossible.. that’s not how this works”. So far when I’ve run into these situations, it seems I’ve been right (odd mechanical or deployment issues), but each time your heart skips a few beats as you’re forced to question yourself, your understanding, and the basis of the reality your system is built around.

But, it is worth it.

Put a different way, a common joke is that real programmers use a magnetic pen to write data onto a hard disk. Somewhere out there are people who, given sufficiently steady hands and sufficiently small points to their pens, know enough about how a hard drive works that they could write data that way. There are people out there that, if you give them the raw electrical signals off your ethernet cable pairs, they can tell you what website you are surfing. These are those that grok.

Thanks to Rick for asking a question I probably should have known the answer to already.

Communication Issues in “The Challenge of the Multicores”

The Talk

A few weeks ago I listened in on a lecture given by Fran Allen, a Turing award winner and a language/compiler/optimization researcher at IBM.

The talk was on “The Challenge of the Multicores”. It meandered a bit into the history of 60’s era IBM machines, a few reflections, and a basic explanation of the problem being encountered with an emphasis on scientific computing. I think- the lecture was rather unfocused, and a few weeks ago, so memory=dead. Part of the lecture was a list of solutions to the multicore challenge:

1. Cache needs to die a bloody and well deserved death
2. We should move away from low level general purpose languages (C/C++/Java/Python/etc)

(Humorous tilt added by me, but otherwise this is roughly what she said)

I’m not sure if there were more, but these two stuck in my head because of what insued. With the elimination of cache, you could hear almost every engineer in the audience groan in horror, and roughly similar may have occurred with the death of low level languages. The questions at the end of the seminar were roughly 90% “How do we handle the discrepency between CPU speed and memory speed without cache”, “How could any low level general purpose language be completely displaced by a high level language”, etc. And through this, I’m doing a combination of laughing, crying, and shaking my head. This seems a classic issue of miscommunication.

The Death of Cache

With the first point, Fran isn’t saying “Get rid of the cache and have the CPU talk directly to memory” (or she might be, I’m not sure how well she understands hardware concerns). What she is saying is that how cache is implemented today is a large source of performance problems. Cache is operated largely without instruction from the program- it makes educated guesses about to load, and what to keep. When it guesses wrong, a cache miss occurs and a massive microsecond or so overhead occurs while memory is fetched.

Here is the problem:  cache guessing is based largely on assembly code and current use. A program can’t tell the CPU ‘I’m going to use this data soon’; a compiler can’t provide meta data to the CPU of the form ‘by the time this method finishes, we’re going to need data from one of these three locations’. Lack of certainty about what the cache will do impedes automated optimization. That is what she was getting at. If instead we were able to treat the cache as 4MB worth of really slow registers, with it’s own lesser instruction set and controller, we could see massive performance gains as we can get much closer to a perfect cache with an intelligent cache controller then we could with a controller that only guesses based on current and previous state.

When phrased that way, cache death doesn’t seem like such an incredibly terrible idea. The cache is still there in some form, it’s just not the cache of today. There are still all manner of issues that would need to be worked out, but it’s alot more clear that “yes, you may have a point there”.

The Death of C

Again, she isn’t saying “C should be eradicated from everywhere and everything”, she’s saying that using a low level language removes the semantics of what you’re trying to do. The best example I can think of would be the difference between using SQL, and hand coding a query over a data structure. (Ignore small issues like ethics, responsibility, pain, etc).

If you encode a query yourself, you are responsible for parallelizing it, and doing that correctly. That means you need to keep in mind data dependencies, lock acquisition orders, etc. You may need to take into account niggly little details about the machine architecture you’re working on if you want massive performance. If you have a sufficiently complex query, it might be worthwhile to precompute certain parts of the query and reuse them. And so on.

With SQL, instead of specifying the steps to get to the state you want, you specify “I want everything that looks like x, cross referenced with everything that feels like y, ordered by z”.  Your database server is then responsible for building a query execution plan. It asks “what can I precompute to make this faster”, “Do I need to do a linear scan through this entire data set, or do I have meta data somewhere such that I can do a binary search”, etc.

SQL constrains what you can ask for, but in return it exploits all manner of optimizations and parallelizations, without your lifting of a finger. Fran’s focus is on high performance scientific computing. If the people doing a weather simulation say “I need the solution to Ax=b” rather then coding a matrix inverse or an LU decomposition by hand, the compiler can provide a very efficient implementation, which may be able to exploit optimizations that the programmers could not see. She isn’t saying “Throw out C#, write your web applications in MATLAB”; but she is saying that current practice makes it hard for optimization researchers to help your code run faster.

Conclusion

Communicate better. It’s better for you, your message, and us.

Google Apps

I decided to switch from GMail as a primary address to an address @codertao.com. However, I ran into a bit of a snag. I like GMail. It’s friendly and has over 1,000 daily slashdot headlines waiting for me to search them the next time I want to remember what I read about small scale nuclear reactors. That, and the mail service that comes with my web host isn’t exactly perfect (and a 7GB inbox is larger then the disk space I have in the web hosting account). So I tried the clearly logical thing of playing with the free version of google apps.

And I can now say I’ve found something Google doesn’t do well- GMail -> Google Apps Migration. Once everything is setup and the old accounts are forwarding to the new ones, everything seems to work fine; with the possible exception that Apps seems to be behind GMail in so far as UI features.

To actually get all of my infinitely valuable slashdot daily headlines to transfer, I signed up for the free demo of Google Apps Premiere Edition, which includes an IMAP migration tool. Some amount of setup was need with that, the details of which I have forgotten and don’t wish to live through again. The end result is everything appears to have transferred- tags seem to still be in place, my 600mb inbox has stayed roughly the same; but I am still shocked. That Google doesn’t consider the use case of a user switching from gmail to google apps important enough to warrant time for streamline migration is just… weird.

Granted, I can hardly complain. Standard Edition of Google Apps is free. I finally have an email address simple enough to be written down in chicken scratch and still be read. Along with easy inbox searching and the email log of my last ~5 years online. Overall I think it was worth it.

Seven Segment Thermometer

Hey look, a project!

Overview of Thermometer + 7 segment display

While I’m waiting for everything to align perfectly for my descent into robotics (still waiting on Mars to align with Neptune, and a few misc pieces from Sparkfun, and soon I’ll be waiting for time), I’ve built a thermometer for the dining room. Three times. I’ve now gotten it to some form of a stopping point.

Pieces and Parts

This uses:

• 4x Common Anode 7 segment displays (got from Allied Electronics)
• 2x A6276- a 16 bit constant current (sink) LED driver (from somewhere)
• 2x 10k resistors
• 1x DC Boarduino (from Adafruit)- Arduino clone intended for breadboarding use
• 1x Prototyping PCB (from RadioShack)
• 1x TMP36 (also from Adafruit)
• More 22ga solid core hookup wire then I care to remember

The A6276 is pin compatable with the STP16C596, the apparent Arduino LED driver chip of choice. It was acquired in efforts to fix the legendary Proton LED sign- sadly (or fortunately) the chips on the sign were a different form factor, and the A6276’s were donated to my evil prototyping causes. The chips work as a constant current sink; when a pin is set high, it effectively opens a current limited channel to ground; when set low the pin is at high impedance.

The Boarduino was originally intended for use in a cable tester due to it’s awesome size (cable tester may be a different post… or just a set of images). Strange things happened with that, and it is now serving as an overpowered thermometer.

Displays of Seven Segments

Technically the displays are eight segments including the decimal. Which works out nicely for being driven from a 16 bit driver. This 4 digit display is the main reason that the thermometer is getting posted, and here’s why: I’m using a protoboard and 4 7-segment displays. There’s no direct/simple way to connect the LED driver’s to the pins of the displays. 32 pins need to be connected for the displays. 32 small wires. 64 solder joints. In a small space. I present: pain.

Pain Defined

There’re probably also a great many samples of ‘bad soldering’ in that photo, but I’m ignoring that for now. Why? Because of this:

It Works!!!

I’m 90% certain there is a much better way to do this (Possibly a 4 digit seven segment display?). But it works. And it is awesome.

The wiring for this part, other then being tedious and made of pain, isn’t complex. To prevent excess pain, I have the hookup wires always run parallel. What this functionally means is the pin out on the right side of an LED driver chip is reversed on the left side. This requires some special handling in the software, and is not necessarily ideal, but, we tossed out ideal with the 40 hookup wires. Ignoring the reversing bit, each display has it’s pins hooked up in the same order to a given 8 pin side of the driver chip. The rest is basic stuff- serial out on chip one to serial in on chip two; latch, and clock are shared between both chips, chip output (the R-EXT pin on the datasheets) is a 10k resistor to ground, etc.

I would actually like to do this again as an intro to PCB design project. When time is found to figure out how to use Eagle.

Sensing Temperature

Temperature sensing is mildly straightforward- the TMP36 sensor is supposed to put out a 0V-someV signal based on the temperature it is currently at, following a roughly specific formula (outputting 500mV at 0C, and increasing at 10mV per degree C). Just a simple analog read and conversion. Roughly.

Close up on the Breadboard

You can see the TMP36 at the bottom of the pic, snuggled next to 0.1uF capacitor as the spec sheet requests. I tried this without the capacitor and tended to get strange readings quickly (within a few minutes). With the capacitor, they tend to be less frequent (that said, no matter how bad the insulation in my house, it was not 4F last night. I refuse to believe). I started taking a median of several readings in order to solve the issue of strange outliers, and it appears to have worked. No ghosts causing 4F readings yet.

One other quick comment though: The TMP36 outputs 10mv/C roughly. Due to the fact that the Arduino is using a 10bit ADC converter over a 5V range, it effectively reads in 5mv increments. Therefore, we can only read the temperature to an accuracy of about 1 degree F. Which is a bit sad, as it makes those last decimals of accuracy kind of meaningless. But alas.

Conclusion

I’ve built a thermometer! With (reusable) seven segment display! For more cash then I care to think about! I’ve had two other variations of this before: outputting current temperature to a set of normal LED’s in binary (fun, simple, slightly confuses relatives, need right LED size to make it nice), and to an LCD (can display high/low/current readings simultaneously, and be read by non techies). A few other variations could be done relatively easily: an indoor/outdoor meter, monitoring multiple rooms, temperature loss in ducts from straight out of AC to last outlet, etc.

This and a few other projects I’ve done fall under the ‘can be done with 3 output pins and maybe an analog read’ category of projects. I’m plotting to start playing around with the ATTiny series of uC’s to get the project down to component parts / decrease the requisite bulk. We’ll see how that goes. I’d also like to remake the 4 digit 7 segment display as a PCB prototype if I get the time/chance.

Depending on how things go, I suspect either the box game, tilt RC bot, or a report on the cable tester will be next. Or, alternatively, LC3D may get finished. Who knows with me?

More details are available on request, as I’m not sure what the best level of detail is for folk (non-existent ones at that).

UPDATE:

Small update. I changed the analog temperature sensor to a digital sensor, the DS18B20 (from Sparkfun), using a set of libraries for the sensor (from Miles Burton). The nicest thing about the new sensor is that it has an onboard 12bit ADC, which lets it sense temperature accurately to the last tenth of a degree that I was wanting. It also doesn’t appear to suffer from the same noisey readings I was getting with the TMP36. The only downside is that it takes 3/4’s of a second to get the 12 bit value and send it back to the Arduino. Which is fine for what I am doing, but it doesn’t seem ideal for other applications.

One interesting other bit about the new sensor: it can operate on only two lines; a ground line, and a data line. The data line is supposed to be connected (via a 4.7k resistor (why 4.7k?)) to a voltage source. When the sensor wants to send a 0 to the uC, it connects the data line to ground, and the uC reads 0. When it wants a 1, the data pin becomes high impedance, and the uC reads a 1 coming from the pull up resistor. Which I find fascinating- it’s about like staring into the abyss of infinite knowledge, seeing all these little connections, and then start to see the big picture form and make perfect sense. (It should be noted, I am not an author).

AI Project- Sudoku Through Constraint Satisfaction

One of the final projects in the AI class is to teach middle schoolers about an aspect of AI. I chose to teach about the fun and joy of constraint satisfaction through Sudoku. Why constraint satisfaction? Because that is one of the first AI topics I came across in the class and thought ‘Wow, this is awesome… and I haven’t seen it twenty times before’. It is a solid method for solving a specific class of problems.

To see it in action, look here. Source code for everything (from the simple (and terrible) php webpage, to the Constraint Satisfaction Solvers, is available here.

I’ll warn though that the code isn’t completely clean. A fair amount of the code in the various solvers could have been implemented… differently. Such that it wouldn’t be a copy and pasting between the ~5 solver implementations.

Also, the way possible values are determined is a horrible kludge, that I should have known better then to do. Part of the goal of the Solver implementations is to make the intermediate states visible. To make that simpler, no actual recursion is used in the course of searching. Since no recursion is being used, it’s harder to make changes to intermediate state, such as ‘we need remove values 5 and 6 from the possible values for cell 15′, and then undo those changes. Being lazy, I opted to just generate the possible values for all cells on each step of the algorithm. Terribly inefficient, but, honestly, that’s not a problem for this. Drawing out the entire board on screen probably takes much more time. What was unfortunate was when I went to try and encode Forward Checking / Arc Consistency, I needed the Variables to store their possible values in order for the code to be not terrible. As such, Arc Consistency turned out to be rather messy, and surprisingly useless on the small Sudoku grid (or I did it wrong; but surely that is impossible), so I scrapped it and moved on. But, overall, the implementation would be more robust if the variables were responsible for storing their individual values. And if I didn’t need those intermediate states.

In conclusion, it was fun, I learned things, hopefully middle schoolers will also learn things, or at least lie and say they did, and I now have other finals I need to worry about.

Special thanks, again, to Peter Norvig’s Solving Every Sudoku Puzzle. It provided for entertaining quotes and thoughts, and the inclusion of a 62 digit number in the final website.

Arduino Project Ideas

Projects I’d like to eventually work on with the Arduino:

• PC Remote Control Robot- Preferably Built with K’Nex, but that’s inner child talking. A simple, lightly mobile, robot that can be computer controlled. Preferably with video cam for a robots-eye-view of the world.
• Tilt RC Robot- An interesting idea probably from a video I watched- using an accelerometer and a psuedo-game-pad to provide tilt based control of the robot. True, at this point it’s little more then an RC car,  but it would have a cool controller!
• Mapping Robot- A bit more complex; a bot that can try and map out the space it is located in; no doubt in constant communication with a PC workstation
• Motion Control Lighting- We use a set of lights on a timer as walkway lights; I’d like to change that to motion activated from two locations, in some overly complex scheme
• PT Camera Mount- A Pan/Tilt mount for a camera; possibly to be combined with motion tracking.
• LED Table- More specifically, I’ve seen a coffee table esque item with LED panels underlaid. I’d like to do something similar as a sole source of light for a room. And/or implement Game of Life on it
• Simple Web Server- Web Server Controlled… thing. I’m thinking something for outputting, say, two connected temperature sensors in a web clean format; but it’d also be nice to figure out an application for a stationary motor
• Wireless Sensor Network- A set of sensors, connected wirelessly, each re/broadcasting sensor information at timed intervals. Each node would have the most recent reading of every other node stored, such that you only needed to interface with one node to get an idea of what everything is doing. Could also be an application of adhoc network routing; given a sensor network, find a route to and from the furthest node.
• Solar Powered/Recharged Wireless Sensor- Either as part of a motion sensing network for controlling outdoor lights, or finding the temperature of the outdoor air. Attach a set of solar panels to recharge a battery powered Sensor Node.
• Persistence of Vision Odometer- A set of LEDs connected to a bike wheel with a Hall Effect Sensor, set to display interesting characteristics of the journey as the wheel turns- current speed, trip distance, overall distance, etc.
• LED Clock + Weather- Build a binary LED clock which includes a color coding for current and forecast weather- Blue in the hours column for rain in 12h, Red in Minutes for Heat Stroke right now, etc. Would need a method of getting the weather forecast, but I’m sure that’s in some way solvable. Would also allow me to have a binary clock with a date listing, and automatic 24h based clock. (One of the items I dislike about a ThinkGeek binary clock purchased ohh so long ago- on power loss it loses the ‘24h’ display configuration). Possibly to be combined with wireless sensor network above.
• RC Car GPS Control- Hook a GPS device to the Arduino, and combine that with a high performance RC car to see what happens. Akin to having a UAV fly waypoints.
• AutoMower!!!- An automated lawnmower. Basically a push mower with drive motors mounted, hopefully able to map out the yard, and not fall apart due to vibration, or go into a lake
• Bike Trip Logger- For a different project, I would like to figure out how to log bits of data about changes in elevation on a bike trip. It’s theoretically possible that a set of accelerometers could help solve the core problem I’m working with. This eventually evolves into a system for suggesting bike routes; but I need to get data collection first
• Auto-Pilot with Video Transmission- I’d like to combine an RC plane with waypoint following and Wireless Video Transmission. Technically, what I really want from this is to be able to fly an RC plane with a first person view; so not actually an Arduino project. But a project!… for much later in life.
• 3D Rotation Puzzle- A bit simple, but could be interesting. Use either a 3 axis accelerometer, or a set of 3 tilt switches, to build a puzzle that you play by rotating. Generate sequences of increasing length using a random number generator. Use a painful buzzer of shame on failure, cool LED’s of awesome on successful navigation of the puzzle. Alternative would be to use time trials on a puzzle with visual feed back on next turn to take. (The description will make more sense when it’s implemented)
• Knock Lock- An interesting use of Piezo Elements is detection of sudden changes in noise level; as one might expect with, say, knocking. You could reasonably extend this to opening locked doors, for keyless house entry. Alternatively, might be safer to use a keypad, but why go the boring route?
• Plywood Impact Location Sensor- http://www.youtube.com/watch?v=WNZCS-coZjY FPS with real guns… or, you know, duck hunt. Whatever works for you. It also seems like, if this could detect soft enough motion, that you could then use said large surface as a simple input device.
• Kite Control- I’d like to get into Kite Photography. Or flying kites. Or both. One interesting aspect of this could be adding control surfaces to a kite, allowing for rudimentary wireless control… of a kite. (Side note: I am not an RC Plane Hobbyist, or Aeronautical Engineer)
• Air Soft Turret- Probably not technically Air Soft, but I’m not sure of the official name. Many moons ago, I and my brother got a set of small battery powered toy guns that fired reasonably painful yellow BB’s. I’d like to to strip the toy casing, and mount the parts onto a turret for remote controlled target practice… with co-workers. Would also probably go nicely with a robot mounting.

I think one of the more frustrating things about going from PC’s to microcontrollers is that while uC’s have the ‘interact with the physical world’ aspect to them, they have such limited processing power that for a lot of interesting applications they need constant contact with a PC. At least I suspect so. As an example, I’d like to play around with motion tracking cameras. Video Processing like that isn’t something that could be done on a 16 MHz processor. Granted, doing it real time would probably also be a strain on an average computer, but the point still stands. This is probably something better suited to embedded PC’s, which is another ball of wax I’ll need to play with sooner or later.

Broad Update

Yes, this shall be a blog updated once every few months to say ‘I should write more’. Whatever.

ACM and AI
Starting with the current purpose of this blog, the ACM Local competition was last week; and I successfully succeeded at succeeding. First place by one problem. I went to the last two ACM contests with one of my teammates, and the other one I have a fair amount of confidence in. We shall see what happens. But, as a humorous aside to that: I very nearly implemented a Sudoku solver in under 30 minutes. Had I stopped asking myself ‘is it worth it to put in this much effort into a problem you probably won’t solve before the contest is over’; I probably could have solved it. Probably not, but maybe. I solved it using a horribly hacked together Constraint Satisfaction based Solver. For that interesting 30-50 minutes of my life, I would like to thank Robin Murphy (AI Prof), and Peter Norvig (Algorithms God/AI Book Author); both of which suggested Sudoku solving as an application of CSP. I’ll probably clean it up later and post it… as it stands currently it makes me want to cry, but it theoretically should work. (Theoretically because the test data was, in fact, invalid).

Education- Dr. Tao?
On a different note, I think I’m going to go for a PhD. This conclusion was got to by an interesting failure in my ability to communicate. As part of a follow up email, I had written the line ‘assume I go for a PhD’, which led to the thought ‘If I graduate and go into industry with a Bach, I’m going to end up drifting from job to job with mounds of uncertainty and stress’ (drifting coming from the popular consensus that a programmer should expect to change jobs every 2-3 years). If I get a PhD, there’s a lot less uncertainty in terms of job (at least I hope), I have the opportunity to interact with really incredibly frustratingly annoyingly intelligent folk, and if I go the academia route, I can torture a class of Yankee’s with ‘Howdy Class’. How can you not like that?

As a side note, I suspect the reason I was never comfortable with the thought of Grad School before is because I had never really come across something that peaked my interests. There’s a popular quote by Dijkstra: “Computer Science is no more about Computers then Astronomy is about Telescopes”. I have this odd sense that it is often misinterpreted from it’s original context. Computer Science is about the mathematical basis behind computing: proving algorithms correct, classifying problems as NP-hard, finding the most efficient way to find a correct solution, all about the theory. To me, that is what Computer Science Grad School is/was about. And I hate that definition. Mostly because it feels like something from the Ivory Tower- occasionally interesting results with only limited real world applicability. I want to generate solutions to real problems. Is making a formally proven OS kernel useful? Maybe to some, but spending 5 years to develop 10,000 lines of proven code just feels like a waste. I’ll probably regret those statements later, but, such is life.

Further side note: one thing I’ve heard fairly commonly is that in general, you don’t recoup the cost of a PhD. A master’s is worth it, but a PhD won’t earn you more over a lifetime. My response: Who cares? If you’re making a career or education choice based soley on ‘will it pay off in the end’, then you’re doing something wrong. Education (and career) should be driven off personal interest, and as an auxiliary, will it earn enough money such that you won’t live in a cardboard box. Going into advanced education because it will buy your retirement home a heated pool is just plain wrong.

Shiny New Toy- Arduino
Yet another different tact, I have a shiny new toy. An Arduino. With a product name which I can neither remember, pronounce, nor spell. I can at least remember/spell Arduino… pronunciation is still off. I blame the Italians. I got it in part because I wanted to get involved in the electronics/embedded side of computing, and mostly because it provided a convenient way to solve a problem my brother was having.

My brother, through what I assume were family connections, was hired to fix an outdoor LED sign for a bank. The company that manufactured the sign had gone out of business, but he was able to get some schematics for how the individual boards in the sign were wired. While he could take the boards down, ohm out connections, and so on, he didn’t have a convenient way of actually testing that either the repaired sign worked, or finding where issues might lie in malfunctioning boards.

I psuedo-come-in at this point. He asks me if I can write a program that would be able to test the boards. The boards themselves are driven off 4 inputs- 2 serial lines, a clock, and a latch. In the sign they’re driven off of what is probably a parallel port on a 386 running windows 98. I’m not sure if you’ve noticed, future reader, but most computers these days don’t come with parallel ports. So I go through the thought process of ‘how could I go about this’; serial ports don’t really work, as at most you might be able to control voltage on two lines; we could go through the trouble of finding and installing a parallel port expansion on a testing computer, and try to write a program that would drive the port/board. And then I thought “wasn’t there something Kyle mentioned not long ago; an Arduino?”.

It fits the bill perfectly. So the short ending to this is: the first day I got it, I broke it out, did the standard “Make an LED flash” thing to see if everything was working; and the second day I built a controller for the sign boards. A bit later I added some simple configuration bits, a button to switch between testing modes, and hooked up the 9V battery so the computer became completely unnecessary. My brother has since stolen it for testing, until he can get his own.

So, I feel good about that. One thing I’ll probably post soon is a list of projects to go along with it. Y’Know, to go along with the other list of projects I’m not making progress on. I might also post more details about the sign, as it was a fun first project/jaunt into Computer Engineering.

Deutschland
I’m also planning to go to Bonn next Summer as part of a study abroad program. I’m trying to learn some German for that; and it’s coming along slowly. And that’s it. That’s all. See y’all later.

ACM 2008 SCUSA Wormholes- 2nd Edition

Last time we left our time travelling hero’s, they were using a repeated applications of the Bellman-Ford algorithm (at time complexity O(|V| * |E|), where |E| is on par with |V|, and number of requests is probably also on the order of |V|, giving a total of O(|V|^3)). Our valiant programmer desperately seeks to apply an the Floyd-Warshall algorithm to the problem, just so that the time spent reading the analysis of algorithms book isn’t wasted.

The secret to successfully applying the Floyd-Warshall algorithm to this problem is the same secret to getting reasonable performance out of the previous solution. You can’t look at each individual year, you instead must look at time spans between meaningful events. That brings the number of vertices down from many thousand to at most 301 (starting year + 200 distinct wormhole years + 100 mission years). It has the downside of making the process of finding weights a fair bit more complex:

public int[,] BuildInitialWeights(List<int> distinctVerticies)
{
    int[,] weights = new int[distinctVerticies.Count, distinctVerticies.Count];
    for(int i=0; i<distinctVerticies.Count; i++)
        for(int j=0; j<distinctVerticies.Count; j++)
        {
            if (i == j) weights[i,j] = 0;
            else weights[i,j] = Int32.MaxValue;
        }
 
    //assumes vertices are in order, from first year to last
    for (int i = 1; i < distinctVerticies.Count; i++)
    {
        int start = distinctVerticies[i - 1];
        int end = distinctVerticies[i];
        weights[i-1, i] = end - start;
    }
    foreach (int[] years in wormholes)
    {
        int i = distinctVerticies.IndexOf(years[0]);
        int j = distinctVerticies.IndexOf(years[1]);
        int weight;
        if (years[1] > years[0]) weight = (years[1] - years[0]) / 2;
        else weight = (years[1] - years[0]) / 4;
        weights[i, j] = weight;
    }
    return weights;
}

Here we’re building a 2D matrix of weights. Informally we’re mapping each year in the distinct vertices list to its index, then using that index as coordinates in the weight matrix. Weights are constructed by first setting all weights to their default values (0 to get to current node, max value for other nodes). Then default weights for moving forward with time are assigned. Finally, wormholes are accounted for. Wormhole accounting is done last as it will be, by definition, the shortest path between two points. This has the advantage that only one path is ever considered between two points, where as the previous solution allowed for multiple paths.

public List<int> BuildDistinctVerticies(List<int> addedYears)
{
    List<int> years = new List<int>(addedYears);
    foreach (EndPoint wormhole in wormholes)
    {
        years.Add(wormhole.Start);
        years.Add(wormhole.End);
    }
    years.Sort();
    for (int i = 1; i < years.Count; i++)
        if (years[i - 1] == years[i])
            years.RemoveAt(i--);
    return years;
}

This is the simple method for building all distinct vertices. It starts by taking all mission and starting years, adds each end point from a wormhole to the list, then sorts it and removes duplicates. Again we get into ‘it would be nice to have a Sorted Set’ (Should appear in .NET 4; or, alternatively, has always been in Java… accursed Java with its nicer Collections libraries…).

public int[,] AllPairs(List<int> missionYears, out List<int> distinctVerticies)
{
    distinctVerticies = BuildDistinctVerticies(missionYears);
    int[,] currentWeights = BuildInitialWeights(distinctVerticies);
    int[,] nextWeights = new int[distinctVerticies.Count, distinctVerticies.Count];
    for (int i = 0; i < distinctVerticies.Count; i++)
    {
        Extend(currentWeights, nextWeights, i);
        int[,] temp = currentWeights;
        currentWeights = nextWeights;
        nextWeights = temp;
    }
    return currentWeights;
}
 
public void Extend(int[,] previosLevel, int[,] thisLevel, int k)
{
    for(int i=0; i<previosLevel.GetLength(0); i++)
        for(int j=0; j<previosLevel.GetLength(1); j++)
        {
            int iToJ = previosLevel[i,j];
            int iToK = previosLevel[i,k];
            int kToJ = previosLevel[k,j];
            if (iToK != Int32.MaxValue && kToJ != Int32.MaxValue)
                thisLevel[i,j] = Math.Min(iToJ, iToK + kToJ);
            else thisLevel[i,j] = iToJ;
        }
}

I’m about 90-100% certain I misspelled previous. Ignoring that, here we can see Floyd-Warshall algorithm implemented. I don’t fully understand how it works. I’ve read that the ‘extension’ element is simulating whether or not the shortest path from i to j will go through k; but at this hour of the morning I still can’t quite wrap my head around how it works. Something to learn for the new school year.

The distinct verticies are passed as an out parameter to the caller, so that they have the map from index to year available to them.

List<int> years = new List<int>(missions);
years.Add(startingYear);
int[,] distances = timeline.AllPairs(years, out years);
 
foreach(int destination in missions)
{
    int i = years.IndexOf(startingYear);
    int j = years.IndexOf(destination);
    int toDistance = distances[i, j];
    int fromDistance = distances[j, i];
    if(toDistance==Int32.MaxValue || fromDistance==Int32.MaxValue)
        Console.WriteLine("IMPOSSIBLE");
    else
        Console.WriteLine(toDistance+fromDistance);
}

Finally, the relevant changes to the problem solving method. The down side to using this approach is that there isn’t a direct mapping from year to index; so a linear search is performed to get that mapping. It’s not really an issue, considering what else is being done, but it is a bit unfortunate.

Analysis
Psuedo-analysis might be more accurate. Comparing this to the previous solution, I like the fact that the algorithm seems more straight forward, and that in the end we end up with a massive table of possible paths, should our time travelling agents ever need to do strange other things. It also has a slight performance advantage over the straight version from last time. (It’s about on par with not continuing the Bellman Ford algorithm if no relaxations occur, though that might be in part due to poor implementation of that algorithm).

That said, in its current form, it adds about 30 lines of code, and the indirect mapping from index to representative year feels ungood. In the end, the question for ACM problems is ‘which could you code fastest with the lowest probability of error’, and looking at the two, I think the Bellman Ford would be a bit easier, specifically because it uses a series of edges, rather then a weight table. I could be wrong though, and the performance level does seem to be in favor of Floyd Warshall.

Side Rant
I seem to be rather poor at a very specific bit of contestifying. That is seeing points where you can discard unimportant information. In this problem, it was my attempt to treat every year as a vertex. In a problem about a disk defragmenter, I was tempted to treat the disk as a series of sectors rather then a series of filled and unfilled ranges (would have massively increased computation time to simulate, and probably over complicated the code; didn’t get to find out due to contest ending). I find that this seems like a common theme to me: I constantly attempt the simplest solution that could possibly work, and these problems are more often then not tuned to make that ‘the wrong way’. I suspect this comes from my many years of employment, where you’re not necessarily seeking the best solution, but rather just something that works well enough to get by. That is, of course, part of why I started this crazy blog: to get better at recognizing when I’m going down an incredibly wrong path.

Full Source Code for this solution.

ACM 2008 SCUSA Wormholes

South Central USA has to be one of the odder acronyms in common use… a single character away from SCUBA no less.

The last time I went to ACM, this problem was delegated to one of my team mates, and for one reason or another we never got it solved. I was reading through an Analysis of Algorithms book and came across a section on All Pairs Shortest Path and thought ‘This would apply perfectly and elegantly to this situation’. (I was wrong, but we’ll get to that soon). (Also, judge data can be had at this location, and I have been cheating miserably).

Synopsis
You work at Time Travel Inc. in the payroll department. Sick of keeping up with all the math related to time travel, you contracted yourself (while in college) to develop an application to determine how much a person has aged during their time travel, and whether or not their last journey was even physically possible. More specifically, time travel is acheived by portals which appear at specific moments in time, and exit at other specific moments, either aging or youthifying the human in the process, according to a specific formula; and ignoring the concept that you could die, or be negative years old.

Analysis
This is a graph traversal problem with negative weight directed edges. The goal is to find the minimum weight path that takes you from a start, to a destination, and back to a start; or equivelantly, two graph traversals.

As I said, I had read a bit on All Pairs Shortests Paths and was interested to see how it would handle this. Specifically, I was thinking ‘if you treat each year as a vertex, then each vertex has a weight one edge to the next year; and if a wormhole is present, an edge to that destination year. At this point in time, I thought the input was constricted to a few hundred years near the 2000’s (where else would you time travel to?). The actual range of years is from 1-10,000. 10,000 verticies, 2 10,000 x 10,000 matricies for storing path weights… no. Not gonna work. (As we’ll see in a bit, this is actually a bit of a lie).

Still curious to further my learning, I read up on the Bellman-Ford algorithm, which is a single source shortest paths algorithm. It works on the assumption that the absolute longest path will go through every single vertex in V, and therefore you can determine the minimum cost to get anywhere by going through each edge, relaxing the edge’s destination weight if appropriate, and then repeating that |V| times. Complexity of |V|*|E|. That actually sort of worked, in the sense that it produced an answer for most problems in under a minute. But, under a minute isn’t quite ideal.

To get reasonable response times, you can’t simulate every single meaningless year. You have to focus on only the meaningful ones, and declare edges between them. If you’re in 1950 and want to get to 2050, yes, you can look at it as 100 1 year edges, but it would be less pain to look at it as 1 100 year edge… or, if a wormhole happens to open up in 2012, a 62 year edge followed by a 38 year edge. The downside to ignoring meaningless years is this adds a fair bit of complex non intuitive code, just for the purpose of filling in the ‘time moves forward at a constant rate’ bits.

With that said, you could apply the same reasoning to all pairs shortest path, so long as you only kept track of the vertexes you actually cared about.

Source Code
As this one is a tad bit long, and far from being the greatest, I’m only going to post bits and peices of it.

public static void ProcessProblem(int id, TextReader input)
{
	Console.WriteLine("DATA SET #" + id);
	Timeline timeline = new Timeline();
	int wormHoleCount = ReadInt(input);
	for (int i = 0; i < wormHoleCount; i++)
	timeline.AddWormhole(ReadInts(input));
	int startingYear = ReadInt(input);
	int missionCount = ReadInt(input);
	for (int m = 0; m < missionCount; m++)
	{
		int destination = ReadInt(input);
		int distance = timeline.ShortestPath(startingYear, destination);
		int returnDistance = timeline.ShortestPath(destination, startingYear);
		if(distance==Int32.MaxValue || returnDistance==Int32.MaxValue)
			Console.WriteLine("IMPOSSIBLE");
		else
			Console.WriteLine(distance+returnDistance);
	}
}

Above is the primary problem solving bit. We create a timeline, register wormholes, then go through each mission and determine if the destination can be reached from the starting point, and if the starting point can be reached from the destination. Note that we’re using the max value of an int as a ‘no path’ return code.

class Timeline
{
	private List<int[]> wormholes=new List<int[]>();
 
	public void AddWormhole(int[] wormhole)
	{
		wormholes.Add(wormhole);
	}
 
	public int ShortestPath(int sourceYear, int destYear)
	{
		List<Edge> edges = new List<Edge>();
		List<int> vertexes=new List<int>();
		vertexes.Add(sourceYear); vertexes.Add(destYear);
		foreach (int[] wormhole in wormholes)
		{
			vertexes.Add(wormhole[0]);
			vertexes.Add(wormhole[1]);
			edges.Add(new Edge(wormhole[0], wormhole[1], true));
		}
		vertexes.Sort();
		for (int i = 1; i < vertexes.Count; i++)
			if (vertexes[i] == vertexes[i - 1])
				vertexes.RemoveAt(i--);
		for (int i = 1; i < vertexes.Count; i++)
			edges.Add(new Edge(vertexes[i - 1], vertexes[i], false));
 
		Dictionary<int, int> distances = new Dictionary<int, int>();
		distances[sourceYear] = 0;
 
		for (int i = 0; i < vertexes.Count; i++ )
		foreach (Edge edge in edges)
		{
			if (!distances.ContainsKey(edge.start)) continue;
 
			int distance = distances[edge.start] + edge.weight;
			if (!distances.ContainsKey(edge.end) || distances[edge.end] > distance)
				distances[edge.end] = distance;
		}
		if (distances.ContainsKey(destYear))
			return distances[destYear];
		return Int32.MaxValue;
	}
}

And here we have the meat of the problem. The graph traversal algorithm/timeline class. The first portion of the ShortestPath method is soley responsible for building a list of edges (note, third parameter to edge constructor is ‘isWormhole’). Once that is constructed, the Bellman Ford algorithm is repeatedly applied to get the distance from the start point to every other point. Bellman Ford performance can actually be improved slightly by not continuing to iterate if no relaxations were needed on a given iteration. On my machine, execution time went from about 3s to .5s. (Also, as a fun aside, note the sad lack of a .NET Set class).

That’s all for now. I think I’ll reimplement this with an all pairs shortest path just to see if it would meet time constraints on execution; and make a post about that later. Also, I’m planning to try and deploy/install Wordpress, with some form of auto syntax highlighting magic included, to make this blog thing a bit easier. We’ll see how that goes. And, for a third thought, I finally got started on LC3D, after mere months. I’m working on the GUI now, getting camera to work right, everything rendering, etc. Then I can start in on the fun that is integrating EVERYTHING. Yay.

Full Source Code for First Solution.

Developer Training

Let’s chat about an idea I had for a training project; something to bring someone from an academic environment into a mildly professional environment. When I first started at the ESL, I was given a relatively simple project… after I was given a fair amount of grunt work you’d expect of a high school intern. I spent more time then I should have on that project, but in retrospect I realize that, if adapted slightly, it’s perfect for bringing someone up to speed on things like databases, ORM, .NET, how the web actually works, etc.

Background
Part of what our lab used to do is maintain a database of hourly weather readings at sites across the state. In the past we received emails from the Meteorology department with a fixed width file that contained the relevant data; and we would parse these emails with a cron job on an ancient UNIX machine; the data going into an Informix database. For one reason or another this system needed to be shutdown (Meteorology stopped sending emails; UNIX machine got hacked and destroyed; desire to make the data more accessible; etc).

The original goal of this project was to replace the old system with a more accessible system; in our case using Microsoft technologies (SQL Server for data storage; and a .NET language for data retrieval). The new goal is to do this while iterating through technologies that you’ll encounter in your everyday life.

Data
I figure this is worth spelling out first. Previously we received data in the form of an email. Where precisely are we going to get weather data now? We can’t just go around installing internet enabled weather stations… this is only a training project, not a mass system deployment (sadly).

As it happens, NOAA provides the (current) weather readings in a freely available XML format. As an example: http://www.weather.gov/xml/current_obs/KCLL.xml is for Easterwood Airport, College Station, TX. They provide these for many locales, listed here: http://www.weather.gov/xml/current_obs/seek.php?state=tx&Find;=Find. Most of the XML files will update only once an hour, but there are a few that’ll update more often.

Goal
The goal is to, given a list of weather stations (either URL’s or just station names), write a service that periodically pulls down the weather data for each station, parses it, and puts it into some form of long term data storage. Duplicate readings (ie the weather station hasn’t updated) shouldn’t be stored. Also, the XML files contain a fair bit of extraneous data that can be done without; we can ignore anything extra.

Advised Process

1. Start by getting source control setup.
   • If getting an svn server is too much overhead, look into using Bazaar, git, Mercurial, just some form of source control.
   • Setup a project / solution structure. In our lab we would have a root project folder containing overhead files (solution file, build files, etc), and then a Source folder and a Database folder under the root.
   • Throughout this I’ll mention that ‘everything should be in source control’ at the end of an iteration. This is not to imply that that is the one specific point to check in all your changes to date. Source control should be an integrated part of development: once you hit a milestone, it’s time to do a commit. Remember, ’commit early, commit often’. Just don’t commit broken things.
2. For a first iteration, download a single file, parse it, and display it to the screen
   • Interjecting a bit of personal thought; when you first attempt this, try it using a Raw Socket, and the HTTP protocol. Not because it’s advisable (it’s not), but because it shows you the foundation on which the web is built. It’s good to understand this most basic building block.
   • Once you’ve had fun with raw sockets, look into what your language provides by default for making web requests. C# provides a WebRequest object with a Create method that can be used; Java, python, etc probably provide something similar.
   • For Parsing. DO NOT USE ANY METHODS ON THE STRING CLASS. Parsing XML by hand is something that you will be shot for: it’s a death penalty offense. Look into what your language provides for XML Parsing.
   • For storage; for this first iteration, just store to a flat file; one entry per line.

   And that’s it for the first iteration. Make sure everything is in source control, and have a senior fellow review what you’ve done. At this point the senior is looking for basic faults: did you name a public property ‘theTemperatureRightNow’ or ‘Temp’; as well as basic class structure.

3. The next element is to add configuration, multiple stations, and the ’service’ aspect to it.
   • .NET configuration is usually done through a file called app.config (later renamed to AppName.<extension>.config), and is accessible through System.Configuration.ConfigurationManager ; I’m not sufficiently familiar with other languages to say what’s available; but writing a Config Manager isn’t terribly difficult if your language doesn’t provide it.
   • When I say service; I don’t necessarily mean a Windows Service (or unix dameon process); just a program that contains something akin to for(a very long time). At the simplest level, this can be done with a while(true) loop, with a 15 minute thread sleep. Your language may also provide a Timer construct specifically for firing off threads at specific intervals; using that would be perfectly valid too.
     NOTE: this isn’t something that would be repeated once every second, or once every minute. The data updates at best once every fifteen minutes; common ettiquete demands that ~fifteen minutes be your shortest pause.
   • Logging would also be good to play around with at this point. Most logging packages also come with a form of file configuration; look into playing with that a bit.

   At this point we have a configurable service that will pull down data from any number of weather stations, and parse out the bits we want. Put everything in source control, get a senior to do a quick review of what you’ve done, and listen to any comments they have.

4. Next, we’re going to add database storage.
   • Determine an appropriate database schema. I would suggest two tables, one carrying weather station information, the other carrying reading information. A reading should have a link back to its weather station; and each table a primary key.
   • For this version, use the raw API’s provided by your platform/language; learn the joys of SqlConnection, SqlDataReader, and parametrized queries.

   So, again, everything in source control; have a senior look at it. At this point, database design and class structure are probably most important; the data storage layer should have a well defined, simple interface that doesn’t cause a headache on viewing.

   Also at this point, you should have a starting idea for what SQL is like. The project should be far enough along that it can collect data. Let it run for a day, and play around with getting interesting weather stats in SQL.

5. An ORM layer
   • If the data access component was coded to both save and load Weather Readings, then it’s probably possible to extrapolate the fact that writing this transform code sucks. A lot. If left with only SQL, a developer can spend a few days working out data access for a mildly complex object; potentially weeks with things more complex.

     ORM fixes this by implementing a wrapper layer for the whole of SQL Transformation; your only job in turn is to define what’s relevant to the transformation.

   • Implement another Data Storage class using an ORM technology. Use the same interface as the SQL storage class above.

   That’s it for this one. Call a senior over to see what you’ve done; they should be checking to see that everything makes sense, looking for possible points of confusion, etc.

And that’s it for now. It could be extended to include things like Dependency Injection for choosing the output method; a web application fed off the database to get summary data, which can in turn evolve into an AJAX web app with web service back end. You could also go the route of a desktop summary viewer if that’s relevant to what you do. You can attempt more random and off the wall ideas- try to build a temperature map off the data and an overlay of the state map; AI algorithms for predicting the next hours readings; statistical analysis (linear regression to predict temperature at a station that didn’t report); feeding the data into a weather simulation in an MMO. All manner of things.

There’s also a bit of unit testing / TDD possibility, though I’m not certain it’s quite complicated enough to warrant it, and a TDD intro is probably better done by pairing at first, which goes against the goal of a (mostly) solo training project.

Conclusion
I have presented a poorly worded and untested training project. This project is suitable for use as a first project by interns and student developers. This project’s primary goal is to bring less experienced developers up to speed on shop practices, while also providing a reasonably interesting and non-daunting problem for the new developer to solve.

The primary problem with this approach is that it isn’t immediately relevant to what’s being done in your group. Once finished, you’ll still have to go through and bring the dev up to speed on your project. Hopefully the active training will take slightly less time as you don’t have to go through and explain the major concepts. And hopefully they’ll be less likely to commit major sins, but it’s still not ideal. The ideal would probably be to bring the dev up to speed through pair programming, and slowly let them start working on their own / take control.

All that said; it might be just me that’s interested in this stuff. I like being able to go back and say ‘yes, the high for last week was 103 F; with a max wind speed of 20 mph’. I can foresee some developers being less enthusiastic about developing this system. However, for those actually interested, I think this would be a good learning experiment.