from fractions import Fraction def peg2rad(first, pegs): rad = [Fraction(first, 1)] for j in range(1, len(pegs)): rad.append(pegs[j] - pegs[j - 1] - rad[-1]) return rad def rad2ratio(rad): ratios = [rad[i] / rad[i + 1] for i in range(0, len(rad) - 1)] return reduce(lambda x, y: x * y, ratios) def answer(pegs): rad = peg2rad(1, pegs) smallest = min(rad[::2]) if smallest <= 0: smallest = 2 - smallest else: smallest = 1 small_rad = peg2rad(smallest, pegs) largest = smallest + min(small_rad[1::2]) - 1 if largest < smallest: return [-1, -1] small_ratio = rad2ratio(small_rad) slope = small_ratio < 2 large_rad = peg2rad(largest, pegs) large_ratio = rad2ratio(large_rad) # print "Original:", [str(x) for x in rad] # print "Start:", [str(x) for x in small_rad], small_ratio # print "End:", [str(x) for x in large_rad], large_ratio # print "small:", smallest, "\tlarge:", largest if small_ratio < 2 and large_ratio < 2 or small_ratio > 2 and large_ratio > 2: return [-1, -1] for i in range(int(smallest), int(largest) + 1): rad = peg2rad(i, pegs) ratio = rad2ratio(rad) # print "Loop:", [str(x) for x in rad], ratio if ratio == 2: return [rad[0].numerator, rad[0].denominator] if ratio < 2 and not slope or ratio > 2 and slope: if ratio > 2: i -= 1 n = 1 d = 1 f = Fraction(n, d) ratio = rad2ratio(peg2rad(i + f, pegs)) while ratio != 2: d += 1 if ratio < 2: n += 1 else: n -= 1 f = Fraction(n, d) ratio = rad2ratio(peg2rad(i + f, pegs)) f += i return [f.numerator, f.denominator] return [-1, -1] from random import randint import sys print answer([4, 30, 50]) print answer([4, 17, 50]) print answer([4, 12]) # FRACTION sys.exit() while True: # arr = [40, 80, 100, 150] arr = sorted([randint(1, 100) for i in range(4)]) ans = answer(arr) print ans if ans[1] not in (-1, 1): break sys.exit() a = Fraction(17, 37) n = 1 d = 1 f = Fraction(n, d) print "target", a, "(" + str(float(a)) + ")" while int(a) + f != a: d += 1 print int(a) + f, "(" + str(float(int(a) + f)) + ")" if int(a) + f < a: n += 1 else: n -= 1 f = Fraction(n, d) print int(a) + f, "(" + str(float(int(a) + f)) + ")"