The Creation of a Code Jam Problem
Since its inception in 2003, Google’s Code Jam has drawn the top amateur and professional coders in the world together in a contest to determine who will stand alone as Code Jam Champion. Now in its 11th year, Code Jam once again will be throwing intense algorithmic puzzles at programmers from around the world starting April 11, 2014.
To provide a behind-the-scenes glimpse of what is involved in the problem development for Code Jam, we recently sat down with two members of the Code Jam development team, Software Engineers +Bartholomew Furrow
and +Igor Naverniouk
, two of the four people who founded Google's Code Jam team in June 2007.
Bartholomew learned to love computer science while earning a B.Sc. in Physics from Queen's University, when he discovered programming contests. In 2006, shortly after obtaining a M.Sc. in Physics from the University of British Columbia (UBC) with his thesis "A Panoply of Quantum Algorithms", Bartholomew joined Google's Ads Quality team.
Igor started programming in the first grade, when he learned to create his own games with his father’s IBM 286 computer. While working on his B.Sc. at the UBC, he was lured to his first programming competition by a poster promising free pizza. He has been competing, coaching teams, creating problems for competitions, and eating pizza ever since.
Prior to working together as part of the Code Jam team at Google, Igor and Bartholomew were also teammates on the UBC ACM International Collegiate Programming Contest (ICPC) team.
Read on to learn part of the development of a Code Jam problem:
------Research at Google:
Every year, Code Jam comes up with 26 coding problems. Can you explain the process of how the challenges are developed and a sense of how long it takes? Who comes up with them? Igor Naverniouk:
Submissions of potential coding challenges for Code Jam start pretty much immediately after the finals are over, so nearly a full year is spent in preparing. Initially, any individual at Google can submit a problem they think has potential to be a good challenge, which then goes through selection and development by a team of 15-20 Google engineers who devote 20% of their time to Code Jam.
There is a variety of methods by which we come up with a problem; generally, one of us might read a paper and learn about an interesting algorithm and then see how to form it in an interesting puzzle. Or we might use a real-life problem, something we encounter at work or in daily life, that could be automated. It’s fun to take examples from everyday life and construct a challenge from it, especially if it’s something that people haven’t thought of from a computer science perspective. I think it makes participants feel like they they have solved something that’s relevant, and to feel good about that.Bartholomew Furrow:
A good example of a problem that was inspired by a real-life problem would be Candy Store, from the 2010 Code Jam Finals (http://goo.gl/K1oZl9
). It is one of my favorites because it was a problem I was trying to solve myself. I wanted to figure out the minimum number of dumbbells I'd need to purchase, so that I could lift any amount I wanted to in each hand. It was a good example of a Greedy Algorithm (http://goo.gl/8tGCp0
) and the genesis of Candy Store, which has a really wonderful greedy solution.IN:
The ideas don’t have to be thoroughly thought out, initially. The team reviews all the problem ideas, and anonymously ranks them based on originality, creativity, whether it is motivated by a real world problem, and whether it is a purely algorithmic problem or if a simple mathematical solution exists. R@G:
You distinguish between algorithmic and mathematical puzzles. Are there any problems that are quite challenging algorithmically but can be solved more simply if mathematical principles are used?IN:
The Revenge of the Hot Dog Vendor (http://goo.gl/MQco5E
) is a problem that comes to mind. While it can be solved algorithmically, there is an elegant mathematical solution as well, that is a bit simpler to implement. It is also a puzzle related to something in real life; on a boardwalk or a beach you tend to see concession stands clustered together, but ideally you want the placement of concession stands to be optimally spread out so that people only walk the minimum distance to get something to eat. R@G:
Once you have a list of potential problems for candidates, what are the next steps in the development of a problem before it ends up in the competition?BF:
Once the ideas are there, the next step is to carefully prepare the problem statement. A lot of time is spent on this, making sure it is understandable to both native and non-native english speakers. Anything that is really important about the problem we state twice, we give examples to try and make the problem statement as clear as possible…IN:
After that comes the development and testing of the input data for the large and small test cases for the problem, as well as the generation of sample I/O that is displayed in the problem statement. Of course, there is substantial testing to verify the solutions of the problem, providing sample solutions, proofreading…BF:
…in all I’d say it takes roughly 5-40 engineering hours, depending on the difficulty, to fully develop a single problem after
it has been selected, and there are 26 problems in total. That’s a lot of time to spend, in addition to normal job responsibilities, but we want to make sure that Code Jam is a medium for problems that are accessible to a wide variety of skill levels, but challenging enough that skilled competitors aren’t bored.R@G:
How do you strike that balance of accessibility and making the problems challenging? IN:
Well, it’s hard. We haven’t gotten 100% there…BF:
…But I think it’s okay if we have a problem that nobody solves in the final round, like we did in 2010 (http://goo.gl/N5j5Ex
) and 2011 (http://goo.gl/3FqSG7
). We love to have people discussing a really challenging problem for months after, that’s awesome! But for the earlier online rounds, everyone should be able to solve something. The problems should be simple to explain and relatively straightforward to solve. IN:
We also release the code for solutions and provide an analysis; what the steps are and why we think this is the best solution, so if anyone cannot solve one of the problems, they can come back and see how the solution is implemented. In addition to being a challenging contest, we also want Code Jam to be accessible to aspiring coders, those who are just starting out. I think its useful to be able to go back and read the solution to a problem that you have struggled with, and see the different ways in which it was solved, and build up one’s skill set.R@G:
With Code Jam going into its 11th year, in addition to other programming competitions out there, such as ICPC and TopCoder, how do you ensure problems aren’t repeated?IN:
We rely on the Googlers who participate in a lot of contests, people who are able to recognize problems from other competitions. But, even if we did end up with a problem that is functionally similar to one presented in the past, it would be very difficult copy/paste answers or adapt it to one presented at Code Jam, as subtle changes in a problem can make a huge difference in the solution. BF:
I believe that the incredible variety and permutations possible, even in similar problems, it is a testament to the beauty of computer science and algorithms. Code Jam really is a creative enterprise. I find it fascinating that a mathematical or algorithmic endeavor could have the same variety as, for example, painting. It is an art; our tools are just different from those of traditional artists. There really are a lot of beautiful, fun, and interesting non-conventional problems out there that are challenging, and can push the boundaries of computer science.
Registration for Code Jam 2014 opened March 11th. The Qualification Round will begin April 11th so be sure you register today, at http://goo.gl/j9wVyM