### The Josephus Problem

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 4^{th} 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 ProblemIn 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.

Filed under: Uncategorized | Leave a Comment

Tags: computer science, computing, contest, Contest Coding, Lewis Cornwall, Pascal

## No Responses Yet to “The Josephus Problem”