Rcjp's Weblog

January 6, 2007

Twenty Questions Game in C

Filed under: c — rcjp @ 3:33 pm

Tree traversal is really really easy in Common Lisp so for a bit more of a challenge I wrote this in C. The game is for the user to think of an object and answer questions while the program tries to guess. The code is just a binary search tree, but you have to look ahead to see if you need to add in a piece of tree rather than just a straighforward leaf node.

    #include <stdio.h>
    #include <string.h>
    #include <stdbool.h>
    #include <stdlib.h>

    #define LINE_MAX 512

    typedef struct node NODE;
    struct node {
        char qu[LINE_MAX];
        NODE *yes, *no;
    };

    /*
     * print message and read stdin into LINE_MAX reply buffer
     * trimming newline
     */
    void getreply(char *message, char reply[LINE_MAX])
    {
        puts(message);
        fflush(stdout);
        fgets(reply, LINE_MAX, stdin);
        strtok(reply, "\n");        /* trim off \n */
    }

    bool ask(char *question, bool object)
    {
        char line[LINE_MAX], reply[LINE_MAX], qu[LINE_MAX];

        if (object)
            sprintf(qu, "Is it %s?", question);
        else
            strcpy(qu, question);
        getreply(qu, line);
        sscanf(line, "%s", reply);
        if (!strcmp(reply, "yes") || !strcmp(reply, "y"))
            return true;
        return false;
    }

    int main()
    {
        NODE info = { "Is it an animal?",
            &(NODE) {"Is it slimy?",
                     &(NODE) {"a fish", NULL, NULL},
                     &(NODE) {"a bear", NULL, NULL}},
            NULL
        };

        char object[LINE_MAX], clarify[LINE_MAX];
        bool yesno;
        do {
            NODE *curr = &info, *next, *newnode;
            while (curr) {
                yesno = ask(curr->qu, false);
                next = yesno ? curr->yes : curr->no;
                if (!next) {
                    /*  
                     * we need to add a leaf 
                     */
                    curr->no = malloc(sizeof(NODE));
                    getreply("What is it? ", curr->no->qu);
                    break;
                }
                if (!next->yes && !next->no) {
                    /* 
                     * we might need to add a new node in here 
                     */
                    if (ask(next->qu, true))
                        break;      /* the leaf was right.. new game */

                    newnode = malloc(sizeof(NODE));
                    getreply("What is it? ", object);
                    sprintf(clarify, "What question distiguishes %s from %s?",
                            object, next->qu);
                    getreply(clarify, newnode->qu);

                    /* check which way round this new question applies */
                    sprintf(clarify, "A %s, %s", object, newnode->qu);
                    if (ask(clarify, false)) {
                        newnode->yes = malloc(sizeof(NODE));
                        strcpy(newnode->yes->qu, object);
                        newnode->no = next;
                    } else {
                        newnode->no = malloc(sizeof(NODE));
                        strcpy(newnode->no->qu, object);
                        newnode->yes = next;
                    }
                    if (yesno)
                        curr->yes = newnode;
                    else
                        curr->no = newnode;
                    break;
                }
                curr = next;
            }
        }
        while (ask("New Game", false));
        return 0;
    }


    /*   Sample run...

        Is it an animal?
        y
        Is it slimy?
        n
        Is it a bear?
        y
        New Game
        y

        Is it an animal?
        n
        What is it?
        a box
        New Game
        y

        Is it an animal?
        n
        Is it a box?
        n
        What is it?
        a banana
        What question distiguishes a banana from a box?
        is it yellow?
        A a banana, is it yellow?
        y
        New Game
        y

        Is it an animal?
        n
        is it yellow?
        y
        Is it a banana?
        n
        What is it?
        the sun
        What question distiguishes the sun from a banana?
        is it cold?
        A the sun, is it cold?
        n
        New Game
        y

        Is it an animal?
        n
        is it yellow?
        y
        is it cold?
        n
        Is it the sun?
        y
        New Game
        n
        r@laptop:~/c/tmp$
    */

I started thinking about how this would look in a C++ object type program but, to be honest, I don’t enjoy trying to think out the right class structure; and what is annoying is that you can’t start coding and explore the problem as you code, because you’ll come to a grinding halt if you’ve got the structure wrong. I guess I just don’t think OOP is fun coding, at least not in C++.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: