"100 prisoner problem" (attempts)

[boris602]

Hello guys, i have found a code in the internet that i changed a bit. I tested it for a small group of prisoners , but the problem is, that my result shows always "True".

def my_prisoners(p):
    for i in range(6):
        attempt=0
        idx=i
        found= False
        while attempt<3:
            if p[idx]==i:
                found=True
                break
            else:
                idx=p[idx]
                attempt += 1
        if not found:
            return False
    return True

my_prisoners([5,4,3,2,1,0])

True

Here for example the cycle of the permutation has the longest range 5->4->3->2->1->0->5. However, it still shows "True" and should actually show "False". Only if i change "while attempt<3" to "while attempt<1" it shows False and "True" only for [0,1,2,3,4,5], as its supposed to be. I would be really grateful for some helpful advice.

[j.crater]

I don't really understand what the code should be doing and what are the expected results. But in line 11:
idx=p[idx]
you set idx, but in the very next for iteration you change it with idx=i, and line #11 will have no effect. Is this where some logic problem may be hiding?

[boris602]

I don't really understand what the code should be doing and what are the expected results.

The idea in this code should be that every prisoner gets the number 0,1,2,3,4,5 and go into a room where 6 boxes with the same numbers are randomly sorted. In my example [5,4,3,2,1,0]-> ([5]=box 0 , [4]=box 5 and so on). However, every prisoner should start with his own number. For example 0 opens in my example in box 0 the number[5]. So he goes to to box [5] and opens the number[4]. Now he goes to box[4] and opens number[3]. However, now he has reached 3 attempts and has not found number 0 and it should return "False"

[j.crater]

0 opens in my example in box 0 the number[5]. So he goes to box [5] and opens the number[4]

I don't understand this part. Doesn't box[5] contain number[1]?

[boris602]

well i know see my own problem,because my cycle(5,4,3,2,1,0),doesnt really match with the code. I gonna try to change it first, because box5 really should contain number 1 in this code, what actually is not true.

---

i actually looked at the code, my cycle(5,4,3,2,1,0) is equal to [5,0,1,2,3,4] and then the code does exactly what i should,it shows "False". I was thinking it was the same for some reason, but thank u for paying attention on it, because i was wondering why it doesnt work.

[boris602]

I dont want to spam,so i just write it here. Since the code seems to work , i want to change it in a way , that my index starts of 1.

def my_prisoners(p):
    for i in range(6):
        attempt=0
        idx=i
        found= False
        while attempt<3:
            if p[idx]==i:
                found=True
                break
            else:
                idx=p[idx]
                attempt += 1
        if not found:
            return False
    return True
 
my_prisoners([0,1,2,3,4,5])

True

Now i change "idx=i" to idx=i+1 and "p[idx]==i" to p[idx]==i+1

def my_prisoners(p):
    for i in range(6):
        attempt=0
        idx=i+1
        found= False
        while attempt<3:
            if p[idx]==i+1:
                found=True
                break
            else:
                idx=p[idx]
                attempt += 1
        if not found:
            return False
    return True

my_prisoners([1,2,3,4,5,6])

False

Why it does not work?

[j.crater]

Your first attempt will always work because the "p" list you pass as argument matches the numbers you get from range(6). p[idx]==i - this condition is True in the first attempt already.

Whereas in the second case, 3 attempts aren't enough for p[idx]==i+1 to be True. In each iteration p[idx] is always ahead of [i+1]. I added a few prints in the code so you see what is happening:

def my_prisoners(p):
    for i in range(6):
        attempt = 0
        idx = i + 1
        found = False
        while attempt < 3:
            print("ATTEMPT {} --- i: {}, idx: {}, p[idx]: {}, i+1]: {}".format(attempt, i, idx, p[idx], i+1))
            if p[idx] == i + 1:
                found = True
                break
            else:
                idx = p[idx]
                attempt += 1
        if not found:
            return False
    return True

Output:
ATTEMPT 0 --- i: 0, idx: 1, p[idx]: 2, i+1: 1
ATTEMPT 1 --- i: 0, idx: 2, p[idx]: 3, i+1: 1
ATTEMPT 2 --- i: 0, idx: 3, p[idx]: 4, i+1: 1

[boris602]

def my_prisoners(p):
    for i in range(6):
        attempt=0
        idx=i
        found= False
        while attempt<3:
            if p[idx]==i+1:
                found=True
                break
            else:
                idx=p[idx]
                attempt += 1
        if not found:
            return False
    return True

my_prisoners([1,2,3,4,5,6])

True

Now it at least works if its correctly sorted, i just dont understand why

my_prisoners([2,1,3,4,5,6])
 
False

shows "False". The attempt should be exactly 1

[j.crater]

False result is as expected with this input and current code. Just print out some variables, something like I did in post #7, and you will see why that happens.

[boris602]

well i actually found the mistake already, just trying to correct it, i need to make -1.For example this would work until 1 stays on "i=0"

def my_prisoners(p):
    for i in range(6):
        attempt=0
        idx=i
        found= False
        while attempt<3:
            if p[idx]==i+1:
                found=True
                break
            else:
                idx=p[idx]-p[0]
                attempt += 1
        if not found:
            return False
    return True

my_prisoners([1,2,3,4,6,5])

True

However i want to replace p[0] against something like 1.Just not sure how to do it yet.