Just another Perl shrine  
PerlMonks 
Re: Odd Ball Challengeby etcshadow (Priest) 
on Jun 25, 2005 at 00:36 UTC ( #469864=note: print w/ replies, xml )  Need Help?? 
This is an excellent challenge. Very nicely done. I started to code a solution and was just getting bogged down in it. So for now, I'll just explain the algorithm. If I have time, later, maybe I'll finish the code. Also, I'm afraid that my method (a bruteforce searchspace traversal) would be very slow and, if implemented in a way that directly maps against the description, memory hungry. The memory hungriness is actually what started bogging me down. It's the sort of thing that would be so much easier to do with a system that supported large, lazy (and forgetful!) lists that understood powerful operators like crossproducts and powersets. Interestingly, bits and pieces of such can be found on CPAN, but nothing that would all tie together. I almost implemented such a thing, so that I could solve the problem in like 2030 lines, or so, with all the messiness handled elsewhere... but I digress.
So, the basic concept requires that you first define a way of representing an algorithm. There's a few different ways of thinking of this, but they're all some sort of massive combinatorics (refer to the memory hungry crossproducts and powersets mentioned above). An algorithm that is a potential solution to the problem can be thought of as a trinary tree, four levels deep. The nodes of the first three levels represent a measurement on the scale, the and the nodes at the fourth level represent answers. The vertices represents the results of the measurements (three possible outcomes of any measurement: less than, greater than, and equal). In CSspeak, they are simply, acyclic determinstic finate state automata (say five times fast).
OK, so that's what a potential algorithm is. What distinguishes one potential algorithm from another, is the measurements that are made at each of those nodes in the first three levels and the answers in the fourth level. How do we define a measurement? Well, it's basically just two lists of balls that will go on the scale (one on the right, one on the left). To optimize a little, make them of equal number (no sense in comparing the weight of two balls to the weight of three balls... the weight difference is not known to be more or less than the base weight of a ball). There will be thirteen such (mutually exclusive) pairs of subsets of the twelve balls in each algorithm. Finally, there will be 27 outputs. Each output consists of both the odd ball, and whether it is heavier or lighter than the rest. So, given all that, one method for determining an algorithm that solves the problem would be to generate all of the possible permutations of balls, and all of the potential algorithms for solving the problem, and then test each algorithm against every possible permutation of the balls. If an algorithm yields the correct answer for every possible permutation of balls, then it is a correct algorithm. Simple. Just really slow (without doing anything to smarten it up), since there are so many different possible combinations of balls that you could choose to weigh against one another. As a side note to anyone not familiar with AI, this is actually somewhat representative (though tricky to optimize, because it lacks any kind of obvious hueristic) of a large class of AI problems. Essentially: consider every possible first choice that you could make, and, then consider every possible second choice that you could make after each of those initial choices, THEN consider every possible third choice that you could make, etc, etc, etc. Take path finding, for example: an AI trying to determine the best path might do so by saying (essentially), let me go to the end of my driveway. I can turn left or right. Assuming I turn left, then I go to the corner, where I can turn left right or straight. Likewise if I turn right. And so on. The possibilities balloon out of control very quickly. Anyway, I don't want to go into a big rant here. I just wanted to point out to any bistanders how this problem ties into the larger topic of artificial intelligence.
In Section
Meditations

