How to find the smallest N

Question

I have a code that determines the survivor from a list of names to walk the plank in this scenario, the last person in the list survives the code i have for this is:

names =  ["Andrew", "Brenda", "Craig", "Deidre", "Edward", "Felicity", "Greg", "Harriet"]
def survivor(names, step):
    Next = step - 1
    while len(names) > 1:
        names.pop(Next)
        Next = Next + step
        Next = (Next - 1) % len(names)
        print names

    return names[0]

this works to return the survivor based on what put in step but i also need to work out the smallest N for step for a person to survive e.g. 3 for greg and 2 for andrew.

the codes i have tried for this are:

assert name in names
for step in survivor(names, step):
    if survivor == name:
        return step

but it keeps saying local variable step referenced before assignment or global step is not defined.

and

assert name in names
for step in itertools.count(1):
    if survivor(names, step) == name:
        return step

but this returns

['Brenda', 'Craig', 'Deidre', 'Edward', 'Felicity', 'Greg', 'Harriet']

['Craig', 'Deidre', 'Edward', 'Felicity', 'Greg', 'Harriet']

['Deidre', 'Edward', 'Felicity', 'Greg', 'Harriet']

['Edward', 'Felicity', 'Greg', 'Harriet']

['Felicity', 'Greg', 'Harriet']

['Greg', 'Harriet']

['Harriet']

which is not what i want

Can anyone help me work this out?

This question is about the [Josephus problem](http://en.wikipedia.org/wiki/Josephus_problem). — Kos, Nov 21 '12 at 17:43

score 2 · Answer 1 · answered Nov 21 '12 at 17:59

This loop does not do what you expect. What you want should be similar to this:

def shortest(name):
    assert name in names
    for step in range(1, len(names)+1):
        #Go through all possible steps, from 1 to number of items (the +1 is to include the last item too)
        if survivor(names[:], step) == name: # Check that this item matches
            return step # Break out of the loop when you get to it

The itertools.count(1) would work, but you could just as well use a while True and it makes no sense to have a step greater than the length of the names list.

Your problem was probably with the names array becoming empty after the first name. Because you are poping out all the elements, and modifying the names list which is in the global scope (defined out of the function). So you have to duplicate it (using either names[:] or list(names) which will both achieve the same purpose).

That's the test I made:

for n in names:
    print n, shortest(n)

And the output:

Andrew 2
Brenda None
Craig 5
Deidre 7
Edward None
Felicity 4
Greg 3
Harriet 1

Note: I don't know why there are Nones in there... but the examples you gave did match!

Thank you @jadkik94 i really appreciate it, been trying for ages — user1839493, Nov 21 '12 at 18:20

score 1 · Answer 2 · edited May 23 '17 at 11:56

1

for step in survivor(names, step):

Notice how you're using step twice here. How is Python supposed to pass it to the survivor function before it gets it out of that function?

I think what you want is the range function. This will loop through every step value from 1 to the length of the list of names:

for step in range(1, len(names)):

Your itertools.count version should also work, now that I think about it. Are you checking the return value of this function or just looking at what it prints out? The output looks like it's from this line:

print names

One other thing is that your function changes the original list every time it runs, since you change names and you're not making a copy. Maybe you want to make a copy before changing it:

def survivor(names, step):
    names = names[:]
    # etc

See this question for why names[:] creates a copy of the list.

edited May 23 '17 at 11:56

Community

1
1

answered Nov 21 '12 at 17:33

Brendan Long

53,280
21
146
188

i have been trying it every way i can think of, i just cant get it working, im not sure how – user1839493 Nov 21 '12 at 17:35
@user1839493 I updated the answer with what I think you're looking for. – Brendan Long Nov 21 '12 at 17:38
it returns an integer which is what i need it to do but it doesnt return the right number i have been working with step = 3 which means greg survives but when i use your suggested piece of code it returns 1 when it should be 3 – user1839493 Nov 21 '12 at 17:42
@user1839493 I think it's doing that because you alter the original list every time you call this function. See my last edit. – Brendan Long Nov 21 '12 at 17:45
even with the edit it does the same thing, playing around with it it seems the number entered in the brackets for the range function is what gets returned – user1839493 Nov 21 '12 at 17:58
@user1839493 Sorry I had a typo, should be `names = names[:]` to make the copy. – Brendan Long Nov 21 '12 at 18:06

How to find the smallest N

2 Answers2