# 100 gunmen in circle kill next person

The question is here.

100 people are standing in a circle with gun in their hands. 1 kills 2, 3 kills 4, 5 kills 6 and so on till we are left with only one person. Who will be the last person alive. Write code to implement this efficiently.

Here is my Java implementation:

public static void main(String[] args) throws Exception {
int numberOfGuys = 100;
MyObject[] objetList = new MyObject[numberOfGuys];
for(int i=1;i<numberOfGuys+1;i++) {
objetList[i-1] = new MyObject(i);
}
boolean oneElementLeft = false;
while(!oneElementLeft) {

for(int i=0;i<objetList.length;i++) {
if(i != objetList.length-1 && (i+1)%2==1) {
objetList[i+1]=null;
}
if(i == objetList.length-1 && objetList[i] != null) {
objetList[0]=null;
}
}
List<MyObject> newList = new ArrayList<MyObject>();
for (MyObject myObject:objetList) {
if(myObject != null) {
}
}
objetList = new MyObject[newList.size()];
for(int i=0;i<newList.size();i++) {
objetList[i] = newList.get(i);
}
if(objetList.length==1) {
oneElementLeft = true;
}
}
System.out.println(objetList[0].getIndex());
}


I am not a math guy, so I do not really understand the clever solutions with formulas, recursion etc...

Any review or better code with explanations are welcome.

-
Rethink your q, pls. Start from the end. 100 is killed by 99. Who kills 99? 98. Who kills 98? If you start with 1 kills 2, who kills 3? The way you stated it, 1 kills everyone :-P or, what do you mean? Draw with pencil and paper. –  Thufir Jul 13 at 20:19
@Thufir For simplicity's sake, consider 5 people: 1 kills 2, (2 is dead), 3 kills 4, (4 is dead), 5 kills 1, (1 is dead, 2 is dead), 3 kills 5 (4 was already dead), 3 wins. –  Simon André Forsberg Jul 13 at 22:26
ah, that's fine. I thought that the question had been mis-stated. In terms of an answer, I think it's necessary, or much easier, at least, to use a link list. –  Thufir Jul 13 at 22:41
@Thufir I do not think trying to go backwards will work for every problem on earth. :) Can you please provide a solution with LinkedList? I think it will be a little cleaner, you are right, but it will essentially work very similar, right? –  Koray Tugay Jul 14 at 5:17
@KorayTugay going "backwards" would only be applicable were it that 100 was killed by 99, who was killed by 98, etc. which is not your problem. which does not rule out recursion as being useful. I just wanted to be clear on what your problem was. –  Thufir Jul 14 at 8:56
show 1 more comment

The accepted answer in the linked question uses a cirucular linked list, which is the data structure that most closely represents this situation. That answer shows how to do that implementation, so I'll instead focus on the approach you look to be taking, which can be equally valid if it produces equivalent results.

public static void main(String[] args) throws Exception {


Why does your main method throw Exception? This is useless and potentially confusing. Your code does not encounter any expected exceptions, so why are you telling the reader to expect one? The exception you are telling them to expect is any exception, which is itself completely unhelpful. If your program encounters an uncaught exception, it will die just the same. Drop the throws Exception.

int numberOfGuys = 100;


Here, this is fine, but many people would probably just move it outside the method as static final int NUMBER_OF_GUYS = 100; since it is essentially a constant (unless you are planning to vary it with input in another iteration of the program).

MyObject[] objetList = new MyObject[numberOfGuys];


Two major issues here. First is naming. MyObject is a terrible name that tells the reader nothing of the nature of this class. A better name might be Gunman or Shooter, etc. For the variable name, objetList is also a terrible name. First, it looks very close to objectList, which increases the possibility of misspellings. It also says little to the nature of the variable, and what it does say is wrong. The suffix "List" might be interpreted to mean that this is a List object, but it is not. A better name might be gunmen or shooters (preferably matching off of the class name of the objects it holds).

The second major issue is the data structure chosen. We know that we will be removing elements from this structure, but we also know this is not efficient with a primitive array. Either we delete by using nulls, having to check that condition through the loop, or we delete by making a copy of the array, sans an element, each time we remove an element. A data structure built for this type of scenario is a List. There are several to choose from, each giving a potentially different performance profile, but we can just pick one to start and change that later if performance demands are not met.

for(int i=1;i<numberOfGuys+1;i++) {
objetList[i-1] = new MyObject(i);
}


First, spacing is important. It is much harder to read code that does not have spacing around operators and such. Second, you perform excess operations that confuse what the loop is doing. Rather than start at one, go to numberOfGuys + 1, and insert at index objetList[i-1], start at 0. It would look more like this:

for(int i = 0; i < numberOfGuys; i++) {
objetList[i] = new MyObject(i + 1);
}


boolean oneElementLeft = false;
while(!oneElementLeft) {
...
if(objetList.length==1) {
oneElementLeft = true;
}
}


(SPOILER: Read all the way through this part before changing the code.)

This code tells a story, but it has a lot of noise in it. We test against a boolean, and exit out of the loop if it changes. We will only change that boolean based on a boolean test (objetList.length == 1) checked at the end of the loop. We already have a loop structure that does this more succinctly: the do-while loop! We could rewrite it so that we just have do { ... } while(objetList.length != 1); So much cleaner! And wrong. The story this code tells is misleading, and is in fact buggy. If objetList.length is already 1, we don't want to do anything! What we want is a simple while loop without the need for the flag:

while(objetList.length > 1) {
...
}


for(int i=0;i<objetList.length;i++) {
if(i != objetList.length-1 && (i+1)%2==1) {
objetList[i+1]=null;
}
if(i == objetList.length-1 && objetList[i] != null) {
objetList[0]=null;
}

}


Again, spacing.

These conditionals do not really tell a clear story. First of note, (i+1)%2 == 1 is asking if i plus one is odd. What it is really asking, though, is if i is even, or the same thing more succinctly, i % 2 == 0. (You will also see this written as i & 1 == 0 on occasion). Looking more generally, though, we are nulling the odd elements, and the first element if the list is an odd length. The conditionals don't come out and say this clearly, though. We check if we are at the end of the list every iteration, and do something when we reach the end only under certain special conditions. It is not totally clear that the condition is when the list is an odd length, either. More clearly, we can write:

for(int i = 0; i < objetList.length - 1; i += 2) {
objetList[i + 1] = null;
}

if(objetList.length % 2 == 1) {
objetList[0] = null;
}


Also note the vertical spacing used here. We often need space in both directions to make code the most readable.

List<MyObject> newList = new ArrayList<MyObject>();
for (MyObject myObject:objetList) {
if(myObject != null) {
}
}
objetList = new MyObject[newList.size()];
for(int i=0;i<newList.size();i++) {
objetList[i] = newList.get(i);
}


Here the code is basically just shuffling array data. This is the biggest indicator that a primitive array is the wrong data structure to be using.

I wrote the following version that accomplishes the same thing in a similar (non-circular) manner. It can probably be improved by using an iterator inside of it, but it suffices on its own.

Main class:

public class Main
{
public static final int NUMBER_OF_GUNMEN = 100;

public static void main(String[] args) {
List<Gunman> gunmen = new ArrayList<>(NUMBER_OF_GUNMEN);
for(int i = 1; i <= NUMBER_OF_GUNMEN; i++) {
}

while(gunmen.size() > 1) {
for(int i = 0; i < gunmen.size(); i++) {
Gunman killer = gunmen.get(i);
Gunman killed = gunmen.remove((i + 1) % gunmen.size());
System.out.println(killer.getNumber() + " kills " + killed.getNumber());
}
}

System.out.println("\n" + gunmen.get(0).getNumber() + " lives another day...");
}
}


Gunman class:

public class Gunman
{
private int number;

public Gunman(int number) {
this.number = number;
}

public int getNumber() {
return number;
}
}

-
Thanks, great comments. You are right in most of (if not all) of your comments. Also Oracle suggests convention: for (initialization; condition; update) { statements; } so I will fix my template according to this! –  Koray Tugay Jul 14 at 5:18
The code is simple, which is nice. However, the problem asks for efficient code, and ArrayList.remove() is not efficient. The first shot, killing number 2, causes 98 elements to be copied over. –  200_success Jul 14 at 5:38
@200_success You are right. My code tries to mirror his approach. I address performance at three points. First, I note that circular linked list is the most correct structure to use. Later, I note that we can vary which list structure we use through polymorphism based on performance criteria. Finally, I note that my implementation can be improved with iterators. All in all, with ArrayList or with LinkedList, 100 elements gets done in ~0.1s for me. The efficiency in this is that I put working code up now instead of spending 20 minutes researching Java lists to optimize milliseconds. –  cbojar Jul 14 at 15:11
Fair enough. I've upvoted it as a very thorough answer. –  200_success Jul 14 at 15:14

## Critique

I think the following code was implied:

public class MyObject {
private int index;

public MyObject(int i) {
this.index = i;
}

public int getIndex() {
return index;
}

public static void main(String[] args) {
…
}
}


That works, but MyObject is the least informative name for a class possible. Gunman would be much better. Similarly, I suggest renaming objetList to gunmen.

The oneElementList variable is pointless. You could just say

while (objetList.length != 1) { … }


Reconsolidating the list after reaching the end is inefficient. You want to either implement a , or as I've done below, simulate a circular buffer by using an iterator. Since the problem calls for elements to be spliced out frequently, this is one of those rare situations where a is useful.

## Suggested solution

Since the code for the shootout loop can get rather complex, it's worth making an effort to simplify it. By using an iterator, we can relieve ourselves of the need to use any array indices at all.

In this problem, a gunman is just a number. I've represented it using an Integer.

public class CircularGunmenIterator<T> implements Iterator<T> {

private List<T> list;
private Iterator<T> iter;

public CircularGunmenIterator(List<T> list) {
this.list = list;
this.iter = list.iterator();
}

@Override
public boolean hasNext() {
// Continue as long as there is a shooter and a victim
return this.list.size() >= 2;
}

@Override
public T next() {
if (!this.iter.hasNext()) {
// Wrap around, creating the illusion of a circular buffer
this.iter = this.list.iterator();
}
return this.iter.next();
}

@Override
public void remove() {
this.iter.remove();
}

public static void main(String[] args) {
// Create the gunmen
for (int i = 1; i <= 100; i++) {
}

// Shootout!
Iterator<Integer> ringIter = new CircularGunmenIterator<Integer>(gunmen);
while (ringIter.hasNext()) {
Integer shooter = ringIter.next();
Integer victim  = ringIter.next();
System.out.printf("%2d shoots %2d\n", shooter, victim);
ringIter.remove();  // Bang!
}
System.out.println("Last one alive: " + gunmen.get(0));
}
}

-
Great solution, thank you very much. Very clear as well. –  Koray Tugay Jul 14 at 5:20