Program 5: Queues

Due Date

This assignment is due at the beginning of your lab period on Thursday, April 29th.

Partners

You may work with at most one other person on this assignment. Your partner must be in the same lab section as yourself. Please review the class collaboration policy (available off of the main CS 221 page) so that you know what is and what isn't allowed.

Purpose

The purpose of this program is to introduce you to queues and to develop your problem solving skills. You will also have to implement an appropriate sorting technique for the problem.

Number Chains

Given a number, we can form a number chain by

1. arranging its digits in descending order
2. arranging its digits in ascending order
3. subtracting the number obtained in (2) from the number obtained in (1) to form a new number
4. and repeat these steps unless the new number has already appeared in the chain

Note that 0 is a permitted digit. The number of distinct numbers in the chain is the length of the chain. You are to write a program that reads numbers and outputs the number chain and the length of that chain for each number read.

The input consists of a sequence of positive numbers, all less than 10^9, each on its own line, terminated by 0. The input file contains at most 10 numbers.

The output consists of the number chains generated by the input numbers, followed by their lengths exactly in the format indicated below. After each number chain and chain length, including the last one, there should be a blank line. No chain will contain more than 1000 distinct numbers.

Sample Input

123456789
1234
444
0

Sample Output

Original number was 123456789
987654321 - 123456789 = 864197532
987654321 - 123456789 = 864197532
Chain length 2

Original number was 1234
4321 - 1234 = 3087
8730 - 378 = 8352
8532 - 2358 = 6174
7641 - 1467 = 6174
Chain length 4

Original number was 444
444 - 444 = 0
0 - 0 = 0
Chain length 2

General Requirements

• The data should be read from a file named program5.dat. It will appear in the same format as the Sample Input section above.
• Create a Queue class that extends java.util.LinkedList and behaves like a queue ADT. This class should be utilized to hold each number in the number chain.

What to Submit

1. A disk with your code on it. This is important as your program will be tested in lab on Thursday, April 29th.
2. A printout of the source code that you write.
3. A printout of the output that your program produces when it is run on the Sample Input above.

Grading

• 60% Correctness.
• 20% Good Design.
• 10% Good Code.
• 10% Good Style (including Javadoc comments).