In Java General Overview In case you missed it we just had an election and Ameri
ID: 3864574 • Letter: I
Question
In Java
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 kth 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 mth candidate.
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:
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:
Explanation / Answer
package cdl;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
/* Class Node */
class Node {
protected int data;
protected Node next, prev;
/* Constructor */
public Node() {
next = null;
prev = null;
data = 0;
}
/* Constructor */
public Node(int d, Node n, Node p) {
data = d;
next = n;
prev = p;
}
/* Function to set link to next node */
public void setLinkNext(Node n) {
next = n;
}
/* Function to set link to previous node */
public void setLinkPrev(Node p) {
prev = p;
}
/* Funtion to get link to next node */
public Node getLinkNext() {
return next;
}
/* Function to get link to previous node */
public Node getLinkPrev() {
return prev;
}
/* Function to set data to node */
public void setData(int d) {
data = d;
}
/* Function to get data from node */
public int getData() {
return data;
}
}
/* Class linkedList */
class linkedList {
protected Node start;
protected Node end;
public int size;
/* Constructor */
public linkedList() {
start = null;
end = null;
size = 0;
}
/* Function to check if list is empty */
public boolean isEmpty() {
return start == null;
}
/* Function to get size of list */
public int getSize() {
return size;
}
/* Function to insert element at begining */
public void insertAtStart(int val) {
Node nptr = new Node(val, null, null);
if (start == null) {
nptr.setLinkNext(nptr);
nptr.setLinkPrev(nptr);
start = nptr;
end = start;
} else {
nptr.setLinkPrev(end);
end.setLinkNext(nptr);
start.setLinkPrev(nptr);
nptr.setLinkNext(start);
start = nptr;
}
size++;
}
/* Function to insert element at end */
public void insertAtEnd(int val) {
Node nptr = new Node(val, null, null);
if (start == null) {
nptr.setLinkNext(nptr);
nptr.setLinkPrev(nptr);
start = nptr;
end = start;
} else {
nptr.setLinkPrev(end);
end.setLinkNext(nptr);
start.setLinkPrev(nptr);
nptr.setLinkNext(start);
end = nptr;
}
size++;
}
/* Function to insert element at position */
public void insertAtPos(int val, int pos) {
Node nptr = new Node(val, null, null);
if (pos == 1) {
insertAtStart(val);
return;
}
Node ptr = start;
for (int i = 2; i <= size; i++) {
if (i == pos) {
Node tmp = ptr.getLinkNext();
ptr.setLinkNext(nptr);
nptr.setLinkPrev(ptr);
nptr.setLinkNext(tmp);
tmp.setLinkPrev(nptr);
}
ptr = ptr.getLinkNext();
}
size++;
}
public int deleteNode(Node node) {
int pos = 1;
if(node.data == start.data){
return pos;
}
Node ptr = start.next;
while(ptr !=start){
pos++;
if(ptr.data == node.data){
return pos;
}
ptr = ptr.getLinkNext();
}
return -1;
}
/* Function to delete node at position */
public void deleteAtPos(int pos) {
if (pos == 1) {
if (size == 1) {
start = null;
end = null;
size = 0;
return;
}
start = start.getLinkNext();
start.setLinkPrev(end);
end.setLinkNext(start);
size--;
return;
}
if (pos == size) {
end = end.getLinkPrev();
end.setLinkNext(start);
start.setLinkPrev(end);
size--;
}
Node ptr = start.getLinkNext();
for (int i = 2; i <= size; i++) {
if (i == pos) {
Node p = ptr.getLinkPrev();
Node n = ptr.getLinkNext();
p.setLinkNext(n);
n.setLinkPrev(p);
size--;
return;
}
ptr = ptr.getLinkNext();
}
}
public void display(int pos) {
Node ptr = start;
if(pos == 1){
System.out.print(start.data+" ");
}
int count = 2;
while (ptr.getLinkNext() != start) {
ptr = ptr.getLinkNext();
if(count == pos){
System.out.print(ptr.data+" ");
}
count++;
}
}
/* Function to display status of list */
public void display() {
Node ptr = start;
if (size == 0) {
System.out.print("empty ");
return;
}
if (start.getLinkNext() == start) {
System.out.print(start.getData() + " <-> " + ptr.getData() + " ");
return;
}
System.out.print(start.getData() + " <-> ");
ptr = start.getLinkNext();
while (ptr.getLinkNext() != start) {
System.out.print(ptr.getData() + " <-> ");
ptr = ptr.getLinkNext();
}
System.out.print(ptr.getData() + " <-> ");
ptr = ptr.getLinkNext();
System.out.print(ptr.getData() + " ");
}
}
/* Class CircularDoublyLinkedList */
public class CircularDoublyLinkedList {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
/* Creating object of linkedList */
linkedList list = new linkedList();
// System.out.println("Circular Doubly Linked List Test ");
System.out.println("Enter the file Name");
String fileName = scan.nextLine();
File file = new File(fileName);
try {
scan = new Scanner(file);
while (scan.hasNextLine()) {
System.out.println(" *********************");
String[] line = scan.nextLine().split(" ");
int n = Integer.parseInt(line[0]);
int k = Integer.parseInt(line[1]);
int m = Integer.parseInt(line[2]);
for (int i = 1; i <= n; i++) {
list.insertAtEnd(i);
}
Node first = list.start;
Node last = list.end;
int count = 0;
list.display();
while (!list.isEmpty()) {
for(int i=1;i<k;i++){
first = first.next;
}
for(int i=1;i<m;i++){
last = last.prev;
}
if(first.data == last.data){
list.display(list.deleteNode(first));
list.deleteAtPos(list.deleteNode(first));
//list.display();
first = first.next;
}
else{
//list.display();
list.display(list.deleteNode(first));
list.deleteAtPos(list.deleteNode(first));
//list.display();
first = first.next;
boolean check = list.deleteNode(first) == list.deleteNode(last);
list.display(list.deleteNode(last));
list.deleteAtPos(list.deleteNode(last));
if(check){
first = list.start;
}
System.out.println();
//list.display();
}
last = last.prev;
}
}
scan.close();
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
System.out.println("File not found!");
}
list.display();
System.out.println(" Do you want to continue (Type y or n) ");
}
}
Output:
Enter the file Name
nkm
*********************
1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <-> 7 <-> 8 <-> 9 <-> 10 <-> 1
4 8
9 5
3 1
2 6
10 7
*********************
1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <-> 7 <-> 8 <-> 9 <-> 10 <-> 11 <-> 12 <-> 13 <-> 14 <-> 15 <-> 16 <-> 17 <-> 1
6 14
12 10
2 5
11 17
4 9
1 16 8
7 13
15 3 empty
Do you want to continue (Type y or n)
Input text file:
10 4 3
17 6 4
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.