mastermind.c

Ugrás a fájl dokumentációjához.

 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
enum {
    NUM_COLORS = 10,    
    NUM_PEGS = 4,       
    N0 = 10000          
};
 
typedef struct {
    int black;  
    int white;  
} Response;
 
void printResponse(Response r) {
    printf("(%d,%d)", r.black, r.white);
}
 
int isSameResponse(Response r1, Response r2) {
    return r1.black == r2.black && r1.white == r2.white;
}
 
void digits(int a, int d[]) {
    int i;
    for (i = 0; i < NUM_PEGS; ++i) {
        d[i] = a % NUM_COLORS;
        a /= NUM_COLORS;
    }
}
 
Response common_digits(int guess, int secret) {
    Response res = {0, 0};
    int i, j, dg[NUM_PEGS], ds[NUM_PEGS];
 
    digits(guess, dg);  /* tipp jegyeinek számítása */
    digits(secret, ds); /* titok jegyeimek számítása */
 
    /* fekete tüskék gyűjtése */
    for (i = 0; i < NUM_PEGS; ++i)
        if (dg[i] == ds[i]) {
            res.black++;
            dg[i] = -1;
            ds[i] = -2;
        }
 
    /* fehér tüskék gyűjtése */
    for (i = 0; i < NUM_PEGS; ++i)
        for (j = 0; j < NUM_PEGS; ++j)
            if (dg[i] == ds[j]) {
                res.white++;
                ds[j] = -2;
                break;
            }
 
    return res;
}
 
int filter(int S[], int N, int guess, Response response)
{
    int n = 0, i;
    for (i = 0; i < N; ++i)
        if (isSameResponse(common_digits(S[i], guess), response))
            S[n++] = S[i];
    return n;
}
 
int weight(int S[], int N, int guess, Response response)
{
    int w = 0, i;
    for (i = 0; i < N; ++i)
        if (isSameResponse(response, common_digits(S[i], guess)))
            w++;
    return w;
}
 
int worstWeightOfGuess(int S[], int N, int guess) {
    Response r;
    int Weight = 0;
    for (r.black = 0; r.black <= NUM_PEGS; ++r.black)
        for (r.white = 0; r.white < NUM_PEGS; ++r.white) {
            int w;
            if (r.black+r.white > NUM_PEGS)
                continue;
            w = weight(S, N, guess, r);
            if (w > Weight)
                Weight = w;
        }
    return Weight;
}
 
int findBestGuess(int S[], int N) {
    int ming = 0, g;
    int W = worstWeightOfGuess(S, N, S[ming]);
    for (g = 1; g < N; ++g) {
        int w = worstWeightOfGuess(S, N, S[g]);
        if (w < W) {
            W = w;
            ming = g;
        }
    }
    return S[ming];
}
 
int main(void) {
    int S[N0], N, secret, i, k;
 
    srand(time(NULL));
    secret = rand() % N0;
    printf("     %04d\n", secret);
    printf("     ------------\n");
    k = 0;
 
    N = N0;
    for (i = 0; i < N0; ++i)
        S[i] = i;
 
    do {
        time_t t0 = time(NULL);
        int guess = findBestGuess(S, N);
        double dt = difftime(time(NULL), t0);
        Response response = common_digits(guess, secret);
        N = filter(S, N, guess, response);
 
        k++;
 
        printf("%3d: %04d | ", k, guess);
        printResponse(response);
        printf(" %4d %5.2f\n", N, dt);
    } while (N > 1);
 
    printf("%d", S[0]);
 
    return 0;
}