# Joesphus Problem

• 11-20-2013, 10:35 PM
MitchellWall
Joesphus Problem
I'm trying to work with the Josephus Problem of continually removing an element until one remains through a circular Linked List. I am lost of how to remove the element though. I keep getting NullPointerExceptions and I do not know why.

For my version of the Josephus, I use int elements
such as

1 2 3 4 5 6
and let's remove every second element until 1 remains
4 5 6 1 2
1 2 4 5
5 1 2
5 1
1
element 1 is the remainder.

I am able to add all elements, but removing is the difficulty.
Code:

```/** * Prisoner is a class that is used for a linked list * of prisoners.  The linked list is * circular where the tail points back to the head. */ //import java.util.Iterator; class Prisoner{         class DigitNode     {             public int num=0;                        // Digit's position in line             public DigitNode next=null;        // Reference to next Digit             /**             * Digit constructor, initializes number             */             public DigitNode(int number)             {                   //                 num = number;                 next = null;             }                         public String toString() {                 return "" + num;             }     }         private int digit;     private DigitNode head = null;        // Linked list of prisoners     private DigitNode tail = null;        // Tracks end of list as it is constructed         /**     * constructs a circular linked list of     * @param n DigitNode, current is the first DigitNode and tail is the last DigitNode(next of tail is current)     */       public Digi(int n)     {         //         digit= n;         head = null;         tail = null;     }         public void add(int n) {         DigitNode newNode = new DigitNode(n);         newNode.next = head;         head = newNode;     }         /*     * prints all Digit starting from current until tail     */     @Override     public String toString()     {         //         String strVal = "";         Digit p = new Digit(digit);                 for (int i = digit; i >= 1; i--) {             p.add(i);         }         DigitNode position = p.head;         while (position != null) {             strVal = strVal + position.num + " ";             //System.out.println(strVal);             position = position.next;         }         return strVal;     }               /**       * moves the current       * @param n positions       */     public void move(int k)     {             //         DigitNode current = head;         while (current.num != k) {             current = current.next;         }     }     /*       * call move(k) and then remove the digit in current position       */     public void eliminate(int k)     {         //                  move(k);         DigitNode current = head;         DigitNode previous = tail;                 while (current.num != k) {             previous = current;             current = current.next;         }         if ( current == head) {             head = head.next;         } else {             previous.next = current.next;         }     }               }```
• 11-20-2013, 11:03 PM
MitchellWall
Re: Joesphus Problem
Thank you for adding code tags, now I know how to do that JosAH.
• 11-20-2013, 11:04 PM
MitchellWall
Joesphus Problem
I'm trying to work with the Josephus Problem of continually removing an element until one remains through a circular Linked List. I am lost of how to remove the element though. I keep getting NullPointerExceptions and I do not know why.

For my version of the Josephus, I use int elements
such as

1 2 3 4 5 6
and let's remove every second element until 1 remains
4 5 6 1 2
1 2 4 5
5 1 2
5 1
1
element 1 is the remainder.

I am able to add all elements, but removing is the difficulty.
Code:

```/** * Prisoner is a class that is used for a linked list * of prisoners.  The linked list is * circular where the tail points back to the head. */ //import java.util.Iterator; class Prisoner{         class DigitNode     {             public int num=0;                        // Digit's position in line             public DigitNode next=null;        // Reference to next Digit             /**             * Digit constructor, initializes number             */             public DigitNode(int number)             {                   //                 num = number;                 next = null;             }                         public String toString() {                 return "" + num;             }     }         private int digit;     private DigitNode head = null;        // Linked list of prisoners     private DigitNode tail = null;        // Tracks end of list as it is constructed         /**     * constructs a circular linked list of     * @param n DigitNode, current is the first DigitNode and tail is the last DigitNode(next of tail is current)     */       public Digi(int n)     {         //         digit= n;         head = null;         tail = null;     }         public void add(int n) {         DigitNode newNode = new DigitNode(n);         newNode.next = head;         head = newNode;     }         /*     * prints all Digit starting from current until tail     */     @Override     public String toString()     {         //         String strVal = "";         Digit p = new Digit(digit);                 for (int i = digit; i >= 1; i--) {             p.add(i);         }         DigitNode position = p.head;         while (position != null) {             strVal = strVal + position.num + " ";             //System.out.println(strVal);             position = position.next;         }         return strVal;     }               /**       * moves the current       * @param n positions       */     public void move(int k)     {             //         DigitNode current = head;         while (current.num != k) {             current = current.next;         }     }     /*       * call move(k) and then remove the digit in current position       */     public void eliminate(int k)     {         //                  move(k);         DigitNode current = head;         DigitNode previous = tail;                 while (current.num != k) {             previous = current;             current = current.next;         }         if ( current == head) {             head = head.next;         } else {             previous.next = current.next;         }     }               }```
• 11-20-2013, 11:25 PM
jim829
Re: Joesphus Problem
I am assuming you mean removing an item in a linked list.

In a circular linked list, the tail points back to the head. So to delete an item, save the parent of the item you want to delete. Now you have parentOfItem so you just need to have parentOfItem.child = item.child. And the link is deleted. When item.child = item, the node points to itself, so you are done since you only have one item remaining.

Regards,
Jim
• 11-21-2013, 09:01 AM
JosAH
Re: Joesphus Problem
If I remove every second element from the circular list (1, 2, 3, 4, 5, 6) I get (1, 3, 5); I don't understand your result ...

kind regards,

Jos
• 11-21-2013, 10:01 AM
JosAH
Re: Joesphus Problem
What happened to this thread? There's a 'soft link', pointing to the same thread; one of the links states that the thread was moved ... it's bitrot, I'm telling you ...

kind regards,

Jos

ps. I don't dare to remove one of the 'links'.
• 11-21-2013, 10:43 AM
gimbal2
Re: Joesphus Problem
... I have no idea what you're talking about here! I see nothing wrong.
• 11-21-2013, 10:50 AM
JosAH
Re: Joesphus Problem
Don't you see two (identical) threads 'Josephus Problem' and one of them seems to be moved; they're both one thread only ...

kind regards,

Jos
• 11-23-2013, 08:00 PM
natdizzle
Re: Joesphus Problem
i use arraylists remove method.. and make sure you have the right index

im removing from a list here Lists

its also supposed to be a countdown too zero