{{ message }}

Instantly share code, notes, and snippets.

# Veedrac/search_deep.py

Last active Jan 27, 2017
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 from itertools import combinations, combinations_with_replacement, product need = 43, 25, 20, 16, 15, 13, 12, 12, 11, 10, 10, 8, 8, 4, 4, 3, 3, 1, 1, 1, 1 def is_ok(pred): # This is equivalent to the naïve Counter-based method, but # optimized to be fast on PyPy. counts = [0] * 256 for tok in range(256): counts[pred(tok) & 255] += 1 if max(counts) < 43: return False counts = [c for c in counts if c] if len(counts) < 21: return counts.sort(reverse=True) for i in range(21): if counts[i] < need[i]: return False return True # All shapes composed of pairwise functions f, g, h, i # that I can think of satisfying # # 1. Every function call depends on tok (else it is constant valued) # 2. Every function call depends on a constant (else it is probably trivial) # # The functions depend on a specified number of # constants. The functions are curried by their operators, # then their constants, then tok. shapes = ( (1, lambda f, g, h, i: lambda m: lambda tok: f(tok, g(tok, h(tok, i(m, tok)))) ), (2, lambda f, g, h, i: lambda m, n: lambda tok: f(tok, g(tok, h(m, i(n, tok)))) ), (2, lambda f, g, h, i: lambda m, n: lambda tok: f(tok, g(m, h(tok, i(n, tok)))) ), (2, lambda f, g, h, i: lambda m, n: lambda tok: f(m, g(tok, h(tok, i(n, tok)))) ), (2, lambda f, g, h, i: lambda m, n: lambda tok: f(g(m, tok), h(tok, i(n, tok))) ), (3, lambda f, g, h, i: lambda m, n, o: lambda tok: f(tok, g(m, h(n, i(o, tok)))) ), (3, lambda f, g, h, i: lambda m, n, o: lambda tok: f(m, g(tok, h(n, i(o, tok)))) ), (3, lambda f, g, h, i: lambda m, n, o: lambda tok: f(m, g(n, h(tok, i(o, tok)))) ), (3, lambda f, g, h, i: lambda m, n, o: lambda tok: f(g(m, tok), h(n, i(o, tok))) ), (4, lambda f, g, h, i: lambda m, n, o, p: lambda tok: f(m, g(n, h(o, i(p, tok)))) ), ) fns = ( ("({0}) & ({1})".format, lambda x, y: x & y), ("({0}) + ({1})".format, lambda x, y: x + y), ("({0}) ^ ({1})".format, lambda x, y: x ^ y), ("({0}) | ({1})".format, lambda x, y: x | y), ("({0}) - ({1})".format, lambda x, y: x - y), ("({1}) - ({0})".format, lambda x, y: y - x), # ("({}) * ({})".format, lambda x, y: x * y), # ("({}) >> ({})".format, lambda x, y: x >> y), ) def main(): for n_args, shape in shapes: for args in product(fns, repeat=4): names, ops = zip(*args) print(shape(*names)(*("?" * n_args))("tok")) for ns in product(range(256), repeat=n_args): if is_ok(shape(*ops)(*ns)): print(shape(*names)(*ns)("tok")) main()
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters