Few companies ask the below brain teaser to the candidates during the interview.
The director of a prison offers 100 death row prisoners, who are numbered from 1 to 100, a last chance. A room contains a cupboard with 100 boxes. The director randomly puts one prisoner’s number in each closed boxes. The prisoners enter the room, one after another. Each prisoner may open and look into 50 boxes in any order. The boxes are closed again afterwards. If, during this search, every prisoner finds his number in one of the boxes, all prisoners are pardoned. If just one prisoner does not find his number, all prisoners die. Before the first prisoner enters the room, the prisoners may discuss strategy — but may not communicate once the first prisoner enters to look in the boxes. What is the prisoners’ best strategy?
But what if it is a coding challenge:
The director of a prison offers N death row prisoners, who are numbered from 1 to N, a last chance. A room contains a cupboard with N boxes. The director randomly puts one prisoner’s number in each closed boxes. The prisoners enter the room, one after another. Each prisoner may open and look into N/2 boxes in any order. The boxes are closed again afterwards. If, during this search, every prisoner finds his number in one of the boxes, all prisoners are pardoned. If just one prisoner does not find his number, all prisoners die. Before the first prisoner enters the room, the prisoners may discuss strategy — but may not communicate once the first prisoner enters to look in the boxes. What is the prisoners’ best strategy?
Write a code for scenario for any one prisoner.
The coding solution was originally published in my book “Brain Teasers with Coding For Data Scientist”. Puzzles from that book are published on this link. Also, check my books “Brain Teasers with Coding For Data Scientist 2: 9 New Computational Puzzles” and “Puzzles with Coding: Puzzles for Everyone” and “Computational Puzzles To Flex Your Brain: 50 original puzzles to sharpen computing mind and mathematical skills” at Amazon. For purchasing my books or related queries, feel free to contact me. In these books, you will find interesting brain teasers those are suitable for coders as well as non-coders. Coding solutions are also provided with Python code. So, grab a copy of those books and jump into the world of fascinating and exciting brain teasers.
Solution:
There is a strategy that provides a better survival probability than randomly opening the boxes.
To describe the strategy, not only the prisoners, but also the boxes are numbered from 1 to N. The strategy is now as follows:
1.) Each prisoner first opens the box with his own number.
2.) If that box contains his number then he is successful.
3.) Otherwise, the box contains the number of another prisoner and he next opens the box with this number.
4.) The prisoner repeats steps 2 and 3 until he finds his own number or has opened N/2 drawers.
Coding Solution:
#Strategy for an individual prisoner
from random import randint
# Flling N Boxes randomly
def fillBoxes(N, NBox):
r = randint(1, N)
if r in NBox:
fillBoxes(N, NBox)
else:
NBox.append(r)
if(len(NBox) <N):
fillBoxes(N, NBox)
return NBox
# Finding Own Number
def findingNumber(chosenOne, NBox, checkBoxNo, count, N):
if count >= N/2:
if(NBox[checkBoxNo-1] == chosenOne):
print('Number is found')
else:
print('Number is not found')
return
elif(NBox[checkBoxNo-1] == chosenOne):
print('Number is found')
return 1
else:
print('At Step:', count+1,': ','checked box number:', NBox[checkBoxNo-1])
findingNumber(chosenOne, NBox,NBox[checkBoxNo-1], count+1, N)
# N Number of Prisoners
N = int(input("Enter N:"))
if N < 1:
print("N should be greater than 0")
exit()
print('Total number of Prisoners', N)
# Fill N boxes randomly with numbers 1 to N
NBox = []
NBox = fillBoxes(N, NBox)
print('Arrangement of Boxes', NBox)
chosenOne = randint(1, N)
print('Prison No.', chosenOne,'is sent')
print('At step: 1: checked box number:', chosenOne)
findingNumber(chosenOne, NBox, chosenOne, 1, N)
Note: (Keeping non-coder readers in mind, code optimization may not be fully utilized.)
Test Output 1:
Enter N:75
Total number of Prisoners 75
Arrangement of Boxes [39, 46, 55, 19, 21, 45, 12, 52, 14, 53, 7, 34, 62, 18, 37, 70, 31, 67, 2, 71, 63, 51, 24, 57, 13, 5, 41, 49, 25, 36, 74, 66, 22, 27, 48, 8, 30, 44, 3, 42, 64, 47, 1, 65, 23, 38, 68, 15, 69, 16, 59, 56, 72, 29, 73, 33, 26, 20, 60, 43, 4, 54, 35, 61, 50, 75, 40, 32, 6, 58, 17, 9, 28, 11, 10]
Prison No. 73 is sent
At step: 1: checked box number: 73
At Step: 2 : checked box number: 28
At Step: 3 : checked box number: 49
At Step: 4 : checked box number: 69
At Step: 5 : checked box number: 6
At Step: 6 : checked box number: 45
At Step: 7 : checked box number: 23
At Step: 8 : checked box number: 24
At Step: 9 : checked box number: 57
At Step: 10 : checked box number: 26
At Step: 11 : checked box number: 5
At Step: 12 : checked box number: 21
At Step: 13 : checked box number: 63
At Step: 14 : checked box number: 35
At Step: 15 : checked box number: 48
At Step: 16 : checked box number: 15
At Step: 17 : checked box number: 37
At Step: 18 : checked box number: 30
At Step: 19 : checked box number: 36
At Step: 20 : checked box number: 8
At Step: 21 : checked box number: 52
At Step: 22 : checked box number: 56
At Step: 23 : checked box number: 33
At Step: 24 : checked box number: 22
At Step: 25 : checked box number: 51
At Step: 26 : checked box number: 59
At Step: 27 : checked box number: 60
At Step: 28 : checked box number: 43
At Step: 29 : checked box number: 1
At Step: 30 : checked box number: 39
At Step: 31 : checked box number: 3
At Step: 32 : checked box number: 55
Number is found
Test Output 2:
Enter N:110
Total number of Prisoners 110
Arrangement of Boxes [106, 38, 62, 67, 59, 82, 79, 105, 47, 49, 5, 50, 46, 104, 76, 69, 94, 48, 86, 109, 63, 32, 1, 16, 13, 101, 30, 18, 56, 8, 72, 58, 14, 43, 93, 96, 44, 55, 33, 4, 25, 81, 78, 66, 83, 17, 10, 26, 22, 15, 65, 77, 23, 57, 74, 20, 40, 34, 6, 87, 54, 21, 71, 19, 84, 42, 45, 110, 36, 24, 89, 51, 88, 52, 102, 103, 95, 98, 53, 41, 107, 31, 108, 90, 80, 68, 35, 11, 12, 29, 61, 73, 3, 91, 7, 2, 39, 28, 64, 60, 92, 37, 75, 100, 27, 9, 97, 85, 99, 70]
Prison No. 10 is sent
At step: 1: checked box number: 10
At Step: 2 : checked box number: 49
At Step: 3 : checked box number: 22
At Step: 4 : checked box number: 32
At Step: 5 : checked box number: 58
At Step: 6 : checked box number: 34
At Step: 7 : checked box number: 43
At Step: 8 : checked box number: 78
At Step: 9 : checked box number: 98
At Step: 10 : checked box number: 28
At Step: 11 : checked box number: 18
At Step: 12 : checked box number: 48
At Step: 13 : checked box number: 26
At Step: 14 : checked box number: 101
At Step: 15 : checked box number: 92
At Step: 16 : checked box number: 73
At Step: 17 : checked box number: 88
At Step: 18 : checked box number: 11
At Step: 19 : checked box number: 5
At Step: 20 : checked box number: 59
At Step: 21 : checked box number: 6
At Step: 22 : checked box number: 82
At Step: 23 : checked box number: 31
At Step: 24 : checked box number: 72
At Step: 25 : checked box number: 51
At Step: 26 : checked box number: 65
At Step: 27 : checked box number: 84
At Step: 28 : checked box number: 90
At Step: 29 : checked box number: 29
At Step: 30 : checked box number: 56
At Step: 31 : checked box number: 20
At Step: 32 : checked box number: 109
At Step: 33 : checked box number: 99
At Step: 34 : checked box number: 64
At Step: 35 : checked box number: 19
At Step: 36 : checked box number: 86
At Step: 37 : checked box number: 68
At Step: 38 : checked box number: 110
At Step: 39 : checked box number: 70
At Step: 40 : checked box number: 24
At Step: 41 : checked box number: 16
At Step: 42 : checked box number: 69
At Step: 43 : checked box number: 36
At Step: 44 : checked box number: 96
At Step: 45 : checked box number: 2
At Step: 46 : checked box number: 38
At Step: 47 : checked box number: 55
At Step: 48 : checked box number: 74
At Step: 49 : checked box number: 52
At Step: 50 : checked box number: 77
At Step: 51 : checked box number: 95
At Step: 52 : checked box number: 7
At Step: 53 : checked box number: 79
At Step: 54 : checked box number: 53
At Step: 55 : checked box number: 23
Number is not found
