from fractions import Fraction

def continued_frac_to_rational(cs):
    e = cs[-1]
    for x in reversed(cs[:-1]):
        e = x + Fraction(1) / e
    return e

def rational_to_continued_frac(frac):
    ans = []
    a, b = frac.numerator, frac.denominator
    while b > 0:
        q, r = divmod(a, b)
        ans.append(q)
        a, b = b, r
    return ans
    
def get_stern_brocot_parent(rat):
    cf = rational_to_continued_frac(rat)
    if len(cf) > 0 and cf[-1] == 1:
        cf.pop()
        cf[-1] += 1
    cf[-1] -= 1
    return continued_frac_to_rational(cf)
    
def get_stern_brocot_children(rat):  
    if rat == Fraction(1):
        return (Fraction(1, 2), Fraction(2, 1))
    cf = rational_to_continued_frac(rat)
    print("cf :", cf)
    if cf[-1] != 1:
        c1 = cf[:]
        c1[-1] += 1
        c2 = cf[:]
        c2[-1] -= 1
        c2.append(2)
        c2.pop()
        c2[-1] -= 1
    else:
        c1 = cf[:-1]
        c1[-1] += 1
        c2 = cf[:]
        c2[-1] += 1
    return sorted((continued_frac_to_rational(c1),  continued_frac_to_rational(c2)))


def get_path_from_frac(q):
    path = ""
    left, right = (0, 1), (1, 0)
    while 1:
        mid = (left[0] + right[0], left[1] + right[1])
        fr = Fraction(mid[0], mid[1])
        if fr < q:
            path += "R"
            left = mid
        elif fr > q:
            path += "L"
            right = mid
        else:
            break
    return path

def get_frac_from_path(path):
    a, b, c, d, e, f = 0, 1, 1, 1, 1, 0
    for s in path:
        if s == "L":
            c, d, e, f = a + c, b + d, c, d
        else:
            a, b, c, d = c, d, c + e, d + f
    return Fraction(c, d)
    

print(get_frac_from_path("LLR"))

# print(get_path_from_frac(Fraction(3, 5)))
# print(continued_frac_to_rational([1, 2, 3, 2]))
# print(rational_to_continued_frac(Fraction(23, 16)))
# print(get_stern_brocot_parent(Fraction(23, 16)))
# print(get_stern_brocot_children(Fraction(2, 3)))