ST. PETERSBURG, Russia — The top computer programming talent from universities around the world, including six from Canada, began working Wednesday morning local time in the finals of the International Collegiate Programming Contest (ICPC).
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.
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 Killing
Unfortunately, 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 bisected 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.
