Programming Competition Post-Mortem

Every year the ACM-sponsored International Conference on Functional Programming holds an elite Programming Competition for international recognition (and a $1000 cash prize). Essentially, a problem is posted on their website on Friday at noon and each team has all weekend to complete and submit a solution in whatever programming language they choose. This was the first year I’ve competed and I’m pretty much hooked forever.

The International Conference on Functional Programming is a conference geared to promote functional programming languages, such as Haskell, Lisp and Scheme. For those of you who are unfamiliar with functional programming, it’s a completely different mindset from regular programming. One has to “think recursively”, or as “Lambda geeks” would say: think “purely”. In recent years, the ICFP Competition has become more and more accepting of “general purpose” languages such as Java to make the competition more approachable to mainstream developers. (To illustrate my point, try doing a Monster job search for “Scheme” and “Java” to see the extreme difference in numbers).

This year’s problem was very interesting: our job as the competitors was to create a pathfinding algorithm for a Mars rover simulation, which included obstacles such as Craters and Boulders and intelligent martians (though at times NOT too intelligent) who would destroy your rover on contact. This wasn’t a simple “just-implement-A*-pathfinding-and-be-done-with-it” problem because you had to take into account turning radius, radial acceleration, drag, martian avoidance AND desired location - not just desired location.

Our team (NAU ACM and facebook group) decided to program our solution in Abe Pralle’s gaming language, Slag, not only to promote Abe’s language but also because this was a *perfect* problem to show off Slag’s strengths. Pathfinding is not a new concept to game development and most of our collision detection routines were already written for us in the Plasmacore framework.

Our first lightning solution algorithm was as rough as rough can be: the rover would just make a bee-line for the homebase, damning the consequences and obstacles. We had discovered a bug in our first implementation that forced the rover to “wobble” which actually ended up being a remarkably effective obstacle avoidance technique! Our lightning round solution (within 24 hours) used this basic method with a simple “avoid the closest crater to you” intelligence.

Our final solution algorithm was two-part, working together and sharing information:

1. The first part of our algorithm was taken from our original rough lightning round design - the rover wants to go “home”. If there was an obstacle in the way, the controller would “move” the home base location until the obstacle was no longer blocking our path. We then calculated the rover direction necessary to make that non-obstructing path a reality.
2. Then the path was sent to the “emergency response system”. Our rover had 5 “view fingers”, which were essentially linear vector paths in five different directions (Hard Left, Left, Middle, Right, Hard Right). The rover would determine the linear direction that would get him closest to the “home base” and then determine whether this direction was safe to travel (with line/circle collision detection). If the direction was safe, he would travel there. Otherwise, we had a complex system for him to determine the closest path he can take whilst avoiding the obstacle in front of him. Dr. Palmer came in and explained to us the the closest path around a circular obstacle (craters, boulders, martians) is actually by “hugging the obstacle as close as possible”, so we used that method.

Throughout the experience, we had a sister competitor team we would occasionally call at 3AM to discuss strategy and progress. It felt more like a scientific collaboration than a competition - everyone was trying to find the best solution and working together rather than keeping information under wraps. There were about 350 team submissions to the regular competition and 170 lightning round submissions, according to the competition organizers. During the competition, the IRC channel had close to 350 people all conversing about strategy and rules together. It did seem in this competition, collaboration really did seem to pay off over competitiveness. But you know, hope we win! Sadly, we don’t get to see the results until September!

Music as a Social Event

With the mind-blowing success rates for social networking websites like Facebook and Myspace, it seems like the next logical step would be to integrate music in a more cohesive manner with the network itself. Music has always attracted a sort of cult following - in some cases music can be almost spiritual, creating somewhat of a cult-like following.

So perhaps I seem like the last person on Earth to have heard about social music network thesixtyone, but still I must give props. It’s a music adventure: it’s a great place to find amateur music plus it’s got a full economy of points built into the site so you can actually spend the entire day earning points by “bumping” your favorite music to the top of the charts. My inner Japanese completionist stirs.

Creating Newer, Stronger Artificial Intelligence

With human-like Artificial Intelligence being in it’s current state (essentially non-existent), I’ve been asking myself the question lately:

What would it take to make a truly intelligent artificial intelligence system that could actually comprehend human language?

Let’s start with the history. A chatterbot is essentially a conversational agent, designed to simulate normal human conversation. Early chatterbots, such as Racter, Eliza & ALICE recognized basic keywords to which it would formulate responses (not very intelligent). Racter was the famous author of the first book ever written by a computer, The Policeman’s Beard is Half Constructed, which was essentially a collection of poetry about love, various meats and lettuce (it makes a great read after a few glasses of wine!):

“At all events my own essays and dissertations about love and its endless pain and perpetual pleasure will be known and understood by all of you who read this and talk or sing or chant about it to your worried friends or nervous enemies. Love is the question and the subject of this essay. We will commence with a question: does steak love lettuce? This quesion is implacably hard and inevitably difficult to answer. Here is a question: does an electron love a proton, or does it love a neutron? Here is a question: does a man love a woman or, to be specific and to be precise, does Bill love Diane? The interesting and critical response to this question is: no! He is obsessed and infatuated with her. He is loony and crazy about her. That is not the love of steak and lettuce, of electron and proton and neutron. This dissertation will show that the love of a man and a woman is not the love of steak and lettuce. Love is interesting to me and fascinating to you but it is painful to Bill and Diane. That is love!” -Racter

So aside from the obvious fact that Racter belongs in a mental hospital, he does actually understand a lot about the syntactic constructs of the English language. Let’s break down an English sentence together:

But this is simple, right? Even the mentally unstable Racter chatterbot could have broken this sentence down into it’s syntactical constructs. Let’s look at the meaning now.

The pensive warthog thinks about Lucy in the morning.

So, does the warthog think about Lucy while she’s making breakfast in the morning or does the warthog always wake up thinking about Lucy? The meaning here is ambiguous, even as a human reading the sentence. Grammar Queens would tell you that prepositional phrases that end a sentence are actually associated with the location or context of the action, so the warthog would be thinking in the morning rather than the opposite. But do humans always speak with perfect grammatical clarity? Hells naw!

So then what would it take to make an intelligent agent?

Semantic Web enthusiasts would tell you to have the human hive-mind pre-compute the meaning of everything on the internet: That is, assign meta-data about relationships, connotations, categories and labels to every single piece of information on the internet.

One website states the ecological habitat of the African Swallow: caves and cliffs of a few particular regions in Africa. Another website lists all of the shrubbery that grows in these particular regions. How could an intelligent agent infer what an African Swallow might eat? If all of the data on these websites has listed the relationships (A swallow lives in Africa. Africa has trees, shrubs and grass growing there.), the intelligent agent could make intelligent inferences, such as “Since there are no coconut trees growing in Africa, the African swallow couldn’t possibly eat coconuts.”

That’s quite a feat, but that might actually be what is required for an intelligent agent to learn the culture of humanity in context.

It’s been mentioned to me before as a joke, but isn’t this the kind of super-network of information that would allow a SkyNet to take over? Terminator: The Sarah Conner Chronicles is an excellent show, by the way - you should definitely check it out! It’s free!

Resources for Learning Brazilian Portuguese

Since ACM SAC 2008 is going to be held in Brazil this year, I’ve decided I’m going to learn Brazilian Portuguese before I go in March. Brazilian Portuguese is a bit different from regular European Portuguese (Portugal), so I’ve been having to do a lot of digging online for specifically Brazilian Portuguese Language-learning links. Since I have the links anyway, I thought I might share them in case anyone was having as difficult a time finding specifically (free) Brazilian Portuguese language learning resources:

Websites

• Brazilian Portuguese Grammar This is an excellent all-around resource for learning the basic grammatical constructs of Brazilian Portuguese.
• Handy Travel Phrasebook This is a digitally available Brazilian Portuguese phrase book. It’s $2.00, but I think it’s well worth the money.

Podcasts

• Brazilian Portuguese Podcast (Episodes 1-15) (Episodes 16 - 49) (Episodes 49+). I’ve found the speaker to go at an extremely slow pace, which is great for total beginners, but the website that hosts episodes 1-15 seemed impossibly slow at times. If you prefer to learn languages at a slower pace (repeating the same word three times), this is definitely the podcast for you. The sound quality isn’t remarkable, but since he repeats everything a few times, I can actually understand the words better than a lot of other podcasts.
• Brazilian PodClass (iTunes) (Web Site). I’ve found this speaker goes remarkably fast at times. I had to pause, rewind and repeat the sentences at times and only half the podcast transcript is included with the podcast. But if you tend to learn languages at more of an “immersion” pace (being constantly bombarded with new material), this is definitely the podcast for you. The sound quality is superb.

For any of you actual diplomats out there that need to really learn the language quickly and efficiently, I highly recommend the very expensive Rosetta Stone program. It’s a huge chunk of change for us poor college students, but if you have an extra two hundred dollars laying around - go for it! It really is the quickest and most effective way of learning a language.

Also, if you readers have any other suggestions or resources, I would love to hear from you!

3 Post-failure Inspirational Quotes

This semester, I’m taking a Computer Science class on Artificial Intelligence. While reading the textbook for the class, I came across this very interesting quote:

A performance measure embodies the criterion for success of an agent’s behavior. When an agent is plunked down in an environment, it generates a sequence of actions according to the precepts it receives. This sequence of actions causes the environment to go through a sequence of states. If the sequence is desirable, then the agent has performed well. Obviously, there is not one fixed measure suitable for all agents. We could ask the agent for a subjective opinion of how happy it is with its own performance, but some agents would be unable to answer, and others would delude themselves.

There is a footnote at the bottom of the page that explains the last sentence:

Human agents in particular are notorious for “sour grapes” - believing they did not really want something after not getting it, as in, “Oh well, never mind, I didn’t want that stupid Nobel prize anyway.”

This just puts me in a very introspective mood - what kinds of things have I failed at and just decided the goal was stupid anyway? Is there a way I can be true with myself and deem a failure just a temporary setback? Being a typically cynical person, I’m trying to make a valiant effort to outwardly vocalize the silver linings of every situation. Here are a few of my favorite post-failure “pick me up” quotes (I have them posted in my office):

“It’s not that I’m so smart, it’s just that I stay with problems longer.”
-Albert Einstein

“My great concern is not whether you have failed, but whether you are content with your failure.“
-Abraham Lincoln

The Mathematical Formula for Romanticism

Given the similarity of my chromosomes (XX), I love Valentine’s Day. Not only for the cute lolcat pictures available on icanhascheezburger, but also for the sentiment. Of course it was a holiday created by Hallmark to sell more greeting cards and other stuffed-flowery-fluffy-balloon-chocolate gifts. But it’s the only day that I get to outwardly embrace my inner female (often hidden from my Computer Science friends). In fact, I brought in heart-shaped pink sugar cookies for all my generally classically male peer group today. It’s fun being the den mother :)So a few days ago, we were having a frustration-induced conversation about what general guidelines males should adhere to in order for a Valentine’s Day gift to be considered “romantic” and this is what we were able to come up with:

This means that the frillier, larger and more useless the gift, the better it will be received on Valentine’s Day! Take this into account when you’re wanting to buy her a USB hub that she’ll be able to use everyday with all of her devices - save that for another day!! For today, buy that Big, Useless Pink Bunny that makes you want to roll your eyes!

But at least buy her a gift that makes collision detection very simple

3 Best All-Nighter Hacks

Since writing in my blog has become my procrastinating activity of choice as of late, I feel compelled to write an entry on how to successfully pull off those inevitable all-nighters (which I’m going to be doing as soon as this entry is finished):

• Perfect your caffeine intake. There’s an excellent ScienceBlog article on Caffeine Hacks, which outlines a few important ways to optimize your caffeine intake.
  • Ingest approximately 20mg of caffeine (a cup of hot green tea) every hour.
  • Make sure not to have more than 600mg of caffeine in your body at one time, because it can actually adversely affect your mental capacity to learn new ideas and solve more generalized problems.
• The 20 Minute Nap. Never underestimate the power of a nap. My favorite method of choice is to quickly “chug” a redbull and then set my alarm for 20 minutes. A couple things about this method:
  • By the time the caffeine kicks in from your energy drink, you’ll be just about finished your nap.
  • It doesn’t matter if you actually spend the entire 20 minutes sleeping or just laying with your eyes closed - you’ll feel better when you wake up either way.
• Implement a microcosmic batch/martini method. This is my very favorite method of getting very involved tasks done in a small amount of time.
  • First, outline your tasks in gruesome detail: the more you have written down, the less time you’ll spend thinking and pondering the task later. Do not do anything else until this is finished.
  • Designate a reward that you will look forward to. Having the task done isn’t a reward: Make sure it’s something that gets you emotionally charged when you think about it (For me, it’s a romantic movie). Make sure to schedule the reward - it doesn’t have to be the same night as the all-nighter: in fact, looking forward to a clear head when doing something you love the next day can be a remarkably effective motivator.
  • Batch process time! Finish one task to it’s end. In Computer Science programming projects, this usually means 4+ hours of constant working. Don’t stop or let your mind wander. Just go.
  • After finishing your first task, deliberately take a break to switch gears. This must be a minimum of 15 minutes and a maximum of 1 hour. If it’s any more than an hour, you will lose enthusiasm and develop “lazy inertia”.
  • Repeat this process, including designating and scheduling a reward in the future (not the same one) until you’ve got everything you’ll need to get done finished for the night.
  • Sleep! Go warm up some milk to calm yourself down from the loads of caffeine you’ve forced upon your body, slip into your comfy silk pajamas and curl up in your bed. Enjoy your rest - you have certainly earned it tonight!
  • Recite your work out loud to yourself in the morning - your project you needed to finish by today is done and you’ll proudly and tiredly march to school and turn it in! Do not sleep in!

Games Breed Entrepreneurs

I saw this article on ACM CareerNews and I can’t help but put in my two cents. Anyone who has played a structure MMO like World of Warcraft knows that social contexts in these sorts of games can actually simulate a very office-like atmosphere.

My old World of Warcraft guild would make scheduled real-time “raids” on dungeons: Every Monday, Wednesday and Saturday at 8:00PM. Not only would I have to schedule time on my actual iCal calendar to make time for the guild raid, I would need to do several menial tasks during the day (collect various items including ammo for my gun) to prepare my character to actually run the raid! This kind of structure breeds productive employees:

1. Long-term Goals (To collect every piece of a certain matching armor set, you will need to run several Guild Raids)
2. Weekly, Scheduled Status Meetings (Run Dungeon Every Monday, Wednesday & Friday at 8:00PM and show to the guild that you’ve improved your skills)
3. Menial Daily Tasks (Collect 80 Rat Pelts, etc.)
4. Tolerance for Failure (If you don’t complete your daily menial tasks, you can become very useless during a Guild Raid.)
5. Self-motivated Goals Which Require an Organization (Guild) to Complete

Not only does this breed a very specific kind of employee that is more tolerant of menial tasks and failure, but isn’t this the formula that makes a good entrepreneur? You’ve got to be self-directed and self-motivated (but with the help of a social organization or network of “connections”), but most importantly, you’ve got to put yourself in risky situations that will more than likely result in failure! Very interesting read

8 Best GTD Links for Students

I’ve been actively searching the web for the best blog & news articles on the GTD (Getting Things Done) Organizational paradigm. These are my favorite GTD articles (with a college slant):

Nix the ‘Net: Turn Off the Internet to Get Better Grades

LifeHack.org’s Humungous List of Tools for Students

FruitfulTime’s Free eBook on Overcoming Procrastination

10 Simple Ways to Only Do 3 Things Today (Which is a lot!)

Embrace Randomness: The Anti-Planning Method

The Straight-A Method: How to Get Straight As in College!

The Famous Martini Method: How to get your PhD!

Using Time Arbitrage to Increase Productivity

Uberman Polyphasic Sleep Schedule

Everyone wishes they had more time in the day, right? How about modifying that 8-hour chunk during the night to work as?

Newborn babies nap every few hours and eventually grow to assimilate into our sleep culture of 8-hour chunks at the end of the day.

So, inspired by LifeHacker, I’ve decided to give the Uberman Sleep schedule another try. Thomas Jefferson and Albert Einstein have backed it as one of the reasons they were so successful in their endeavors. And let’s face it, I would love more time in my day!