The top computer programming talent from universities around the world was all pooled in St. Petersburg, Russia on Wednesday for the International Collegiate Programming Contest (ICPC).
For five hours, teams of three students huddle around computer monitors and put their brain power to the test. They work through a problem set of about 10 questions that would normally constitute an entire semester’s work for your average university-level computer programming course. IBM Corp. has assembled these coding prodigies here in a bid to recruit them to come and work for Big Blue – all the finalist contestants are told they have open job offers. But IBM is interested in more than just coding knowledge – they want real problem solvers.
That desire for real ingenuity in solving problems is reflected in the problem set. Before contestants can even write one line of code, they first must figure out the right approach to take. Unpacking these problems often requires knowledge of established principles of physics and mathematical formula. To help explain how these top problem-solving minds work through a question, we asked the University of British Columbia‘s (UBC) team to dissect one for us.
Here’s a step-by-step approach to a problem from the 2012 ICPC world finals that no team managed to solve during the contest. The answer is explained by UBC students Paul Liu, a third-year math and physics undergraduate; Jonathen Shen, a graduate of the computer science and math program; and Karlming Chen, a math graduate.
Defining the problem
Problem H from last year’s world finals contest is titled “Room Service.” It seems like a problem that programmers of Roomba vacuum cleaners might face:
You are working for a company designing cute, funny robot vacuum cleaners. At a high level, the robots’ behavior is divided into three modes:
1. Exploration
2. Vacuuming
3. Rampant KillingUnfortunately, while consumer testing shows that the last two modes are working perfectly, the exploration mode still has bugs. You’ve been put in charge of debugging.
At the beginning of the exploration mode, the robot is placed into a convex polygonal room. It has sensors that should tell it where all the walls are. Your job is to write a program that verifies that these readings are correct. To do this, the robot needs to physically touch every wall in the room.
Your problem is this: given the shape of a convex polygonal room with N walls and a starting point P inside it, determine the shortest route that touches each wall and then returns to P . Touching a corner counts as touching both incident walls.
Along with the problem description, some mathematical input information is given and some example output for that input. This allows the students to test their program to see if they might have the right solution.
Probing
The UBC students start coming to grips with the problem by drawing it out visually. Liu draws a pentagonal room and starts drawing imaginary paths a robot might take to find the walls. A “convex polygonal” room simply means a room with more than two corners that can be bi-sected by a line.
“You’re trying to think like the robot and get some intuition like that,” he says.
At this point the students are probing to find a possible way to think about coming up with a solution. Just playing with the scenario given and imagining different experiences a robot could have in a room helps. But it can be frustrating to try and come up with an angle that makes sense.
“We drew a few paths and pretty much got nowhere,” admits Shen.
Insight
A breakthrough comes when Chen realizes a core principle of physics can be applied in this situation. Fermat’s Principle of Least Time holds that light will always take the fastest route between two points. So it makes sense for the robot to behave like light – reflecting off the walls at the same angle that it bumped into it.
Reading the problem carefully leads to another shortcut for our imaginary robot. Liu points out that if the robot touches a corner, it will detect two edges at once and know the placement of two walls in the room. Therefore taking a route that will touch the corners of a room could save time.
Solving
At this point the students have enough information to start coding. They know some behaviours to instruct the robot to exhibit in different situations and how it will move around a room. While the problem seems big at first, the method of dynamic programming can be used to deconstruct it into smaller problems, Liu says.
“The problem keeps getting smaller and smaller until we immediately know what the solution should be,” he says.
The method also makes coding more efficient. Instead of solving the same problem each time – such as what to do when the robot hits a wall – the robot remembers how to solve repeated problems after doing so just once.
The UBC students design a program that will take their robot from corner to corner in a given room. This solves the problem that no team could manage during last year’s world finals competition. Hopefully, they will see a similar problem on this year’s set of questions.