wu :: forums
« wu :: forums - Good/Bad computers »

Welcome, Guest. Please Login or Register.
Apr 25th, 2024, 1:09pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium
(Moderators: towr, Icarus, SMQ, william wu, Grimbal, Eigenray, ThudnBlunder)
   Good/Bad computers
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Good/Bad computers  (Read 6453 times)
Garzahd
Guest

Email

Good/Bad computers  
« on: Oct 9th, 2002, 3:18pm »
Quote Quote Modify Modify Remove Remove

Alright, I'll add a puzzle to the bunch...
 
You have N computers on a space station. An accident happens, and some of the computers are damaged, but you know the number of good (undamaged) computers is greater than the number of bad (damaged) ones.
 
Your goal is to find *one* computer that's still good.
 
Your only method of testing is the following: Use one computer (say, X) to test another (Y). If X is a good computer, it tells you correctly the status of Y. If X is bad, it may or may not give the correct status of Y; assume it will give whatever answer is least useful to your testing strategy.
 
In worst-case, how many tests must you use to find one computer that's still good? (in terms of N)
 
You're permitted any combination of tests, though keep in mind the bad machines may not be consistent in the results they give you.
« Last Edit: Oct 23rd, 2003, 7:40pm by Icarus » IP Logged
Pietro K.C.
Full Member
***





115936899 115936899    
WWW

Gender: male
Posts: 213
Re: New Puzzle: Good/Bad computers  
« Reply #1 on: Oct 9th, 2002, 10:16pm »
Quote Quote Modify Modify

  Well, here's a sort of efficient answer, asymptotically: Smiley

   Let Ng, Nb be the number of good and bad computers, respectively. We know that Ng is strictly greater than Nb. Hence, if you choose a random computer C out of the bunch, then you will end up with at least as many good as bad computers.
 
   Now let C be tested by the other Ng + Nb - 1 machines. The verdict of the majority (good or bad) is the actual status of C, and if the verdicts tie then C is good. If C is decided to be good, then we are done and it took us N-1 comparisons.
 
   If not, then we discard it (and whichever computers returned "good" when examining it) and repeat the process with the remaining Ng good and Nb - k bad computers; since the number of bad ones decreased, the strategy still applies. In the worst case, all bad computers will answer correctly, and the Nb will decrease by only 1 in each step. Furthermore, we must repeat the step, in the worst case, until exactly ceiling((N+1)/2) computers are left, in which case we know from the initial hypothesis that those must be good. This will take, in all,
 
S = sum (i-1)  (sum from i = N down to i = ceiling((N+3)/2)) =
 
= sum (i) (sum from ceiling((N+1)/2) to N-1) =
 
= N(N-1)/2 - ceiling((N-1)/2)*ceiling((N+1)/2) / 2 = O(n2).
 
I think. Well, it IS 2am... some +1's or -1's must definitely be missing. Smiley
IP Logged

"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
TimMann
Senior Riddler
****






   
WWW

Gender: male
Posts: 330
Re: New Puzzle: Good/Bad computers  
« Reply #2 on: Oct 10th, 2002, 1:05am »
Quote Quote Modify Modify

Here's my algorithm.  I don't have any proof that it's optimal, though it may be. It's tighter than Pietro's but still O(N2).
 
First, notice that if B ever says that A is bad, then at least one of the two must be bad. Therefore you can safely discard both of them, because good machines must still be in the majority amongst those remaining.
 
Algorithm:
 
1) Initialize the set of discarded machines to empty, and let D be the number of discarded machines.
 
2) If N-D <= 2, all non-discarded machines are good; stop.
 
3) Choose a non-discarded candidate machine, and let C be the number of "good" votes for this candidate.  Set C = 1 initially; i.e., assume that the candidate votes for itself, but don't actually ask it to test itself.
 
4) Begin asking the other non-discarded machines in turn to test the candidate.  Each time you hear "good", add one to C; if this makes C > (N-D)/2, stop and conclude that the candidate is good.  If you ever hear "bad", discard both the candidate and the machine that said "bad" (thus adding 2 to D), and go back to step 2.
 
The worst case for this strategy occurs when everyone in step 4 says "good" until we have one less than a majority (i.e., C+1 > (N-D)/2 >= C), then the next one says "bad".
 
The worst case number of questions required for odd N > 1 is  
(N-1)/2 + (N-3)/2 + ... + (N-(N-2))/2 = (N2-1)/8
 
The worst case number for even N > 2 is  
N/2 + (N-2)/2 + ... + (N-(N-4))/2 = (N2+2N-8)/8
IP Logged

http://tim-mann.org/
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: New Puzzle: Good/Bad computers  
« Reply #3 on: Oct 10th, 2002, 7:11am »
Quote Quote Modify Modify

This is an awesome puzzle! I contest that there is probably an O(n) solution out there. This is likely because there are less than 2N-1 possibilities for which computers are bad.
 
I just haven't found it yet Wink
 
Okay, here's an O(n log n) idea:
 
Number the computers from 1 to N, calling them A1 to AN. Now ask A1 about A2, ask A3 about A4, etc. Discard the pair of computers if the answer is "bad" (thanks Tim!).
 
For all the pairs of computers that answered "good", now ask the question back the other way (eg ask A2 about A1). Again, discard all pairs where the computer answers "bad".
 
Now you have "entwined" the goodness of the two computers in the pair. If one is good, the other is good, and if one is bad, the other is bad too. This is the basis for my scheme.
 
Now you can combine pairs (in nlogn fashion) by asking a computer in one pair about a computer in a different pair (eg. ask A1 about A3). If the answer is "bad", then discard both pairs. Ask the question in reverse, and you have linked the pairs.
 
Keep linking up your pairs, then quadruples, etc. like this, until every computer is connected to every other computer. All computers you haven't discarded by now are good.
 
Border cases must be considered, however, to make sure that this thing terminates (otherwise, you could end up discarding all the computers). At some point, you will have to combine groups which aren't the same size. This leads to the possibility of tossing out more "good" computers than "bad" computers if you aren't careful.
« Last Edit: Oct 10th, 2002, 7:31am by James Fingas » IP Logged

Doc, I'm addicted to advice! What should I do?
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: New Puzzle: Good/Bad computers  
« Reply #4 on: Oct 10th, 2002, 7:39am »
Quote Quote Modify Modify

Okay! I figured out how to avoid tossing out too many good computers! Here's the problem: Consider three computers,  
 
G G B
 
You entwine the goodness of the first two computers to form a pair (and keep them, since they're both good)
 
(G G) B
 
But when you ask computer 1 about computer 3, you get "bad", which might make you throw away all three of them!
 
However, at this point you can reason out which computers are good and which ones are bad. The important thing is that there are more good computers than bad computers. The pair therefore must be good.
 
This is true in general--you never have to combine groups of differing sizes. When you get to the end, you in general have groups of computers, the sizes of which are powers of 2. None of these powers of 2 can be the same (because then you wouldn't be done). Since you know there are more good than bad, the computers in the largest group are all good (since they form the majority of computers). QED!
IP Logged

Doc, I'm addicted to advice! What should I do?
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: New Puzzle: Good/Bad computers  
« Reply #5 on: Oct 10th, 2002, 7:47am »
Quote Quote Modify Modify

You know what I just realized? My solution isn't O(n log n)  Sad It's O(n)  Grin Grin Grin
 
The first pass takes ~n questions (two for each pair)
The second pass takes ~n/2 questions (one for each pair)
The third pass takes ~n/4, etc.
 
Which, of course, sums to 2n!
IP Logged

Doc, I'm addicted to advice! What should I do?
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: New Puzzle: Good/Bad computers  
« Reply #6 on: Oct 10th, 2002, 7:56am »
Quote Quote Modify Modify

I just figured out how to do it in half as many questions. Turns out you can "entwine" the pairs sufficiently for these purposes with only one question.
IP Logged

Doc, I'm addicted to advice! What should I do?
Garzahd
Guest

Email

Re: New Puzzle: Good/Bad computers  
« Reply #7 on: Oct 10th, 2002, 11:35am »
Quote Quote Modify Modify Remove Remove

Tim's catch of "if you ever get a bad response, toss both of them" is a good one.  
 
O(N^2) algorithms are a too slow. Remember, you only need to find *one* good one, not all.
 
James, you're quite close to one of the two most common solutions (I came up with the other one when I solved the problem, so I can't critique as well as I want). What if your pairings were (B G), returning G? Seems to me like you might get a couple false positives this way.
 
The correct answer is that N-2 tests are required. I'll let James iron out some border cases and post my solution tomorrow.
IP Logged
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: New Puzzle: Good/Bad computers  
« Reply #8 on: Oct 10th, 2002, 12:53pm »
Quote Quote Modify Modify

Any pair of computers (B,G) cannot both return G, for obvious reasons. Remember that I'm considering pairings where both return G, or I toss them both. But this is for my first idea, where the worst case is 2N-4 tests.
 
My optimized solution indeed gives worst-case performance of N-2 tests. Here's how to work it out exactly:

You are going to organize the computers into groups, the sizes of which are all powers of 2. Consider the groups organized into "buckets". In each bucket are groups of exactly the same size. Each group has a "leader" computer, which is certified to be good by all computers in the group. This leader is therefore the most trustworthy computer in the group. There is also a computer discard pile.
 
Initially, all buckets are empty, except for bucket 0, which has N individual computers. Each computer is a group of size 20. Each computer is therefore the leader in the group.
 
1) Examine the highest-numbered bucket that is non-empty. If it has just one group, and that group contains at least half of non-discarded computers, then the leader of that group is a "good" computer.
 
2) If the bucket contains more than one group, then combine the two groups, by asking the leader of one group about the leader of the other group. If the answer is "bad", discard both groups. You are guaranteed to discard at least as many bad computers as good computers. If the answer is "good", then the subject of the test has been certified by both groups, and is the leader of a new, larger group. Move this group into the next bucket.
 
4) If the bucket contains only one group, but it does not contain at least half of the non-discarded computers, examine all lower-numbered buckets in turn, until you find one with more than one group in it. Combine this group in the way suggested in step 2.
 
Here is the pseudocode:
 
computer findGoodComputer( int N, computers C[N] ) {
 computerList buckets[log2(N)];
 int discards;
 int i;
 int curBucket = 0;
 int maxBucket = 0;
 
 // All individual computers go into bucket 0.
 for( i=0; i < N; i++ )
  Buckets[0].add( C[i] );
 
 // We only store the leader in the bucket. None of the other
 // computers matter.
 while ( exp(2, maxBucket + 1) < N - discards ) {
  while( buckets[curBucket].size() <= 1 )
   curBucket--; // find a bucket with at least 2 groups
  if ( buckets[curBucket].computer(1).test( buckets[curBucket].computer(2) ) == GOOD ) {
   buckets[curBucket + 1].add( buckets[curBucket].computer(2) );
   buckets[curBucket].remove(2);
   buckets[curBucket].remove(1);
   maxBucket = max( ++curBucket, maxBucket );
  } else {
   discards += exp(2, curBucket + 1);
   buckets[curBucket].remove(2);
   buckets[curBucket].remove(1);
  }
 }
 return Buckets[maxBucket].computer(1);
}

Note that once you have identified a good computer, it is easy to test all the other computers.
« Last Edit: Oct 10th, 2002, 1:28pm by James Fingas » IP Logged

Doc, I'm addicted to advice! What should I do?
Garzahd
Guest

Email

Re: New Puzzle: Good/Bad computers  
« Reply #9 on: Oct 10th, 2002, 1:39pm »
Quote Quote Modify Modify Remove Remove

That seems to work. Good job; it's a better explanation of the pairing/bucket solution that I knew when I posted Smiley
 
Here's my solution, which I think is somewhat simpler: (sorry, don't know how to color-encode yet)
 
 
If there are an even number of computers, toss one randomly (the good>bad rule still applies).
 
Line up all N computers and have each of the first (N-2) computers test the next one in line. If any return "bad", toss the tester and testee. Say K computers remain, each of the first (K-2) having tested the next one and return "good".  If K=1, you've thrown out all but one computer; therefore that one is good. Otherwise, the (K-1)th remaining computer is good.
 
Why this is true requires a little more explanation: Getting a "good" response only means that the tester/testee combination is not GB. It could still be GG, BG, or BB. Since you've gotten "good" responses from each of the K-2 tests for which the tester and testee are still around, because of the chain effect, you know the first K-1 remaining computers must be some number of bads followed by some number of goods.  
 
You know that no bad computers will appear later in the chain then a good computer because then a good would have tested a bad and returned "bad", causing the pair to be thrown out. Therefore the last testee, the (K-1)th computer, must be good.
IP Logged
frsyj
Guest

Email

Re: New Puzzle: Good/Bad computers  
« Reply #10 on: Oct 10th, 2002, 5:16pm »
Quote Quote Modify Modify Remove Remove

Garzahd,
 
I think I'm having trouble understanding your solution. Say I iniatially have a line up something like this:
 
GGGGBBB
 
Every test returns good except 4(G) testing 5(B). My understanding of your solution then calls for dumping these two computers leaving K computers in this configuration:
 
GGGBB
 
Obviously the K-1th computer isn't good. Have I misinterpreted your solution?
IP Logged
frsyj
Guest

Email

Re: New Puzzle: Good/Bad computers  
« Reply #11 on: Oct 10th, 2002, 5:28pm »
Quote Quote Modify Modify Remove Remove

Sorry, worked out my obvious mistake! Smiley
IP Logged
TimMann
Senior Riddler
****






   
WWW

Gender: male
Posts: 330
Re: New Puzzle: Good/Bad computers  
« Reply #12 on: Oct 10th, 2002, 11:55pm »
Quote Quote Modify Modify

I think frsyj actually had a good question on a point that wasn't clear in Garzahd's writeup, but picked the wrong example. (Well, or maybe that wasn't what frsyj had in mind at all, but I wanted to post this clarification anyway!)
 
Suppose you have GGGGBBBBG.  Then when 4 tests 5, it says "bad" and both are thrown out. The point that Garzahd didn't make clear is that you then need to have 3 test 6 in order to continue the chain. 3 already tested 4 previously, but this doesn't add another question; 3 is getting the question that you would have asked 6 if you hadn't thrown it out.
 
James's and Garzahd's solutions are actually pretty similar. The chain being built in Garzahd's is just like one of the groups in James's, with the last testee being the leader. In both you have the property that if the leader is bad, the whole group is bad. (Therefore in Garzahd's, you can stop as soon as your chain has more elements than are left undiscarded; you don't always have to go all the way to N-2 questions.) Garzahd turns out not to need the trick of keeping the groups power-of-2 sizes so that you can sometimes throw out more than two computers at a time.
 
Anyway, cool puzzle. I kind of wish I had waited to post until I'd thought about it some more. Then maybe I could have been the first one with an optimal solution. Wink
« Last Edit: Oct 11th, 2002, 12:01am by TimMann » IP Logged

http://tim-mann.org/
Garzahd
Guest

Email

Re: New Puzzle: Good/Bad computers  
« Reply #13 on: Oct 11th, 2002, 12:00pm »
Quote Quote Modify Modify Remove Remove

Tim, you're right. Sorry for being a little vague.
 
In many cases, my solution will finish faster than N-2, since after several "good" answers you can conclude that the rest must be good because of the good>bad condition, and knowing that the bads (if any) must be packed at the beginning of the chain. Excluding the last untested element, of course.
 
The pessimal case for my algorithm is an alternating set, i.e. BGBGBGBG...(G)
Here, #1 tests #2, good. Then #2 tests #3, tossing both. Then #1 tests #4, good. Then #4 tests #5, tossing both. Then #1 tests #6, etc. This requires all N-2 tests.
IP Logged
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: New Puzzle: Good/Bad computers  
« Reply #14 on: Oct 11th, 2002, 12:54pm »
Quote Quote Modify Modify

Garzahd,
 
How can this sequence have more Gs than Bs?
 
BGBGBGBG...  
 
Your solution takes N-2 tests if you never build up a large enough chain to end things. One example:
 
GGGBBGB
 
Here's a good question: which method works better on average? Are they average-case equivalent? Note that in the above example, my solution does a little better.  Grin
IP Logged

Doc, I'm addicted to advice! What should I do?
Jonathan_the_Red
Junior Member
**





   
Email

Gender: male
Posts: 102
Re: New Puzzle: Good/Bad computers  
« Reply #15 on: Oct 11th, 2002, 4:56pm »
Quote Quote Modify Modify

Garzahd--
 
Welcome to the forum! Now register, dammit!
 
To color encode, put your text between ]color[ and ]/color[ tags (reversing the brackets so they point the right way; I put them like they are so vBulletin doesn't think they're real color tags.)
 
This board uses an alternating background scheme of dark gray and medium gray and you gotta pay attention on which color your post will appear. The dark gray is hex color 252525 and the light gray is 444444. So if your post will appear on dark gray, hide text like so:
 
]color=252525[This text is hidden by color]/color[
 
...again reversing the brackets. Here's a "real" example:
 
This text is in color 444444, which is hidden on a medium background
 
Use your mouse to highlight the text and read the hidden line.
« Last Edit: Oct 11th, 2002, 4:57pm by Jonathan_the_Red » IP Logged

My arcade cabinet
Garzahd
Junior Member
**





    mlahut


Gender: male
Posts: 130
Re: New Puzzle: Good/Bad computers  
« Reply #16 on: Oct 11th, 2002, 8:43pm »
Quote Quote Modify Modify

Alright, alright, I'll register....
 
I tend to disapprove of forums that rate someone's quality based on volume of posts, but here it might actually be justified Smiley
 
Jonathan: FYI, I ended up on this site as a result of giving up on the Gibberland puzzle from the puzzhunt list...
 
As for my first item on my last post breaking the good>bad criterion, what I meant to say was an arbitrary amount of BG's followed by one G.
 
As for average-case analysis? Hmm. I'd be tempted to just code up both algorithms and brute-force it. Actually that wouldn't work, because the B's are evil. Grr.
IP Logged
Jonathan_the_Red
Junior Member
**





   
Email

Gender: male
Posts: 102
Re: New Puzzle: Good/Bad computers  
« Reply #17 on: Oct 12th, 2002, 1:52pm »
Quote Quote Modify Modify

on Oct 11th, 2002, 8:43pm, Garzahd wrote:
Jonathan: FYI, I ended up on this site as a result of giving up on the Gibberland puzzle from the puzzhunt list...

 
Cool, what team were you on? I hear that the CGTs are planning the next hunt to take place much sooner than a year from now... Mission:Impuzzible was my second hunt and I can't wait for my third.
IP Logged

My arcade cabinet
Garzahd
Junior Member
**





    mlahut


Gender: male
Posts: 130
Re: New Puzzle: Good/Bad computers  
« Reply #18 on: Oct 13th, 2002, 10:59am »
Quote Quote Modify Modify

Water Based Solutions. Didn't do too well, but I was only there for about 8 hours total, and we had some other team members who were around for less than that. I really wish there was some clever game mechanism that avoided the need for all-nighters. But it was still immensely satisfying. And now I know a lot more tricks to use for the next hunt.
 
I'm really excited about the suggestion of the bring-your-own puzzle event with some neutral arbitrator. I've already started on putting one together Smiley  
 
It was my first hunt. Just moved to the area 2 months ago.
IP Logged
titan
Newbie
*





   


Posts: 33
Re: Good/Bad computers  
« Reply #19 on: Oct 12th, 2013, 9:23pm »
Quote Quote Modify Modify

Why has this been said in an earlier post:-
"2) If N-D <= 2, all non-discarded machines are good; stop. "
And 4) point too. I'm not getting the logic!
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Good/Bad computers  
« Reply #20 on: Oct 13th, 2013, 8:18am »
Quote Quote Modify Modify

on Oct 12th, 2013, 9:23pm, yoyoy wrote:
Why has this been said in an earlier post:-
"2) If N-D <= 2, all non-discarded machines are good; stop. "

The assumption is the majority is good. Good and bad are thrown away in pairs, so if there's 1 or 2 left they must be good.
 
Quote:
And 4) point too. I'm not getting the logic!
If the candidate is bad, a good computer would have said so. So once you've tested with more than half the computers, one of those must have been good, therefor if the candidate hasn't been rejected it must be good.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board