search_deep.hs

module Search_Deep where

import Data.Bits

data Fun = And | Add | Xor | Or  | Sub | Bus
data Shape = F Shape Shape | Var | Tok
data Expr a = C Fun (Expr a) (Expr a) | V a | T
data U = U
instance Show U where
    showsPrec _ U = ("?" ++)

shapes :: [Shape]
shapes =
    [ F Tok (F Tok (F Tok (F Var Tok)))
    , F Tok (F Tok (F Var (F Var Tok)))
    , F Tok (F Var (F Tok (F Var Tok)))
    , F Var (F Tok (F Tok (F Var Tok)))
    , F (F Var Tok) (F Tok (F Var Tok))
    , F Tok (F Var (F Var (F Var Tok)))
    , F Var (F Tok (F Var (F Var Tok)))
    , F Var (F Var (F Tok (F Var Tok)))
    , F (F Var Tok) (F Var (F Var Tok))
    , F Var (F Var (F Var (F Var Tok)))
    ]

funs :: [Fun]
funs = [And, Add, Xor, Or, Sub, Bus]

output :: Show a => Expr a -> String
output (V a)       = show a
output T           = "tok"
output (C And a b) = "(" ++ output a ++ ") & (" ++ output b ++ ")"
output (C Add a b) = "(" ++ output a ++ ") + (" ++ output b ++ ")"
output (C Xor a b) = "(" ++ output a ++ ") ^ (" ++ output b ++ ")"
output (C Or  a b) = "(" ++ output a ++ ") | (" ++ output b ++ ")"
output (C Sub a b) = "(" ++ output a ++ ") - (" ++ output b ++ ")"
output (C Bus a b) = "(" ++ output b ++ ") - (" ++ output a ++ ")"

withFuns :: Shape -> [Expr U]
withFuns Var = [V U]
withFuns Tok = [T]
withFuns (F l r) = [ C f a b | f <- funs, a <- withFuns l, b <- withFuns r ]

varSubst :: [Int] -> Expr U -> [Expr Int]
varSubst is (C f l r) = [ C f a b | a <- varSubst is l, b <- varSubst is r ]
varSubst is (V U) = [ V i | i <- is ]
varSubst is T = [ T ]

runExpr :: Expr Int -> Int -> Int
runExpr (C And l r) t = runExpr l t .&. runExpr r t
runExpr (C Add l r) t = runExpr l t + runExpr r t
runExpr (C Xor l r) t = runExpr l t `xor` runExpr r t
runExpr (C Or  l r) t = runExpr l t .|. runExpr r t
runExpr (C Sub l r) t = runExpr l t - runExpr r t
runExpr (C Bus l r) t = runExpr r t - runExpr l t
runExpr (V n)       _ = n
runExpr T           t = t

isOk :: (Int -> Int) -> Bool
isOk pred = False -- TODO

main :: IO ()
main = mapM_ (print.output) $ do
    expr <- concat [varSubst [0..255] fn | s <- shapes, fn <- withFuns s]
    [ expr | isOk $ runExpr expr]

search_deep.py

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()

search_deep.rs

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();
    }
}

search_shallow.py

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