Basics of Computer Programming

By Fadhel Habeeb, Engineer, VLSI department, NIELIT, Calicut. His interests include Algorithm development and implementation, Linux based system development.

27990
Advertisement

Mastermind Game

Mastermind (Bulls and Cows numerical version) is an old code breaking mind game. It’s a two-player game, played with pencil and paper. Here one player assumes a unique 4 digit number and the opponent tries to guess it, with a limited number of chances (usually 8). The first player replies the matching digits in terms of number of bulls and cows.

If the matching digits are in the correct position, then it is a “bulls”, if in a different position it is a “Cow”.

For example

  • Secret number : 1953
  • Opponent’s try : 1235

Player1 replies: 1 bull and 2 cows. (The bull is “1”, the cows are “5” and “3”)

Then again the second player is given a second chance to guess the correct number based on present information and the game continues.

Mastermind is a typical example of both Forward and Inverse Algorithms for Computers.

In Forward Problem, Algorithm is to be developed such that computer assumes a secret 4 digit number, and a human tries to guess it back. Each time user guesses a 4 digit number, inputs it, computer calculates the matches in terms of number of bulls and cows and gives the response back to the user. User is given a limited number of chances to guess the number.

In Inverse Problem, Algorithm is to be developed such that computer tries to guess the 4-digit number assumed by a human. User assumes a unique 4 digit, computer tries a guess and human inputs the matches (number of bulls and Cows) from user. Computer is given a limited number of chances to guess the number.

Mastermind – Forward Problem

You are free to try the Algorithm, here the challenge is to develop an algorithm that selects a unique four digit number, inputs the user guess and computer computes the matches (Bulls and cows) and outputs the matches to the user. The Algorithm could be described as:

  • STEP1: Assume a 4 digit unique number and store in a variable named NUM.
  • STEP2: Set bulls and cows = 0
  • STEP3: inputs the user guess and store it in a variable named userGuess.
  • STEP4: Take each digit of userGuess and compare it with each digits of NUM,

if They are equal and in the same position

then increment bulls by one

else if they are equal and in different position

then increment cows by one

else

Continue;

  • STEP5: Respond to the user with the Bulls and cows.
  • STEP6: while chances are there OR (Bulls not equal to 4),

Repeat STEP3

A python implementation of the Algorithm is provided along.

Mastermind – Reverse Problem

(Here computer tries to guess the number assumed by a Human.)

Humans have an intuitive approach in solving such problems and it’s quite difficult to capture such intuition into Algorithms. Computers only obey instructions and here we need to develop an algorithm that can make computers behave like an intuitive being.

Computers are competent in generating a long list of numbers, traversing through the list, comparing two or three lists. Humans are error prone in such approaches and very slow. This competency of computer is what we will use here to develop an Algorithm that can guess the unique number.

Looking the problem, one can see that there are 4536 combination of unique four digit numbers possible for the game. Initially computer chooses a number from the possible lists as first guess and outputs it to the user. User Inputs the matches (Number of Bulls and Cows) for the guess. Now computer can use the first guessed number and traverse through the list to see which all numbers give the same matches (as given by the user) and generate a new list. This list will be shorter than previous lists and computer can choose a number from the new list as second guess. And the process continues. This could briefly be described as:

STEP1: Generate all the 4536 unique numbers and store them in a list.

STEP2: Check if user is ready with the number. If ‘yes’ continue else ‘wait’

STEP3: Respond the first number in the list(Response) to user as the guess.

STEP4: Get the user feedback (number of bulls and cows).

STEP5: Compare the Response through each number in the list and generate the matches (Bulls and Cows).

STEP6: If the matches generated is same as the user matches,

store them in a new list,

else discard the number from the list.

STEP7: Update the list and continue STEP3, until Bulls = 4.

The Algorithm, when tested guesses the number with 5 – 6 moves.

A python implementation of the Algorithm is provided along.

Conclusion

Algorithms drive computers into placing our satellites in orbits, route our communications world-wide, they brought to life Facebook, YouTube, Google and innumerable other computer applications. They still drive the need to invent the Next computing systems.

Developing and implementing algorithms is a key skill required by anyone to be part of this digital revolution. As computer scientists and Technologists world-wide are thriving to make computers as simple as possible for anyone to program and implement their ideas,

What will you make?

Advertisement


6 COMMENTS

SHARE YOUR THOUGHTS & COMMENTS

Please enter your comment!
Please enter your name here