Mastermind is a number guessing game. Under the fixed number of digits, you make up a number. For example, let us have four as the number of digits. You are assumed to have a number 2113. Then the mastermind is trying to guess what number you have in your mind by repeating presenting a guessing number and asking the score on how close to your number it is.
Of course, you need to answer how many digits are correct digits in the correct positions, which is called bulls. Also, you are guided to answer how many digits are correct digits but not in the correct positions, which is called cows. In the second answer, you only consider the rest of the digits, not counted as bulls. A pair of bulls and cows is called a score.
For example, the mastermind's suggestion would be 1234. Its score is 0 (bulls) and 3 (cows). Compared with your number 2113, no position of the suggested digits has any matches. But 1, 2, and 3 in the suggested digits occur in your number in different places. So is the score.
When the mastermind suggests 1111, what is the score? It is 2 (bulls) and 0 (cows). For 1212, the score is 1 (bulls) and 2 (cows).
The mastermind WILL pick up the number eventually as long as you keep answering consistently. I like to make up a mastermind program that behaves as the mastermind. My haskell code is available in:
https://github.com/kwanghoon/mastermind
The idea is simple. I made a function score that calculates a score from a given secrete code and a guess. After I get the number of digits, say, n, I generate all n-digit numbers. I suggest each number in the list to user, asking a score if it is not his or her number. I gather all the scores together with the corresponding numbers suggested. With this history (a list of pairs of a suggested number and a score), the next number to suggest is determined as this. I compute scores with each of the candidates (from the rest of the n-digit numbers) and all the previous suggestions to compare with user's answer (score). If there is any mismatch between the user's score and the calculated one, the candidate number is excluded from our interest. This procedure is used as a filter to exclude inappropriate candidate numbers (from the rest of the n-digit numbers). If we find a number (from the rest of the n-digit numbers) that matches all user's scores in the history, then we suggest this number to ask him or her if this is the number in mind. We repeat this procedure until we find the number!
Here is a sample run of the program for your understanding, assuming that your number is 2113.
Thanks to Haskell's laziness, the program generates candidate numbers on demand. This makes it run efficiently. Great!
One improvement to this version is to find and print inconsistent answers from users if such a situation happens. Do you want to try?
Of course, you need to answer how many digits are correct digits in the correct positions, which is called bulls. Also, you are guided to answer how many digits are correct digits but not in the correct positions, which is called cows. In the second answer, you only consider the rest of the digits, not counted as bulls. A pair of bulls and cows is called a score.
For example, the mastermind's suggestion would be 1234. Its score is 0 (bulls) and 3 (cows). Compared with your number 2113, no position of the suggested digits has any matches. But 1, 2, and 3 in the suggested digits occur in your number in different places. So is the score.
When the mastermind suggests 1111, what is the score? It is 2 (bulls) and 0 (cows). For 1212, the score is 1 (bulls) and 2 (cows).
The mastermind WILL pick up the number eventually as long as you keep answering consistently. I like to make up a mastermind program that behaves as the mastermind. My haskell code is available in:
https://github.com/kwanghoon/mastermind
The idea is simple. I made a function score that calculates a score from a given secrete code and a guess. After I get the number of digits, say, n, I generate all n-digit numbers. I suggest each number in the list to user, asking a score if it is not his or her number. I gather all the scores together with the corresponding numbers suggested. With this history (a list of pairs of a suggested number and a score), the next number to suggest is determined as this. I compute scores with each of the candidates (from the rest of the n-digit numbers) and all the previous suggestions to compare with user's answer (score). If there is any mismatch between the user's score and the calculated one, the candidate number is excluded from our interest. This procedure is used as a filter to exclude inappropriate candidate numbers (from the rest of the n-digit numbers). If we find a number (from the rest of the n-digit numbers) that matches all user's scores in the history, then we suggest this number to ask him or her if this is the number in mind. We repeat this procedure until we find the number!
Here is a sample run of the program for your understanding, assuming that your number is 2113.
GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> :load "Main.hs"
[1 of 1] Compiling Main ( Main.hs, interpreted )
Ok, modules loaded: Main.
*Main> main
How many digits?
4
Enter your choice: y with nothing, or n with bulls and cows (say, n 1 3)
[0,0,0,0] ? n 0 0
[1,1,1,1] ? n 2 0
[2,2,1,1] ? n 2 1
[2,1,3,1] ? n 2 2
[1,2,3,1] ? n 0 4
[2,1,1,3] ? y
*Main>
Thanks to Haskell's laziness, the program generates candidate numbers on demand. This makes it run efficiently. Great!
One improvement to this version is to find and print inconsistent answers from users if such a situation happens. Do you want to try?
No comments:
Post a Comment