R

@RealSaitama

Prisoner Riddle

Python
2 years ago
from random import randint l = ("0000", "0011", "0101", "1000", "1010", "1011", "1101", "1111") u = 0 for y in l: u ^= int(y, 2) print(bin(u)) x = 0b1001010010110101 k = x.bit_length() p = 0b0110

Minimum steps to reach a given number

Python
2 years ago
import re def solve(x, n): fmt = lambda e: e if e.isdigit() else f"({e})" d = {} d[1] = {x: str(x)} values = set([x]) k = 2 while 1: d[k] = {}

Binary trees and parenthesis

Python
2 years ago
class BinaryTree: def __init__(self, left=None, right=None): self.left = left self.right = right def __str__(self): left = "" if self.left is None else self.left.__str__() right = "" if self.right is None els

Pollard Brent (Voile)

Python
2 years ago
from collections import Counter from math import gcd, prod, isqrt import random def brent(n): y, c, m = random.randint(1, n - 1), random.randint(1, n - 1), random.randint(1, n - 1) g, r, q = 1, 1, 1 while g == 1: x = y f

Pollard Rho

Python
2 years ago
from collections import Counter from random import randrange from math import gcd def miller_rabin_test(n): if n < 2 or not n % 2 or not n % 3: return n in (2, 3) k, r, d = 5, 0, n - 1 while d % 2 == 0: d //= 2

Modular polynomial

Python
2 years ago
class Polynomial: def __init__(self, coef, mod): self.mod = mod self.coef = [c % mod for c in coef[:]] while len(self.coef) > 1 and self.coef[0] == 0: self.coef.pop(0) self.deg = len(self.coef)

Polynomial Class

Python
2 years ago
class Polynomial: def __init__(self, coef): self.coef = coef[:] while len(self.coef) > 1 and self.coef[0] == 0: self.coef.pop(0) self.deg = len(self.coef) - 1 def __str__(self): st = "".jo

Polynomial Riddle

Python
2 years ago
import uuid import weakref class HideStorageMeta(type): def __dir__(cls): return [item for item in super().__dir__() if item != '_storage'] class RiddleData: def __init__(self, poly): self.poly = poly

QR Ascii

Python
2 years ago
w, h = int(input()), int(input()) qr_code = [list(input()) for _ in range(h)] def clean(arr): new_arr = [row[:] for row in arr] n, m = len(arr), len(arr[0]) for x, y in ((1, 2), (1, m - 3), (n - 2, 2), (n - 3, m - 5)): c = arr[x]

Count apples falling

Python
2 years ago
n, idx = map(int, input().split()) apples = sorted((list(map(int, input().split())) + [i] for i in range(n)), key=lambda x: -x[2]) i = 0 while i < n and apples[i][4] != idx: i += 1 falling = [i] i += 1 while i < n:

Highest building

Python
2 years ago
import re w, h = map(int, input().split()) lst = [input() for _ in range(h)] base = [(x, len(x)) for x in re.split(r'(\s+)', lst[-1]) if len(x) > 0] print(base) j = 0 start = [] for s, l in base: if s[0] == "#":

Binary permutations

Python
2 years ago
n, c = map(int, input().split()) ns = [list(map(lambda x: bin(int(x))[2:].rjust(n, '0'), input().split())) for _ in range(c)] from itertools import permutations def find(l): ans = [] for p in permutations(range(n)): if all(x[i] ==

Necklaces and bracelets

Python
2 years ago
from math import gcd, comb # https://oeis.org/A081720 # https://oeis.org/A056344 n = int(input()) k = int(input()) def totient(m): ans = 0 for d in range(1, m + 1): if gcd(m, d) == 1: ans += 1

Closest permutation

Python
2 years ago
from collections import Counter n, m = input().split() def nearest(sa, sb): if sa == "": return "" if len(sb) < len(sa): return ''.join(sorted(sb, reverse=True))

Affine Cipher

Python
2 years ago
# w, h = map(int, input().split()) # lst = [list(input()) for _ in range(h)] # print(lst) msg = "@Hello" seed = 581980637 off = 10 "135 155 214 19 183 44" def rnd(o=0): s = 0

Lyndon and De Bruijn Words

Python
2 years ago
def LengthLimitedLyndonWords(s,n): w = [-1] # set up for first increment while w: w[-1] += 1 # increment the last non-z symbol yield w m = len(w) while len(w) <

Rational roots

Python
2 years ago
import re from math import gcd from fractions import Fraction RXP = r"(\s*[\+\-]\s*)?(\d*)(x?)(\d*)" tests = ["2x2 - 5x + 2", "x2 + x - 6", "x + 5", "12x2 + 4x1 + 0x0"] def rational_zeros(st): poly = {}

Integer factor

Python
2 years ago
from collections import Counter from math import gcd def factor(m): n = m f = [] for d in [2, 3, 5]: while n % d == 0: f.append(d) n //= d

Cantor's enumeration

Python
2 years ago
from math import gcd from itertools import chain, count, islice def gen(): # generator of terms return chain.from_iterable((i, n-i) for n in count(2) for i in range(1, n) if gcd(i, n-i)==1) lst = list(islice(gen(), 10**7)) print(lst[-2], lst[-1]

Archimedes

Python
2 years ago
RAC3 = 3**0.5 s, t = 3 * RAC3 / 2, 3 * RAC3 for _ in range(10): t = (2 * s * t) / (s + t) s = (s * t)**0.5 print(s, t)