nummap = {
    'I' : 1,
    'V' : 5,
    'X' : 10,
    'L' : 50,
    'C' : 100,
    'D' : 500,
    'M' : 1000,
}
rnummap = {
    1:'I',
    5:'V',
    10:'X',
    50:'L',
    100:'C',
    500:'D',
    1000:'M',
}
tryorder = [ 'M', 'D', 'C', 'L', 'X', 'V', 'I' ]
def decompose( value, trylist ):
    res = []
    if value == 1:
        return ['I']
    if value == 0: return []

    n = trylist[0]
    cval = nummap[ n ]
    oldval = value
    if cval in [ 5, 50, 500 ] :
        # try things like IX
        next = cval / 5
        prev = cval * 2
        if value - ( prev - next ) >=0:
            res.append( rnummap[ next ] )
            res.append( rnummap[ prev ] )
            value -= ( prev - next )
        elif value - cval >= 0:
            res.append( n )
            value -= cval
        elif value - ( cval - next) >= 0:
            res.append( rnummap[ next ] )
            res.append( rnummap[ cval ] )
            value -= ( cval - next )
    elif value - cval >= 0:
        res.append( n )
        value -= cval
    if oldval == value:
        if len(trylist) > 1:
            trylist = trylist[1:]
    res.extend( decompose( value, trylist ) )
    return res


def main( ):
    f = open( 'data' )
    while True:
        line = f.readline()
        if not line:
            break
        x, y = line.split()
        print x, y
    romannumeral = ''.join( decompose( int(y), tryorder ) )
    # the romannumeral returned must be equal to x
    print romannumeral, y
    f.close()


main()

import random

def randomizedselect( k, array ):
    if len( array ) == 1:
        return array[0]

    # randomize the pivot to avoid getting stuck in infinite loop
    # if the partition results in array of same length
    pivot = array[ random.randint( 0, len( array ) -1 ) ]
    left, right, match = [], [], []
    for x in array:
        if x < pivot:
            left.append( x )
        elif x == pivot:
            match.append( x )
        else:
            right.append( x )

    size_left, size_match = len( left ), len( match )

    if size_left >= k :
        return randomizedselect( k , left )
    elif k > size_left and k <= size_left + size_match:
        return match[0]
    else:
        return randomizedselect( k - ( size_left + size_match ), right )

def randomized_median( array ):
    n = len( array )
    k = n / 2 + 1 if n % 2 != 0 else n / 2
    return randomizedselect( k, array )

import copy
import matplotlib.pyplot as plt
import median
import numpy
import pprint
import random

class KDTree( object ):

    _IDX_LOOKUP = { 'x-axis' : 0, 'y-axis' : 1 }

    def __init__( self ):
        self._tree = {}

    def build_kdtree( self, point_list ):

        self._point_list = point_list

        dic = {}
        dim = len( point_list[0] )
        MAXLEVEL = 16

        print 'processing points=%s' % point_list

        def build( d, level, points ):

            if points.size == 0:
                return None
            elif points.size == 1 or level == MAXLEVEL:
                return points

            axis_index = level % dim
            _median = median.randomized_median( points[ :, axis_index ] )
            median_points = points[ numpy.where( points[ :,axis_index ] == _median ) ]
            left_points = points[ numpy.where( points[ :,axis_index ] < _median ) ]
            right_points = points[ numpy.where( points[ :,axis_index ] > _median ) ]

            d[ 'median_points' ] = median_points
            d[ 'split_axis' ] = 'y-axis' if axis_index else 'x-axis'
            d[ 'left_node' ] = build( {}, level + 1, left_points )
            d[ 'right_node' ] = build( {}, level + 1, right_points )

            return d

        self._tree = build( dic, 0, point_list )

    def pprint( self ):
        pprint.pprint( self._tree )




    def show( self ):
        x, y = zip( *self._point_list )
        plt.autoscale( enable=True, tight=False )
        plt.margins( 0.1, 0.1 )
        plt.plot( x, y, 'o', color='b' )

        yline_color = '#FFB0B0'
        #yline_color = '#FF9595'
        xline_color = '#b0e2ff'
        def plot_separating_planes( v, node):

            idx = KDTree._IDX_LOOKUP[ node[ 'split_axis' ] ]
            pos = node[ 'median_points' ][0][ idx ]

            if idx == 0:
                plt.vlines( pos, v[2], v[3], color=yline_color, linewidth=2.0 )
            elif idx == 1:
                plt.hlines( pos, v[0], v[1], color=xline_color, linewidth=2.0   )

            if node[ 'left_node' ]:
                v_new = copy.deepcopy( v )
                if idx == 0: # decide to shorten the bounding box along whichever axis               
                    v_new[1] = pos
                elif idx == 1:
                    v_new[3] = pos
                plot_separating_planes( v_new, node[ 'left_node' ] )
            if node[ 'right_node' ]:
                v_new = copy.deepcopy( v )
                if idx == 0: # decide to shorten the bounding box along whichever axis               
                    v_new[0] = pos
                elif idx == 1:
                    v_new[2] = pos
                plot_separating_planes( v_new, node[ 'right_node' ] )

        v_start = numpy.array( plt.axis() )
        plot_separating_planes( v_start, self._tree )
        plt.show()

def random_points():

    points = []
    for i in xrange( 0, 20 ):
        points.append( ( random.randint( 0, 100 ), random.randint( 0, 100 ) ) )

    return points

def main():
    #point_list = [(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)]
    point_list = random_points()

    array = numpy.array( point_list )
    kdtree = KDTree()
    kdtree.build_kdtree( array )
    kdtree.pprint()
    kdtree.show()


main()