Problem 1092. Decimation

Created by James

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?><w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>When dealing to the Roman Army, the term decimate meant that the entire unit would be broken up into groups of ten soldiers, and lots would be drawn. The person who was unlucky enough to draw the short straw would be executed by the other nine members of his group.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>The bloodthirsty Roman Centurion Carnage Maximus decided to apply this to his prisoners, with a few gruesome differences. Rather than kill every tenth prisoner and allow the rest to live, he is going to leave only one prisoner alive and kill all of the others. Instead of killing every tenth prisoner, he chooses a number (kill_every). If kill_every=3, he kills every third prisoner. If kill_every=5, he kills every fifth prisoner. He always chooses a number between 2 and the number of prisoners he has, and this process will be repeated until there is only one prisoner left. For example, if there are 10 prisoners, and kill_every=3</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>First iteration: 1 2 3 4 5 6 7 8 9 10</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>1-2-3 4-5-6 7-8-9 10</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Prisoners 3, 6 and 9 will be killed.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Second iteration: 1 2 4 5 7 8 10</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Because Prisoner 10 was counted during the first iteration, the executions will proceed as such: 10-1-2 4-5-7 8-10, so prisoners 2 and 7 will be killed</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Third iteration: 1 4 5 8 10 8-10-1 4-5-8 10, so prisoners 1 and 8 executed.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Fourth Iteration: 10-4-5 10 Prisoner 5 is executed.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Fifth iteration: 10-4 10 Prisoner 10 is executed</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Since the sole survivor is prisoner 4, he is released.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>You are an unlucky prisoner caught by Carnage Maximum. Prior to lining up the prisoners, he reveals the number of prisoners he has and his value of kill_every for the day. Your job is to figure out which prisoner you need to be in order to survive. Write a MATLAB script that takes the values of num_prisoners and kill_every. The output will be survivor, which is the position of the person who survives. If you write your script quickly enough, that person will be you.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Good luck!</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

When dealing to the Roman Army, the term decimate meant that the entire unit would be broken up into groups of ten soldiers, and lots would be drawn. The person who was unlucky enough to draw the short straw would be executed by the other nine members of his group.The bloodthirsty Roman Centurion Carnage Maximus decided to apply this to his prisoners, with a few gruesome differences. Rather than kill every tenth prisoner and allow the rest to live, he is going to leave only one prisoner alive and kill all of the others. Instead of killing every tenth prisoner, he chooses a number (kill_every). If kill_every=3, he kills every third prisoner. If kill_every=5, he kills every fifth prisoner. He always chooses a number between 2 and the number of prisoners he has, and this process will be repeated until there is only one prisoner left. For example, if there are 10 prisoners, and kill_every=3First iteration: 1 2 3 4 5 6 7 8 9 101-2-3 4-5-6 7-8-9 10Prisoners 3, 6 and 9 will be killed.Second iteration: 1 2 4 5 7 8 10Because Prisoner 10 was counted during the first iteration, the executions
will proceed as such: 10-1-2 4-5-7 8-10, so prisoners 2 and 7 will be killedThird iteration: 1 4 5 8 10
8-10-1 4-5-8 10, so prisoners 1 and 8 executed.Fourth Iteration: 10-4-5 10
Prisoner 5 is executed.Fifth iteration: 10-4 10
Prisoner 10 is executedSince the sole survivor is prisoner 4, he is released.You are an unlucky prisoner caught by Carnage Maximum. Prior to lining up the prisoners, he reveals the number of prisoners he has and his value of kill_every for the day. Your job is to figure out which prisoner you need to be in order to survive. Write a MATLAB script that takes the values of num_prisoners and kill_every. The output will be survivor, which is the position of the person who survives. If you write your script quickly enough, that person will be you.Good luck!

When dealing to the Roman Army, the term decimate meant that the entire unit would be broken up into groups of ten soldiers, and lots would be drawn.  The person who was unlucky enough to draw the short straw would be executed by the other nine members of his group.

The bloodthirsty Roman Centurion Carnage Maximus decided to apply this to his prisoners, with a few gruesome differences.  Rather than kill every tenth prisoner and allow the rest to live, he is going to leave only one prisoner alive and kill all of the others.  Instead of killing every tenth prisoner, he chooses a number (kill_every).  If kill_every=3, he kills every third prisoner.  If kill_every=5, he kills every fifth prisoner.  He always chooses a number between 2 and the number of prisoners he has, and this process will be repeated until there is only one prisoner left.  For example, if there are 10 prisoners, and kill_every=3

First iteration: 1 2 3 4 5 6 7 8 9 10

1-2-3 4-5-6 7-8-9 10

Prisoners 3, 6 and 9 will be killed.

Second iteration: 1 2 4 5 7 8 10

Because Prisoner 10 was counted during the first iteration, the executions
will proceed as such: 10-1-2 4-5-7 8-10, so prisoners 2 and 7 will be killed

Third iteration: 1 4 5 8 10
8-10-1 4-5-8 10, so prisoners 1 and 8 executed.

Fourth Iteration:  10-4-5 10
Prisoner 5 is executed.

Fifth iteration:  10-4 10
Prisoner 10 is executed

Since the sole survivor is prisoner 4, he is released.

You are an unlucky prisoner caught by Carnage Maximum.  Prior to lining up the prisoners, he reveals the number of prisoners he has and his value of kill_every for the day.  Your job is to figure out which prisoner you need to be in order to survive.  Write a MATLAB script that takes the values of num_prisoners and kill_every.  The output will be survivor, which is the position of the person who survives.  If you write your script quickly enough, that person will be you.

Good luck!

Solve

Solution Stats

742 Solutions
193 Solvers

Last Solution submitted on Jan 12, 2023

Last 200 Solutions

Problem Comments

8 Comments

8 Comments

Show 5 older comments

Tim on 4 Dec 2012

I seem to get 1773 for test case 6.

@bmtran (Bryant Tran) on 4 Dec 2012

I also get 1773 for test case 6

James on 4 Dec 2012

I'll look into it a bit later on. In the meantime, that test case is deleted, so you can see if your solutions work for the rest of the test cases.

Andrew Newell on 11 Jul 2013

An interesting test case would have kill_every=1.

Elmar Zander on 27 Mar 2017

Am I the only one who finds the problem description really lacking? WTF does it mean "Because Prisoner 10 was counted during the first iteration,..." IMHO this is just blah and not a well-defined problem definition...

Christopher Lanning on 3 Oct 2022

At least 2 of the test cases do not match what I find if I run the sequence by hand on paper. Specifically:
num_prisoners = 30; kill_every = 5;
Survivor is prisoner number 14, not number 3
and,
num_prisoners = 10; kill_every = 10;
Survivor is prisoner number 6, not number 8

Based on other comments, it looks like the test cases may have changed at some point. I believe at least these two (and likely a couple others) are now incorrect.

Christian Schröder on 6 Oct 2022

@Christopher Lanning, decimate(10, 10) = 8 is correct; perhaps you made a mistake on paper. When doing this by hand, it's easiest to count kill_every steps, wrapping around at the end of the line and skipping over crossed-out entries (think Eeny Meeny Miny Moo). Prisoner 6 gets killed in the 4th iteration.

Christian Schröder on 6 Oct 2022

Also, I agree with Andrew Newell's earlier comment that there should be a test case for kill_every = 1.

Solution Comments

Solution 9243390

1 Comment

1 Comment

Christian Schröder on 6 Oct 2022

This fails if kill_every = 1.

Solution 3088591

2 Comments

2 Comments

Jimmy Sølvsteen Nielsen on 6 Oct 2020

I passed test 3 by using a WHILE loop but not a recursive function. IMHO the method should not affect the test cases but in this case it does.

Akrem Hadji on 19 Oct 2020

This is a hard one it took me a while to solve it. Thanks God Roman empire has fallen log time ago otherwise I would have no chance to escape decimation.

Solution 3088451

1 Comment

1 Comment

Jimmy Sølvsteen Nielsen on 6 Oct 2020

test 3 fails. not because of an infinite recursion in my program but owing to the lack of memory. My program is correct

Solution 1163863

1 Comment

1 Comment

bainhome on 5 May 2018

really wonderful thought!!! One of the best solution!

Solution 196399

4 Comments

4 Comments

Show 1 older comment

Ben Petschel on 21 Sep 2016

how does this work?

James on 22 Sep 2016

To paraphrase Arthur C Clarke: "Any sufficiently advanced Cody solution from Alfonso is indistinguishable from magic."

Jan Orwat on 23 Sep 2016

sdrawkcaB

Michael Cappello on 16 Sep 2018

Generalized Josephus problem

Solution 181680

1 Comment

1 Comment

Alfonso Nieto-Castanon on 25 Jan 2013

great solution! (effectively working backwards to get the initial state)

Problem Recent Solvers193

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 1092. Decimation

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers193

Suggested Problems

More from this Author80

Problem Tags

Community Treasure Hunt

Problem 1092. Decimation

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers193

Suggested Problems

More from this Author80

Problem Tags

Community Treasure Hunt

Players