Skip to content

Instantly share code, notes, and snippets.

@Veedrac
Last active January 27, 2017 05:52
Show Gist options
  • Save Veedrac/1de5711526d06f1148d2bf3258ae3b89 to your computer and use it in GitHub Desktop.
Save Veedrac/1de5711526d06f1148d2bf3258ae3b89 to your computer and use it in GitHub Desktop.
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()
use std::thread;
static NEED: [u8; 21] = [43, 25, 20, 16, 15, 13, 12, 12, 11, 10, 10, 8, 8, 4, 4, 3, 3, 1, 1, 1, 1];
fn is_ok<F>(pred: F) -> bool
where F: Fn(u8) -> u8
{
let mut counts = [0; 256];
for tok in 0..256 {
counts[pred(tok as u8) as usize] += 1;
}
if counts.iter().cloned().max().unwrap() < 43 {
return false;
}
let mut counts2 = [0; 256];
let mut end = 0;
for src in counts.iter().cloned().filter(|&x| x > 0) {
counts2[end] = src;
end += 1;
}
counts2[..end].sort_by(|a, b| b.cmp(a)); // reverse
for i in 0..21 {
if counts2[i] < NEED[i] {
return false;
}
}
return true;
}
type Op = fn(u8, u8) -> u8;
fn and(x: u8, y: u8) -> u8 { x & y }
fn add(x: u8, y: u8) -> u8 { x + y }
fn xor(x: u8, y: u8) -> u8 { x ^ y }
fn or (x: u8, y: u8) -> u8 { x | y }
fn sub(x: u8, y: u8) -> u8 { x - y }
fn bus(x: u8, y: u8) -> u8 { y - x }
fn mul(x: u8, y: u8) -> u8 { x * y }
fn rsh(x: u8, y: u8) -> u8 { if y >= 8 { 0 } else { x >> y } }
fn hsr(x: u8, y: u8) -> u8 { if x >= 8 { 0 } else { y >> x } }
const OPS: [Op; 9] = [
and, add, xor, or, sub, bus, mul, rsh, hsr
];
const OP_NAMES: [&'static str; 9] = [
"&", "+", "^", "|", "-", "←", "*", ">>", "<<"
];
fn run<Shape>(s: &'static str, n_args: usize, shape: Shape)
where Shape: Fn(Op, Op, Op, Op, u8, u8, u8, u8, u8) -> u8
{
for mut idx in 0..6561 {
let f_idx = idx % 9;
idx /= 9;
let g_idx = idx % 9;
idx /= 9;
let h_idx = idx % 9;
idx /= 9;
let i_idx = idx % 9;
let f = OPS[f_idx];
let g = OPS[g_idx];
let h = OPS[h_idx];
let i = OPS[i_idx];
let f_name = OP_NAMES[f_idx];
let g_name = OP_NAMES[g_idx];
let h_name = OP_NAMES[h_idx];
let i_name = OP_NAMES[i_idx];
// println!("{}",
// s.replace("F", f_name)
// .replace("G", g_name)
// .replace("H", h_name)
// .replace("I", i_name)
// .replace("M", "?")
// .replace("N", "?")
// .replace("O", "?")
// .replace("P", "?")
// );
for mnop in 0..(1 << (8 * n_args)) {
let m = ((mnop >> 0) & 255) as u8;
let n = ((mnop >> 8) & 255) as u8;
let o = ((mnop >> 16) & 255) as u8;
let p = ((mnop >> 24) & 255) as u8;
if is_ok(|tok| shape(f, g, h, i, m, n, o, p, tok)) {
println!("{}",
s.replace("F", f_name)
.replace("G", g_name)
.replace("H", h_name)
.replace("I", i_name)
.replace("M", &m.to_string())
.replace("N", &n.to_string())
.replace("O", &o.to_string())
.replace("P", &p.to_string())
);
}
}
}
}
fn main() {
let mut threads = Vec::new();
threads.push(thread::spawn(|| run("(tok) F (tok G (tok H (M I tok)))",
1, |f, g, h, i, m, _, _, _, tok|
f(tok, g(tok, h(tok, i(m, tok))))
)));
threads.push(thread::spawn(|| run("tok F (tok G (M H (N I tok)))",
2, |f, g, h, i, m, n, _, _, tok|
f(tok, g(tok, h(m, i(n, tok))))
)));
threads.push(thread::spawn(|| run("tok F (M G (tok H (N I tok)))",
2, |f, g, h, i, m, n, _, _, tok|
f(tok, g(m, h(tok, i(n, tok))))
)));
threads.push(thread::spawn(|| run("M F (tok G (tok H (N I tok)))",
2, |f, g, h, i, m, n, _, _, tok|
f(m, g(tok, h(tok, i(n, tok))))
)));
threads.push(thread::spawn(|| run("(M G tok) F (tok H (N I tok))",
2, |f, g, h, i, m, n, _, _, tok|
f(g(m, tok), h(tok, i(n, tok)))
)));
threads.push(thread::spawn(|| run("tok F (M G (N H (O I tok)))",
3, |f, g, h, i, m, n, o, _, tok|
f(tok, g(m, h(n, i(o, tok))))
)));
threads.push(thread::spawn(|| run("M F (tok G (N H (O I tok)))",
3, |f, g, h, i, m, n, o, _, tok|
f(m, g(tok, h(n, i(o, tok))))
)));
threads.push(thread::spawn(|| run("M F (N G (tok H (O I tok)))",
3, |f, g, h, i, m, n, o, _, tok|
f(m, g(n, h(tok, i(o, tok))))
)));
threads.push(thread::spawn(|| run("(M G tok) F (N H (O I tok))",
3, |f, g, h, i, m, n, o, _, tok|
f(g(m, tok), h(n, i(o, tok)))
)));
threads.push(thread::spawn(|| run("M F (N G (O H (P I tok)))",
4, |f, g, h, i, m, n, o, p, tok|
f(m, g(n, h(o, i(p, tok))))
)));
for thread in threads {
thread.join().unwrap();
}
}
from collections import Counter
need = 1, 1, 1, 1, 3, 3, 4, 4, 8, 8, 10, 10, 11, 12, 12, 13, 15, 16, 20, 25, 43
def is_ok(pred):
counts = [0] * 256
for tok in range(256):
counts[pred(tok) & 255] += 1
counts.sort()
return all(c >= u for c, u in zip(counts[-21:], need))
from itertools import combinations, combinations_with_replacement, product
fns = {
"{} + {}": lambda tok, n: tok + n,
# "{} * {}": lambda tok, n: tok * n,
"{} ^ {}": lambda tok, n: tok ^ n,
"{} & {}": lambda tok, n: tok & n,
"{} | {}": lambda tok, n: tok | n,
# "-{} + {}": lambda tok, n: -tok + n,
# "-{} ^ {}": lambda tok, n: -tok ^ n,
# "-{} & {}": lambda tok, n: -tok & n,
# "-{} | {}": lambda tok, n: -tok | n,
# "~{} ^ {}": lambda tok, n: ~tok ^ n,
# "~{} & {}": lambda tok, n: ~tok & n,
# "~{} | {}": lambda tok, n: ~tok | n,
# "{} >> {}": lambda tok, n: tok >> n,
# "{} << {}": lambda tok, n: tok << n,
# "-{} >> {}": lambda tok, n: -tok >> n,
# "-{} << {}": lambda tok, n: -tok << n,
# "~{} >> {}": lambda tok, n: ~tok >> n,
# "~{} << {}": lambda tok, n: ~tok << n,
}
for (name1, fn1), (name2, fn2), (name3, fn3) in product(fns.items(), repeat=3):
if fn1 is fn2:
continue
print(" ({}) & ({})".format(
name1.format("({})".format(name2.format("tok", "?")), "?"),
name3.format("tok", "?")
))
for n1, n2, n3 in product(range(256), range(256), range(256)):
if is_ok(lambda tok: fn1(fn2(tok, n2), n1) & fn3(tok, n3)):
print("({}) & ({})".format(
name1.format("({})".format(name2.format("tok", n2)), n1),
name3.format("tok", n3)
))
break
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment