Program 4

Dole Manager

due Thursday, April 6^th by the start of lab

Test Data - Released After Assignment Due

10 4 3
99 1 1
50 5 6
50 50000 60000
1 17 16
0 0 0

Lab Partners

Everyone is encouraged to work with one lab partner (who is in the same lab section as yourself) on this assignment. If you do work with a partner, submit one solution with both of your names on it. Also, please look at the class collaboration policy so that you know what is and what isn't allowed.

General Overview

Every year ACM sponsors programming competitions at the local, regional and world levels. This assignment is adapted from a problem that appeared at one of these competitions.

Purpose

The purpose of the assignment is to give you experience implementing a circular, doubly linked list that contains a dummy header node.

Problem Statement

In a serious attempt to downsize (reduce) the dole line, The New National Green Labour Rhinoceros Party has decided on the following strategy. Every day all dole applicants will be placed in a large circle, facing inwards. Someone is arbitrarily chosen as number 1, and the rest are numbered counter-clockwise up to N (who will be standing on 1's left). Starting from 1 and moving counter-clockwise, one labour official counts off k applicants, while another official starts from N and moves clockwise, counting m applicants. The two who are chosen are then sent off for retraining; if both officials pick the same person she (he) is sent off to become a politician. Each official then starts counting again at the next available person and the process continues until no-one is left. Note that the two victims (sorry, trainees) leave the ring simultaneously, so it is possible for one official to count a person already selected by the other official.

Input File Format

Write a program that asks the user for the name of a valid input file. If the file exists, the program should read in (in that order) the three numbers (N, k and m; k, m > 0, 0 < N < 100) and determine the order in which the applicants are sent off for retraining. Each set of three numbers will be on a separate line and the end of data will be signalled by three zeroes (0 0 0).

Here is a sample input file:

10 4 3
0 0 0

Output Requirements

The output should be sent to a file named program4.txt. For each input, the output should show the order in which the people are chosen. For each round in which two different people are chosen, list the person chosen by the counter-clockwise official first.

Here is the required output for the above input file:

Program 4
---------

N = 10, k = 4, m = 3

Output
------
4 8
9 5
3 1
2 6
10 
7

End of Program 4

Requirements and Grading

30 points. You are required to design and implement your own linked list (in the style of what we did in lecture on March 22) as opposed to using a built-in class provided by Java. The class you use should be doubly-linked (20 points), circular (5 points) and contain a dummy header node (5 points).
30 points. The program finds the correct answer. The TAs will test your program on some sample files that John will provide to them after the assignment is due. Thus, please test your program thoroughly before submitting it.
10 points. The program finds the solution in a reasonably efficient manner. For example, if N = 10, k = 1 and m = 450, the m judge should not circle around the candidates needlessly.
5 points. The program sends it output to a file named program4.txt
5 points. The program's output matches the required output format described above.
20 points. The program uses good style. This includes factors such as appropriate commenting (including Javadoc), good object oriented design, readable code that is high quality, etc.

What to Submit

E-mail your code to your lab TA in one message. The subject of the message should be: CS221-xx program4 your-names. The xx is the number of your lab section. Your lab TA must receive your e-mail by the start of your lab period on the date on which the assignment is due. Otherwise there will be a 25 point per day late penalty.