LebGeeks

A.L

Member

[Exercise] josephus problem

It's my first time posting to the programming section, so here it is.
"There are people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.

The task is to choose the place in the initial circle so that you are the last one remaining and so survive."
(quoted from Wikipedia: http://en.wikipedia.org/wiki/Josephus_problem)
in other words if you have n people ( numbered from 1 to n) the kth person is always eliminated until there is only one person after the first elimination the counting restarts from  person numbered k+1 in the original circle ex: lets say we have 10 persons in a circle and we're eliminating the 4th starting anywhere ( its a circle after all) the elimination would go like this :
1 2 3 5 6 7 8 9 10
1 2 3  5 6 7 9 10
1 3 5 6 7 9 10
1 3 5 6 9 10
1 5 6 9 10
1 5 6 9
1 5 6
5 6
5
i solved it in java if you want me to post the solution tell me.

NuclearVision

Member

Re: [Exercise] josephus problem

What are inputs, outputs for the code?
Edit : I read the wiki, I think input is n, output is the persons order that's surviving.(?)

Last edited by NuclearVision (August 17 2014)

A.L

Member

Re: [Exercise] josephus problem

input is n output is the survivor ( i got it working in a way that it prints the ones remaining after every elimination until there is only one left)

NuclearVision

Member

Re: [Exercise] josephus problem

k is arbitrary?

A.L

Member

Re: [Exercise] josephus problem

yes in the question it is between 1 and n-1 but the code will eventually accept any value ( ex: if  is 50 and k is 49 after two elimination n will be less than k  so you'll have to account for that)
if you mean by arbitrary that it changes every time then no it is constant you assign it before running the code

Last edited by A.L (August 17 2014)

NuclearVision

Member

Re: [Exercise] josephus problem

I meant I could chose any value. Ok got it.

m.sabra

Member

Re: [Exercise] josephus problem

import java.util.Scanner;
public class josephus {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(); // number of mens
        int k = input.nextInt();// the kth guy will be killed
        int i=1;
        int[] a = new int[n];
        for(int x=0;x<a.length;x++){
            a[x]=i++;  // filling the array
        }
        System.out.println(survivor(a,k));
    }
    public static int survivor(int[] a,int k){
        int kills=0; // number of guys killed
        int x=-1;  // index of the element in the array
        int count =0; // the current count
        while(kills<= a.length-2){ // breaks when only 1 guy is left
            x=x+1;
            if(x>a.length-1){
                x= x- a.length; // to stay inside the array bounds
            }
            if(a[x] !=0){ // !=0 means not killed 
                count++;   
            }
            if(count == k){ // when the count reach the man to kill
                a[x]=0;    // we kill the man
                count=0;  // and reset the count 
                kills++; // and increment the number of kills
            }
        }
        for(int y=0;y<a.length;y++){
            if(a[y]!=0){ // checking for the survivor in the array
                return a[y];
            }
        }
        return 0;
    }
}

some excessive comments to make it more understandable,i know it can be solved in possibly a faster way,but it still works and i tried for a circle with a million guy in it and obtained the solution in few milliseconds.(if my solution was correct (10,4) should return 5 and (41,3) should return 31)

A.L

Member

Re: [Exercise] josephus problem

i solved it in a slightly more elaborate way than you. I don't know why i didn't think of an array of integers i worked with an array of string. here is my code:

package trial;

public class trial2 {
	public static void main(String[] args) {
		int n = 1000; // didnt want to bother and import the scanner
		String s = "";
		for (int i = 1; i <= n; i++) {
			s = s + i + " ";
		}
		for (int i = 0; i < n - 1; i++) {
			s = method(s, 5);
			System.out.println(s);
		}
	}

	public static String method(String s, int j) {
		int k =j;
		String[] a = s.split(" ");
		if (a.length >= j) {
			j = j;
		} else {
			for (int i = 0; i < (j / a.length); i++) {
				k = k - a.length;
			}
			if (k==0){k=1;}
		}

		String[] b = new String[k - 1];
		String[] c = new String[a.length - k];
		String[] d = new String[a.length - 1];
		for (int i = 1; i < k; i++) {
			b[i - 1] = a[i - 1];
		}
		for (int i = k; i < a.length; i++) {
			c[i - k] = a[i];
		}
		for (int i = 0; i < c.length; i++) {
			d[i] = c[i];
		}
		for (int i = c.length; i < d.length; i++) {
			d[i] = b[i - c.length];
		}

		String l = "";
		for (int i = 1; i <= d.length; i += 2) {
			if (i < d.length) {
				l += d[i - 1] + " " + d[i] + " ";
			} else {
				l += d[i - 1];
			}
		}
		return l;

	}
}

Last edited by A.L (August 17 2014)

NuclearVision

Member

Re: [Exercise] josephus problem

def last(n):
  circle=range(1,n+1)
  k=3 #here k=4, 0,1,2,3needed for python list stuff
  j=0
  while True:
    j+=k
    if j<=len(circle):
      circle.pop(j)
    else:
      circle.pop(j%len(circle))
    if len(circle)==1:
      break
  print circle[0]
last(10)

venam

Member

Re: [Exercise] josephus problem

--

Last edited by venam (September 9 2016)

Ra8

Member

Re: [Exercise] josephus problem

My JS solution

function lastMan(n,k){
    var a=[];
    for(var i=1;i<n+1;i++)
        a.push(i);
    var s=0;
    for(var i=0;i<n-1;i++)
        a.splice(s=(s+k-1)%a.length,1);
    return a[0];
}