balancing_scale_problem.py

#
# Date   : 15/May/2018
# Author : Dinesh Devaraj
# Mobile : 8939773989
# Email  : dineshdevarajece@gmail.com
# Github : https://github.com/dineshdevaraj
# Gist   : http://bit.ly/deepvalue-bsprob
#

import re
import sys


class ProcessingError(Exception) :

    pass

def sowrite(x) : return sys.stdout.write(x)
def soreadline() : return sys.stdin.readline()

class WeightScale :

    def __init__(self, name) : # constructor

        self.name = name

        self.left = None
        self.right = None

        self.ldiff = 0
        self.rdiff = 0

        self.expected_weight = 1
        # self.actual_weight = 1

        # this flag defines if this weight-scale definition is done
        self.isset = False

        # this flag defines if this weight-scale is in-turn
        # being included in other weight-scale
        self.link = False

    def __setitem__(self, key, value) :
        self.__dict__[key] = value

    def __getitem__(self, key) :
        return self.__dict__[key]

    def local_print(self) : # print internal structure

        if isinstance(self.left, int) :
            lval = str(self.left)
        else : lval = self.left.name

        if isinstance(self.right, int) :
            rval = str(self.right)
        else : rval = self.right.name

        # sowrite("%s %d %d %d\n"%(self.name,
        #     self.expected_weight, self.ldiff, self.rdiff))
        # sowrite("%s %s %s\n"%(self.name, lval, rval))
        sowrite("%s %d %d\n"%(self.name, self.ldiff,
            self.rdiff))

        if isinstance(self.left, WeightScale) :
            self.left.local_print()
        if isinstance(self.right, WeightScale) :
            self.right.local_print()

        return

    def estimate_difference(self) :

        rweight = lweight = 0

        if isinstance(self.left, WeightScale) :
            lweight = self.left.estimate_difference()
        else : lweight = self.left

        if isinstance(self.right, WeightScale) :
            rweight = self.right.estimate_difference()
        else : rweight = self.right

        if lweight < rweight :
            self.ldiff = rweight - lweight
        elif lweight > rweight :
            self.rdiff = lweight - rweight

        self.expected_weight += self.ldiff + self.rdiff
        self.expected_weight += lweight + rweight

        return self.expected_weight

def process_wsentry(wsentry) : # process weight-scale entries

    pieces = wsentry.split(",")

    if len(pieces) != 3 :

        sowrite("Invalid format for weight-scale entry\n")
        raise ProcessingError()

    if pieces[0] == '' or pieces[1] == '' or pieces[2] == '' :

        sowrite("Values cannot be empty\n")
        raise ProcessingError()

    return pieces

def process_wsname(wsname, wsobj_dict) : # process weight-scale name

    if not wsname[0].isalpha() :

    # This rule for weight-scale name is looks
    # liberal. We may consider the following rule

    # if not re.match("[A-z][0-9]+", wsname) :

        sowrite("1st value should be always weight-scale name\n")
        sowrite("And %s is not a valid weight-scale name\n"%(wsname))
        raise ProcessingError()

    elif wsname not in wsobj_dict :

        wsobj_dict[wsname] = WeightScale(wsname)

    elif wsobj_dict[wsname].isset == True :

        # Uncomment if you do not want duplicate entry
        '''
        sowrite("%s is already defined\n"%(wsname))
        sowrite("Define different weight-scale name\n")
        raise ProcessingError()
        '''
        pass

    else : # do nothing

        pass

    return

def delete_weight_scale(wsobj, wsobj_dict) :

    if isinstance(wsobj.left, WeightScale) :
        delete_weight_scale(wsobj.left, wsobj_dict)
        del(wsobj_dict[wsobj.left.name])
        wsobj.left = None

    if isinstance(wsobj.right, WeightScale) :
        delete_weight_scale(wsobj.right, wsobj_dict)
        del(wsobj_dict[wsobj.right.name])
        wsobj.right = None
        
    return

def process_value(value, wsobj, wsobj_dict, base_wsobj_name, side) :

    if value.isdigit() :

        wsobj[side] = int(value)
        value = wsobj[side]

    elif value[0].isalpha() :
    # elif re.match("[A-z][0-9]+", value) :

        if wsobj.name == value :

            sowrite("%s cannot contain itself\n"%(value))
            raise ProcessingError()

        elif value == base_wsobj_name :

            sowrite("Base weight-scale %s cannot " % (value)
                + "be included into another weight-scale\n")
            raise ProcessingError()

        elif isinstance(wsobj[side], WeightScale) \
             and wsobj[side].name != value :
            
            # this condition happens when duplicate definition for
            # weight-scale is not disable. So during the 2nd definition
            # the resources created during 1st definition should be
            # deleted properly
            
            delete_weight_scale(wsobj[side], wsobj_dict)
            del(wsobj_dict[wsobj[side].name])
            wsobj[side] = None

        if value in wsobj_dict :
                
            if wsobj_dict[value].link != False and \
               wsobj_dict[value].link != wsobj.name :

                sowrite("%s cannot be included twice. "%(value))
                sowrite("It is already added to %s\n"%(wsobj_dict[value].link))
                raise ProcessingError()

            wsobj[side] = wsobj_dict[value]

        else :

            wsobj[side] = WeightScale(value)
            wsobj_dict[value] = wsobj[side]

        wsobj[side].link = wsobj.name

    else :

        sowrite("2nd value doesn't match the syntax for neither weight-scale name nor weight-value\n")
        raise ProcessingError()

    return wsobj[side]

def read_wsent(wsobj_dict, name_list) : # read weight scale entries

    stop_read = False
    base_wsobj_name = None
    base_wsobj = None

    # read-line until there are no weight-scale in the input line
    while stop_read != True :

        try :

            line = soreadline().strip()

            if line == 'exit' : exit(-1)
            elif line[0] == '#' : continue

            v1, v2, v3 = process_wsentry(line)
            process_wsname(v1, wsobj_dict)
            
            if v1 not in name_list :
                name_list.append(v1)

            # temporary variable to avoid length array access
            wsobj = wsobj_dict[v1]

            if base_wsobj == None :
                base_wsobj_name = wsobj.name
                base_wsobj = wsobj

            v2 = process_value(v2, wsobj, wsobj_dict,
                        base_wsobj_name, 'left')
            v3 = process_value(v3, wsobj, wsobj_dict,
                        base_wsobj_name, 'right')

            wsobj.isset = True
            if isinstance(v2, int) and isinstance(v3, int) :
                stop_read = True

        except ProcessingError as err : # don't do anything

            pass

    return base_wsobj

def print_in_order(wsobj_dict, name_list) :
    for name in name_list :
        sowrite("%s %d %d\n"%(name, wsobj_dict[name].ldiff,
            wsobj_dict[name].rdiff))

if __name__ == '__main__' :

    name_list = []
    wsobj_dict = {}
    # bwsobj - base weight-scale object
    bwsobj = read_wsent(wsobj_dict, name_list)

    # bwsobj.local_print()

    for key, value in wsobj_dict.items() :
        if value.isset == False :
            sowrite("weight-scale %s is not defined\n"%(key))
            exit(-1)

    bwsobj.estimate_difference()
    print_in_order(wsobj_dict, name_list)
    # bwsobj.local_print()