Python: binary search (5) Weighing pool balls with n input

Python: binary search (5) Weighing pool balls with n input

 

Abstract: There are n ()N.=3 balls are identical in size and appearance, but 1 is an odd weight which could be either lighter or heavier.

 Here is the code.

# -*- coding: utf-8 -*-

"""

Created on Tue May 30 14:43:05 2017

@author: yuan

"""

import random

import math

class search:

def __init__(self, array):

if len(array)<3:

print 'at least 3 balls'

return

else: #at least 3 elements

self.pool=array

self.arr=range(len(array))

#print array

#alway group self.arr into 3 arrays

#the ratio is about 3:3:4

def triple_groups(self):

sub_len=int(len(self.arr)*.3+.5)

print sub_len

self.group1=self.arr[:sub_len]

self.group2=self.arr[sub_len:(sub_len*2)]

self.group3=self.arr[(sub_len*2):]

print self.arr, self.group1, self.group2,self.group3

#

def judge_equal(self):

s1=sum([self.pool[x] for x in self.group1])

s2=sum([self.pool[x] for x in self.group2])

if s1==s2:

self.arr=self.group3

self.ref=self.group1.pop()

else:

self.arr=self.group1+self.group2

self.ref=self.group3.pop()

#seek the odd:

#3 index of self.arr

def screen_odd(self):

tag=-1

for index in self.arr:

if self.pool[index]!=self.pool[self.ref]:

tag=index

return tag

#group1:3 balls, group2: 3 balls, group3: 3 balls

def screen_loop(self):

tag=-2

while tag==-2:

#grouping

self.triple_groups()

#judge where is the odd in 0.6 or 0.4 regrion

self.judge_equal()

#judge the terminal

if len(self.arr)<=3:

tag=self.screen_odd()

print tag, self.pool[tag]

return tag, self.pool[tag]

###########

if __name__=="__main__":

#build pool balls

l=122

random_index=random.randint(0,l-1)

odd=8

arr=[10]*(l-1)

arr.insert(random_index, odd)

print random_index, arr, '\n'

#search([1]*13).triple_groups()

#arr=[10, 10, 10, 8, 10, 10, 10, 10, 8]

search(arr).screen_loop()

print "ok"