Friday, November 18, 2016

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]

Labels: ,

0 Comments:

Post a Comment

<< Home

Site Meter