C Program for 21 Sticks game

Here is a good brain refreshing puzzle that I solved recently. Thanks to my friend Raghul for sharing this good piece of puzzle with me. Its a turn based 2 player game (player and computer in our case). c

Now, I am to write a program for this game in such a way that however the player plays, he always picks the last one and thus the computer wins. Looked very simple at first and I came with the following program in 15 minutes and thought to myself (very proudly) that I solved it.

    
    int lineCount;
    int userPick;
    int aiPick;

    lineCount = 21;
    while (lineCount > 1) {
        printf("\n\n%d lines remaining. Pick 1 or 2 or 3 or 4: ", lineCount);
        scanf("%d", &userPick);
        lineCount -= userPick;

        if (lineCount == 1) {
            printf("\nyou win and AI lose\n");
            return;
        }
        if (lineCount <= 5) {
            aiPick = lineCount - 1;
        } else {
            aiPick = rand() % 4 + 1;
        }

        printf("you took %d lines", userPick);
        printf("\nAI took %d lines", aiPick);
        lineCount -= aiPick;
    }
    if (lineCount == 1) {
        printf("\nyou win and AI lose\n");
        return;
    } else {
        printf("\n1 line remains and u lose\n\n");
    }

The AI seems to be working good, but its not perfect. It fails occasionally, especially when the player gets a turn with the remaining number of sticks in the range 2 to 5. So I tried to fix this by playing in such a way that AI always gets its turn when the remaining number of sticks is in the range 2 to 5. But I couldn’t figure out how to do this inside my little mind. So I took a pen and paper and started writing the remaining number of lines, all possibilities of AI’s move and corresponding result, which resulted in a table such as this:

Possible States with results
Remaining Sticks AI Move Worst Case
2 1 Win
3 2 Win
4 3 Win
5 4 Win
6 1 Lose
2 Lose
3 Lose
4 Lose
7 1 Win
2 Lose
3 Lose
4 Lose
8 1 Lose
2 Win
3 Lose
4 Lose
9 1 Lose
2 Lose
3 Win
4 Lose
20 1 Lose
2 Lose
3 Lose
4 Win
21 1 Lose
2 Lose
3 Lose
4 Lose

Only after completely writing out the above table, I found that when there are some certain magic remaining sticks at your turn, regardless of your move, if ur opponent plays his best move, he can win. The magic numbers are found to be 21, 16, 11, 6 and of course 1.

Since the player begins the game with 21 remaining sticks (one of the magic number), as long as my AI plays its best move, it can win. The AI’s best move nothing but the move which makes the remaining number of lines to the next lowest magic number and as we continue when the player plays his move, he will have the remaining sticks as 16, 11, 6 and finally 1 and he loses. Here is the final working program with perfect AI:

#include <stdio.h>

int lineCount;

void main() {

    int userPick;
    int aiPick;

    lineCount = 21;
    while (lineCount > 1) {
        printf("\n\n%d lines remaining. Pick 1 or 2 or 3 or 4: ", lineCount);
        scanf("%d", &userPick);

        lineCount -= userPick;

        if (lineCount >= 17 && lineCount <= 20) {
            aiPick = lineCount - 16;
        } else if (lineCount >= 12 && lineCount <= 15) {
            aiPick = lineCount - 11;
        } else if (lineCount >= 7 && lineCount <= 10) {
            aiPick = lineCount - 6;
        } else {
            aiPick = lineCount - 1;
        }

        printf("you took %d lines", userPick);
        printf("\nAI took %d lines", aiPick);
        lineCount -= aiPick;
    }

    printf("\n1 line remains and u lose\n\n");
}

I am sure this is not the best way to solve this problem, I should have done some research on maths and find some elegant solution, but I guess this is fine for the first step and to achieve the goal. I will look into other possible elegant solutions and if I find any, I will post about it later.

Happy Programming !!!

C program to implement evaluation of Postfix expression using Stack

Program:

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

struct node {
    double element;
    struct node *next;
} *head;

void push(int c);      // function to push a node onto the stack
int pop();             // function to pop the top node of stack
void traceStack();      // function to //print the stack values

int main() {
    int i = 0, j = 0;   // indexes to keep track of current position for input output strings
    char *exp = (char *)malloc(sizeof(char)*100);
    double res = 0;
    char tmp;
    head = NULL;

    printf("Enter the postfix expression: ");
    scanf("%s", exp);

    while( (tmp=exp[i++]) != '\0') {    // repeat till the last null terminator
        // if the char is operand, pust it into the stack
        if(tmp >= '0' && tmp <= '9') {
            int no = tmp - '0';
            push(no);
            continue;
        }

        if(tmp == '+') {
            int no1 = pop();
            int no2 = pop();
            push(no1 + no2);
        } else if (tmp == '-') {
            int no1 = pop();
            int no2 = pop();
            push(no1 - no2);
        } else if (tmp == '*') {
            int no1 = pop();
            int no2 = pop();
            push(no1 * no2);
        } else if (tmp == '/') {
            int no1 = pop();
            int no2 = pop();
            push(no1 / no2);
        }
    }

    printf("Result of the evalution is %d", pop());
    return 0;
}

void push(int c) {
    if(head == NULL) {
        head = malloc(sizeof(struct node));
        head->element = c;
        head->next = NULL;
    } else {
        struct node *tNode;
        tNode = malloc(sizeof(struct node));
        tNode->element = c;
        tNode->next = head;
        head = tNode;
    }
}

int pop() {
    struct node *tNode;
    tNode = head;
    head = head->next;
    return tNode->element;
}

Sample Output:

Enter the postfix expression: 65*3+
Result of the evalution is 33

C program to implement infix to postfix expression

Program:

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

struct node {
    char element;
    struct node *next;
} *head;

void push(char c);      // function to push a node onto the stack
char pop();             // function to pop the top node of stack
int precedence(char c); // function to find the precedence of an operator
void traceStack();      // function to //print the stack values

int main() {
    int i = 0, j = 0;   // indexes to keep track of current position for input output strings
    char *exp = (char *)malloc(sizeof(char)*100);
    char *res = (char *)malloc(sizeof(char)*100);
    char tmp;
    head = NULL;

    printf("Enter the infix expression: ");
    scanf("%s", exp);

    while( (tmp=exp[i++]) != '\0') {    // repeat till the last null terminator
        // if the char is operand, copy it to output string
        if(tmp >= 97 && tmp <= 122) {
            res[j++] = tmp;
            continue;
        }

        if(tmp == '(' || tmp == '[' || tmp == '{') {
            push(tmp);
            continue;
        }

        if(tmp == ')' || tmp == ']' || tmp== '}') {
            char cl, tp;
            if(tmp == ')') cl = '(';
            if(tmp == '}') cl = '{';
            if(tmp == ']') cl = '[';

            tp = pop();

            while(tp != cl) {
                res[j++] = tp;
                tp = pop();
            }
            continue;
        }

        // if char is operator
        if(tmp == '+' || tmp == '-' || tmp == '*' || tmp == '/') {
            if(head == NULL) {
                push(tmp);
            } else {
                // if operator at top of stack has high precedence, pop it and
                // add to output string, else just push the operator
                while(precedence(tmp) <= precedence(head->element) && head->element != '(' && head->element != '[' && head->element != '{') {
                    char tp = pop();
                    res[j++] = tp;
                    if(head == NULL)
                        break;
                }
                push(tmp);
            }
        }
    }

    // pop all the operators from stach to output string
    while (head != NULL) {
        res[j++] = pop();
    };
    res[j++] = '\0';

    printf("Postfix expression is %s\n\n", res);
    return 0;
}

void push(char c) {
    if(head == NULL) {
        head = malloc(sizeof(struct node));
        head->element = c;
        head->next = NULL;
    } else {
        struct node *tNode;
        tNode = malloc(sizeof(struct node));
        tNode->element = c;
        tNode->next = head;
        head = tNode;
    }
}

char pop() {
    struct node *tNode;
    tNode = head;
    head = head->next;
    return tNode->element;
}

int precedence(char c) {
    if (c == '*' || c == '/')
        return 2;
    else if (c == '+' || c == '-')
        return 1;
    else
        return 5;
}

void traceStack() {
    struct node *tNode;
    tNode = head;
    while(tNode != NULL) {
        printf("%c --> ", tNode->element);
        tNode = tNode->next;
    }
    printf("\n");
}

Sample Output:

Enter the infix expression: (a+b)*(d+e)
Postfix expression is ab+de+*

C Program to Check Leap Year

Program Logic:

If the year is divisible by 4, it is a leap year. But, if it is divisible by 100, it is not. If the year is divisible by 400, it is a leap year.

Examples:

1. 1996 is a leap year. (divisible by 4)
3. 2100 is a not leap year. (divisible by 100)
2. 2000 is a leap year. (divisible by 100 but also divisible by 400)

Program:

#include<stdio.h>
#include<conio.h>

void main()
{
int year;
clrscr();
printf(“Enter a Year to check : “);
scanf(“%d”, &year);

if(year % 400 == 0)
printf(“%d is a Leap Year.”, year);
else if(year % 100 == 0)
printf(“%d is not a Leap Year.”, year);
else if(year % 4 == 0)
printf(“%d is a Leap Year.”, year);
else
printf(“%d is not a Leap Year”, year);

printf(“\nPress any key to Quit…”);
getch();
}

C Program to find sum of cubic roots of individual digits of a number

Examples:

123 : 11/3 + 21/3 + 31/3

Program:

#include<stdio.h>
#include<conio.h>
#include<math.h>

void main()
{
long int no;
float sum = 0;
clrscr();
printf(“Enter a Number : “);
scanf(“%ld”, &no);
while (no > 0)
{
sum = sum + pow(no % 10,(1/3));
no = no / 10;
}
printf(“\nSum is %f\n”, sum);
getch();
}