Mastermind-like game computer player sources
Nomen Nescio
The computer tries to guess 4-digit code.
You inform the computer about the results, giving it
a two-digit answer.
The first digit is a number of digits on right position.
The second digit is a number of right digits, but on wrong
position (just like in the original Mastermind).
If you want to watch quickly how the computer finds the solution,
then you can run the program, providing the code in the command line:
$ ./mmind 6722
I try: 2634:02
I try: 0243:01
I try: 1356:01
I try: 6392:20
I try: 5727:20
I try: 6722:40
I've won!
Otherwise, you'll need to enter the answers manually after
each computer's guess.
The program was written as simple as possible. No error checking
is done, so enter the answers carefully.
The algorithm is very simple. In each turn, the computer selects
the guess, which divides all still possible codes into smallest
clusters (in fact the size of the bigest cluster is considered).
When only one matching code remains, it is selected as a guess.
#!/bin/sh
# This is a shell archive (produced by GNU sharutils 4.6.3).
# To extract the files from this archive, save it to some FILE, remove
# everything before the `#!/bin/sh' line above, then type `sh FILE'.
#
lock_dir=_sh28535
# Made on 2008-08-29 23:27 CEST by <nobody@nowhere>.
# Source directory was `/tmp/mmind'.
#
# Existing files will *not* be overwritten, unless `-c' is specified.
#
# This shar contains:
# length mode name
# ------ ---------- ------------------------------------------
# 3533 -rw-r--r-- mmind.c
#
MD5SUM=${MD5SUM-md5sum}
f=`${MD5SUM} --version | egrep '^md5sum .*(core|text)utils'`
test -n "${f}" && md5check=true || md5check=false
${md5check} || \
echo 'Note: not verifying md5sums. Consider installing GNU coreutils.'
save_IFS="${IFS}"
IFS="${IFS}:"
gettext_dir=FAILED
locale_dir=FAILED
first_param="$1"
for dir in $PATH
do
if test "$gettext_dir" = FAILED && test -f $dir/gettext \
&& ($dir/gettext --version >/dev/null 2>&1)
then
case `$dir/gettext --version 2>&1 | sed 1q` in
*GNU*) gettext_dir=$dir ;;
esac
fi
if test "$locale_dir" = FAILED && test -f $dir/shar \
&& ($dir/shar --print-text-domain-dir >/dev/null 2>&1)
then
locale_dir=`$dir/shar --print-text-domain-dir`
fi
done
IFS="$save_IFS"
if test "$locale_dir" = FAILED || test "$gettext_dir" = FAILED
then
echo=echo
else
TEXTDOMAINDIR=$locale_dir
export TEXTDOMAINDIR
TEXTDOMAIN=sharutils
export TEXTDOMAIN
echo="$gettext_dir/gettext -s"
fi
if (echo "testing\c"; echo 1,2,3) | grep c >/dev/null
then if (echo -n test; echo 1,2,3) | grep n >/dev/null
then shar_n= shar_c='
'
else shar_n=-n shar_c= ; fi
else shar_n= shar_c='\c' ; fi
f=shar-touch.$$
st1=200112312359.59
st2=123123592001.59
st2tr=123123592001.5 # old SysV 14-char limit
st3=1231235901
if touch -am -t ${st1} ${f} >/dev/null 2>&1 && \
test ! -f ${st1} && test -f ${f}; then
shar_touch='touch -am -t $1$2$3$4$5$6.$7 "$8"'
elif touch -am ${st2} ${f} >/dev/null 2>&1 && \
test ! -f ${st2} && test ! -f ${st2tr} && test -f ${f}; then
shar_touch='touch -am $3$4$5$6$1$2.$7 "$8"'
elif touch -am ${st3} ${f} >/dev/null 2>&1 && \
test ! -f ${st3} && test -f ${f}; then
shar_touch='touch -am $3$4$5$6$2 "$8"'
else
shar_touch=:
echo
${echo} 'WARNING: not restoring timestamps. Consider getting and'
${echo} 'installing GNU `touch'\'', distributed in GNU coreutils...'
echo
fi
rm -f ${st1} ${st2} ${st2tr} ${st3} ${f}
#
if test ! -d ${lock_dir}
then : ; else ${echo} 'lock directory '${lock_dir}' exists'
exit 1
fi
if mkdir ${lock_dir}
then ${echo} 'x - created lock directory `'${lock_dir}\''.'
else ${echo} 'x - failed to create lock directory `'${lock_dir}\''.'
exit 1
fi
# ============= mmind.c ==============
if test -f 'mmind.c' && test "$first_param" != -c; then
${echo} 'x -SKIPPING mmind.c (file already exists)'
else
${echo} 'x - extracting mmind.c (text)'
sed 's/^X//' << 'SHAR_EOF' > 'mmind.c' &&
#include <stdio.h>
#include <stdlib.h>
int check(char * a_code, char * a_guess)
{
X int i,j;
X int result;
X char code[4], guess[4];
X //Copy both code and guess
X for (i=0;i<4;i++) {
X code[i]=a_code[i];
X guess[i]=a_guess[i];
X }
X //First try if chars are on proper positions
X result=0;
X for (i=0;i<4;i++) {
X if (code[i]==guess[i]) {
X result += 10;
X // Mark "used" chars
X guess[i] = 0;
X code[i] = 0;
X }
X }
X //Now check if chars are on other positions
X for (i=0;i<4;i++) {
X if (code[i] != 0)
X for (j=0;j<4;j++) {
X if ((code[i] != 0) &&
X (guess[j] != 0) &&
X (code[i]==guess[j])) {
X //printf("%d, %d, %c, %c\n",i,j,code[i],guess[j]);
X result += 1;
X // Mark "used" chars
X code[i]=0;
X guess[j]=0;
X }
X }
X }
X return result;
}
X
// Pattern table
char patterns[10000][5];
X
void test_check(char * guess, char * pattern)
{
X printf("result for: %4.4s and %4.4s is %2.2d\n",guess,pattern,check(guess,pattern));
}
X
int main(int argc, char * argv[])
{
X int c,i,msize,min_msize,nguess;
X int match, i_match;
X int niter=0;
X int answer;
X unsigned int irnd;
X int ni;
X int code_given=0;
X FILE * frnd;
X char * code;
X
X if(argc>1) {
X code_given=1;
X code=argv[1];
X }
X
X for(i=0;i<10000;i++) {
X patterns[i][4] = 1; //Pattern still possible
X patterns[i][3] = '0'+(i % 10);
X patterns[i][2] = '0'+((i/10) % 10);
X patterns[i][1] = '0'+((i/100) % 10);
X patterns[i][0] = '0'+((i/1000) % 10);
X }
X
X //Open the random source
X frnd=fopen("/dev/urandom","r");
X //start main loop
X while(1) {
X niter++;
X if(niter>10) {
X printf("I've lost :-(\n"); //unlikely
X return 0;
X }
X min_msize=10000;
X nguess=-1;
X //Browse all possible guesses starting from random one
X fread(&irnd,sizeof(irnd),1,frnd);
X irnd=irnd % 10000;
X for(i=0;i<10000;i++) {
X ni=(i+irnd) % 10000;
X //Zero the result table
X //Possible results: 40 31? 30 22 21 20 12 11 10 04 03 02 01 00
X //However, to make the life easier, we just make a 41 element table...
X int results[41];
X int j;
X for(j=0;j<41;j++) results[j]=0;
X //Check response for each possible guess
X for(j=0;j<10000;j++) {
X if (patterns[j][4])
X results[check(patterns[ni],patterns[j])]++;
X }
X //Now find the maximum cluster size
X msize=0;
X for(j=0;j<41;j++) {
X if (results[j]>msize) msize=results[j];
X }
X //We find the guess, which provides the smallest clusters
X if(i==0) {
X nguess=ni;
X min_msize=msize;
X } else {
X if(msize<min_msize) {
X nguess=ni;
X min_msize=msize;
X }
X }
X }
X match=0;
X i_match=-1;
X for(i=0;i<10000;i++) {
X if (patterns[i][4]) {
X match++;
X i_match = i;
X }
X }
X if (match==0) {
X printf("No code matches your responses.\nYou must have mistaken!\n");
X return 1;
X }
X //If there is only one matching pattern - try it
X if (match==1) nguess=i_match;
X //Ask the question - variable "guess"
X //printf("msize=%d, zgaduje: %4.4s:",min_msize,patterns[nguess]);
X printf("I try: %4.4s:",patterns[nguess]);
X //Read the result "answer"
X if(code_given) {
X answer=check(patterns[nguess],code);
X printf("%2.2d\n",answer);
X } else {
X scanf("%d",&answer);
X }
X if(answer==40) {
X printf("I've won!\n");
X return 0;
X }
X //Filter out patterns, which do not match result
X for(i=0;i<10000;i++) {
X if (check(patterns[nguess],patterns[i]) != answer) {
X patterns[i][4]=0;
X }
X }
X }
}
SHAR_EOF
(set 20 08 08 29 23 04 31 'mmind.c'; eval "$shar_touch") &&
chmod 0644 'mmind.c'
if test $? -ne 0
then ${echo} 'restore of mmind.c failed'
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'mmind.c: MD5 check failed'
) << SHAR_EOF
8c9083ec6e80bff7935adb0ea2599038 mmind.c
SHAR_EOF
else
test `LC_ALL=C wc -c < 'mmind.c'` -ne 3533 && \
${echo} 'restoration warning: size of mmind.c is not 3533'
fi
fi
if rm -fr ${lock_dir}
then ${echo} 'x - removed lock directory `'${lock_dir}\''.'
else ${echo} 'x - failed to remove lock directory `'${lock_dir}\''.'
exit 1
fi
exit 0