stau.space
My omnium-gatherom of scripts and source code.
1def func_exp(func, p: int):
2 """
3 Exponentiates a function. In other words, returns a function that will be
4 executed p times when called.
5
6 Paramaters
7 ----------
8 func : a -> a
9 A function going from some type to that same type.
10 Returns
11 -------
12 a -> a
13 A function that will run the parameter p times.
14 """
15
16 def ret(x):
17 for i in range(p):
18 x = func(x)
19 return x
20
21 return ret
22
23
24def average(lst: list[int]) -> int:
25 """
26 Takes the average of a list of ints.
27
28 Parameters
29 ----------
30 lst : list[int]
31 The list to take an average of.
32
33 Returns
34 -------
35 int : the average of that list.
36 """
37 return sum(lst) / len(lst)
38
39
40def derive_sequence(lst: list[int]) -> list[int]:
41 """
42 Takes the discrete derivative of a sequence of ints.
43
44 Parameters
45 ----------
46 lst : list[int]
47 The list to derive.
48
49 Returns
50 -------
51 list[int] : The discrete derivative of lst.
52 """
53 ret = []
54 for idx, n in enumerate(lst[1:]):
55 ret.append(n - lst[idx])
56 return ret
57
58
59def pairwise_transform(lst: list[int], func) -> list:
60 """
61 Transforms all the adjacent values in lst using func.
62
63 Parameters
64 ----------
65 lst : list[int]
66 The list to transform.
67
68 func : (int, int) -> a
69 A function that takes two ints and produces some result.
70
71 Returns
72 -------
73 list : A list of the result of applying func to consecutive elements of lst.
74 """
75 ret = []
76 for idx, n in enumerate(lst[1:]):
77 ret.append(func(n, lst[idx]))
78 return ret
79
80
81def remove_repeats(lst: list) -> list:
82 """
83 Removes repeated consecutive elements in a sequence.
84
85 Parameters
86 ----------
87 lst : list
88 The list to verify.
89
90 Returns
91 -------
92 list : A list containing non-repeated elements of lst.
93 """
94 if len(lst) == 0:
95 return []
96 ret = [lst[0]]
97 for e in lst:
98 if ret[-1] != e:
99 ret.append(e)
100 return ret
101
102def sliding_window_sum(vals: list[int]) -> list[int]:
103 """
104 Computes the sliding window sum of vals.
105
106 Parameters
107 ----------
108 vals : list[int]
109 The array to compute.
110
111 Returns
112 -------
113 list[int] : The sliding window sum of vals.
114 """
115 ret = []
116 for idx, i in enumerate(vals[1:]):
117 if idx == len(vals) - 2:
118 ret.append(i + vals[0])
119 else:
120 ret.append(i + vals[idx + 2])
121 return ret
122
123
124def sliding_window(vals: list[int], f) -> list[int]:
125 """
126 BUG: Doesn't actually work.
127 Applies f as a sliding window to vals.
128
129 Parameters
130 ----------
131 vals : list[int]
132 The array to run a sliding window over
133
134 f : (int, int) -> int
135 A function that takes two ints and produces an int.
136
137 Returns
138 -------
139 list[int] : An array resulting from applying f to consecutive elements of
140 vals.
141 """
142 ret = []
143 for idx, i in enumerate(vals[1:]):
144 ret.append(f(vals[idx], i))
145 return ret
146
147def choose(n: int, k: int) -> int:
148 """
149 Calculates the combinations of n choose k.
150 https://en.wikipedia.org/wiki/Combination
151
152 Parameters
153 ----------
154 n : int
155 The size of subsets of k.
156
157 k : int
158 The size of the larger set.
159
160 Returns
161 -------
162 int : n choose k.
163 """
164 if k > n: return 0
165 if k == 0: return 1
166 if k == 1: return n
167 return factorial(n) / (factorial(n - k) * factorial(k))
168
169
170def ballot(k: int, l: int) -> int:
171 """
172 The ballot function for k, l.
173 https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem
174
175 Parameters
176 ----------
177 k : int
178
179 l : int
180
181 Returns
182 -------
183 int
184 """
185
186 return (k - l + 1) / (k + 1) * binomial(k + l, k)
187
188
189def callot(n: int, k: int) -> int:
190 """
191 The modified ballot function defined in the Glass Wagner paper.
192
193 Parameters
194 ----------
195 n : int
196
197 k : int
198
199 Returns
200 -------
201 int
202 """
203 return ballot(n - 1, n - k)
204
205
206def insert_at(arr: list, i: int, x) -> list:
207 """
208 Inserts x at index i in list arr.
209
210 Parameters
211 ----------
212 arr : list
213 The list to insert into.
214
215 i : int
216 The index to insert at.
217
218 x : a
219 The value to insert.
220
221 Returns
222 -------
223 list : A list with x inserted at position i.
224 """
225 return arr[0:i] + [x] + arr[i:]
226
227def catalan(n: int) -> int:
228 """
229 Computes the n'th Catalan number.
230 https://en.wikipedia.org/wiki/Catalan_number
231
232 Parameters
233 ----------
234 n : int
235 The index in the sequence of Catalan numbers to retrieve.
236
237 Returns
238 -------
239 int : The n'th Catalan number.
240 """
241 return factorial(2 * n) / (factorial(n + 1) * factorial(n))
242
243def pairwise_sum(v1: list[int], v2: list[int]) -> list[int]:
244 """
245 Sums adjacent elements in v1 and v2.
246
247 Parameters
248 ----------
249 v1 : list[int]
250 A list of ints to sum.
251
252 v2 : list[int]
253 A list of ints to sum.
254
255 Returns
256 -------
257 list[int] : The result of adding each int in v1 with each int in v2.
258 """
259 return list(map(lambda x: x[0] + x[1], zip(v1, v2)))
260
261def characteristic(n: int, i: int) -> list[int]:
262 """
263 Creates the n-dimensional characteristic vector of i.
264
265 Parameters
266 ----------
267 n : int
268 The amount of dimensions for the vector.
269
270 i : int
271 The number to fill the vector with.
272
273 Returns
274 -------
275 list[int] : The n-dimensional characteristic vector of i.
276 """
277 ret = [0] * n
278 ret[i] = 1
279 return ret
280
281def load_file(file_path: str):
282 f = open(file_path, "r")
283 content = eval(f.read())
284 return content
285
286def mod_mul(a: int, b: int, m: int) -> int:
287 return ((a % m) * (b % m)) % m
288
289
290def mod_pow(base: int, exp: int, m: int) -> int:
291 ret = 0
292 if m != 1:
293 ret = 1
294 for e in range(0, exp):
295 ret = (base * ret) % m
296
297 return ret
298
299# def mod_pow_bin(base: int, exp: int, m: int) -> int:
300
301def is_primitive_root(p: int, alpha: int) -> bool:
302 for exp in range((p - 1) // 2):
303 if mod_pow(alpha, exp, p) == p - 1:
304 return False
305 return mod_pow(alpha, (p - 1) // 2, p) == p - 1
306
307def primitive_roots(p: int) -> list[int]:
308 ret = []
309 for i in range(p):
310 if is_primitive_root(p, i):
311 ret.append(i)
312
313 return ret
314
315def seq(p: int, alpha: int) -> list[int]:
316 ret = []
317 i = 1
318 base = alpha
319 while base != 1:
320 base = mod_pow(alpha, i, p)
321 ret.append(base)
322 i += 1
323 return ret
324
325def naive_match(p: int, lst: list[int]) -> list[int]:
326 ret = []
327 for x in lst:
328 for idx, e in enumerate(lst, 1):
329 if e + x == p + 1:
330 ret.append(idx)
331 return ret
332
333def stride_difference(lst: list[int], stride: int, cols = []) -> list[int]:
334 ret = []
335 l = len(lst)
336 lst = lst + cols + lst
337 for idx in range(l):
338 x = lst[idx]
339 y = lst[(idx + stride) % len(lst)]
340 ret.append(y - x)
341 return ret
342
343def lempel_sd(lst: list[int], stride: int) -> list[int]:
344 diffs = stride_difference(lst, stride, [0])
345 diffs[-stride] = '*'
346 diffs.append('*')
347 diffs.append(f"k = {stride}")
348 return diffs
349
350def diff_square(p: int, alpha: int) -> list[list[int]]:
351 ret = []
352 half = p - 1 # (p - 1) // 2 + 1
353 for i in range(1, half):
354 ret.append(lempel_sd(naive_match(p, seq(p, alpha)), i))
355 return ret
356
357def diff_rect(p: int, alpha: int) -> list[list[int]]:
358 ret = []
359 for i in range(1, p - 1):
360 ret.append(stride_difference(seq(11, 2), i))
361 return ret
362
363def ints(lst) -> list[int]:
364 return list(filter(lambda x: type(x) == int, lst))
365
366def sieve_of_eratosthenes(limit: int) -> list[int]:
367 is_prime = [True] * (limit + 1)
368 p = 2
369 while p * p <= limit:
370 if is_prime[p]:
371 for i in range(p * p, limit + 1, p):
372 is_prime[i] = False
373 p += 1
374 primes = [p for p in range(2, limit + 1) if is_prime[p]]
375 return primes
376
377#primes = sieve_of_eratosthenes(1000)
378
379def mod_seq(lst: list[int], mod: int) -> list[int]:
380 return list(map(lambda x: x % mod, lst))
381
382def mod_ast(lst: list[int], mod: int) -> list[int]:
383 ret = []
384 for i in lst:
385 if (type(i) == int):
386 ret.append(i % mod)
387 else:
388 ret.append(i)
389
390def is_costas(lst: list) -> bool:
391 return False
392
393def lempel3d(p: int, alpha: int) -> list[list[list[int]]]:
394 return [[[0]]]
395
396