1

I am trying to solve a assignment where are 13 lights and starting from 1, light is turned off at every 5th light, when the count reaches 13, start from 1st item again. The function should return the order of lights turned off. In this case, for a list of 13 items, the return list would be [5, 10, 2, 8, 1, 9, 4, 13, 12, 3, 7, 11, 6]. Also, turned off lights would not count again.

So the way I was going to approach this problem was to have a list named turnedon, which is [1,2,3,4,5,6,7,8,9,10,11,12,13] and an empty list called orderoff and append to this list whenever a light gets turned off in the turnedon list. So while the turnedon is not empty, iterate through the turnedon list and append the light getting turned off and remove that turnedoff light from the turnedon list, if that makes sense. I cannot figure out what should go into the while loop though. Any idea would be really appreciated. 

def orderoff():
    n=13
    turnedon=[]
    for n in range(1,n+1):
        turnedon.append(n)
    orderoff=[]

    while turneon !=[]:
Improve this question
5
  • [5, 10, 2, 8, 1, 9, 4, 13, 12, 3, 7, 11, 6] does not look correct. 5-1 = 4, 10-5 = 5, 2-10 = 5 -- numbers are different, 4 or 5 Commented Jan 16, 2020 at 9:58
  • 1
    @lenik - "Also, turned off lights would not count again." You count 5 steps to light #5, then 5 steps to light #10, then 5 steps to light #2, then the next 5 steps goes to light #8 because #5 is already off so you shouldn't count it. The solution based on pure modulo arithmetic won't give correct results because it doesn't have this behaviour. Commented Jan 16, 2020 at 10:00
  • What is your expected output if the number of items and the step are not coprime? Commented Jan 16, 2020 at 10:00
  • @FBruzzesi With e.g. 4 lights and a step size of 2, the first light turned off is #2, then #4, then the remaining lights are #1 and #3 so stepping by 2 means #3 is turned off next. So the output would be [2, 4, 3, 1]. Commented Jan 16, 2020 at 10:01
  • @kaya3 thank you for the clarification, your previous comment made me realize that already. Commented Jan 16, 2020 at 10:04

3 Answers 3

Reset to default
2

This problem is equivalent to the well-known Josephus problem, in which n prisoners stand in a circle, and they are killed in a sequence where each time, the next person to be killed is k steps around the circle from the previous person; the steps are only counted over the remaining prisoners. A sample solution in Python can be found on the Rosetta code website, which I've adapted slightly below:

def josephus(n, k):
    p = list(range(1, n+1))
    i = 0
    seq = []
    while p:
        i = (i+k-1) % len(p)
        seq.append(p.pop(i))
    return seq

Example:

>>> josephus(13, 5)
[5, 10, 2, 8, 1, 9, 4, 13, 12, 3, 7, 11, 6]
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Thank you!! However, what is k representing in the function?
k is the number of steps you count each time; 5 in your example.
also may I ask in the line, i = (i+k-1) % len(p), i is first 4 and then 8. So a[4]=5 so is it right but since a[8]=9, it would not be the right number to come next? Could you explain the logic? Thanks!
The list is originally [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13], so the value at index 4 is 5. But the value at index 4 is removed from the list, so it becomes [1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13], and then the new value at index 4 + 5 - 1 = 8 is 10, not 9. The -1 in the formula is to compensate for the fact that the previous value gets removed from the list.
1

This works, but the results are different from yours:

>>> pos = 0
>>> result = []
>>> while len(result) < 13 :
...     pos += 5
...     pos %= 13
...     if pos not in result :
...         result.append(pos)
... 
>>> result = [i+1 for i in result]  # make it 1-based, not 0-based
>>> result
[6, 11, 3, 8, 13, 5, 10, 2, 7, 12, 4, 9, 1]
>>>
Improve this answer

Comments

1

I think a more optimal solution would be to use a loop, add the displacement each time, and use modules to keep the number in range

def orderoff(lights_num,step):
    turnd_off=[]
    num =0
    for i in range(max):
        num =((num+step-1)%lights_num)+1
        turnd_off.append(num)
    return turnd_off

print(orderoff(13))
Improve this answer

2 Comments

Just for best practice, I would suggest to avoid using the name max for a variable, since it is a built-in function. Moreover since you create a function, it is worth it to pass a step parameter instead of hard-coding it
your result: [5, 10, 2, 7, 12, 4, 9, 1, 6, 11, 3, 8, 13] is different from what OP quoted

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.