+/foobar

google programming puzzles

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

Joseph RyanI made it2e1d345

master
1.8 KiB87 linesraw
1def brute(n):
2    n = int(n)
3    if n <= 1:
4        return 0
5    if n % 2 == 0:
6        return 1 + brute(n / 2)
7    return min(brute(n + 1), brute(n - 1)) + 1
8
9def trailingZeros(n):
10    return len(bin(n).split('1')[-1])
11
12def answer(n):
13    n = int(n)
14    count = 0
15    while n > 3:
16        if n % 2 == 0:
17            n /= 2
18        else:
19            n += 1 if bin(n + 1).count('0') >= bin(n - 1).count('0') else -1
20        count += 1
21    return count + n - 1
22
23def answer2(n):
24    n = int(n)
25    count = 0
26    while n > 3:
27        if n % 2 == 0:
28            n /= 2
29        else:
30            n += 1 if trailingZeros(n+1) > trailingZeros(n-1) else -1
31        count += 1
32    return count + n - 1
33
34def answer3(num):
35    num = int(num)
36    num = [int(i) for i in "{0:b}".format(num)]
37
38    count = len(num) - 1
39
40    while len(num) > 1:
41        a = (num[-2], num.pop())
42
43        if a == (1, 1) and len(num) > 1:
44
45            while num[-1] is not 0 and len(num) > 1:
46                num.pop()
47
48            count += 1
49            num[-1] = 1
50
51            if len(num) is 1:
52                count += 1
53
54        elif a == (1, 1):
55            count += 1
56
57        elif a == (0, 1):
58            count += 1
59
60    return count
61
62def answer4(n):
63    n = int(n)
64    count = 0
65    while n > 3:
66        if n % 2 == 0:
67            n /= 2
68        else:
69            n += 1 if n % 4 == 3 else -1
70        count += 1
71    return count + n - 1
72
73# print trailingZeros(58)
74# import sys
75# sys.exit()
76
77print ' '.join('{:2}'.format(i) for i in range(30))
78print ' '.join('{:2}'.format(answer4(str(n))) for n in range(30))
79print ' '.join('{:2}'.format(answer(str(n))) for n in range(30))
80
81for i in range(5, 10000):
82    print i
83    if answer2(i) != answer(i):
84        print answer4(i), answer(i)
85        break
86
87print answer(10**300)