Josephus Problem

The Josephus problem  is a problem often discussed and seen in CS literature. I got introduced to the problem when I initially started programming and knowing nothing about linked lists and/or recursion had a really hard time solving it.

The problem is stated as:
There are people standing in a circle waiting to be executed. After the first man is executed, certain number of people are skipped and one man is executed. Then again, people are skipped and a man is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last man remains, who is given freedom.

The task is to choose the place in the initial circle so that you survive (are the last one remaining).

The easiest and most logical way to solve the problem is to simply simulate it using a circular link list.

N is no. of people, M as the count.

struct node {  
	int item; 
	node* next; 
};


int simple_simulation(int N, int M)
{ 
  int i;
  node *t=new node();
  node *x=t;
  t->item = 1; t->next = t;

  //Construct the list 
  for (i = 2; i <= N; i++)
  {
    x = (x->next = new node ());
    x->item = i; 
    x->next = t;
  }

  //Find the survivor
  while (x != x->next)
  {
    for (i = 1; i < M; i++) 
      x = x->next;
    x->next = x->next->next; N--;
  }
  return x->item;
}

A better way to solve the problem is through recursion. Its easy to find who is killed first, (Hint: it’s the Mth guy from the start) after that we are left with N-1 total people and the count starts from the new guy who was at M+1th position earlier. Going on like this gives us a simple recursive function:

int formula (int N, int M) 
{ 
if (N == 1)
	return 0; 
return (formula (N-1, M) + M) % N; 
}

References:

http://en.wikipedia.org/wiki/Josephus_problem

Climb the Pyramid

Cal Newport describes the pyramid strategy to evaluate one’s progress.

http://calnewport.com/blog/2009/06/03/the-pyramid-method-a-simple-strategy-for-becoming-exceptionally-good/

From the blog:

[quote]

I call this general technique the Pyramid Method. I claim that it’s a powerful approach for anyone looking to transform an interest or natural talent into an expertise that cannot be ignored. Regardless of the pursuit in question, if you want to take it someplace serious, follow Chris’s example. This means:

1. Pick a single relevant venue to join at the entry level and work to increase your standing.
2. Make sure the venue offers clear metrics on your progress; use these metrics to guide your efforts to get better.
3. Forget all the other bullshit advice and mini-strategies people offer for getting ahead in your pursuit. If you can’t master this one venue, then you don’t yet deserve the world’s respect.
4. Put your head down, and get it done.

[/quote]

The strategy can work for many skills music, sports and coding. But choosing the proper venue is critical. IMO, apart from the above properties mentioned by Chris, The venue should have some other properties.  I would talk about them from a coder’s perspective.

1. Have a low entry barrier: So that you can start early from a entry-level. So, when you only know the syntax and basic constructs of a high level language (C++, Java, C#)

2. A high competition/quality: So, you don’t “win” the venue too soon. So, you are actively engaged when you can solve non-trivial problems in your arena also. This also ensures that good coders will keep coming to your venue rather than taking off someplace else.

3. Can cater to more than 1 skill: I find this important to be a successful programmer you have to do more than code! This can involve making system architecture, understanding existing codebases, soft skills like communication.

One of the venues I know is Topcoder.com as it offers all what Chris has outlined in his article and what I have outlined here in this post.

Now, I just have to go and follow the all important Step 4 from Chris’s post.