All,
There is a well known riddle as follows:
You are presented with 12 balls identical in appearance but 1 of the 12 is either heavier or lighter than the other 11. Your task is to identify which is the odd ball and if it is heavy or light. You are only allowed to make 3 weighings using a balance.
I have included a currently* non-working Perl6 solution below because that is not the challenge:
use v6;
my %ball = map { $_ => 1; } 1..12;
Modify_Ball( %ball );
say ~Find_Odd_Ball( %ball );
say %ball.perl;
sub Find_Odd_Ball (%ball) {
my $result_1 = [+] %ball{1..4} <=> [+] %ball{5..8};
given $result_1 {
when 0 {
my $result_2 = [+] %ball{9,10} <=> [+] %ball{1,11};
given $result_2 {
when 0 { return (12, %ball{12} <=> %ball{0}) }
default {
my $result_3 = %ball{9} <=> %ball{10};
given $result_3 {
when -1 { return (9, $result_2 == $result_3 ?
+? -1 :: 1 }
when 0 { return (11, $result_2 * -1 }
when 1 { return (10, $result_2 == $result_3 ?
+? 1 :: -1 }
}
}
}
}
default {
my $result_2 = [+] %ball{1,2,5} <=> [+] %ball{3,6,10};
given $result_2 {
when -1 {
my $result_3 = %ball{1} <=> %ball{2};
given $result_3 {
when -1 { return (1, $result_1) }
when 0 { return (6, $result_1 * -1) }
when 1 { return (2, $result_1 * -1) }
}
}
when 0 {
my $result_3 = %ball{7} <=> %ball{8};
given $result_3 {
when -1 { return (8, $result_1 * -1) }
when 0 { return (4, $result_1) }
when 1 { return (7, $result_1 * -1) }
}
}
when 1 { return %ball{3} == %ball{10} ?? (5, $result_
+1 * -1) :: (3, $result_1); }
}
}
}
}
sub Modify_Ball( %ball is rw ) returns Void {
my $num = int( rand 12 ) + 1;
my $adj = .1 * (int( rand 2 ) ?? 1 :: -1);
%ball{$num} += $adj;
}
Challenge: Start out not knowing how to solve the riddle and write code that tells you how. It should generate a set of groups and measurements that when followed will solve the riddle. I am not real particular in how a human would interpret the output, but bonus points for code that understands its own output and produces code that solves the riddle (such as my example).
How many ways are there to measure 12 balls in groups of two 3 times so that you are guaranteed to know which ball is odd and how it is odd? I think Ovid's AI::Prolog may be the right way to go.
Every time you make a measurement using the balance there are 3 possible outcomes.
- If they balance, the odd ball must be in the group not currently being weighed
- If the right side goes down, either a ball in that group is heavy or a ball on the left side is light
- If the right side goes up, either a ball in that group is light or a ball on the left side is heavy
All solutions, to include Perl6, are welcome.
* I say currently because I suspect the problem is with Pugs and not with the code.
Update: Clarified challenge to indicate I am not looking for a solution to the riddle but for code that can figure out a solution on its own. That is to say, a solution-generator. See Challenge: Setting Sun Puzzle for an example.
|
Re: Odd Ball Challenge
by kaif (Friar) on Jun 23, 2005 at 21:51 UTC
|
Challenge accepted. For better or worse, I am using "math" when it comes to this problem (this problem clearly generalizes).
sub c{print"@{$_[0]} <=> @{$_[1]}: -/+1 if left/right heavier, 0 if eq
+ual: ";<>}
sub b{$_[0]<13?$_[0]:26-$_[0]} sub a{2>($_[0]+($_[0]>11))%4} sub d{sor
+t{$a<=>$b}
map b($_),grep{a($_)&&$_[1]==int($_%3**$_[0]/3**$_[0]*3)}1..25}$;+=3**
+$_/3*(1+c(
[d($_,0)],[d($_,2)]))for 1..3;print b($;)." is ".(a($;)?"heavi":"light
+")."er\n";
| [reply]
[d/l] |
|
|
kaif,
I think you misunderstood the challenge and wrote a solution to the riddle instead. You are supposed to start out not knowing how to solve the riddle and write code that tells you how. The bonus was to have the code smart enough to understand whatever it outputted and generate a solution (such as the one you provided).
Let me try and be clearer this time since it was likely my fault. You start out knowing only the rules of riddle. You right code that starts searching for combinations of groupings and weighings that keeps track of what knowledge it has gained along the way. Eventually it has enough information to say:
- Split the 12 balls up into X groups of Y balls
- First, balance group A against group B
- If they balance do ....
- If A is heavier do ....
- etc, etc, etc
I am not real particular in how that information is conveyed but it would be really cool if once the code reaches its conclusion it is smart enough to understand its own output and also generate code to execute the steps.
| [reply] |
|
|
I've thought about this particular problem before, and I wrote the kind of program you would like to see, in C++. It was challenging, and somewhat time-consuming, which is probably why no one has responded yet like that; I was going to simply translate my program to Perl, but I think I dropped it in the bit bucket.
I eventually generalized the problem and solved it mathematically, noticing that 12 == (3**3 - 1)/2 - 1. Thus, to me, this is an old case of the following: given the task "write a program to sum the numbers from 1 to $x" after learning about loops, does one write print $x*($x+1)/2 or
for $i ( 1 .. $x ) {
$sum += $i;
}
print $sum;
So, I went the easier route and golfed in a relatively general way; my comparisons "2 9 11 12 <=> 3 5 6 8", etc., are not hard-coded (I could write a much shorter program otherwise) and the computation of the result is clever. I hope that this is okay. I understand your challenge, but I still think that the less-than-240-characters above is an accomplishment. Thank you for the clarification, though. | [reply]
[d/l]
[select] |
|
|
Re: Odd Ball Challenge
by blokhead (Monsignor) on Jun 24, 2005 at 12:41 UTC
|
The strategy you list is adaptive, i.e, depending on the outcome of a weighing, you do different things. An interesting special class of solutions is fixed strategies, where you just have 3 fixed weighings such that no matter how the one ball is odd, you will detect it. Unfortunately, I know that my analysis is not complete, and I'm not sure that any such strategies exist (I suppose I could google, but I haven't yet). I wrote some very basic brute search code to look for a fixed strategy, but came up cold.
The reason I am drawn towards fixed strategies is that, if they exist, they have the benefit of having a much simpler representation. You can look at a fixed strategy as a 12 x 3 table, filled with L, R and - (or L, R, and ~ if you like), to denote whether a ball is on the left or right side of the scale, or not weighed in a certain round. Example:
L L L L R R R R - - - -
L L - - R R - - L R - -
L - L - L - R - R - R -
This strategy says to weigh balls 1-4 vs balls 5-8. Then weigh 1,2,9 vs 5,6,10. Then weigh 1,3,5 vs 7,9,11.
It's easy to check whether this gives a real solution. First of all, in order to give you any information about ball weight, each round has to have the same number of balls on the LHS and RHS of the scale. Then, you have to pretend the odd ball is each of the 12 balls and see whether all other candidates would get logically eliminated. If the odd ball is one that is measured, then the scale tips so you can throw out the ones that weren't measured. If the odd ball is not measured, the scale balances, so you can throw out the ones that were measured. In code, that looks like this (with the table being represented as a 2d, 3x12 array):
sub check_scheme {
my @scheme = @_;
## check that each round measures the same amount of balls
for my $round (0 .. 2) {
my $lhs = grep { $scheme[$round][$_] eq "L" } 0 .. 11;
my $rhs = grep { $scheme[$round][$_] eq "R" } 0 .. 11;
return 0 if $lhs != $rhs
}
## simulate the scheme with each of the balls being the odd one
for my $item (0 .. 11) {
my @candidates = (0 .. 11);
for my $round (0 .. 2) {
if ($scheme[$round][$item] eq "-") {
@candidates = grep { $scheme[$round][$_] ne "-" } @can
+didates;
} else {
@candidates = grep { $scheme[$round][$_] eq "-" } @can
+didates;
}
}
## by this point we should have eliminated all but one ball!
return 0 if @candidates != 1;
}
return 1
}
Unfortunately, I know that this analysis is incomplete, because (depending on the statement of the problem) you may be able to use information about the direction of the scale and keep track of which balls were on sides of the scale that went up and down. The only information I assume we use here is whether or not the two sides were equal. In fact, now that I'm writing this, I think a basic counting argument shows that there is no fixed strategy that works unless you use information about whether balls were in the heavy or light side of the scale (Update: Indeed, look at the "L" or "R" entries as 1s and the "-" entries as 0. For two balls to be distinguished, they must at some point have mismatched 0/1's in their column. There are 8 ways a ball can have an assignment of 0/1's, but there are 12 balls. Conclusion: some pair of balls must be indistinguishable in this very simple scheme).
Oh well, it was a nice attempt at a simple analysis, but it was too simple to yield any solutions. My feeling is that this analysis could be extended by keeping a two lists of candidates (the possibly heavy balls and the possibly light balls), seeing which way the scale swings, and making the logical deductions. Feel free to expand on it, but unfortunately I need to go get other work done this morning ;)
| [reply]
[d/l]
[select] |
|
|
blokhead,
Thanks. I doubt I have your skill to expand on it. Perhaps the idea will begin to haunt you at night depriving you of sleep (as it has me) and you won't be able to rest until you come up with a solution.
Background:
Having solved the riddle itself at least 2 different ways myself, I began wondering how many ways there were to solve it and how one might automate that. Since I couldn't work out in my head a smart way of doing it - I figured I would post it here as a challenge.
| [reply] |
|
|
Good thinking. As djohnston concluded, such a strategy does exist. As you say, it does and must use the information of which side of the scale went up. My solution above uses a fixed strategy, actually. Try it out! Here's a detailed explanation of the strategy it uses:
| [reply]
[d/l]
[select] |
|
|
This pattern seems to work:
- - - - L L R L R L R R
- L L L R R L - - - R R
L R - L R - R R - L L -
I wrote a proof of theory script which uses this fixed strategy technique. I don't know if it satisfies all of the requirements of the challenge, but it does appear to work.
Each of the three fixed weighs results in either 0, 1, or -1. These weigh results are joined together to create a unique key for each ball/weight combination which are then used to generate a lookup table that can then be used to quickly find the oddball and its weight in any given set.
| [reply]
[d/l]
[select] |
Re: Odd Ball Challenge
by jcoxen (Deacon) on Jun 24, 2005 at 01:54 UTC
|
Here's my solution. Is this the kind of thing you had in mind?
#! /usr/bin/perl
use strict;
use warnings;
my @left;
my @right;
for (my $i = 0; $i <= 11; $i++) {
my $j = $i+1;
$j = 0 if $j == 12;
print "Weigh Balls $i and $j\n";
print "Enter a result for each ball as follows:\n";
print " b-b Both balls balance\n";
print " u-d Left side up, right side down\n";
print " d-u Left side down, right side up\n";
chomp( my $input = <STDIN>);
my @results = split/-/, $input;
$left[$i] = $results[0];
$right[$j] = $results[1];
}
for (my $i = 0; $i <= 11; $i++) {
if (( $left[$i] eq "b") ||
( $right[$i] eq "b")) {
print "Ball $i is normal\n\n";
} elsif (( $left[$i] eq "d" ) &&
( $right[$i] eq "d")) {
print "Ball $i is Heavy!\n\n"
} elsif (( $left[$i] eq "u" ) &&
( $right[$i] eq "u" )) {
print "Ball $i is Light!\n\n";
} else {
print "Something is FUBAR somewhere!\n";
}
}
I haven't included any error checking for input errors, etc. It's just the bare logic.
Jack | [reply]
[d/l] |
|
|
| [reply] |
|
|
Yeah, I've been following the thread and had figured out on my own that I was off base.
Interesting puzzle. I can figure out a solution but trying to duplicate the steps my brain took to solve this and then translating those steps into Perl is beyond me. Actually, trying to figure out how (or if) my brain works is more than enough challenge for anyone.
Anyway, I'll be interested to find out if anyone manages to solve this one - and if their program comes up with the same solution I did.
Jack
| [reply] |
Re: Odd Ball Challenge (details)
by tye (Sage) on Jun 24, 2005 at 04:53 UTC
|
As stated, there are some ways to attempt a solution that strictly shouldn't be allowed (I'm sure it can be solved at least one of these ways, but I haven't worked through whether it can be solved without using the technique that shouldn't be allowed). If you made them dice instead of balls, if they were numbered, if you had stated that we had sacks or cups or such that we already knew were of equal weight, if we had a pen or other marking device that would not make a detectable change in weight on the balls, or if ...
But it is a subtle point that doesn't detract from the programming challenge (and provides alternate interpretations to make things more interesting) so I'll just leave it at that. (:
I don't know Perl6 and don't have Perl6 so getting it, learning it, and writing a solution-generator for this puzzle are more than I have time for at the moment, so I apologize for not offering or even attempting such. Thanks for the puzzle, though.
| [reply] |
|
|
tye,
I said the balls are identical in appearance, I didn't say that there wasn't anyway of keeping track of which ball was which. A human could do it by keeping the groups separate when not being weighed and always put them on the balance the same way, let's just assume your code can too via array indices, hash keys, or method X.
This isn't a Perl6 challenge. As I said, All solutions, to include Perl6, are welcome. I understand that it is a bit of work for no immediate tangible reward so don't worry about not offering or attempting a solution-generator. Something to think about on a rainy day (-;
| [reply] |
|
|
Of course you can keep balls segregated when not being weighed. Otherwise, the challenge would be hopeless. But you can't, without a change similar to one I mentioned, confidently keep balls segregated from each other on the same side of the balance across a weighing. That limitation prevents some strategies. Coding with or without that limitation will give different sets of solutions. And there is at least one initial division of balls for the first weighing of your problem that either leads to a solution or doesn't depending on whether you accept that limitation.
"All solutions to include Perl6" means only Perl6 solutions are welcome. With the comma, your sentence just doesn't make sense to me. :) Thanks for clarifying.
| [reply] |
|
|
|
|
If you made them dice instead of balls, if they were numbered, if you had stated that we had sacks or cups or such that we already knew were of equal weight, if we had a pen or other marking device that would not make a detectable change in weight on the balls, or if ...
A typical (if not downright the most typical) way to render this problem is as a search for a counterfeit coin of unknown weight in a collection of fair coins; clearly, with coins, it is not difficult to keep track of the individual coins from one weighing to the next. (BTW, this "coin version" of the puzzle strikes me as realistic enough to suggest the possibility that the puzzle originally arose as an embellishment of a relatively common everyday task.)
| [reply] |
Re: Odd Ball Challenge
by greenFox (Vicar) on Jun 24, 2005 at 04:01 UTC
|
"How many ways are there to measure 12 balls in groups of two 3 times so that you are guaranteed to know which ball is odd and how it is odd?"
That sentence completely threw me. 12/2 = 6, how can you possibly measure 6 groups with just three measurements? Or maybe it was 12/2*3??? Heres my best attempt, I am sure it can be improved upon :)
What possibile groupings of the 12 balls would allow you to pick the one odd ball after just three measurements?
--
Do not seek to follow in the footsteps of the wise. Seek what they sought. -Basho
| [reply] |
|
|
greenFox,
The question was a restatement of the riddle itself and I probably did a poor job of capturing it. Let me be a little more verbose. Each time you use the balance, you are going to be comparing 2 groups (left and right) which may or may not represent the total number of balls (12). That's the part about 12 balls in groups of 2. You can only use the balance 3 times.
The problem as I see it can be attacked at least 2 ways. The first is just to exhaustively calculate all possible groupings which should result in balanced pairs over 3 tries and sift through the aftermath attempting to pick a set that can answer the riddle. The second is to assess what information is gained after each weighing and determine which ways might lead to a correct solution (which will require backtracking).
Personally, I have no idea how to go about writing this code and am not even sure if the approaches I described are the right ones to use. It was keeping me awake the other night so I figured if it got under my skin my fellow monks would like it too.
| [reply] |
Re: Odd Ball Challenge
by etcshadow (Priest) on Jun 25, 2005 at 00:36 UTC
|
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.
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
| [reply]
[d/l] |
Re: Odd Ball Challenge
by TedPride (Priest) on Jun 23, 2005 at 22:37 UTC
|
I'm still trying to figure out how to solve the puzzle, never mind code an AI to solve it :) | [reply] |
|
|
Assuming one ball is heavier than the other 11
|
0. Divide balls into sets of 6. Weigh on a balance and select the heavier set.
1. Divide the heavier set into sets of 3. Weigh on a balance and select the heavier set.
2. Take two balls from the heavier set. Weigh on a balance.
Select the heavier ball.
If the two balls are equal, the third ball from the set is heavier.
|
| [reply] |
|
|
jpeg,
Unfortunately, you don't know if the ball is heavy or light. A solution set has multiple outcomes but there are at least two solution sets that I have thought of. The Monastery now supports real spoiler tags by the way.
| [reply] |
Re: Odd Ball Challenge
by zby (Vicar) on Jun 24, 2005 at 10:13 UTC
|
You need to define where is the variable in the problem. The way it is stated now it is all constant there is no programming challange in it.
To explain it other way - the solution is a program that prints a constant which is the program that solves the riddle. But printing a constant is a bit trivial.
To make it a reall programming assignements you need to declare that the imput is for example the number of the balls, or the number of the odd balls, or some other parameter. | [reply] |
|
|
| [reply] |
|
|
So take following riddle - "How much is it 2 + 2?". You want a program that would print a program printing solution to this riddle. I say this the solution to this is:
print "print 4;";
But you say that this is not enough, that the solution should somehow compute the "print 4;" output. | [reply]
[d/l] |
|
|
|
|
|
Re: Odd Ball Challenge
by djohnston (Monk) on Jun 24, 2005 at 22:18 UTC
|
In order to understand the challenge, I translated the code in your OP (I lack Perl 6) to a scripting language which happens to support given, when, and default. I had a hell of a time getting it to work - then I noticed this little detail in the OP which I had originally misread:
I have included a currently non-working Perl6 solution below.
I say currently because I suspect the problem is with Pugs and not with the code.
So, maybe my time was not wasted.. perhaps if we compare our results, we can determine whether or not it's your algorithm that is to blame.
| [reply]
[d/l] |
|
|
djohnston,
The code won't even run at all currently under Pugs. If it is consistently giving the wrong answers then it is probably just a mapping issue. In order to verify, you would need to remove the randomness and force each ball to be heavy and then light in succession. The solution itself isn't the challenge though. The challenge is to write code that generates a solution.
| [reply] |
|
|
when -1 { return (9, $result_2 == $result_3 ?
+? -1 :: 1 }
a syntax error (mismatched parentheses)? If so, there are a few lines like that. Also, one line refers to
when 0 { return (12, %ball{12} <=> %ball{0}) }
where 0 should probably be 1. Finally, I confirm all of djohnston's results by translation to Perl 5 (for example, just imagine ball 1 is heavier and run through the code mentally --- it indeed says something about either ball 3 or 5). Pardon the ugly code; the Perl 6 is certainly prettier. But as Limbic~Region says, solving the riddle isn't the challenge, right?
| [reply]
[d/l]
[select] |
|
|
|
|
djohnston,
There were a few missing parens in my code, a handful of bugs in Pugs, and an incorrect translation of the puzzle solution logic to code. The following is working p6 code that produces correct results.
| [reply]
[d/l] |
Re: Odd Ball Challenge
by TedPride (Priest) on Jun 26, 2005 at 21:41 UTC
|
Actually, pathfinding is doable, if you optimize properly. Work out from both sides, not just one; eliminate all paths that arrive at a node (intersection) reached with a better time; put on hold the x% of paths with the worst distance / time ratio. What you end up with is more or less a diamond area connected on opposite points by the start and end of the path, with every intersection inside the area being a node, and the maximum number of paths corresponding roughly to the surface area of the diamond plus the distance through the middle of the diamond. This is workable, assuming the distance you need to cover isn't more than 10 miles or so, and if it is, you can modify the path to travel into three segments, with the middle segment being travel on trunk lines, of which there are few
This would be much more efficient if programmed in C / C++, however. Perl is a memory hog. | [reply] |
|
|
Oh, certainly. I never intended to imply otherwise. There are two things, there, though: 1) you're talking about a good bit of intelligent optimization (removing redundant paths through the same point, for example), and 2) there's an existing hueristic (the distance/time ratio, and so on).
Likewise, there's a lot of work that's gone into other known search-space problems. Adversarial strategy (like playing chess), for example has had a ton of work poured into it. There's the so-called "A*" algorithm, which employs some interesting pruning techniques against the search tree. That, of course, has to employ a huersitic function, again (generally some sort of "scoring", like in chess you could add up the point values of all your pieces and subtract the point-values of all of your opponent's pieces). It also makes use of some interesting properties of adverserial strategy, such as the fact that your opponent will not willingly choose a move that allows the possibillity of an exceptional counter-move on your part.
Anyway, the point I meant was: I don't have a good optimization to use against this (and I gave an example of how this is similar to some other AI problems that do have interesting optimizations). Part of what gets in the way is the lack of some sort of helpful heuristic. That is, I haven't yet thought of a good way of representing (as a mathematical function applied against a stage of the algorithm) that an algorithm is likely to "contain more information", in such a way that it doesn't "cheat" and impose my foreknowledge of the answer on the problem :-)
------------
:Wq
Not an editor command: Wq
| [reply]
[d/l] |
Re: Odd Ball Challenge
by barrachois (Pilgrim) on Jul 13, 2005 at 18:07 UTC
|
A nice question; thanks. I had fun with it.
Here's some code that does an exhaustive
search for a specific number of balls and weighings,
from 3 balls and 2 weighings up to about
20 balls and 4 weighings. Full
documentation (POD format) is included.
To give you an idea of what it
does, a snip of the output looks like this:
Searching for odd ball in 12 balls with 3 weighings ...
'' : at node=1
... 1 partitions (4 L's, 0 different)
'b' : at node=2
... 11 partitions (1 L's, 4 different)
... 32 partitions (2 L's, 4 different)
'bb' : at node=3
... 2 partitions (1 L's, 1 different)
'bl' : at node=7
... 7 partitions (1 L's, 3 different)
'br' : at node=11
... 7 partitions (1 L's, 3 different)
etc.
done. Solution found after 40 nodes and 2147 partitions.
start => [ L L L L R R R R o o o o ]
b => [ R o o o o o o o L L R o ]
l => [ L R o o L L R R o o o o ]
r => [ L L R R L R o o o o o o ]
bb => [ R o o o o o o o o o o L ]
bl => [ o o o o o o o o L R o o ]
br => [ o o o o o o o o L R o o ]
lb => [ o o L R o o o o o o o o ]
etc.
bbl => ball 12 is heavy.
bbr => ball 12 is light.
blb => ball 11 is light.
bll => ball 9 is heavy.
blr => ball 10 is heavy.
etc.
I should warn you that code isn't exactly brief...
Regards,
barrachois
| [reply]
[d/l] |
Re: Odd Ball Challenge
by ej8000 (Initiate) on Aug 01, 2011 at 22:18 UTC
|
hi all,
I have a working solution in perl 5.14
use v5.10;
%ball=map{$_ =>1}1..12;
Modify_Ball( %ball );
say Find_Odd_Ball( %ball );
sub Find_Odd_Ball (%ball) {
my $result_1 = ((eval join '+', @ball{1..4}) <=> (eval join '+', @ball
+{5..8}));
given ($result_1) {
when (-1) {
my $result_2 = ((eval join '+', @ball{1,2,5}) <=> (eval jo
+in '+', @ball{3,6,10}));
given ($result_2) {
when (-1) {
my $result_3 = $ball{1} <=> $ball{2};
given ($result_3) {
when (-1) { return (1, $result_1) }
when (0) { return (6, $result_1 * -1) }
when (1) { return (2, $result_1 ) }
}
}
when (0) {
my $result_3 = $ball{7} <=> $ball{8};
given ($result_3) {
when (-1) { return (8, $result_1 * -1) }
when (0) { return (4, $result_1) }
when (1) { return (7, $result_1 * -1) }
}
}
when (1) { return $ball{3} == $ball{10} ? (5, $result_
+1*-1 ) : (3, $result_1) }
}
}
when (0) {
my $result_2 = ((eval join '+', @ball{9,10}) <=> (eval
+ join '+', @ball{1,11}));
given ($result_2) {
when (0) { return (12, $ball{12} <=> $ball{1}) }
default {
my $result_3 = $ball{9} <=> $ball{10};
given ($result_3) {
when (-1) { return ($result_2 == $result_3 ? 9
+ : 10, $result_2 == $result_3 ? -1 : 1) }
when (0){ return (11, $result_2 * -1) }
when (1) { return ($result_2 == $result_3 ? 9
+: 10, $result_2 == $result_3 ? 1 : -1) }
}
}
}
}
when (1) {
my $result_2 = ((eval join '+', @ball{1,5,6}) <=> (eval jo
+in '+', @ball{2,7,10}));
given ($result_2) {
when (-1) {
my $result_3 = $ball{5} <=> $ball{6};
given ($result_3) {
when (-1) { return (5, $result_1*-1) }
when (0) { return (2, $result_1 ) }
when (1) { return (6, $result_1 * -1) }
}
}
when (0) {
my $result_3 = $ball{3} <=> $ball{4};
given ($result_3) {
when (-1) { return (4, $result_1 ) }
when (0) { return (8, $result_1*-1) }
when (1) { return (3, $result_1 ) }
}
}
when (1) { return $ball{7} == $ball{10} ? (1, $result_
+1 ) : (7, $result_1*-1); }
}
}
}
}
sub Modify_Ball( %ball ) {
my $num = int( rand 12 ) + 1;
my $adj = .1 * (int( rand 2 ) ? 1 : -1);
$ball{$num} += $adj;
say $num;
say $ball{$num};
}
| [reply]
[d/l] |
Re: Odd Ball Challenge
by jimX11 (Friar) on Jun 28, 2005 at 03:01 UTC
|
A slightly off topic question, is a solution still possible if you use 15 balls and still keep the number of weighings at 3? I think so.
| [reply] |
|
|
No, it is not. Here's an information theory approach: by asking three questions which have three possible answers each (left side goes down, right side goes down, or equal), there are only 3**3 == 27 possible "inputs". Suppose there were 15 balls --- then there would be 15 * 2 == 30 (each ball can be heavier or lighter than the rest) possible "outputs". There are more outputs than inputs, so it is impossible. (This is the same approach as analyzing the "game tree".)
In fact, this argument shows that it is not possible to do the same for more than 13 balls; a slightly more sophisticated argument shows that 12 is actually the maximum. The best that is possible for 13 balls is determining which ball is different, but not necessarily whether it is heavier or lighter; this is not possible for 14 or more balls.
| [reply]
[d/l]
[select] |
|
|
You use "outputs" the way I'd use "inputs."
While thinking more about the algorithm, I see I assumed that we'd know if the odd ball was heavier or lighter than the others. My bad.
If we know that the odd ball is, say, heavier, then we can find in in 3 weighings even if there are 14 other balls.
I don't follow your informational theory argument, do you think the argument shows that what I claim in the paragraph above is not possible?
| [reply] |
|
|
|
|
