The Josephus Problem

21Jun13

In the twelve months from March 2013 to March 2014, I programmed solutions to the problems posted on the Contest Coding blog run by Lewis Cornwall, solving 33 problems (out of 47) and achieving a position of 4th on the leaderboard (out of 23).

As that blog has now been discontinued, I’m posting here the solutions I programmed to those problems.

The Josephus Problem

In the Jewish revolt against Rome, Josephus and 39 of his comrades were holding out against the Romans in a cave. With defeat imminent, they resolved that they would rather die than be slaves to the Romans. They decided to arrange themselves in a circle. One man was designated as number one, and they proceeded clockwise killing every seventh man… Josephus was among other things an accomplished mathematician; so he instantly figured out where he ought to sit in order to be the last to die. But when the time came, instead of killing himself he joined the Roman side. Find the position at which Josephus sat.

Solution and answer (The Josephus Problem.pas):

Uses: lib_seal_suffix.

{$R+}
program The_Josephus_Problem( output );
{
Solution and answer for problem "The Josephus Problem" (21st June 2013) of http://ContestCoding.WordPress.com/

Josephus should sit at the 24th position.

Solution programmed in Pascal using Metrowerks CodeWarrior IDE 2.1 (Discover Programming Edition); solution took ~1s to run on a 80MHz PowerPC 601.
}
uses
  lib_seal_suffix;
label
  l_LOOP;
const
  k_INITIAL_NUMBER = 40;
  k_NUMBER_TO_SKIP = 6;
var
  number_alive : 1..k_INITIAL_NUMBER;
  i : 0..k_INITIAL_NUMBER;
  alive : array [ 1..k_INITIAL_NUMBER ] of boolean;
  c : 0..k_NUMBER_TO_SKIP + 1;
begin
  number_alive := k_INITIAL_NUMBER;
  for i := 1 to k_INITIAL_NUMBER do
    alive[ i ] := true;
  i := 0;
  repeat
    c := 0;
    l_LOOP:
      if i + 1 > k_INITIAL_NUMBER then
        i := 1
      else
        i := i + 1;
      if alive[ i ] then
        c := c + 1;
      if c = k_NUMBER_TO_SKIP + 1 then begin
          number_alive := number_alive - 1;
          alive[ i ] := false
        end
      else
        goto l_LOOP
  until number_alive = 1;
  i := 0;
  repeat
    i := i + 1
  until alive[ i ];
  writeln( 'Josephus should sit at the ', i, f_Suffix( i ), ' position.' )
end.
Advertisements


No Responses Yet to “The Josephus Problem”

  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: