Question
In an ancient land, the beautiful princess Eve had many suitors. She decided on the following procedure to determine which suitor she would marry. First, all of the suitors would be lined up one after the other and assigned numbers. The first suitor would be number 1, the second number 2, and so on up to the last suitor, number n. Starting at the first suitor, she would then count three suitors down the line (because of the three letters in her name) and the third suitor would be eliminated from winning her hand and removed from the line. Eve would then continue, counting three more suitors, and eliminating every third suitor. When she reached the end of the line, she would reverse direction and work her way back to the beginning. Similarly, on reaching the first person in line, she would reverse direction and make her way to the end of the line.
For example, if there were five suitors, then the elimination process would proceed as follows:
12345 Initial list of suitors; start counting from 1.
1245 Suitor 3 eliminated; continue counting from 4 and bounce from end back to 4.
125 Suitor 4 eliminated; continue counting back from 2 and bounce from front back to 2.
15 Suitor 2 eliminated; continue counting forward from 5.
1 Suitor 5 eliminated; 1 is the lucky winner.
Write a program that uses an ArrayList or Vector to determine which position you should stand in to marry the princess if there are n suitors. Your program should use the ListIterator interface to traverse the list of suitors and remove a suitor. Be careful that your iterator references the proper object upon reversing direction at the beginning or end of the list. The suitor at the beginning or end of the list should only be counted once when the princess reverses the count.
Answer
PROGRAM CODE:
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
public class PrincessMarryingSuitors {
public static void main(String[] args) {
int numSuitors = 5;
// Create and populate the list of suitors
List<Integer> suitors = new ArrayList<>();
for (int i = 1; i <= numSuitors; i++) {
suitors.add(i);
}
ListIterator<Integer> iterator = suitors.listIterator();
boolean forward = true;
while (suitors.size() > 1) {
int count = 0;
// Move the iterator forward or backward based on the direction
if (forward) {
while (count < 3) {
if (iterator.hasNext()) {
iterator.next();
} else {
iterator = suitors.listIterator(suitors.size());
iterator.next();
}
count++;
}
} else {
while (count < 3) {
if (iterator.hasPrevious()) {
iterator.previous();
} else {
iterator = suitors.listIterator();
iterator.previous();
}
count++;
}
}
// Remove the suitor at the current position
iterator.remove();
// Reverse the direction if reached the end or beginning of the list
if (!iterator.hasNext()) {
forward = false;
} else if (!iterator.hasPrevious()) {
forward = true;
}
}
int winningSuitor = suitors.get(0);
System.out.println("Position to stand in to marry the princess: " + winningSuitor);
}
}
OUTPUT OF THE PROGRAM CODE:
Position to stand in to marry the princess: 1