1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
#!/usr/bin/env python3
import functools
import math
from heapq import heappop, heappush
from typing import List
class RunningMedian(object):
"""A running median computer.
>>> median = RunningMedian()
>>> median.add_number(1)
>>> median.add_number(10)
>>> median.add_number(3)
>>> median.get_median()
3
>>> median.add_number(7)
>>> median.add_number(5)
>>> median.get_median()
5
"""
def __init__(self):
self.lowers, self.highers = [], []
def add_number(self, number):
if not self.highers or number > self.highers[0]:
heappush(self.highers, number)
else:
heappush(self.lowers, -number) # for lowers we need a max heap
self.rebalance()
def rebalance(self):
if len(self.lowers) - len(self.highers) > 1:
heappush(self.highers, -heappop(self.lowers))
elif len(self.highers) - len(self.lowers) > 1:
heappush(self.lowers, -heappop(self.highers))
def get_median(self):
if len(self.lowers) == len(self.highers):
return (-self.lowers[0] + self.highers[0]) / 2
elif len(self.lowers) > len(self.highers):
return -self.lowers[0]
else:
return self.highers[0]
def gcd_floats(a: float, b: float) -> float:
if a < b:
return gcd_floats(b, a)
# base case
if abs(b) < 0.001:
return a
return gcd_floats(b, a - math.floor(a / b) * b)
def gcd_float_sequence(lst: List[float]) -> float:
if len(lst) <= 0:
raise ValueError("Need at least one number")
elif len(lst) == 1:
return lst[0]
assert len(lst) >= 2
gcd = gcd_floats(lst[0], lst[1])
for i in range(2, len(lst)):
gcd = gcd_floats(gcd, lst[i])
return gcd
def truncate_float(n: float, decimals: int = 2):
"""
Truncate a float to a particular number of decimals.
>>> truncate_float(3.1415927, 3)
3.141
"""
assert decimals > 0 and decimals < 10
multiplier = 10 ** decimals
return int(n * multiplier) / multiplier
def percentage_to_multiplier(percent: float) -> float:
"""Given a percentage (e.g. 155%), return a factor needed to scale a
number by that percentage.
>>> percentage_to_multiplier(155)
2.55
>>> percentage_to_multiplier(45)
1.45
>>> percentage_to_multiplier(-25)
0.75
"""
multiplier = percent / 100
multiplier += 1.0
return multiplier
def multiplier_to_percent(multiplier: float) -> float:
"""Convert a multiplicative factor into a percent change.
>>> multiplier_to_percent(0.75)
-25.0
>>> multiplier_to_percent(1.0)
0.0
>>> multiplier_to_percent(1.99)
99.0
"""
percent = multiplier
if percent > 0.0:
percent -= 1.0
else:
percent = 1.0 - percent
percent *= 100.0
return percent
@functools.lru_cache(maxsize=1024, typed=True)
def is_prime(n: int) -> bool:
"""
Returns True if n is prime and False otherwise. Obviously(?) very slow for
very large input numbers.
>>> is_prime(13)
True
>>> is_prime(22)
False
>>> is_prime(51602981)
True
"""
if not isinstance(n, int):
raise TypeError("argument passed to is_prime is not of 'int' type")
# Corner cases
if n <= 1:
return False
if n <= 3:
return True
# This is checked so that we can skip middle five numbers in below
# loop
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i = i + 6
return True
if __name__ == '__main__':
import doctest
doctest.testmod()
|
