in reply to Re^8: Odd Ball Challenge
in thread Odd Ball Challenge

If you want to make this precise you need to have a definition that would differentiate between finding the right series of steps and writing program for finding the right series of steps. How do you decide which one is more difficult?

Replies are listed 'Best First'.
Re^10: Odd Ball Challenge
by Limbic~Region (Chancellor) on Jun 24, 2005 at 15:28 UTC
    zby,
    The challenge is to write a program for finding the right series of steps. I guess what you are saying is where do I draw the lines between what I "know" and what I let the program figure out on its own.

    For instance, it is pointless to weigh groups that have an unequal number of balls since it will not lead to any useful information. Is it ok to add that logic?

    I guess I just don't know how to answer that. The two solutions I know that work require dividing the 12 balls into 3 groups of 4. I wouldn't want a program that didn't consider other sizes unless there was some mathematical way of knowing that no other group/sizes were possible. I however wouldn't think anything of a solution that didn't consider groups of unequal number of balls since they would never be expected to balance.

    Sorry I can't give an exhaustive list of things that are ok and not ok. I am not interested in a translation of a known solution to code though.

    Cheers - L~R

[reply]

      Here's one way to answer it: make the problem more general. Ask for a program that will find the least number of weighings to find the odd ball among n, where n is given as a parameter.

      Now I suspect the answer can be reduced to a simple formula, in which case someone might derive the formula and write a program to calculate only that.

      If that doesn't fall within the parameters of what you're looking for, you will then need to specify much more clearly what you do and don't want to allow.

      I suspect the purpose is to show different people's approaches to solving this sort of thing, and I (and I suspect many of the people that would be interested in this sort of puzzle) would always start off with: "the simplistic approach is to traverse the entire search space, but combinatorial explosion will scupper that pretty quickly; so let's sit down with pencil and paper and see what logic or maths I can apply to reduce that search space". With this approach, finding a formula is an ideal solution: it reduces the search space to one, and so if I found such a formula I'd post just that instead of writing the program at all.

      Of course if no-one knows (or can find) a formula, this secondary issue might not arise.

      Hugo

[reply]
        I think problem statement is more confused than that. Reading between the lines, I think the challenge maybe boils down to something like...
        1. We're given a set of axioms
        2. We're told a particular statement is true
        3. Find a set of inference rules which can provide a proof of #2, starting with the axioms
        Thoughts? Anyone?
[reply]

In Section Meditations