Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Re: Odd Ball Challenge

by etcshadow (Priest)
on Jun 25, 2005 at 00:36 UTC ( #469864=note: print w/ replies, xml ) Need Help??


in reply to Odd Ball Challenge

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 brute-force search-space 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 cross-products and power-sets. 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 20-30 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 cross-products and power-sets 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 CS-speak, 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.

------------ :Wq Not an editor command: Wq


Comment on Re: Odd Ball Challenge
Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://469864]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (8)
As of 2014-07-28 12:05 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (196 votes), past polls