wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> does secret key exist?
        
(Message started by: inexorable on Oct 22^nd, 2012, 3:08pm)

Title: does secret key exist?
Post by inexorable on Oct 22^nd, 2012, 3:08pm

Mastermind is a game of two players. In the beginning, first player decides a secret key, which is a sequence (s1,s2,...sk) where 0 < si <= n, Then second player makes guesses in rounds, where each guess is of form (g1,g2, ...gk), and after each guess first player calculates the score for the guess. Score for a guess is equal to number of i's for which we have gi = si.

For example if the secret key is (4,2,5,3,1) and the guess is (1,2,3,7,1),then the score is 2, because
g2 = s2 and g5 = s5.

Given a sequence of guesses, and scores for each guess, your program must decide if there exists at least one secret key that generates those exact scores.

Title: Re: does secret key exist?
Post by Johnson on Dec 2^nd, 2012, 8:50am

seem like a cool game.

________________________________________________________
Riddle : A Cat in the Hat With (spam removed) in one hand.

Title: Re: does secret key exist?
Post by wiley on Dec 5^th, 2012, 9:35am

Just puting my thoughts:

- Take a guess with maximum count. say: x1,x2,..xk
- Invalidate locations if possible, for example: say there exists another guess with count 0 and its 2nd location equals x2. So x2 cannot be right.

After good number of in-validations, we'll reach a state where we can positively say the particular location's value. for example: say there exists another guess with count 1 and all keys invalid except at location 3. And location 3 matches x3.

If we keep doing this iteratively again and again, we should reach the state where we can positively find a secret key or fails due to un-knowns.