Author |
Topic: does secret key exist? (Read 4720 times) |
|
inexorable
Full Member
Posts: 211
|
 |
does secret key exist?
« on: Oct 22nd, 2012, 3:08pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
Johnson
Newbie
G33k
Gender: 
Posts: 5
|
|
Re: does secret key exist?
« Reply #1 on: Dec 2nd, 2012, 8:50am » |
Quote Modify
|
seem like a cool game.
________________________________________________________
Riddle : A Cat in the Hat With (spam removed) in one hand.
|
| « Last Edit: Dec 6th, 2012, 4:51am by Grimbal » |
IP Logged |
|
|
|
wiley
Newbie
Posts: 12
|
|
Re: does secret key exist?
« Reply #2 on: Dec 5th, 2012, 9:35am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print