Results 1 to 6 of 6

Thread: Al Zimmerman's Programming Contest

  1. #1
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts

    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. #2
    Member
    Join Date
    Feb 2013
    Location
    San Diego
    Posts
    1,057
    Thanks
    54
    Thanked 71 Times in 55 Posts
    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).
    Last edited by nburns; 24th September 2013 at 20:55.

  3. #3
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    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.

    You could ask the same question about the Calgary challenge.

  4. #4
    Member
    Join Date
    Feb 2013
    Location
    San Diego
    Posts
    1,057
    Thanks
    54
    Thanked 71 Times in 55 Posts
    Quote Originally Posted by Matt Mahoney View Post
    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.

    You could ask the same question about the Calgary challenge.
    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. #5
    Member
    Join Date
    Feb 2013
    Location
    San Diego
    Posts
    1,057
    Thanks
    54
    Thanked 71 Times in 55 Posts
    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.
    Last edited by nburns; 2nd October 2013 at 23:56.

  6. #6
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    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.

Similar Threads

  1. RarVM programming guide
    By Bulat Ziganshin in forum Data Compression
    Replies: 0
    Last Post: 12th October 2012, 16:18
  2. Another? DNA contest
    By Shelwien in forum Data Compression
    Replies: 2
    Last Post: 8th February 2012, 17:17
  3. A Programming Problem: How to know if a file is already opened?
    By Fu Siyuan in forum The Off-Topic Lounge
    Replies: 7
    Last Post: 6th August 2010, 17:12
  4. Programming Fonts
    By Bill Pettis in forum The Off-Topic Lounge
    Replies: 0
    Last Post: 10th February 2010, 18:16
  5. Lisaac programming language
    By lunaris in forum The Off-Topic Lounge
    Replies: 0
    Last Post: 11th December 2008, 18:51

Posting Permissions

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