<s> """<STR_LIT>""" <EOL> from decimal import Decimal <EOL> import math <EOL> import numbers <EOL> import operator <EOL> import re <EOL> import sys <EOL> __all__ = [ '<STR_LIT>' , '<STR_LIT>' ] <EOL> def gcd ( a , b ) : <EOL> """<STR_LIT>""" <EOL> while b : <EOL> a , b = b , a % b <EOL> return a <EOL> _PyHASH_MODULUS = sys . hash_info . modulus <EOL> _PyHASH_INF = sys . hash_info . inf <EOL> _RATIONAL_FORMAT = re . compile ( r"""<STR_LIT>""" , re . VERBOSE | re . IGNORECASE ) <EOL> class Fraction ( numbers . Rational ) : <EOL> """<STR_LIT>""" <EOL> __slots__ = ( '<STR_LIT>' , '<STR_LIT>' ) <EOL> def __new__ ( cls , numerator = <NUM_LIT:0> , denominator = None ) : <EOL> """<STR_LIT>""" <EOL> self = super ( Fraction , cls ) . __new__ ( cls ) <EOL> if denominator is None : <EOL> if isinstance ( numerator , numbers . Rational ) : <EOL> self . _numerator = numerator . numerator <EOL> self . _denominator = numerator . denominator <EOL> return self <EOL> elif isinstance ( numerator , float ) : <EOL> value = Fraction . from_float ( numerator ) <EOL> self . _numerator = value . _numerator <EOL> self . _denominator = value . _denominator <EOL> return self <EOL> elif isinstance ( numerator , Decimal ) : <EOL> value = Fraction . from_decimal ( numerator ) <EOL> self . _numerator = value . _numerator <EOL> self . _denominator = value . _denominator <EOL> return self <EOL> elif isinstance ( numerator , str ) : <EOL> m = _RATIONAL_FORMAT . match ( numerator ) <EOL> if m is None : <EOL> raise ValueError ( '<STR_LIT>' % <EOL> numerator ) <EOL> numerator = int ( m . group ( '<STR_LIT>' ) or '<STR_LIT:0>' ) <EOL> denom = m . group ( '<STR_LIT>' ) <EOL> if denom : <EOL> denominator = int ( denom ) <EOL> else : <EOL> denominator = <NUM_LIT:1> <EOL> decimal = m . group ( '<STR_LIT>' ) <EOL> if decimal : <EOL> scale = <NUM_LIT:10> ** len ( decimal ) <EOL> numerator = numerator * scale + int ( decimal ) <EOL> denominator *= scale <EOL> exp = m . group ( '<STR_LIT>' ) <EOL> if exp : <EOL> exp = int ( exp ) <EOL> if exp >= <NUM_LIT:0> : <EOL> numerator *= <NUM_LIT:10> ** exp <EOL> else : <EOL> denominator *= <NUM_LIT:10> ** - exp <EOL> if m . group ( '<STR_LIT>' ) == '<STR_LIT:->' : <EOL> numerator = - numerator <EOL> else : <EOL> raise TypeError ( "<STR_LIT>" <EOL> "<STR_LIT>" ) <EOL> elif ( isinstance ( numerator , numbers . Rational ) and <EOL> isinstance ( denominator , numbers . Rational ) ) : <EOL> numerator , denominator = ( <EOL> numerator . numerator * denominator . denominator , <EOL> denominator . numerator * numerator . denominator <EOL> ) <EOL> else : <EOL> raise TypeError ( "<STR_LIT>" <EOL> "<STR_LIT>" ) <EOL> if denominator == <NUM_LIT:0> : <EOL> raise ZeroDivisionError ( '<STR_LIT>' % numerator ) <EOL> g = gcd ( numerator , denominator ) <EOL> self . _numerator = numerator // g <EOL> self . _denominator = denominator // g <EOL> return self <EOL> @ classmethod <EOL> def from_float ( cls , f ) : <EOL> """<STR_LIT>""" <EOL> if isinstance ( f , numbers . Integral ) : <EOL> return cls ( f ) <EOL> elif not isinstance ( f , float ) : <EOL> raise TypeError ( "<STR_LIT>" % <EOL> ( cls . __name__ , f , type ( f ) . __name__ ) ) <EOL> if math . isnan ( f ) : <EOL> raise ValueError ( "<STR_LIT>" % ( f , cls . __name__ ) ) <EOL> if math . isinf ( f ) : <EOL> raise OverflowError ( "<STR_LIT>" % ( f , cls . __name__ ) ) <EOL> return cls ( * f . as_integer_ratio ( ) ) <EOL> @ classmethod <EOL> def from_decimal ( cls , dec ) : <EOL> """<STR_LIT>""" <EOL> from decimal import Decimal <EOL> if isinstance ( dec , numbers . Integral ) : <EOL> dec = Decimal ( int ( dec ) ) <EOL> elif not isinstance ( dec , Decimal ) : <EOL> raise TypeError ( <EOL> "<STR_LIT>" % <EOL> ( cls . __name__ , dec , type ( dec ) . __name__ ) ) <EOL> if dec . is_infinite ( ) : <EOL> raise OverflowError ( <EOL> "<STR_LIT>" % ( dec , cls . __name__ ) ) <EOL> if dec . is_nan ( ) : <EOL> raise ValueError ( "<STR_LIT>" % ( dec , cls . __name__ ) ) <EOL> sign , digits , exp = dec . as_tuple ( ) <EOL> digits = int ( '<STR_LIT>' . join ( map ( str , digits ) ) ) <EOL> if sign : <EOL> digits = - digits <EOL> if exp >= <NUM_LIT:0> : <EOL> return cls ( digits * <NUM_LIT:10> ** exp ) <EOL> else : <EOL> return cls ( digits , <NUM_LIT:10> ** - exp ) <EOL> def limit_denominator ( self , max_denominator = <NUM_LIT> ) : <EOL> """<STR_LIT>""" <EOL> if max_denominator < <NUM_LIT:1> : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> if self . _denominator <= max_denominator : <EOL> return Fraction ( self ) <EOL> p0 , q0 , p1 , q1 = <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:0> <EOL> n , d = self . _numerator , self . _denominator <EOL> while True : <EOL> a = n // d <EOL> q2 = q0 + a * q1 <EOL> if q2 > max_denominator : <EOL> break <EOL> p0 , q0 , p1 , q1 = p1 , q1 , p0 + a * p1 , q2 <EOL> n , d = d , n - a * d <EOL> k = ( max_denominator - q0 ) // q1 <EOL> bound1 = Fraction ( p0 + k * p1 , q0 + k * q1 ) <EOL> bound2 = Fraction ( p1 , q1 ) <EOL> if abs ( bound2 - self ) <= abs ( bound1 - self ) : <EOL> return bound2 <EOL> else : <EOL> return bound1 <EOL> @ property <EOL> def numerator ( a ) : <EOL> return a . _numerator <EOL> @ property <EOL> def denominator ( a ) : <EOL> return a . _denominator <EOL> def __repr__ ( self ) : <EOL> """<STR_LIT>""" <EOL> return ( '<STR_LIT>' % ( self . _numerator , self . _denominator ) ) <EOL> def __str__ ( self ) : <EOL> """<STR_LIT>""" <EOL> if self . _denominator == <NUM_LIT:1> : <EOL> return str ( self . _numerator ) <EOL> else : <EOL> return '<STR_LIT>' % ( self . _numerator , self . _denominator ) <EOL> def _operator_fallbacks ( monomorphic_operator , fallback_operator ) : <EOL> """<STR_LIT>""" <EOL> def forward ( a , b ) : <EOL> if isinstance ( b , ( int , Fraction ) ) : <EOL> return monomorphic_operator ( a , b ) <EOL> elif isinstance ( b , float ) : <EOL> return fallback_operator ( float ( a ) , b ) <EOL> elif isinstance ( b , complex ) : <EOL> return fallback_operator ( complex ( a ) , b ) <EOL> else : <EOL> return NotImplemented <EOL> forward . __name__ = '<STR_LIT>' + fallback_operator . __name__ + '<STR_LIT>' <EOL> forward . __doc__ = monomorphic_operator . __doc__ <EOL> def reverse ( b , a ) : <EOL> if isinstance ( a , numbers . Rational ) : <EOL> return monomorphic_operator ( a , b ) <EOL> elif isinstance ( a , numbers . Real ) : <EOL> return fallback_operator ( float ( a ) , float ( b ) ) <EOL> elif isinstance ( a , numbers . Complex ) : <EOL> return fallback_operator ( complex ( a ) , complex ( b ) ) <EOL> else : <EOL> return NotImplemented <EOL> reverse . __name__ = '<STR_LIT>' + fallback_operator . __name__ + '<STR_LIT>' <EOL> reverse . __doc__ = monomorphic_operator . __doc__ <EOL> return forward , reverse <EOL> def _add ( a , b ) : <EOL> """<STR_LIT>""" <EOL> return Fraction ( a . numerator * b . denominator + <EOL> b . numerator * a . denominator , <EOL> a . denominator * b . denominator ) <EOL> __add__ , __radd__ = _operator_fallbacks ( _add , operator . add ) <EOL> def _sub ( a , b ) : <EOL> """<STR_LIT>""" <EOL> return Fraction ( a . numerator * b . denominator - <EOL> b . numerator * a . denominator , <EOL> a . denominator * b . denominator ) <EOL> __sub__ , __rsub__ = _operator_fallbacks ( _sub , operator . sub ) <EOL> def _mul ( a , b ) : <EOL> """<STR_LIT>""" <EOL> return Fraction ( a . numerator * b . numerator , a . denominator * b . denominator ) <EOL> __mul__ , __rmul__ = _operator_fallbacks ( _mul , operator . mul ) <EOL> def _div ( a , b ) : <EOL> """<STR_LIT>""" <EOL> return Fraction ( a . numerator * b . denominator , <EOL> a . denominator * b . numerator ) <EOL> __truediv__ , __rtruediv__ = _operator_fallbacks ( _div , operator . truediv ) <EOL> def __floordiv__ ( a , b ) : <EOL> """<STR_LIT>""" <EOL> return math . floor ( a / b ) <EOL> def __rfloordiv__ ( b , a ) : <EOL> """<STR_LIT>""" <EOL> return math . floor ( a / b ) <EOL> def __mod__ ( a , b ) : <EOL> """<STR_LIT>""" <EOL> div = a // b <EOL> return a - b * div <EOL> def __rmod__ ( b , a ) : <EOL> """<STR_LIT>""" <EOL> div = a // b <EOL> return a - b * div <EOL> def __pow__ ( a , b ) : <EOL> """<STR_LIT>""" <EOL> if isinstance ( b , numbers . Rational ) : <EOL> if b . denominator == <NUM_LIT:1> : <EOL> power = b . numerator <EOL> if power >= <NUM_LIT:0> : <EOL> return Fraction ( a . _numerator ** power , <EOL> a . _denominator ** power ) <EOL> else : <EOL> return Fraction ( a . _denominator ** - power , <EOL> a . _numerator ** - power ) <EOL> else : <EOL> return float ( a ) ** float ( b ) <EOL> else : <EOL> return float ( a ) ** b <EOL> def __rpow__ ( b , a ) : <EOL> """<STR_LIT>""" <EOL> if b . _denominator == <NUM_LIT:1> and b . _numerator >= <NUM_LIT:0> : <EOL> return a ** b . _numerator <EOL> if isinstance ( a , numbers . Rational ) : <EOL> return Fraction ( a . numerator , a . denominator ) ** b <EOL> if b . _denominator == <NUM_LIT:1> : <EOL> return a ** b . _numerator <EOL> return a ** float ( b ) <EOL> def __pos__ ( a ) : <EOL> """<STR_LIT>""" <EOL> return Fraction ( a . _numerator , a . _denominator ) <EOL> def __neg__ ( a ) : <EOL> """<STR_LIT>""" <EOL> return Fraction ( - a . _numerator , a . _denominator ) <EOL> def __abs__ ( a ) : <EOL> """<STR_LIT>""" <EOL> return Fraction ( abs ( a . _numerator ) , a . _denominator ) <EOL> def __trunc__ ( a ) : <EOL> """<STR_LIT>""" <EOL> if a . _numerator < <NUM_LIT:0> : <EOL> return - ( - a . _numerator // a . _denominator ) <EOL> else : <EOL> return a . _numerator // a . _denominator <EOL> def __floor__ ( a ) : <EOL> """<STR_LIT>""" <EOL> return a . numerator // a . denominator <EOL> def __ceil__ ( a ) : <EOL> """<STR_LIT>""" <EOL> return - ( - a . numerator // a . denominator ) <EOL> def __round__ ( self , ndigits = None ) : <EOL> """<STR_LIT>""" <EOL> if ndigits is None : <EOL> floor , remainder = divmod ( self . numerator , self . denominator ) <EOL> if remainder * <NUM_LIT:2> < self . denominator : <EOL> return floor <EOL> elif remainder * <NUM_LIT:2> > self . denominator : <EOL> return floor + <NUM_LIT:1> <EOL> elif floor % <NUM_LIT:2> == <NUM_LIT:0> : <EOL> return floor <EOL> else : <EOL> return floor + <NUM_LIT:1> <EOL> shift = <NUM_LIT:10> ** abs ( ndigits ) <EOL> if ndigits > <NUM_LIT:0> : <EOL> return Fraction ( round ( self * shift ) , shift ) <EOL> else : <EOL> return Fraction ( round ( self / shift ) * shift ) <EOL> def __hash__ ( self ) : <EOL> """<STR_LIT>""" <EOL> dinv = pow ( self . _denominator , _PyHASH_MODULUS - <NUM_LIT:2> , _PyHASH_MODULUS ) <EOL> if not dinv : <EOL> hash_ = _PyHASH_INF <EOL> else : <EOL> hash_ = abs ( self . _numerator ) * dinv % _PyHASH_MODULUS <EOL> result = hash_ if self >= <NUM_LIT:0> else - hash_ <EOL> return - <NUM_LIT:2> if result == - <NUM_LIT:1> else result <EOL> def __eq__ ( a , b ) : <EOL> """<STR_LIT>""" <EOL> if isinstance ( b , numbers . Rational ) : <EOL> return ( a . _numerator == b . numerator and <EOL> a . _denominator == b . denominator ) <EOL> if isinstance ( b , numbers . Complex ) and b . imag == <NUM_LIT:0> : <EOL> b = b . real <EOL> if isinstance ( b , float ) : <EOL> if math . isnan ( b ) or math . isinf ( b ) : <EOL> return <NUM_LIT:0.0> == b <EOL> else : <EOL> return a == a . from_float ( b ) <EOL> else : <EOL> return NotImplemented <EOL> def _richcmp ( self , other , op ) : <EOL> """<STR_LIT>""" <EOL> if isinstance ( other , numbers . Rational ) : <EOL> return op ( self . _numerator * other . denominator , <EOL> self . _denominator * other . numerator ) <EOL> if isinstance ( other , float ) : <EOL> if math . isnan ( other ) or math . isinf ( other ) : <EOL> return op ( <NUM_LIT:0.0> , other ) <EOL> else : <EOL> return op ( self , self . from_float ( other ) ) <EOL> else : <EOL> return NotImplemented <EOL> def __lt__ ( a , b ) : <EOL> """<STR_LIT>""" <EOL> return a . _richcmp ( b , operator . lt ) <EOL> def __gt__ ( a , b ) : <EOL> """<STR_LIT>""" <EOL> return a . _richcmp ( b , operator . gt ) <EOL> def __le__ ( a , b ) : <EOL> """<STR_LIT>""" <EOL> return a . _richcmp ( b , operator . le ) <EOL> def __ge__ ( a , b ) : <EOL> """<STR_LIT>""" <EOL> return a . _richcmp ( b , operator . ge ) <EOL> def __bool__ ( a ) : <EOL> """<STR_LIT>""" <EOL> return a . _numerator != <NUM_LIT:0> <EOL> def __reduce__ ( self ) : <EOL> return ( self . __class__ , ( str ( self ) , ) ) <EOL> def __copy__ ( self ) : <EOL> if type ( self ) == Fraction : <EOL> return self <EOL> return self . __class__ ( self . _numerator , self . _denominator ) <EOL> def __deepcopy__ ( self , memo ) : <EOL> if type ( self ) == Fraction : <EOL> return self <EOL> return self . __class__ ( self . _numerator , self . _denominator ) </s>
