Question

Linked List Outlab

Political RiffRaff Manager

General Overview

In case you missed it we just had an election and America is very divided I have decided you will write a program to select our politicians that take office in a fair and just way. We just went through a year of all the slimy politicians, and all the political supporters on both sides of the aisle coming out of the woodwork spouting their verbal abuse on each other. And even though the election is over the attacks and bitterness hasn't ended. Both sides are claiming "election foul".

You are going to fix it.  

 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...........very loosely adapted. 

Purpose

The purpose of the assignment is to give you experience implementing a circular, doubly linked list and all the methods and management that is needed for such a list. 

Problem Statement

In a serious attempt to downsize (reduce) the riffRaff in politics, The New Rhinoceros Party with the motto "we promise to keep none of our promises." has decided on the following strategy. Every day all Rhino applicants will be placed in a large circle, facing inwards. Someone is arbitrarily chosen as number 1, and the rest are numbered up to N (so N is the amount of candidates in the circle and N will be standing next to 1  as the end of the potential candidates).

Now you will have two officials that will be the selectors, selector one holds a number we will call k, official two has a number we will call m. Selector k will start at candidate 1 (first candidate) and will move around the circle of candidates clockwise counting off candidates until it counts k candidates and then stop pointing at the k^th candidate.

Selector m will start at candidate N (last candidate) and will move around the circle of candidates counter-clockwise counting off candidates until it gets to the m^thcandidate. 

Now one of two things will have taken place, the selectors will be pointing at two different candidates, or they will be pointing at the same candidate. If the selectors are pointing to two different candidates we will remove the candidates from the circle of candidates (these candidates will be ELIMINATED), starting with k candidate first and then the m candidate. The k selector will need to move clockwise up to the next available candidate and prepare to start counting again. The m selector will do the same but it will always move counter-clockwise. After removal the two selectors will need to be ready to start counting again at the next available candidate.  

If both selectors stop and they are pointing to the same candidate we have found ourselves a worthy candidate that will be put into political office.......keep this candidate off to the side, but remove the candidate from the circle of candidates.......which means k selector will need to be moved clockwise to next available and m selector will need to be moved counterclockwise to the next available candidate. 

Each selector 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 political retraining. Each set of three numbers will be on a separate line and the end of data will be signaled by three zeroes (0 0 0).

Here is a sample input file:

10 4 3
17 6 4
0 0 0

Output Requirements

The output should be sent to a file named LinkedListProgram.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 an 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

(Note: There seems to be an error in either the output or the instructions, because I cannot get get this exact output from the instructions given. Editing the code to make it match the output is fine.)

Requirements and Grading

12 points. You are required to design and implement your own linked list (in the style of what we have done in lecture this week) as opposed to using a built-in class provided by Java. The class you use should be doubly-linked (6 points), circular (3 point) and if it works of course(3 point).12 points. The program finds the correct answer. Your TA will test your program on some sample files after the assignment is due. Thus, please test your program thoroughly before submitting it.6 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 LinkedListProgram.txt5 points. The program's output matches the required output format described above.10 points. The program uses good style. This includes factors such as appropriate commenting, good object oriented design, readable code that is high quality, etc.

Answer 1

Driver.java

import java.io.FileNotFoundException;
import java.io.UnsupportedEncodingException;

public class Driver {

   public static void main(String[] args) throws UnsupportedEncodingException, FileNotFoundException {
       // TODO Auto-generated method stub
       RiffRaff riff = new RiffRaff();
       riff.readIn();
   }

}

RiffRaff.java

import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import java.util.*;

public class RiffRaff {
   PrintWriter writer;
   Scanner scanner = new Scanner(System.in);
   String inFile;
   int line; // what line we are currently reading in

   public void readIn() throws UnsupportedEncodingException, FileNotFoundException { // Reads in the
                                                               // N,K, and M
                                                               // values
       writer = new PrintWriter("LinkedListProgram.txt", "UTF-8");
       System.out.println("What file would you like to use as the input file (Example: input.txt)");
       inFile = scanner.nextLine();
       try {
           // open the file that the user inputs
           FileReader fileName = new FileReader(inFile);
           Scanner fileRead = new Scanner(fileName);
           int sum = 1;
           int n, k, m;
           n = 1;
           k = 1;
           m = 1;
           while (sum != 0) {
               sum = 0;
               n = fileRead.nextInt();
               k = fileRead.nextInt();
               m = fileRead.nextInt();
               sum = n + k + m;
               CircleLinkedList LL = new CircleLinkedList(n,writer);
               if (sum != 0) { // Calls the linked list method if the sum is
                               // not 0 (its not the end of the file)
                   System.out.println(n + " " + k + " " + m);
                   LL.candidateSelection(n, k, m);
               }else{
                   LL.closeWriter();
               }
           }
           fileRead.close();
       } catch (FileNotFoundException exception) {
           // error is thrown if file cannot be found. See directions or email
           // me...
           System.out.println("File Not Found!");
       }
       System.out.println("Done");
   }

}

CircleLinkedList.java

import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;

public class CircleLinkedList {
   Node first = new Node(1);
   Node current = first;
   Node last = first;
   int candidates;
   PrintWriter writer;

   public CircleLinkedList(int n, PrintWriter inWriter) throws FileNotFoundException, UnsupportedEncodingException { // Constructs
                                                                                               // the
                                                                                               // circular
                                                                                               // doubly
                                                                                               // linked
       // list with N nodes
       writer = inWriter;
       for (int x = 2; x <= n; x++) {
           addItem(x);
       }
       candidates = n;
   }

   public void addItem(int inPol) { // adds an item to the end of the doubly
                                       // linked list
       Node temp = new Node(inPol);
       last.setNext(temp);
       temp.setPrev(last);
       temp.setNext(first); // Creates a circularly linked list
       last = temp;
       first.setPrev(last);
   }

   public void deleteItem(int pol) { // Deletes an item with the politician
                                       // value of the parameter
       current = first;
       if (first.getNext() != null) {
           while (pol != current.getPol()) {
               current = current.getNext();
           }
           if (current.getPol() == last.getPol()) {
               last = current.getPrev();
               current.getPrev().setNext(first);
           }
           if (current.getPol() == first.getPol()) {
               first = current.getNext();
               current.getNext().setPrev(last);
               ;
           }
           current.getPrev().setNext(current.getNext());
           current.getNext().setPrev(current.getPrev());

       } else {
           first = null;
           last = null;
       }
       candidates -= 1;
   }

   public int getCandidates() {
       return candidates;
   }
   public void closeWriter(){ //Closes the file writer
       writer.close();
   }
   // Carries out the candidate selection process
   public void candidateSelection(int n, int k, int m) {
       Node selectorK, selectorM;
       selectorK = first;
       selectorM = last;
       System.out.println("Selcector k: " + selectorK.getPol());
       System.out.println("Selcector m: " + selectorM.getPol());
       if (m == 0) {
           m = 1;
       }
       if (m > n) {
           m = m % n;
       }
       int counter = 0;
       while (candidates >= 0) {
           counter += 1;
           for (int x = 1; x < k; x++) { // Selector k : Selector k will start
                                           // at
                                           // candidate 1 (first candidate) and
                                           // will move around the circle of
                                           // candidates clockwise counting off
                                           // candidates until it counts k
                                           // candidates and then stop pointing
                                           // at
                                           // the kth candidate.
               selectorK = selectorK.getNext();
           }
           for (int x = n; x > (n-m); x--) {
               selectorM = selectorM.getPrev();
           }
           if (selectorK.getPol() == selectorM.getPol()) {
               System.out.println("Test: " + selectorK.getPol());
               writer.println(selectorK.getPol());
               deleteItem(selectorK.getPol());
           } else {
               System.out.println(counter);
               System.out.println("Test: " + selectorM.getPol() + " " + selectorK.getPol());
               writer.println(selectorM.getPol() + " " + selectorK.getPol());
               deleteItem(selectorK.getPol());
               deleteItem(selectorM.getPol());
           }

       }
   }

}

Node.java

public class Node {
   private int politician;
   protected Node next;
   protected Node previous;
   public Node(int polNum){
       politician = polNum;
      
   }
   public void setNext(Node n){
       next = n;
   }
   public Node getNext(){
       return next;
   }
   public void setPrev(Node n){
       previous = n;
   }
   public Node getPrev(){
       return previous;
   }
   public int getPol(){
       return politician;
   }
}

LinkedListProgram.txt

7 4
3 8
10 1
5 6
2 9
2
13 6
9 11
4 17
16 7
10 15
2 8
5
12
3 1
14
14

input.txt

10 4 3
17 6 4
0 0 0