Python: binary search (4) Weighing pool balls

Python: binary search (4) Weighing pool balls

Abstract: 8 out of  9 balls are identical in size and appearance,  but 1 is an odd weight which could be either lighter or heavier.

What is the minimum steps required for balancing them. The answer is 3 steps. Here is the code.



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

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.arr=array
            print self.arr
           
#alway group self.arr into 3 arrays   
    def triple_groups(self):
        sub_len=len(self.arr)/3
        #print sub_len
        self.group1=range(sub_len)
        self.group2=range(sub_len,sub_len*2)
        self.group3=range(sub_len*2, len(self.arr))
        print self.group1, self.group2, self.group3
#   
    def judge_equal(self):
        s1=sum([self.arr[x] for x in self.group1])
        s2=sum([self.arr[x] for x in self.group2])
        if s1==s2:
            return 0
        elif s1<s2:
            return -1
        else:
            self.group1,self.group2=self.group2,self.group1
            return 1

#seek the odd:
#3 index of self.arr
    def screen_3ball(self,index):
        tag=-2 #
        a,b,c=index
        while tag==-2:
            if self.arr[a]==self.arr[b]:
                tag=-1 if self.arr[a]==self.arr[c] else c
            else:
                tag=b if self.arr[a]==self.arr[c] else a
        return tag

#group1:3 balls, group2: 3 balls, group3: 3 balls
    def screen_3in(self):
        self.triple_groups()
        tag=-2
        while tag==-2:
            judge=self.judge_equal()
            #odd is in group3
            if judge==0:
                tag=self.screen_3ball(self.group3)
            else:
                #switch the last element between group1 and group2
                self.group1[2],self.group2[2]=self.group2[2],self.group1[2]
                #change the first element of group2
                kicked=self.group2[0]
                self.group2[0]=self.group3[0]
                judge=self.judge_equal()
                #print [self.arr[x] for x in self.group1]
                #print [self.arr[x] for x in self.group2]
                if judge==0:
                    tag=kicked
                elif judge==-1:
                    self.group1[2]=self.group2[1]
                    tag=self.screen_3ball(self.group1)
                else:
                    tag=self.group1[2]
        return tag, self.arr[tag]
       
###########
if __name__=="__main__":
    #build pool balls
    l=9
    random_index=random.randint(0,l-1)
    odd=8
    arr=[10]*(l-1)
    arr.insert(random_index, odd)
   
   
    #arr=[10, 10, 10, 8, 10, 10, 10, 10, 8]
    print search(arr).screen_3in()
    print "ok"