Java Succinctly® Part 1
CHAPTER 9
Example Programs and Conclusion
Our final chapter provides two case studies—Nim and the 3x+1 program. Each consists of complete, useful, and interesting programs that we can create with only minimal understanding of Java. The main difficulty in learning a computer language is gaining the skills to put together the mechanisms of the language into a coherent program. Finding complete, useful programs that only use the smallest subset of the mechanisms of a language is not easy. But the two examples in this chapter show that we do not need anything more than what we have seen so far—we can already create very useful programs.
In fact, while the game of Nim is a bit of fun, the 3x+1 program illustrates that we are already capable of exploring some of the most difficult unsolved problems known in mathematics and computer science. We might know only a tiny portion of Java, but the power that this language gives us is already extraordinary.
I have purposely left out the object-oriented mechanisms we looked at in the previous chapter. Object-oriented programming comes into its own when we look at polymorphism, which we will cover in Java Succinctly Part 2.
The game of Nim
The game presented here is a version of a simple and popular strategy game called Nim (for more on variants of Nim, visit https://en.wikipedia.org/wiki/Nim). You’ll find a collection of sticks (the number begins at 37 in the program), and players take turns (beginning with the human player) to take one, two, or three sticks from the collection, reducing the collection of sticks for the next player. The objective of the game is to take the final stick.
A fun question might be—is there a strategy for beating the computer every time?
(Hint: Yes, there is! Upon careful inspection of the way the computer selects its moves, you might be able to discover how to win against the computer every time.)
Code Listing 9.0: Nim Source Code
import java.util.Scanner; public class MainClass { public static void main(String[] args) { // Declare local variables. Scanner scanner = new Scanner(System.in); // For reading input. String playerInput = ""; // Variable for reading player input. int sticks = 37; // Current number of sticks left. // Print some instructions: System.out.println("Remove 1, 2 or 3 sticks from a pile."); System.out.println("The player who takes the final stick"); System.out.println("is the winner!"); // Main game loop: while(true) { // Tell the user how many sticks are left, and print a prompt. System.out.println("There are " + sticks + " left. "); System.out.print("How many would you like to take? "); // Read the user's input. playerInput = scanner.nextLine(); // Subtract the number of sticks the player chose: if(playerInput.equals("1")) sticks--; else if(playerInput.equals("2")) sticks-=2; else if(playerInput.equals("3")) sticks-=3; // If they did not select 1, 2 or 3, ask them to select again: else { System.out.println ("You can only take 1, 2, or 3 sticks...\n"); continue; } // Did the player win? if(sticks == 0) { System.out.println("You took the last stick, you win!"); break; } // If the player did not win, it's the computer's turn: if(sticks % 4 != 0) { // Print the player's and the computer's moves. System.out.println ("Ok, you take " + playerInput + ", I'll take " + (sticks % 4) + "."); // Subtract the computer's move from the pile: sticks -= (sticks % 4); } else { // We have lost unless the player makes a mistake! // Select a random number of sticks to subtract: int take = (int)(Math.random() * 3.0) + 1; // Print out the player's and computer's moves. System.out.println ("Ok, you take " + playerInput + ", I'll take " + take + "."); // Subtract the computer's move from the pile: sticks-=take; } // If the computer just took the last stick, the player loses! if(sticks == 0) { System.out.println("I took the last stick, I win!"); break; } } } } |
The program uses many of the ideas we’ve seen before, including Math.random(). Recall that Math.random() produces a pseudorandom number in the range from 0.0 up to but not including 1.0. The number generated is a double, so it could be something like 0.266787623 or 0.898898276. If we multiply the double by 3.0, we will get a random number in the range from 0.0 up to (but not including) 3.0. And recall that when we cast a double to an integer, the digits right of the decimal are discarded. Thus, when we convert our double to int, we will get a random integer 0, 1, or 2. And when we add 1 to this value, our integer will be 1, 2, or 3. Thus, when it is the computer’s turn and the computer determines that it has already lost, it will select a random number of sticks in an attempt to throw off the player.
3x+1 program
Java is a big language, and we have only scratched the surface, but the reality is this—even beginner computer programmers have a rare power at their fingertips. In this section, we will look at a small program that might be employed by a mathematician to write a journal paper. We will explore one of the many unsolved problems in mathematics and examine how easy it is to explore such fascinating worlds of thought with minimal Java syntax.
The 3x+1 problem is a famous unsolved mathematical conjecture. It is a question relating to a simple game involving integers. The game is as follows:
Starting with a positive integer x, we must perform the following:
If x is even, divide it by 2.
If x is odd, multiply it by 3 and add 1.
Repeat the above steps until x reaches the number 1.
For example, if x begins as 7:
7 is odd, multiply by 3 and increment to get x = 22.
22 is even, divide it by 2 to get x = 11.
11 is odd, multiply by 3 and increment to get x = 34.
34 is even, divide it by 2 to get x = 17.
17 is odd, multiply by 3 and increment to get x = 52.
52 is even, divide it by 2 to get x = 26.
26 is even, divide it by 2 to get x = 13.
13 is odd, multiply by 3 and increment to get x = 40.
40 is even, divide it by 2 to get x = 20.
20 is even, divide it by 2 to get x = 10.
10 is even, divide it by 2 to get x = 5.
5 is odd, multiply by 3 and increment to get x = 16.
16 is even, divide it by 2 to get x = 8.
8 is even, divide it by 2 to get x = 4.
4 is even, divide it by 2 to get x = 2.
2 is even, divide it by 2 to get x = 1.
At this point, the value of x is 1, and the series for x = 7 terminates. We could continue the sequence even after we reach 1, but the value of x begins to loop through the sequence 1, 4, 2, 1, 4, 2… and never stops.
This game is very simple, but it brings up a question that has thus far thwarted all attempts at answering: Are there any starting values for x that do not lead to 1? That is: Could we set x to some positive integer so that it forms some other loop that does not involve 1, or so that the values of x do not loop but increase toward infinity with no boundary?
At present, the answer to the preceding question is not known. Mathematicians state this question as a conjecture (i.e. an unproven statement): There are no starting values for x that do not lead to 1. For more information, visit the Wikipedia page on the Collatz conjecture: https://en.wikipedia.org/wiki/Collatz_conjecture).
The following program asks the user for an integer. It proceeds to play the 3x+1 game until it reaches the number 1. At that point, it tells the user how many iterations were required to get to the number 1 from the starting point, and it also prints out the largest value that x reached before receding to 1.
Code Listing 9.1: 3x+1 Program
import java.util.Scanner; public class MainClass { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String userInput = ""; // User's input string. int x; // The value of userInput converted to int. int iterations = 0;// Iterations to reach 1. int largest = 0; // Largest value reached in computation. while(true) { System.out.println("Enter a number, or 'Q' to quit: "); userInput = scanner.nextLine().toLowerCase(); // Allow the user to quit: if(userInput.equals("q")) break; x = Integer.parseInt(userInput); largest = 0; for(iterations = 0; ; iterations++) { // If x is even, halve it: if(x % 2 == 0) x /= 2; // Otherwise, x is odd, mul by 3 and increment. else x = (3 * x) + 1; // Make sure we do not overflow the int: if(x <= 0) { System.out.println( "Overflow detected, use long for more range..."); break; } // If x is > than largest, record new record: if(largest < x) largest = x; // If we find 1, we're done: if(x == 1) break; } System.out.println("Reached 1 after " + iterations + " iterations. Largest point reached: " + largest + "."); } } } |
In Code Listing 9.1, I have selected to use int for the main data type of the variable x. We could extend the range of our program by using long, or even BigInteger, if we wanted. Because I have used int, the range that we can test is quite small (limited to about 231/3), but it offers a good demonstration of how simple it is to create a genuinely useful and interesting application.
Challenges
Challenge 9.0 Is there any x value that does not reach 1?
Challenge 9.1 What is the pattern for the number of iterations as x increases?
Challenge 9.2 Is there some easy formula for predicting the number of iterations a given x value will take before it reaches 1, without actually playing through the 3x+1 game?
Challenge 9.3 Why does this simple game lead to such difficult questions?
The answers to these questions are unknown. Have fun exploring!
- 1800+ high-performance UI components.
- Includes popular controls such as Grid, Chart, Scheduler, and more.
- 24x5 unlimited support by developers.