+/foobar

google programming puzzles

git clone https://git.julia.blue/+/foobar

Joseph RyanI made it2e1d345

master
2.5 KiB93 linesraw
1from fractions import Fraction
2
3
4def peg2rad(first, pegs):
5    rad = [Fraction(first, 1)]
6    for j in range(1, len(pegs)):
7        rad.append(pegs[j] - pegs[j - 1] - rad[-1])
8    return rad
9
10
11def rad2ratio(rad):
12    ratios = [rad[i] / rad[i + 1] for i in range(0, len(rad) - 1)]
13    return reduce(lambda x, y: x * y, ratios)
14
15
16def answer(pegs):
17    rad = peg2rad(1, pegs)
18    smallest = min(rad[::2])
19    if smallest <= 0:
20        smallest = 2 - smallest
21    else:
22        smallest = 1
23    small_rad = peg2rad(smallest, pegs)
24    largest = smallest + min(small_rad[1::2]) - 1
25    if largest < smallest:
26        return [-1, -1]
27    small_ratio = rad2ratio(small_rad)
28    slope = small_ratio < 2
29    large_rad = peg2rad(largest, pegs)
30    large_ratio = rad2ratio(large_rad)
31    # print "Original:", [str(x) for x in rad]
32    # print "Start:", [str(x) for x in small_rad], small_ratio
33    # print "End:", [str(x) for x in large_rad], large_ratio
34    # print "small:", smallest, "\tlarge:", largest
35    if small_ratio < 2 and large_ratio < 2 or small_ratio > 2 and large_ratio > 2:
36        return [-1, -1]
37    for i in range(int(smallest), int(largest) + 1):
38        rad = peg2rad(i, pegs)
39        ratio = rad2ratio(rad)
40        # print "Loop:", [str(x) for x in rad], ratio
41        if ratio == 2:
42            return [rad[0].numerator, rad[0].denominator]
43        if ratio < 2 and not slope or ratio > 2 and slope:
44            if ratio > 2:
45                i -= 1
46            n = 1
47            d = 1
48            f = Fraction(n, d)
49            ratio = rad2ratio(peg2rad(i + f, pegs))
50            while ratio != 2:
51                d += 1
52                if ratio < 2:
53                    n += 1
54                else:
55                    n -= 1
56                f = Fraction(n, d)
57                ratio = rad2ratio(peg2rad(i + f, pegs))
58            f += i
59            return [f.numerator, f.denominator]
60    return [-1, -1]
61
62
63from random import randint
64import sys
65
66print answer([4, 30, 50])
67print answer([4, 17, 50])
68print answer([4, 12])  # FRACTION
69sys.exit()
70
71while True:
72    # arr = [40, 80, 100, 150]
73    arr = sorted([randint(1, 100) for i in range(4)])
74    ans = answer(arr)
75    print ans
76    if ans[1] not in (-1, 1):
77        break
78sys.exit()
79
80a = Fraction(17, 37)
81n = 1
82d = 1
83f = Fraction(n, d)
84print "target", a, "(" + str(float(a)) + ")"
85while int(a) + f != a:
86    d += 1
87    print int(a) + f, "(" + str(float(int(a) + f)) + ")"
88    if int(a) + f < a:
89        n += 1
90    else:
91        n -= 1
92    f = Fraction(n, d)
93print int(a) + f, "(" + str(float(int(a) + f)) + ")"