Java Console Programming - Master Mind

Related article

• How to redirect System.out ?
• How to log console output ?
• Logging console output with Exception
  - a console logger with Swing GUI is shown
  
• Tetris from Scratch
  - illustrate the use of bottom up design approach
  

The Game Of Master Mind

I found the following "functional spec" in programmingforums.org.

We will implement this game with a top down design approach.


Mastermind Game

You are to write a program that generates a secret code at random and let the human player guess this code. Each time the player inputs his guess, the program responds with a score that reflects how close or far the player's guess is from the secret code.

To make the game interesting, this secret code is made up of animals. There are 12 animals to choose from, namely: Ant, Bear, Cat, Dog, Emu, Goat, Lizard, Monkey, Parrot, Rabbit, Snake, and Tiger.

Upon start, the program chooses a code, which is 4 randomly selected animals. The program cannot select the same animal more than once in the code. So the 4 animals are all different from each other.

Examples of valid codes:
[ Tiger, Snake, Monkey, Rabbit ]
[ Monkey, Parrot, Snake, Ant ]

Examples of invalid codes:
Reason
[ Ant, Cat, Monkey, Ant ] Ant selected twice
[ Rabbit, Monkey, Snake ] Code must be 4 animals

Scoring:
The objective of the game is for the player to guess the 4 animals, with the least number of attempts. The program has two levels of difficulty. In the low difficulty setting, the player has to guess the 4 animals but not necessarily in the same order.

For example, if the secret code is [Cat, Dog, Ant, Tiger] and the player
guesses [Dog, Tiger, Ant, Cat], the guess will be considered correct.

In the low difficulty setting, the program takes the input guess and finds out which animals in the input matches with those on the code. The score is the number of correct animals. Obviously, if the score is 4, the player wins and the program ends. Here are some examples:

Secret Code: [ Cat, Dog, Ant, Tiger ]
Guess: [ Ant, Rabbit, Monkey, Snake ] Score is 1 (Ant matches)
Guess: [ Rabbit, Ant, Dog, Snake ] Score is 2 (Ant and Dog)
Guess: [ Dog, Tiger, Ant, Cat ] Score is 4 (Player wins)

In the high difficulty setting, the player has to guess the 4 animals and also the positions of each animal. In the third guess above, notice that only "Ant" is guessed correctly at the right position (i.e., third position). In this level, the program outputs two numbers for the score: (a) number of correct animals; and (b) number of
correct animals in the correct position. Study the examples below. Note the computer-generated scores for (a) and (b) are shown on the right side.

Secret Code: [ Cat, Dog, Ant, Tiger ]
Computer Outputs Score
Guess: [ Rabbit, Ant, Dog, Snake ] (a) is 2 (b) is 0
Guess: [ Cat, Ant, Dog, Snake ] (a) is 3 (b) is 1
Guess: [ Cat, Dog, Ant, Snake ] (a) is 3 (b) is 3
Guess: [ Cat, Dog, Ant, Tiger ] (a) is 4 (b) is 4

Obviously, the required score to win is 4 for both (a) and (b). Only then does the program terminate.

Below is a list of specific requirements that your program must satisfy.
1. Your program should use the time() function to seed the random number generator. This will make the program select different codes each time it is executed. Study how to use this with srandom() function.
2. The required input format for each guess is 4 characters. Notice that the 12 animals have different starting characters. Use the first character of each animal as a means to identify it. For example, an input
of "CDAT" means [Cat, Dog, Ant, Tiger]. This makes it unnecessary to use "Ant", "Tiger", etc. for input.
3. Your program must also validate the input. Here are some examples of invalid inputs:
Input Reason Error Message
CDAA A is repeated "Repeated Animal"
SADQ Q is not a valid animal "Invalid Animal"
Use the error messages above when an invalid user input is encountered.


Design

This is a good example of console programming that implements something interesting.

We will use System.in for reading input, System.out for printing output.

There is a java.io.Console class which is available after JDK 1.5, but we won't use this class anyway.

Top down Approach

We will implement the game using the top-down approach. First of all, let's define the flow in the main() method.



Now we are going to fill the above methods one by one. A good starting point is to define the game flow first. Hence the first method I choose to fill is game(). Since the function names used below are self-documentary, the game flow should be easy to understand.

Quick Prototyping

Now we are going to create a first version that doesn't have compilation error. We will create empty functions if necessary.





Now we have a completed prototype, compile it, and run it. It doesn't do anything meaningful right now. But it is a good starting point. Once all the empty functions are filled, we have a fully working game.

Shuffle()

There are quite a few empty methods to be implemented. What should be next ?. There are many reasonable choices. I would choose shuffle() to generate a secret code. Before writing the method, we need to define data structure to hold the animal names and the animal codes(the first letter).






Once we have the data structure ready, we can generate the secretCode, which stands for the 4 randomly picked animals. We are going to use the Knuth Shuffling algorithm to randomize the permutation array. Then use the first 4 index in the permutation to pick 4 animals.

displaySolution()

Now we want to check our shuffe() method, therefore the next reasonable method to implement is displaySolution()



Now it is time to recompile and run MasterMind.java. It will display 4 randomly picked animals every time you run the program.

getPlayeGuess() - getting input from user

Up to now the program is not interactive. We are going to enable the input function right now.



The above method call two auxiliary methods,getInputLine() and validateInput().

getInputLine() - reading from System.in

It simply reads a line from System.in. Implementation follows :

validateInput()

When the user enter a guess, we must validate it.




The above method introduces another auxiliary method, getAnimalIndex(), which would return -1 if the character is not a valid animal, otherwise it would return a index to the array of animals. This function is very simple, it is just a single line method.



Now you may compile and run the program again. You may test the program with the following input. The blue part is input by player. The program will quit whenever a valid input is read.


Animal Code : ABCDEGLMPRST
Enter your guess : abcde
Must enter 4 letters
Animal Code : ABCDEGLMPRST
Enter your guess : abcx
Invalid Animal
Animal Code : ABCDEGLMPRST
Enter your guess : abcc
Repeated Animal.
Animal Code : ABCDEGLMPRST
Enter your guess : abcd
Congratulations ! The solution is :
[Snake, Bear, Ant, Emu]


setDifficulty()

At this point, we have the input validation method ready. The next reasonable step is to calculate and display the score for each guess. However, since the game provides two difficulty settings, which would affect the score calculation method, we must first implement the setDifficulty() method.

calculateScore()

We may now implement calculateScore().




And of course we must display the calculated score, hence the next method would be displayScore()

displayScore()

At this point we have already completed the whole game flow. You may compile and play the game now. We are still missing the replay() method, which asks the player to play another game or not after a successful guess. But it doesn't affect the whole game flow. The method replay() will be implemented in the full source anyway.

Full Source

Conclusion

This article demonstrated how to convert a functional specification into a running program, using a top down design approach. To see example of bottom-up design, read this article :Tetris from Scratch

The Game of TextTwist

Related Articles

1. Permutation Generator
2. Combination Generator

Introduction

The game of text twist is a game of finding words from a given set of letters. For example, you are given the following 6 letters :

["F","O","C","I","E","F"]

And your tasks is to find out all possible words by selecting subsets of the letters. The solution would be :

[ "ICE","OFF","FOE","FOCI","OFFICE" ]

You may compile and play the game to have a better understanding. Source code will be given at the end of this article.

Dictionary

To generate the problem and the solutions, you need a dictionary file. First, select a 6-letters word from the dictionary file. For example, let's choose the word "ABSENT".

Now we have 6 letters, ["A","B","S","E","N","T"]. To create the problem, we shuffle those letters to form a random arrangement. For example :

["S","A","E","B","N","T"]

Now we can generate all combinations and permutations from the set of letters, and check it against the dictionary file again. If it is in the dictionary, then it is part of the solution.
Depending on your dictionary file, possible solution of the above problem would be :

[SEA, SAT, EST, SET, TEA, ATE, EAT, BAN, TAB, BAT, TAN, ANT, BEN, BET, TEN, NET,
BASE, SANE, EATS, EAST, SEAT, BANS, BATS, TABS, STAB, ANTS, BETS, BEST, NETS, TENS,
NEST, SENT, BANE, BEAN, BETA, BATE, BEAT, NEAT, BENT, BEANS, BEATS, BATES, BASTE,
BEAST, ABSENT]


Collection of Problems

We have seen two sample problems so far :

["F","O","C","I","E","F"]
["S","A","E","B","N","T"]

We can easily generate more problems and form a collections. Then we can save all the problems in a class file, such as :

GUI Control

Once we have the problem collections, we can pick a problem at random and start the game. For simplicity, the sample below will use a hard-coded problem instead of really picking one from the Problem class. It is because I want to focus on the GUI control on the game. So you will see the following declaration at the very beginning of TextTwist.java


We will use standard SWING components such as JButton and JLabel. The code should be straight forward enough to be understood. Of course, you should first compile and run it before reading the code. The program flow is best documented by running the program yourself.

External Link

I have created a C# version in programmingforums.org

For those who are interested may visit there to have a look.

Combination Generator

Related Articles

• Permutation Generator

Introduction

Roughly speaking, a combination is a selection of letters inside a String. For example, consider the String "abcde". We want to select 3 letters out of it. How many combinations do we have ?
Answer : 10. The full list is :

["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]

Divide and Conquer

We can keep breaking down the problem into smaller sub-problems, until the sub-problems have obvious solution. This technique of problem solving is known as "divide and conquer".



Problem : Find all 3-letters combinations from "abcde"
Sub-problems :

1. Find the combination that contains the letter "a"
2. Find the combination that doesn't contains the letter "a"

The second sub-problem is identical to :

Find all 3-letters combinations from "bcde", that would produce the list :

["bcd","bce","bde","cde"]

And the first sub-problem is identical to :
Find all 2-letters combinations from "bcde", then add an "a" in front of each combination

Let's write it in details :

all 2-letters combinations of "bcde" = ["bc","bd","be","cd","ce","de"]
add an "a" in front of each of them = ["abc","abd","abe","acd","ace","ade"]

Combining two sub-problems will give the full solutions :

["abc","abd","abe","acd","ace","ade"] + ["bcd","bce","bde","cde"]
=["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]

Implementation

A recursive implementation follows directly from the above algorithm.

Runnable Demonstration

Trace

You may skip this section if you feel you understand the algorithm well enough.

We will trace a smaller problem, find all 3-letters combination from "abcd"

Level 1 expand, divide into 2 sub-problems
combination("","abcd",3)
  1. combination("a","bcd",2)
  2. combination("" ,"bcd",3)

Level 2 expand
combination("","abcd",3)
  1. combination("a","bcd",2)
    1.1 combination("ab","cd",1)
    1.2 combination("a" ,"cd",2)
  2. combination("","bcd",3)
    2.1 combination("b","cd",2)
    2.2 combination("" ,"cd",3) // dead end, cannot pick 3 letters from tail "cd"

Level 3 expand
combination("","abcd",3)
  1. combination("a","bcd",2)
    1.1 combination("ab","cd",1)
      1.1.1 combination("abc","d",0)   // k=0, print "abc"
      1.1.2 combination("ab" ,"d",1)
    1.2 combination("a","cd",2)
      1.2.1 combination("ac","d",1)
      1.2.2 combination("a" ,"d",2)  // dead end, cannot pick 2 letters from tail "d"
  2. combination("","bcd",3)
    2.1 combination("b","cd",2)
      2.1.1 combination("bc","d",1)
      2.1.2 combination("b" ,"d",2)  // dead end, cannot pick 2 letters from tail "d"
    2.2 combination("" ,"cd",3) // dead end, cannot pick 3 letters from tail "cd"

Level 4 expand
combination("","abcd",3)
  1. combination("a","bcd",2)
    1.1 combination("ab","cd",1)
      1.1.1 combination("abc","d",0)   // k=0, print "abc"
      1.1.2 combination("ab" ,"d",1)
        1.1.2.1 combination("abd","",0) // k=0, print "abd"
        1.1.2.2 combination("ab" ,"",1) // dead end, cannot pick 1 letter from tail ""
    1.2 combination("a","cd",2)
      1.2.1 combination("ac","d",1)
        1.2.1.1 combination("acd","",0) // k=0, print "acd"
        1.2.1.2 combination("ac" ,"",1) // dead end, cannot pick 1 letter from tail ""
      1.2.2 combination("a" ,"d",2)  // dead end, cannot pick 2 letters from tail "d"
  2. combination("","bcd",3)
    2.1 combination("b","cd",2)
      2.1.1 combination("bc","d",1)
        2.1.1.1 combination("bcd","",0) // k=0, print "bcd"
        2.1.1.2 combination("bc" ,"",1) // dead end, cannot pick 1 letter from tail ""
      2.1.2 combination("b" ,"d",2)  // dead end, cannot pick 2 letters from tail "d"
    2.2 combination("" ,"cd",3) // dead end, cannot pick 3 letters from tail "cd"

Permutation Generator

Related Articles

• Combination Generator

Introduction

What is permutation ? For a String, it is just a rearrangement of letters.
For example, consider the String "abc", the list all permutations would be :

["abc","acb","bac","bca","cab","cba"]

Algorithm

There are many algorithms to generate permutation systematically. But not all of them are easily understandable. Instead of presenting the most efficient way of permutation generation, I am going to present a simple one that is straight forward.

Consider the String "abc" again. We can choose any letter to start in our permutation, so let's choose the letter "a". Now the problem reduced to finding all permutations of "bc", which is an obvious problem, the permutation list of "bc" is just ["bc","cb"].

Since the permutation can be started with any letter, we arrive at the following algorithm :

Steps to find : permutation("abc")

1. fix "a" and find permutation("bc")
2. fix "b" and find permutation("ac")
3. fix "c" and find permutation("ab")

We can extends it to find permutation of 4 letters

Steps to find : permutation("abcd")

1. fix "a" and find permutation("bcd")
2. fix "b" and find permutation("acd")
3. fix "c" and find permutation("abd")
4. fix "d" and find permutation("abc")

This naturally leads to a recursive algorithm

Demonstration

As usual, I would provide a full runnable demo in my articles. Compile and run the following program :

Trace

Level 1 Expand
perm("","abc")  // head is emtpy and tail is "abc"
    perm("a","bc") // remove "a" from tail and append it to head
    perm("b","ac") // remove "b" from tail and append it to head
    perm("c","ab") // remove "c" from tail and append it to head

Level 2 Expand
perm("","abc")  // head is emtpy and tail is "abc"
    perm("a","bc") // remove "a" from tail and append it to head
        perm("ab","c")  // remove "b" from tail and append to head
        perm("ac","b")  // remove "c" from tail and append to head
    perm("b","ac") // remove "b" from tail and append it to head
        perm("ba","c")  // remove "a" from tail and append it to head
        perm("bc","a")  // remove "c" from tail and append it to head
    perm("c","ab") // remove "c" from tail and append it to head
        perm("ca","b")  // remove "a" from tail and append it to head
        perm("cb","a")  // remove "b" from tail and append it to head

Whenever the tail contains only one character, the recursion is terminated and a permutation will be printed. Hence the above trace result in 6 permutations :

["abc","acb","bac","bca","cab",cba"]

Character Queue - Quiz

The problem

A few days ago, I saw the following question in the programming forums.


Consider the queue (q) of characters where it is a straight queue which is allocated 8 characters:

Front=2 rear=5 q= -,-,A,B,C,-,-,-

(for notational convenience “-” is used to denote an empty cell)

The following operations have to be performed.

(i) D is added to the queue
(ii) Two characters are deleted from the queue
(iii) E and F are added to the queue
(iv) One character is deleted from the queue
(v) G and H are added to the queue

What are the intermediate correct front and rear values when the above operations are performed?

Choose at least one answer.

A. front=5, rear=8
B. front=3, rear=6
C. front=2, rear=6
D. front=4, rear=7
E. front=4, rear=6


Step by Step trace

The problem can be solved by a step by step trace. The first two steps is done below.
It is not difficult to derive the solution after a full trace is done.

index all the cells :
queue   : -,-,A,B,C,-,-,-
index   : 0,1,2,3,4,5,6,7
pointer :     F     R

Step (i) D is added to the queue
queue   : -,-,A,B,C,D,-,-
index   : 0,1,2,3,4,5,6,7
pointer :     F       R

Step (ii) Two characters are deleted from the queue
queue   : -,-,-,-,C,D,-,-
index   : 0,1,2,3,4,5,6,7
pointer :         F   R

Verify the answer

After deriving the solution, you may want to verify the answer. For such a simple problem, it is very easy to make a quick prototype. Compile and Run the program to verify your answer.

Digital Image Processing

Introduction

The techniques described in this article is used in The Game of Snake

Image format

Digital Image is a image that is encoded in some digital format. One of the simplest format for a digital image is an array of pixels. For example :




This is not a very obvious image pattern. But if we make manual highlight to the source code, the data format will become self-documentary.

int[] foodImage = {
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,1,1,1,1,0,0,1,1,0,0,
0,0,0,0,0,1,2,2,2,2,1,0,1,2,1,0,
0,0,0,0,1,1,1,1,1,2,2,1,1,2,1,0,
0,0,0,1,5,5,5,5,5,1,1,1,2,1,0,0,
0,0,1,5,5,6,6,5,1,2,2,2,1,0,0,0,
0,0,1,5,6,6,5,1,2,2,2,2,2,1,0,0,
0,1,5,5,5,5,5,1,1,1,2,2,1,2,1,0,
0,1,5,5,5,5,5,5,7,7,1,1,1,2,1,0,
0,1,7,5,5,5,7,7,7,5,3,3,1,2,1,0,
1,5,7,7,7,7,5,7,7,3,3,4,1,1,0,0,
1,3,7,5,7,7,7,3,4,3,3,3,3,1,0,0,
1,3,3,3,3,4,3,3,3,3,4,3,1,0,0,0,
1,3,4,3,3,3,3,4,3,3,1,1,0,0,0,0,
0,1,3,3,4,3,3,1,1,1,0,0,0,0,0,0,
0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0 
};

The above array actually represents the following image :

Why not use the Java Image object

Just because it hides too many implementation details. And because this article is for educational purpose. And because the pursuit of knowledge is a self-satisfactory act.

Drawing the Image Pixel by Pixel

In the above array, the value 0 is used to represent a black pixel, 1 to represent magenta, 2 to represent green, 3 to represent red, etc.

Hence we can create a color table to represent the color value :


This is known as palette graphics because the colors of the image are limited and they must come from a fixed palette.

Now we can create a nested for loop to draw the image pixel by pixel

Image Transformation

Typical transformation includes rotation and scaling. The generic way is to do matrix multiplications. However, for simple transformation, such as rotation by 90 degree, we can use simpler methods. Some examples of simple rotations will be described in this article.

Coordinate System

The image array consists of 16x16 = 256 pixels. It is a one dimensional array and the color of a pixel can be obtained by :

color = foodImage[i];

But what is the meaning of the array index ? Since the image contains 16 rows and 16 columns, we can index each row and column. The top row is row 0 and the bottom row is row 15. The leftmost column is column 0 and the rightmost column is column 15. Then to get the color of row 5 and column 6, we should write :

color = foodImage[5*16+6];

Or in general, if we know the row and column number, the color of a pixel is given by :

color = foodImage[row*W+column];

where W=16 is the width of the image.


Sometimes we wish to index the image by (x,y) coordinates. In our sample, the coordinates of the upper left corner is (0,0) and the lower right corner is (15,15). Note that a pixel with coordinates (x,y) means that it is located at row y and column x.

Hence, to get the color of pixel at (x,y), we write :

color = foodImage[y*W+x];

Simple Rotation

Upside down

It is not really a rotation but a vertically mirrored image
To create an upside down image of the original one. We may use the hard code method such as :

int[] upsideDownImage = {
0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,
0,1,3,3,4,3,3,1,1,1,0,0,0,0,0,0,
1,3,4,3,3,3,3,4,3,3,1,1,0,0,0,0,
1,3,3,3,3,4,3,3,3,3,4,3,1,0,0,0,
1,3,7,5,7,7,7,3,4,3,3,3,3,1,0,0,
1,5,7,7,7,7,5,7,7,3,3,4,1,1,0,0,
0,1,7,5,5,5,7,7,7,5,3,3,1,2,1,0,
0,1,5,5,5,5,5,5,7,7,1,1,1,2,1,0,
0,1,5,5,5,5,5,1,1,1,2,2,1,2,1,0,
0,0,1,5,6,6,5,1,2,2,2,2,2,1,0,0,
0,0,1,5,5,6,6,5,1,2,2,2,1,0,0,0,
0,0,0,1,5,5,5,5,5,1,1,1,2,1,0,0,
0,0,0,0,1,1,1,1,1,2,2,1,1,2,1,0,
0,0,0,0,0,1,2,2,2,2,1,0,1,2,1,0,
0,0,0,0,0,0,1,1,1,1,0,0,1,1,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 
};

Or we may write an automatic conversion routine :


To write the conversion routine, make the following observation :

The first row of the original image will become the last row of the transformed image.
The second row of the original image will become the second last row of the transformed image.
...

That means :

row 0 of the original image will become row 15 of the transformed image
row 1 of the original image will become row 14 of the transformed image
...

That means :

row n of the original image => row 16-n-1 of the transformed image

or in a more generic way :

row n of the original image => row H-1-n of the transformed image where H=16 is the height of the image.

That leads to the conversion routine is below :

Anti-clockwise Rotation by 90 degree

Just do the following transformation :

(x,y) => (y,15-x)

Or the more generic formula :

(x,y) => (y,W-1-x)

That is, for any point (x,y) in the original image, make it becomes (y,15-x) of the target image. The pseudo code is :

color <= sourceImage[(x,y)];
targetImage[(y,15-x)] <= color

Implementation :

Demonstration

To compile and run the demonstration :

javac ImagePanel.java
java ImagePanel

The Game of Snake - Part 1

Play the Game First

You need to have flash installed.
5 difficulty settings, 10 level layouts, Enjoy !

Source Code

You have just played the flash version of the game. Since this is a Java programming blog, the source code of the Java version will be provided at the end of this article. Of course it won't be compiled to a flash. Instead it will be compiled to a Java application. Nevertheless, the game control is identical to the flash version.

Compile and Run

javac Snake10.java
java Snake10

Adjusting difficulties

The Java version doesn't provide interface to adjust the game difficulty. However, as a programmer, you can do a little hack to the source code. Just locate the line :

int difficulty = 3;  // 1=hardest, 5=easiest

in the method gameLoop(). Change it to any value between 1 and 5.

Explanation of Source Code

Selected portions of the source code will be explained in subsequent articles.

Related Posts

• Tetris From Scratch
• Java Sound Programming
• Moving Object and Sprite Manager
• Digital Image Processing

Source Listing