# Encoder and Decoder to solve the sensor problem:
# Q: Consider N sensors and a binary string S of length L, where L>N.
#    Give an algorithm that generates N binary strings such that any 
#    3 parts can be combined to reconstruct the message S.
#    Also, state the algorithm that takes 3 parts and recontructs S.
# 11.8.2003.
# Jiwon Hahn

def encode(S, N):
	print 'Encoding message:\t',S
	bit = 0
	E = [S[:] for i in range(N)] #initialize encoded messages to original message
	end_of_message = 0
	while 1:
		for i in range(N): #flip one bit of i-th node
			if E[i][bit] == '0': 	flip_bit = '1'
			else:			flip_bit = '0' 
			E[i] = E[i][0:bit]+flip_bit+E[i][bit+1:len(S)]
			bit += 1
			if bit == len(S): 
				end_of_message = 1
				break
		if end_of_message == 1: break
		i = 0
	for i in range(len(E)):	
		print 'Sensor ', i+1, ':\t\t', E[i]
	return E

def decode(E3, N):
	e1, e2, e3 = E3[0], E3[1], E3[2]
	S = ''
	for i in range(len(e1)):
		if e1[i] == e2[i] or e1[i] == e3[i]:	S += e1[i]
		else:	S += e2[i]	
	print 'Decoded Message:\t', S, '\n'
	return S

def choose_random(E):
	import random
	E3 = random.sample(E, 3) #randomly select 3 elements of E
	return E3

#three test messages
S1 = "1100010100101"
S2 = "111111111111111111111"
S3 = "11111111110000000000011111111110000000000"

#number of sensors
N1 = 3 
N3 = 20 

#test
E = encode(S1, N1)
e3 = choose_random(E)
decode(e3, N1)

E = encode(S2, N1)
e3 = choose_random(E)
decode(e3, N1)

E = encode(S3, N3)
e3 = choose_random(E)
decode(e3, N3)