Building a Number Guessing Game in C - C Projects

What are We Building?

The number guessing game is a game where the computer generates a random number and we need to guess that number in minimum tries. After every try, the computer will tell us whether our guess was smaller, larger, or equal to the random computer-generated number and if the number we guessed wasnt equal to the compuer generated number then we can try again until we get the correct guess. The random number in the game is between 1 to 100. We'll be looking at how we can implement this project in C, but before that let us go through the pre-requisites for the project.

Pre-requisites

The languages or algorithms that will be used in this project are:

• C programming language basics like:
  • Do while loop
  • If else statements
• Searching algorithms like:
  • Linear Search
  • Binary Search
  • Randomized Binary Search
  • Improved Binary Search

How are We Going to Build the Game?

The game is built using C programming language and is run in the terminal. The program code makes use of the built in function in C to generate a random number and also one of the standard looping methods which is the do-while loop for the functionality of the game. We keep playing the game till the user guesses the correct answer or stops the game. We keep on taking the next guess from the user and compare it with the generated number until the user's guess matches with the generated number.

Final Output

Requirements

To make this project, the major requirements are:

1. An Integrated Development Environment (IDE) or a text editor where you can write the code for the project.
2. C Compiler
3. The libraries needed for this project in C are: stdio.h, math.h, stdlib.h and time.h.

Building the Number Guessing Game in C

After we have met all the requirements, we can now take a look at how actually the number guessing game will be built in C.

What is the Game about?

Before jumping to the implementation and code, we'll take a moment to understand the game and what it is about.

• The number guessing game will involve one user. When the game starts, the computer will generate a random number strictly between 1 and 100.
• The task of the user is to take a guess at what this number might be.
• Of course, just taking random guesses to find a number sounds boring. So, to make the game more interesting, each time the user takes a guess the game will tell the user whether the guessed number is greater, smaller or equal to the computer generated number.
• In case these are equal, the game finishes and the number of tries it took the user to correctly guess the number becomes his/her score.
• The user has to try to minimize this number of tries.

Now that we have understood how the game works and its rules, we can look at how we will implement the number guessing game in C to complete our project.

How to Implement the Game in C?

Before moving on to the code for the project, we'll look at the different components of the number guessing game in C.

First, at the very start of the game we will have to generate a random number between 1 and 100 which the user will try to guess. For this, we will be using the in-built rand() function in C. This function is defined in the header file <stdlib.h> which we will have to include in our code. The thing to note here is that this function will generate any random integer number. But, we want our number to be between 1 and 100 only. This is why we will make use of the modulo operator. We will take the random number and find it's modulo with 100 and add one to it. this will generate our random number for us in the range 1 to 100. Why so?

The range of any number modulo N is [0,N-1]. When we add 1 to this, the range becomes [1,N]. In our case, N = 100, and the generated number hence lies between 1 and 100 which now the user has to guess.

Another thing to note here is that the rand() function in C will generate the same number each time the program will run if we do not include the srand() function before it. This function basically resets the random number generators so that every time a new number is produced. You can read more about the srand() function in C here.

Now that we have generated the random number, all we have to do is take input from the user, which will be the user's guess and according to the guess either return that the guessed number is greater or less than the generated number, or if both are equal, the game ends and we display the user's score. We will use a do-while loop for this whole sequence, as the property of a do while loop is that the code inside this loop runs atleast once after which the condition is evaluated every time. This loop will run until the user correctly guesses the random number. Now that we've understood the implementation, let us look at the code for this game in C.

Code

Output

Optimal Strategy to Solve the Game

The game is done, but what is the most optimal strategy by which any player can minimize his/her total number of moves to guess the number? This is exactly what we will explore in this section.

Linear Search

In linear search, the user can linearly try guessing all numbers one by one from 1 to 100. The probability of getting the correct guess in the first turn is 1/100 and if we try putting all the numbers, then in the worst case we will end up putting 100 numbers. Hence, this makes the time complexity of this method O(n). But, there exist better methods where we won’t have to put all the numbers to get the answer. We'll be exploring these better startegies next.

Binary Search

Binary Search is a method where we significantly reduce the searching complexity of the program by using the fact that all the elements are ordered. We follow the following steps as the algorithm of binary search:

• We create two pointers, namely low and high which will point to the beginning of the lower half and the ending of the other half.
• Now we create another pointer as mid which we will use to compare the middle element of the elements between low and high.
• Now at every comparison, we will take the element pointed by the mid as our guess, and reduce the elements by removing either of the halves in the next turn.
• If mid matches the random number, we terminate the program.
• Else if mid is less than the random number, then the random number will lie in the left half. So we recur for the left half and change high to mid.
• Else if mid is greater than the random number, the random number lies in the right half, so we recur for the right half and change left to mid.

The complexity of this algorithm is O(log n) as at each step we are halving the range where our result lies.

Randomized Binary Search

In the case of Randomized Binary Search, instead of picking the middle element as the pivot that will divide the array, we choose the pivot element randomly from the array of provided elements. The algorithm is:

• We create two pointers, namely low and high which will point to the lower and upper half of the interval respectively.
• Now, we create another pointer named mid which will act as a pivot and help in dividing the interval into two parts.
• The value of mid is found by generating a random number by using the in-built rand() method provided in C. To make sure this value is between low and high we use the formula mid= low+ rand()%(high-low+1). This will ensure that mid is between high and low.
• Now at every comparison, we will take the element pointed by the mid as our guess, and reduce the elements by removing either of the halves in the next turn.
• If mid matches the random number, we terminate the program.
• Else if mid is less than the random number, then the random number will lie in the left half. So we recur for the left half.
• Else if mid is greater than the random number, the random number lies in the right half, so we recur for the right half.

The complexity of this algorithm will also be O(log n).

Improved Binary Search

In this method instead of taking the middle element as the mid we will take the square root of low and high as the mid. This will considerably reduce the number of iterations performed as compared to binary search. The algorithm is:

• We create two pointers, namely low and high which will point to the beginning of the lower half and the ending of the other half.
• Now we create another pointer as mid which will be the square root of the product of low and high and use this to compare elements further.
• Now at every comparison, we will take the element pointed by the mid as our guess, and reduce the elements by removing either of the halves in the next turn.
• If mid matches the random number, we terminate the program.
• Else if mid is less than the random number then we change low to mid.
• Else we change high to mid.

What’s Next

Now that we've successfully built the number guessing game in C, we can think about building a program that will be able to win this game in the least tries. For this, you can make use of the algorithms described in the above section. Apart from that, we can also modify this game slightly to increase the range of the random number from 100, so that the game becomes more difficult.