Circular linked list game: please create J unit Test In an ancient land, a King
ID: 3724416 • Letter: C
Question
Circular linked list game: please create J unit Test
In an ancient land, a King had many prisoners. He decided on the following procedure to determine which prisoner to grand freedom. First, all of the prisoners would be lined up one after the other and assigned numbers. The first prisoner would be number 1, the second number 2, and so on up to the last prisoner, number n . Starting at the prisoner in the first position, he would then count k prisoners down the line, and the kth prisoner would be eliminated from winning her/his freedom removed from the line. The King would then continue, counting k more prisoners, and eliminate every kth prisoner. When he reached the end of the line, he would continue counting from the beginning. For example, if there were six prisoners, the elimination process would proceed as follows (with step k=2): 123456 Initial list of prisoners; start counting from 1. 12456 Prisoner 3 eliminated; continue counting from 4. 1245 Prisoner 6 eliminated; continue counting from 1. 125 Prisoner 4 eliminated; continue counting from 5. 15 Prisoner 2 eliminated; continue counting from 5. 1 Prisoner 5 eliminated; 1 is the lucky winner. 1 Write a program that creates a circular linked list of nodes to determine which position you should stand in to win your freedom if there are n prisoners. Your program should simulate the elimination process by deleting the node that corresponds to the prisoner that is eliminated for each step in the process. Create appropriate JUnits to test your program.
Explanation / Answer
******************************CricularLinkedList.java************************
package prisoners_freedom;
/**
* This is implementation class for circularly linked list.
*/
public class CricularLinkedList {
private Node start;
private int count;
/**
* This function is used to append nodes into list
*
* @param x the x
*/
public void add(int x) {
count++;
Node temp = new Node(x);
if (start == null) {
start = temp;
}
else {
Node tp = start;
while (tp.link != start) {
tp = tp.link;
}
tp.link = temp;
}
temp.link = start;
}
/**
* this method is used to Adds node to start.
*
* @param x the x
*/
public void addStart(int x) {
count++;
Node temp = new Node(x);
if (start == null) {
temp.link = temp;
}
else {
Node tp = start;
while (tp.link != start) {
tp = tp.link;
}
tp.link = temp;
temp.link = start;
}
start = temp;
}
/**
* Adds the at.
*
* @param pos the pos
* @param x the x
*/
public void addAt(int pos, int x) {
Node temp, tp;
temp = new Node(x);
tp = start;
for (int i = 0; i < pos; i++) {
if (tp.link == start)
break;
tp = tp.link;
}
temp.link = tp.link;
tp.link = temp;
count++;
}
/**
* Display list.
*
* @return the string
*/
public String displayList() {
StringBuilder sb = new StringBuilder();
if (!isEmpty()) {
Node temp = start;
sb.append("[");
sb.append(temp.data).append(", ");
while (temp.link != start) {
temp = temp.link;
sb.append(temp.data).append(", ");
}
sb.append("]");
}
return sb.toString();
}
/**
* Delete at.
*
* @param position the position
* @return the integer
*/
public Integer deleteAt(int position) {
Node current = start;
Node previous = start;
Integer data = null;
for (int i = 0; i < position; i++) {
if (current.link == start)
break;
previous = current;
current = current.link;
}
data =current.data;
if (position == 0) {
deleteFirst();
}
else {
previous.link = current.link;
}
count--;
return data;
}
/**
* Delete first.
*
* @return the integer
*/
public Integer deleteFirst() {
Node temp = start;
Integer data = temp.data;
while (temp.link != start) {
temp = temp.link;
}
temp.link = start.link;
start = start.link;
count--;
return data;
}
/**
* Gets the count.
*
* @return the count
*/
public int getCount() {
return count;
}
/**
* Checks if is empty.
*
* @return true, if is empty
*/
public boolean isEmpty() {
return start == null;
}
/**
* The Class Node.
*/
private static class Node {
/** The data. */
int data;
/** The link. */
Node link;
/**
* Instantiates a new node.
*
* @param data the data
*/
public Node(int data) {
this.data = data;
}
/**
* Instantiates a new node.
*
* @param data the data
* @param link the link
*/
public Node(int data, Node link) {
this.data = data;
this.link = link;
}
}
}
********************************PrisonersFreedom.java************************
package prisoners_freedom;
/**
* The Class PrisonersFreedom is used to perform freedom operations of the prisoners.
*/
public class PrisonersFreedom {
private CricularLinkedList prisoners = new CricularLinkedList();
private int index = -1;
/**
* Load prisoners.
*
* @param numberOfPrisoners the number of prisoners
* @return the string
*/
public String loadPrisoners(int numberOfPrisoners) {
int count = 1;
while (count <= numberOfPrisoners) {
if (prisoners.isEmpty()) {
prisoners.addStart(count++);
}
else {
prisoners.add(count++);
}
}
return prisoners.displayList();
}
/**
* Free prisoners.
*
* @param freePrisonerAt the free prisoner at
* @return the integer
*/
public Integer freePrisoners(int freePrisonerAt) {
for (int i = 0; i < freePrisonerAt; i++) {
index++;
}
return prisoners.deleteAt(index);
}
/**
* Show prisoners.
*
* @return the string
*/
public String showPrisoners(){
return prisoners.displayList();
}
}
********************************FreePrisonerTest.java************************
package prisoners_freedom;
import static org.junit.Assert.assertEquals;
import org.junit.Test;
public class FreePrisonerTest {
public static void main(String args[]) {
org.junit.runner.JUnitCore.main("BoardTests");
}
@Test
public void loadPrisonerTest1() {
PrisonersFreedom prisoners = new PrisonersFreedom();
String actualResult = prisoners.loadPrisoners(10);
assertEquals(expectedPrisoners1(), actualResult);
}
@Test
public void loadPrisonerTest2() {
PrisonersFreedom prisoners = new PrisonersFreedom();
String actualResult = prisoners.loadPrisoners(100);
assertEquals(expectedPrisoners2(), actualResult);
}
@Test
public void freePrisonerTest1() {
PrisonersFreedom prisoners = new PrisonersFreedom();
prisoners.loadPrisoners(100);
assertEquals(Integer.valueOf(5), prisoners.freePrisoners(5));
assertEquals(expectedPrisoners3(), prisoners.showPrisoners());
}
@Test
public void freePrisonerTest2() {
PrisonersFreedom prisoners = new PrisonersFreedom();
prisoners.loadPrisoners(10);
assertEquals(Integer.valueOf(5), prisoners.freePrisoners(5));
assertEquals(expectedPrisoners4(), prisoners.showPrisoners());
assertEquals(Integer.valueOf(10), prisoners.freePrisoners(5));
assertEquals(expectedPrisoners5(), prisoners.showPrisoners());
}
private String expectedPrisoners1() {
return "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ]";
}
private String expectedPrisoners2() {
return "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23,"
+ " 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, "
+ "47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70,"
+ " 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94,"//
+ " 95, 96, 97, 98, 99, 100, ]";
}
private String expectedPrisoners3() {
return "[1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23,"
+ " 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, "
+ "47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70,"
+ " 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94,"//
+ " 95, 96, 97, 98, 99, 100, ]";
}
private String expectedPrisoners4() {
return "[1, 2, 3, 4, 6, 7, 8, 9, 10, ]";
}
private String expectedPrisoners5() {
return "[1, 2, 3, 4, 6, 7, 8, 9, ]";
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.