Problem Description
Recently, I have been reading the book Schaum's Outline of Mathematica (2nd Edition), where I encountered the problem:
Flavius Josephus was a Jewish historian of the first century. He wrote about a group of ten Jews in a cave who, rather than surrender to the Romans, chose to commit suicide, one by one. They formed a circle and every other one was killed. Who was the lone survivor?
The author's solution:
list = Range[10];
While[Length[list] > 1, list = Rest[RotateLeft[list]]];
list
{5}
However, I know it is not efficient to use the procedural methods such as Do
, While
, etc. Rather, I want to use a functional method like NestWhile
, Nest
, or FixedPoint
to solve the problem.
My solutions:
Method 1:
list = Range @ 10;
NestList[Rest @ RotateLeft[#] &, list, 9]
{{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
{3, 4, 5, 6, 7, 8, 9, 10, 1},
{5, 6, 7, 8, 9, 10, 1, 3},
{7, 8, 9, 10, 1, 3, 5},
{9, 10, 1, 3, 5, 7},
{1, 3, 5, 7, 9},
{5, 7, 9, 1},
{9, 1, 5},
{5, 9},
{5}}
Furthermore, this method has the flaw that I must give the number of iterations. In fact, sometimes that is unknown.
Method 2:
list = Range @10;
FixedPoint[If[Length@# != 1 &, Rest @ RotateLeft[#] &], list]
Unfortunately, method 2 doesn't work.
Method 3:
list = Range @ 10;
NestWhileList[Rest @ RotateLeft[#] &, list, Length@list != 1]
{{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}}
So my question is: what is a good way to do it?
Answer
NestWhile[Rest @ RotateLeft @ # &, Range @ 10, Length @ # > 1 &]
{5}
FixedPoint[If[Length @ # > 1, Rest @ RotateLeft[#], #] &, Range @ 10]
Edit
Historical note: As far as I can remember, Josephus roulette (a plain treason to his companions) consisted of killing every third person.
FixedPoint[If[Length@# != 1, Rest@RotateLeft[#, 2], #] &, Range@10]
{4}
Note: The direction is important. RotateRight[]
will select another victim.
Comments
Post a Comment