Prisoner hat problem
This is a problem about a prison where an evil wizard comes and tell the 64 inmates there that tomorrow he will come and put a hat of either black or white color on their head after making them stand in a line. So that they can only see the prisoners in front of them and their hat. He would then start from the inmate at the very end who can see everyone else's hat except for his own. He would ask each of them what color is their hat. They can only answer black or white and no other words. If they are correct he would leave them otherwise he will kill them. They have a whole night to plan their strategy once he puts them in line they cannot communicate.
The problem is to find out a strategy which would allow maximum number of inmates to escape death.
[sourcecode language="python"]
# -*- coding: utf-8 -*-
"""
Created on Wed Nov 16 21:03:20 2016
@author: Sumant
The hats take the input as a STRING of Black and White
Black: Represents even number of black hats
White: Represents odd number of black hats
Black = 1
White = 0
def whatTheySee()
returns an array which contains the parity of black hats they see in front
of them
def whatTheySay()
returns an array which contains what they say
Algorithm: WhatTheySay
We need to use the array whatTheySee and we return an array which contains
what each person should say: except for the first entry which corresponds to
the last number we see. All others are always correct.
The nth position of the array we return populates itself with the responses
of previous n-1 responses and add what the parity of black hats the person
standing at nth position sees.
Input: WWWWBB
Output: WWWWBB
Input: BBBBB
Output: BBBBB
Input: BBBB
Output: WBBB
Input: BWBWBB
Output: WWBWBB
"""
hats="BWBWBB"
def binaryTohat(hat):
change=[]
for i in hat:
if i == 1:
change.append('B')
else:
change.append('W')
return change
def hatTobinary(hat):
change=[]
for i in hat:
if i == 'B':
change.append(1)
else:
change.append(0)
return change
HATS=hatTobinary(hats)
def whatTheySee(hats):
a=[]
for j in range(len(hats)):
sum = 1
for i in range(j+1,len(hats)):
sum= sum+HATS[i]
sum = sum %2
a.append(sum)
return a
def whatTheySay(hats):
a=[]
val=0
a.append(hats[0])
for i in range(1,len(hats)):
val=sum(a)+hats[i]
a.append(val%2)
return a
def stringArraytoString(st):
a=""
for i in st:
a+=i
return a
print("What wizard see",hats)
print("What they say",stringArraytoString(binaryTohat(whatTheySay(whatTheySee(HATS)))))
[/sourcecode]
The problem is to find out a strategy which would allow maximum number of inmates to escape death.
[sourcecode language="python"]
# -*- coding: utf-8 -*-
"""
Created on Wed Nov 16 21:03:20 2016
@author: Sumant
The hats take the input as a STRING of Black and White
Black: Represents even number of black hats
White: Represents odd number of black hats
Black = 1
White = 0
def whatTheySee()
returns an array which contains the parity of black hats they see in front
of them
def whatTheySay()
returns an array which contains what they say
Algorithm: WhatTheySay
We need to use the array whatTheySee and we return an array which contains
what each person should say: except for the first entry which corresponds to
the last number we see. All others are always correct.
The nth position of the array we return populates itself with the responses
of previous n-1 responses and add what the parity of black hats the person
standing at nth position sees.
Input: WWWWBB
Output: WWWWBB
Input: BBBBB
Output: BBBBB
Input: BBBB
Output: WBBB
Input: BWBWBB
Output: WWBWBB
"""
hats="BWBWBB"
def binaryTohat(hat):
change=[]
for i in hat:
if i == 1:
change.append('B')
else:
change.append('W')
return change
def hatTobinary(hat):
change=[]
for i in hat:
if i == 'B':
change.append(1)
else:
change.append(0)
return change
HATS=hatTobinary(hats)
def whatTheySee(hats):
a=[]
for j in range(len(hats)):
sum = 1
for i in range(j+1,len(hats)):
sum= sum+HATS[i]
sum = sum %2
a.append(sum)
return a
def whatTheySay(hats):
a=[]
val=0
a.append(hats[0])
for i in range(1,len(hats)):
val=sum(a)+hats[i]
a.append(val%2)
return a
def stringArraytoString(st):
a=""
for i in st:
a+=i
return a
print("What wizard see",hats)
print("What they say",stringArraytoString(binaryTohat(whatTheySay(whatTheySee(HATS)))))
[/sourcecode]
Labels: Hat Problem, Python
0 Comments:
Post a Comment
<< Home