# Thread: Al Zimmerman's Programming Contest

1. ## Al Zimmerman's Programming Contest

Al Zimmerman's programming contest is already off to a 50-way tie after just 2 days. Turns out the problem (Graceful Graphs) is easy if you recognize it as equivalent to the sparse ruler problem and apply Wichmann's formula. I ended up solving it in about 3 hours after seeing some hints on the mailing list and writing a small program. The only possibility that the top standings could change now is if it turns out that Luschny's conjecture is false by demonstrating a counterexample on the problem set in the next 3 months. It could happen, though. There isn't really a lot of strong evidence to support the conjecture.

2. What is the idea behind a programming contest? Somebody finds a very difficult problem that has no practical use and then a lot of people work very hard to invent solutions? Why not find a difficult problem with practical applications that not a lot of other people are work on and solve that, instead?

I conjecture that there's a fundamental difference in solving real problems and made-up problems. In working a real problem, what usually happens is that the problem turns out to be wrong and leads to a better problem, which leads to a better problem, and so on to the ultimate problem, which is paired with a solution and the problem-solution pair together are enlightening and beautiful. Even in pure math, the search for good problems is at least as important as solutions. When someone finds a really good problem, they want to solve it themselves. The inevitable case when a problem is made up for other people is that its not a very good one.

I don't mean to rain on your parade. I'm sure there's an art to creating good artificial problems. But I think between solving the problem-problem (Which is the right problem?) and solving the solution-problem (What solves this problem?), I enjoy the problem-problem more.

Actually, I take that back, because what makes a problem the right problem is existence of a good solution. So that part can't exist alone.

I can see the fun in showing what you know and maybe being introduced to interesting math along the way. But I could not invest myself in a problem that's artificial, because it's hard work and somebody's already done it and knows that it isn't all that useful (if it was, it wouldn't be a contest, it would be published research).

3. Good question. I guess that winning contests is fun. It's also a tool used by recruiters who are looking for people with good math and programming skills.

4. Originally Posted by Matt Mahoney
Good question. I guess that winning contests is fun. It's also a tool used by recruiters who are looking for people with good math and programming skills.

There's absolutely nothing wrong with that. I'm just sort of proposing that the two activities are of a fundamentally different nature. They might even require a different skillset.

5. I don't put the Calgary Challenge in the same category, because it arises from a real problem. It's just a special case of compressing naturalistic data, there's no predetermined solution, and while working on it, you're studying a real problem that has applications.

This instance of Zimmerman's Programming Contest could be along those lines. The difference for me would be whether it's an open problem, or if you're searching for a canned solution that somebody already found.

When I was thinking about artificial problems, I had just finished doing a programming challenge for a job application and it was pretty much totally canned, despite being a little bit time-consuming, since it had a lot of details. I did a phone interview for google at one point, and they gave a problem that had many potential ways to program it ranging from trivial to arbitrarily clever with absolutely no context. I don't think I gave the right answer, but if I ran into something like it in the real world, I wouldn't spend any time on it trying to be clever unless there was an actual goal to aim for.

6. All of Zimmerman's contests are open problems. They are also designed to require an unreasonable amount of computation to solve, but be easy to check. So you can win a contest by finding clever optimizations, which often require some difficult or creative or non-obvious math. But having a supercomputer can also help.

This particular problem is unsolved but was probably a poor choice because there is a published solution that is probably optimal, although it wasn't proven. Usually selecting a good problem requires a lot of research to see if anyone has already solved it, but this time he missed some related work. It can happen.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•