A while ago, I posted a habit that programming has given me, and here's another. I don't think it's really a bad habit, as the original Stack Overflow question asked, but in a nutshell, I want to know algorithms for everything. The thing is, I'm not as interested in how software running on the space shuttle works, or running the machine that goes "bing" at the hospital. I'm interested in algorithms for relatively simple everyday things. I'd love to take a look at the source code for software running a car stereo, a bank machine, the fountains at the Bellagio in Vegas (I once saw a TV show on the guy who wrote that – very cool), or even a digital watch. One of the coolest projects I've ever worked on was a CD player application while I was at Microsoft in the fall of 1991. There was an app in Windows 3.x called Musicbox, which I suppose was the precursor to Windows Media Player. My job at Microsoft was to write a clone of that application. I never really figured out why they wanted me to do this – they had Musicbox which worked nicely – but I loved the project. I had buttons for play, stop, pause, fast-forward, rewind, and eject (which I labelled "spit" as in "spit out the CD" – it was funny when I was 22), a horizontal scroll bar that allowed you to seek to anywhere within a song, and other cool things like the ability to "bookmark" any part of a song (eg. "Awesome guitar solo!!!1!") and then immediately seek to it again later. MP3 didn't exist at the time, or at least I didn't know about it, so we were solely dealing with actual physical CDs.
Anyway... enough reminiscing, let's get back on topic.
I know how a GPS generally works – there are satellites in orbit that send out signals, and the GPS unit receives the signals from several satellites and somehow uses them to determine its exact position. I don't know exactly how, but I get the general idea. And I can guess how turn-by-turn navigation works – that's just graph theory. But what I want to know is how the information about roads and addresses and stuff is encoded in the graph. Sometimes you get a turn direction like "turn left at Dundas St." and other times it's "keep left onto Hwy 403". Somehow it knows that to get onto the 403, you stay to the left side of the road, rather than actually making a turn. How does it know that? How does it know that 222 Jarvis St. is between Dundas and Gerrard and not south of Queen?
All of the one-way streets and on- and off-ramps must be marked as such, as well as intersections where certain turns are not allowed, and other weird things like when there are two sets of lanes on a highway and you are in a set that doesn't have access to a particular exit. Every address must be encoded in there somehow indicating where on the street it is, including what side of the street and how far it is from the nearest cross street. How is that all encoded? I want the database schema.
Another example would be elevators. They're very simple to use, but how does the software controlling everything work? Say there's only one elevator which is at the ground floor. Someone on the 5th floor presses the "down" button, so you send the elevator up to 5. As they're getting in, someone on the 8th floor presses down, and then the person on 5 presses "2". Do you go down and drop off the person on 2 and then go up to 8? Probably. But while you're going down to 2, what if someone on 4 presses "up" – do you pick him up on the way back up to 8? What if he wants to go to 12 – do you take him up to 12 and then go back down to 8? That means that the guy at 4 got serviced before the guy at 8 although the guy at 8 arrived first. Are you trying to make things fair (i.e. first-come first-served), or reduce average waiting time, or reduce elevator movement, knowing that the occasional "customer" may have to wait a long time? Do people that have been waiting longer gradually become higher priority? Having multiple elevators servicing the same floors should reduce waiting times, but would make the algorithm more complicated. If there are three elevators and one is "out of service", does the software compensate for that by simply ignoring that elevator or does it change the algorithm somehow?
I'm sure some software developers dream of writing software to run in the most complex and important computer systems in the world – air traffic control systems, nuclear power plants, an automobile assembly plant. Me? I would love to write the software controlling a DVD player.
No comments:
Post a Comment