# [find out the lucky position to survive]-will you help me please !

• (2 Pages)
• 1
• 2

## 16 Replies - 1138 Views - Last Post: 26 April 2011 - 08:53 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=224965&amp;s=1fed7f2c569252aa74eecb0984a99114&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 iShrne

Reputation: 0
• Posts: 11
• Joined: 29-March 11

# [find out the lucky position to survive]-will you help me please !

Posted 29 March 2011 - 09:39 AM

This problem is a game where n objects are arranged in a circle and every mth object is deleted until 1 object is left.

The original problem is said to derive from a suicide pact among 41 rebels trapped by the Romans in the first century. The rebels decided to kill every third person until one is left and can escape in a boat that can take only one person. Josephus, the historian who lived to tell the story quickly figured out where he should position himself from the starting point in the circle so that he would survive.

Suppose you were in that situation with the only difference that you have your palm PC to quickly find out the lucky position to survive. Your program should be able to handle the following situation:

n people (n > 0 ) are initially arranged in a circle, facing inwards, and numbered from 1 to n. The numbering from 1 to n proceeds consecutively in a clockwise direction.

Starting with person number 1, counting continues in a clockwise direction, until we get to person number k (k > 0), who is promptly killed.

Counting then proceeds from the person to his immediate left, to kill the kth person, and so on, until only one person remains.

For example, when n = 5 and k = 2, the order of execution is 2, 4, 1, and 5. The survivor is 3.
Hint you have to implement the circular list for your program to be efficient."how that could be !"

Input
Input data is to be read from a file roulette.in. Each line in this file contains values for n and k (in that order). A line containing values of 0 for n and k will terminate input. Your program does know not the maximum number of people taking part in this tragic event.
Output
For each input line, output in a file roulette.out the position of the sole survivor.
Sample Input
1 1
1 5
8 3
0 0

Sample Output
1
1
7

- to be serious with you my friends i did not understand this question very well !
and am not here to just get the solution without learning!
.. i know here a lot of people who have excellent background they can help
me step by step. so please will you help me !! to learn and solve this problem !

Is This A Good Question/Topic? 0

## Replies To: [find out the lucky position to survive]-will you help me please !

### #2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11449
• Posts: 43,165
• Joined: 27-December 08

## Re: [find out the lucky position to survive]-will you help me please !

Posted 29 March 2011 - 09:45 AM

You have 5 objects in a circle, and you're deleting every 3rd as an example:

So start with our five elements, and they are removed as such:
```0 1 2 3 4
0 1 3 4 //2 was removed
1 3 4 //0 was removed
1 3 //4 was removed
3 //1 was removed

```

### #3 iShrne

Reputation: 0
• Posts: 11
• Joined: 29-March 11

## Re: [find out the lucky position to survive]-will you help me please !

Posted 29 March 2011 - 09:50 AM

first of all .. i have good back ground in linked list.

but first of all i have to understand the idea of question to start thinking about coding.

will you explain the question in ordinary word please ? am sorry so that i said i have
to solve it step by step .. just to learn correctly =)

### #4 iShrne

Reputation: 0
• Posts: 11
• Joined: 29-March 11

## Re: [find out the lucky position to survive]-will you help me please !

Posted 29 March 2011 - 08:19 PM

am still wondering ! did you mean that i need to use circular linked list? but look to the input
it's look to me is a 2d matrix ??

### #5 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11449
• Posts: 43,165
• Joined: 27-December 08

## Re: [find out the lucky position to survive]-will you help me please !

Posted 29 March 2011 - 08:59 PM

Each row represents a circular LinkedList, or a separate set of people for the Josephus game. No need for a 2D array here.

### #6 iShrne

Reputation: 0
• Posts: 11
• Joined: 29-March 11

## Re: [find out the lucky position to survive]-will you help me please !

Posted 29 March 2011 - 09:27 PM

am still confuse ! i want to understand the question before i start coding or thinking
if start according these steps does what i will do correct :
first of all i need to read the input file (line by Line ) ..
now I'll arranged my element in cir.LL ,

i have to further questions to start coding .. story said ?
Josephus, the historian who lived to tell the story quickly figured out where he should position himself from the starting point in the circle so that he would survive.
the staring point in circle .. will be the head am a right ?

.
.

the second question:

i understand that n is [1,1,8] & k is [1,5,3] and when n = 0 and k = 0 the program will stop!
but now look to this : For example, when n = 5 and k = 2, the order of execution is 2, 4, 1, and 5. The survivor is 3.

how it calculate the that ? i think the idea is here :
n people (n > 0 ) are initially arranged in a circle, facing inwards, and numbered from 1 to n. The numbering from 1 to n proceeds consecutively in a clockwise direction.

Starting with person number 1, counting continues in a clockwise direction, until we get to person number k (k > 0), who is promptly killed.

Counting then proceeds from the person to his immediate left, to kill the kth person, and so on, until only one person remains.

but i could it pick up directly !

### #7 iShrne

Reputation: 0
• Posts: 11
• Joined: 29-March 11

## Re: [find out the lucky position to survive]-will you help me please !

Posted 29 March 2011 - 10:32 PM

there is one more thing my steps will be as following !
insert elements into CLL
know the algorithm to know who will survive
and then use recursion !
am a right ?
is almost like binary search ,,

This post has been edited by iShrne: 29 March 2011 - 10:33 PM

### #8 iShrne

Reputation: 0
• Posts: 11
• Joined: 29-March 11

## Re: [find out the lucky position to survive]-will you help me please !

Posted 30 March 2011 - 09:51 AM

am working in the code now ,, I'll post it soon ,, but i was wondering ,,
the method that about alogrothim which i did not understand it and i hope someone explain it
to me " in words or mathematical examples" not by coding .. i have to write it in the main class ,
i do not have to write it within in Clinked list method right! " am asking just in case"
because i will leave this algorithm until last step.

This post has been edited by iShrne: 30 March 2011 - 09:55 AM

### #9 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11449
• Posts: 43,165
• Joined: 27-December 08

## Re: [find out the lucky position to survive]-will you help me please !

Posted 30 March 2011 - 09:53 AM

You aren't inserting the File elements into the LinkedList. Those tell you the size and the number of steps to remove an element in each LinkedList. Each row represents a different List.

Why use recursion? I don't see the need. And not like a binary search at all.

### #10 iShrne

Reputation: 0
• Posts: 11
• Joined: 29-March 11

## Re: [find out the lucky position to survive]-will you help me please !

Posted 30 March 2011 - 10:07 AM

ok ! will you explain to me how this algorithm work please !
i can't start coding unless i understand how the method is work !

i recommended use the recursion because when i saw your example , you first
deleted the middle one and then one from right and another one from the left.
it seem to me steps are repeating !

and when i tried this in the example above it gave me wrong answer
"i tried it manually "!

Quote

Those tell you the size and the number of steps to remove an element in each LinkedList. Each row represents a different List.

yeah i know the size "i think "will be range between (n and k ), and i have to determine the
start point .. and method to delete .

look am just saying that based on how i understand the algorithm!!
i believe that if i understand it very well i can go ahead.

### #11 iShrne

Reputation: 0
• Posts: 11
• Joined: 29-March 11

## Re: [find out the lucky position to survive]-will you help me please !

Posted 31 March 2011 - 05:02 AM

can any body tell me how this one BitSet work ?

### #12 cfoley

• Cabbage

Reputation: 2244
• Posts: 4,722
• Joined: 11-December 07

## Re: [find out the lucky position to survive]-will you help me please !

Posted 31 March 2011 - 06:16 AM

To delete a node in a cyclic linked list, all you have to do is make the previous nodde point to the next one. For example, say you have a fragment ....-->A-->B-->C-->...., if you want to delete B, simply make A point to C ....-->A-->C-->....

Quote

Hint you have to implement the circular list for your program to be efficient.

Putting it like this is just a challenge to find other efficient ways of doing it. Here is my effort which uses a while loop to solve the problem. I bet someone more mathematically minded can produce a one-line formula to calculate the answer.

```	public static int getLuckyPersonNumber(final int peopleCount, final int gap) {
int[] ppl = new int[peopleCount];
for(int i = 0; i < peopleCount; i++) {
ppl[i] = i+1;
}

int gunPointsAt = 0;
int countDown = gap;
int nextCopy = 0;
int surviving = peopleCount;

while (surviving > 1) {
if (--countDown == 0) {
surviving --;
countDown = gap;
} else {
ppl[nextCopy] = ppl[gunPointsAt];
nextCopy = (nextCopy+1) % peopleCount;
}
gunPointsAt = (gunPointsAt+1) % peopleCount;
}

return ppl[gunPointsAt];
}
```

### #13 iShrne

Reputation: 0
• Posts: 11
• Joined: 29-March 11

## Re: [find out the lucky position to survive]-will you help me please !

Posted 31 March 2011 - 06:50 AM

am good with linked list , maybe i did not implement a lot of example for CLL but , it same
to Liner Linked list with one difference. My problem in this question is the algorithm to
get the survive person in general without coding i used three ideas but when i tried
i got wrong answer for example :

i tried this trick

change them to binary

for example (1 to 5 )

1 = 001
2 = 100
3 = 011
4 = 100
5 = 101

remove all number that end by one

2 = 100
4 = 100

and look which one had more zeros !
so they are equal .. but the answer should be 1 according to the example !
for a while i think about ArrayList rather than CLL but my code will be complex !
but am stuck on understanding how this algorithm work ! I'll try understand it from your
code .. thank you very much cfoley

### #14 cfoley

• Cabbage

Reputation: 2244
• Posts: 4,722
• Joined: 11-December 07

## Re: [find out the lucky position to survive]-will you help me please !

Posted 31 March 2011 - 06:57 AM

No, don't change it to binary. Loop through the list, deleting every third (or whatever k is) node. Eventually you will be left with 1 node, and that is your answer.

Not helpful to you but here is a refactoring of my solution for if you don't mind creating a bigger array:

```	public static int getLuckyPersonNumber(final int peopleCount, final int gap) {
int[] ppl = new int[gap * (peopleCount - 1) + 1];
int nextCopy = 0;
for(; nextCopy < peopleCount; nextCopy++) {
ppl[nextCopy] = nextCopy+1;
}

for (int i = 1; i < ppl.length; i++) {
if (i%gap != 0) {
ppl[nextCopy++] = ppl[i-1];
}
}
return ppl[ppl.length-1];
}

```

### #15 iShrne

Reputation: 0
• Posts: 11
• Joined: 29-March 11

## Re: [find out the lucky position to survive]-will you help me please !

Posted 31 March 2011 - 07:18 AM

Ah ! now the idea is clear ,, i will implement that in my program ..I'll come back with
my code ,,, thanks cfoley i really appreciated your help !

best regards,

This post has been edited by iShrne: 31 March 2011 - 07:19 AM